题型分析

作业调度

• 通常操作系统和用户之间有哪几类接口 作业控制级接口:为用户提供对作业运行全过程的控制功能 程序级接口:由各个系统调用组成，用户程序取得操作系统服务的一个途径
• 输入井和输出井是在磁盘上开辟的两大存储空间 输入缓冲区和输出缓冲区是在内存中开辟的两个缓冲区
• spooling系统具有如下优点，提高了io速度，将独占设备改为共享设备，实现了虚拟设备功能
• 特权指令是一类只能在管态下执行，而不能在状态下执行的特殊指令 访管指令是处理器从算态进入管态，并向操作系统提供要代为完成的工作 广义指令是系统调用命令
• 系统调用是操作系统提供给软件开发人员的程序级接口，开发人员可以利用它使用系统功能
• 系统调用和过程调用的区别
  • 系统调用本质上是一种过程调用，但它是一种特殊的过程调用 系统调用的调用过程是用户程序，它运行在用户态，其被调用的过程是系统过程，运行在系统态
  • 一般过程调用可以直接由调用过程转向被调用过程，系统调用需要通过软中断机制从调用过程转向被调用过程
• 作业在系统中的状态 输入，后备，执行，完成

进程管理

• 名词解释
  • 顺序程序：程序在计算机上严格按照写入的顺序执行
  • 并发程序：可并发执行的多道程序
  • 进程：程序的一次执行，是一个动态实体
  • 进程控制块：记录进程详细状态和相关信息的基本数据结构
  • 进程映像：进程的执行环境
  • 原语：机器指令构成的可完成特定功能的程序段
  • 临界资源：独占资源
  • 临界区：进程中涉及临界资源的程序段
  • 管程：由过程、变量及数据结构组成的一个集合
  • 消息：发送方形成，接受方接收的一组信息（消息头+消息体）
  • 信箱：对消息进行缓存的地方
• 进程状态的转换 &64
• 进程控制原语
• 解决进程互斥的方法 &导图，进程管理
• 信号量机制 &王道98（经典同步问题）
  • 信号量：资源实体
    • 公用信号量（互斥），私有信号量（同步）
    • P,V操作 &74（看看如何表示）
• 处理机调度的三个层次，调度算法
• 进程与线程的比对 &导图，进程管理
• 进程通信
  • 直接通信 管道
  • 间接通信 信箱

死锁

• 名词解释
  • 死锁：多道程序系统中，当某个进程提出资源的使用请求时后，系统中的一些进程处于无休止的阻塞状态，在无外力的作用下，这些进程将无法运行下去
  • 独占资源：属于永久性资源
  • 永久性资源：不可消耗的资源
  • 临时性资源：可消耗的资源
  • 资源分配图：描述资源申请和资源分配的关系模式图
• 必要条件
  • 互斥使用
  • 非剥夺控制
  • 零散请求
  • 循环等待
• 不发生死锁的最少资源数
  • 并发进程数：k，每个进程所需资源数$n_i$ 不发生死锁的最少资源数：$(\sum n_i )-k+1$
• 死锁预防【破坏必要条件】
  • 破坏互斥使用：SPOOLing技术
  • 破坏非剥夺控制：仅适用于处理机和存储器资源
  • 破坏零散请求：静态分配策略（一次性分配所需所有资源）
  • 破坏循环等待：资源编号（占有资源编号小于申请资源编号才允许分配资源）
• 死锁避免【安全状态，不安全状态】
  • 银行家算法 $Max(i) = Allocation(i) + Need(i)$, $Available$
• 死锁检测【死锁定理】&133第11题
  • 永久性资源：&129
  • 临时性资源

存储管理

• 概念与术语
  • 地址重定位：程序被装入内存，程序的逻辑地址被转化为物理地址的过程
    • 绝对装入（过程简单，依赖于硬件结构）
    • 静态再定位（容易实现，但必须给作业分配一个连续的存储区域）
    • 动态再定位（充分利用空间，缓解内存紧张的矛盾，但需要附加硬件支持）
  • 内碎片与外碎片
    • 内碎片：占用分区内未被利用的空间
    • 外碎片：占用分区间难以利用的空间

    	内碎片	外碎片
    分区存储管理方案	√（固定分区）	√（可变分区）
    段式存储管理方案		√
    页式存储管理方案	√

  • “系统抖动”现象
    • 定义：页面在内存与外存间频繁调度，以至于调度页面所需时间笔进程实际所需的时间还要多，导致系统效率急剧下降，甚至导致系统崩溃。
    • 原因：页面淘汰算法不合理或分配给进程的物理页面数太少
    • 解决方案：采取局部置换原则；引入工作集算法；“L=S”准则；挂起若干进程
  • 覆盖和交换
    • 覆盖：将程序划分为若干个功能上相对独立的程序段,按照程序的逻辑结构，共享同一块内存区的内存扩充技术
      • 有效利用内存，但编程复杂，以时间换空间
    • 交换：先将内存某部分的程序或数据写入外存交换区,再从外存交换区中调入指定的程序或数据到内存中来,并让其执行的一种内存扩充技术
      • 增加并发程序数，但则增加了处理机开销，重定位和信息量大的问题
  • 分段和分页存储
    • 分页出于系统管理需要，分段出于用户需要
    • 页大小固定，段大小不固定
    • 逻辑地址：分页是一维的，分段是二维的
    • 分段可以实现内存共享，分页不能实现内存共享；但两者都不能实现存储扩充
  • 分区存储管理方案
    • 单一连续分区存储管理方案：只有系统区和一整块的用户区
    • 固定分区存储管理方案：在程序装入前，划分好内存分区（若干大小相等，若干大小不等）
    • 可变分区存储管理方案：基于链表，在程序装入时，通过分区分配算法，划分内存分区
    • 可再定位式分区存储管理方案

  • 局部性原理

    程序执行过程的较短时期内，所执行的指令地址和指令的操作数分布局限于一定区域

  • 工作集

    进程执行过程中，所访问页面的集合

  • 页面置换策略
    • 固定分配局部置换
    • 可变分配局部置换
    • 可变分配全局置换
• 页面淘汰算法
  • 算法
    • 最佳置换算法
    • 先进先出页面淘汰算法
    • 第二次机会淘汰算法
    • 页面缓冲算法
    • 最近最少使用页面淘汰算法（LRU）
    • 最不经常使用页面淘汰算法（NFU）
    • 最近问使用页面淘汰算法（NRU）
  • 缺页中断次数判断
  • 缺页率
• 分页存储管理，分段存储管理和请求分页式存储管理
  • 由逻辑地址，页表（段表），块大小和数量，计算物理地址
  • 绘制页表，段表
  • 绘制地址变换图

文件管理

• 根据索引结构，盘块信息（大小，盘块地址长度），对给出文件计算所占用的直接盘块和间接盘块数
• 磁盘调度
  • 按照不同的调度算法，给出请求队列的移动量和访问序列
    • 移臂调度（考察柱面号的访问顺序）
    • 旋转调度（考察扇区号的访问顺序）
• 打开文件机构行为分析
  • 根据执行代码，绘制进程打开文件表，系统打开文件表，内存索引节点表
• 记录的成组存放
• 磁带利用率
• 成组连接法
• 扇区分布与交错数
  • 交错数：相邻扇区中间隔的扇区数+1

设备管理

• 课后习题
  • 缓冲技术引入原因
    • 缓和CPU与I/O设备速度不匹配矛盾
    • 减少对CPU的中断频率，放宽对中断响应时间的限制
    • 提高CPU和I/O设备之间的并行性

  • 设置缓冲区原则

  • I/O设备分类
    • 独占设备
    • 共享设备
    • 虚拟设备

  • 块设备和字符设备区别

    	传输速度	寻址	常采用控制方式
    块设备	慢	√	直接存储访问（DMA）
    字符设备	快	×	中断驱动I/O

分布式计算机系统