操作系统

一、判断辨析题：3分*8=24分

二、简答题：4分*5=20分

第一章 绪论

1. 分时系统的设计目标和特点

目标：追求交互性。特点：同时性，独占性，交互性，及时性。

2. 多道程序设计的概念和特点

概念：在计算机内存中同时存放几道相互独立的程序，它们在管理程序的控制下相互穿插地运行。

特点：

• 多道：
• 宏观上并行运行：
• 微观上串行运行：

3. 分时系统和批处理系统&分时系统和实时系统的异同

1. 分时系统和批处理系统

   • 同：

     ​ 追求作业类型相同。

   • 异：

     ​ 效率：批处理效率更高。

     ​ 规模：批处理运行相对更大的程序。

     ​ 目标：批处理追求效率。分时系统追求交互性。

2. 分时系统和实时系统

   • 同：

     ​ 追求作业类型相同，及时性。

   • 异：

     ​ 系统的设计目标不同。分时系统追求交互性；实时系统追求高可靠性和安全性。

     ​ 交互性强弱不同。分时系统交互性强，实时系统仅允许操作并访问优先的专用程序，交互能力差。

     ​ 响应时间的敏感度不同。实时系统对响应时间的敏感度更强。

4. 操作系统的特征。

最基本特征：并发，共享；虚拟，异步。

5. 操作系统的虚拟性体现在？

• 时分复用技术：资源在时间上进行复用，不同程序并发使用多道程序，分时使用计算机的硬件资源。提高资源的利用率。
• 空分复用技术：用来实现虚拟磁盘、虚拟内存等，提高资源利用率，提升编程效率。

6. 实时操作系统的概念，应用领域，特点。

• 概念：
  • 实时操作系统主要用于过程控制、事务处理等有实时要求的领域，其主要特征是实时性和可靠性。
  • 指计算机对于用户请求能足够快地进行处理，并做出反映。要求毫秒、微秒级。
• 应用领域：
  • 实时控制：工业过程控制、防空系统等。
  • 实时信息处理：情报检索和查询、飞机订票系统、银行信用卡系统。
• 特点：
  1. 系统对外部的信号必须能及时响应，在规定的时间内;
  2. 要求高可靠性和安全性，效率则放在第二位；;
  3. 系统整体性强;
  4. 不要求很强的“会话”能力。

第二章 组织结构

1. 处理机分类及特权指令

• 分类：
  • 在计算机系统中有两类程序运行：用户程序、系统程序。用户程序、系统程序执行时有不同的权限。
  • 根据对系统资源和机器指令的使用权限，把处理机执行时的工作状态分为核态和用户态。
• 特权指令：在核态下操作系统可以使用所有指令，包括一组特权指令
  • 允许和禁止中断；
  • 再进程之间切换处理机；
  • 存取用于内存保护的寄存器；
  • 执行输入和输出操作；
  • 停止一个中央处理机的工作。
• 在下列情况下，由用户态转向核态
  • 用户程序要求操作系统的服务，系统调用；
  • 发生一次中断；
  • 再用户程序中产生了一个错误的状态；
  • 再用户程序中企图执行一条特权指令；
• 从核态转回用户态用一条指令实现，这条指令也是特权指令。一般情况下是：中断返回指令。

2. CPU状态

核态、管态、用户态。

3. 程序状态字的概念及内容

• 在计算机系统中有一个（或多个）寄存器用来存放程序状态字，称为PS。
• 其中包括：
  • 指令计数器
  • 程序现应执行那条指令，当前指令执行的情况
  • 机器处于何种状态（核态、用户态）
  • 程序执行时应屏蔽哪些中断（处理机运行级）
  • 寻址方式、编址、保护键
  • 响应中断的内容

程序状态字（PSW）是计算机系统的核心部件，属于控制器的一部分。

PSW用来存储两类信息：

1. 当前指令执行结果的各种状态信息，如有无进位，有无溢出，结果正负，结果是否为零，奇偶标志位等。
2. 存放控制信息，如允许中断等。
   有些机器中将PSW成为标志寄存器。

4. 操作系统为用户提供的两类接口

命令接口和程序接口

？？键盘命令、和图形化界面？？

5. 中断的分类及中断机制

中断分类：

1. 按中断功能分类

   1. 输入/输出中断
   2. 外中断
   3. 机器故障中断
   4. 程序性中断
   5. 访管中断

2. 按中断方式分类

   1. 强迫性中断
   2. 自愿中断

3. 按中断来源分类

   1. 中断
   2. 俘获

中断机制：

6. 中断响应及内容

中断响应：是处理机发现有中断请求时，中止现运行程序的执行，并自动引出中断处理程序的过程。中断响应的实质是交换指令执行地址和处理机的状态，以达到如下目的：

• 保留程序断点及有关信息；
• 自动转入响应的中断处理程序执行。

中断响应过程：

• 发现中断源（识别中断原因）
• 保存线程，将中断向量推入系统堆栈
• 引出中断处理程序

中断响应具体做法：

• CPU在执行每条指令后扫描中断寄存器，查看有无中断请求。
• 如果没有，则运行吓一跳指令；
• 如果有中断请求，则通过交换中断向量引出（进入）中断处理程序

7. 中断处理程序

中断处理和自陷处理的过程是类似的，当硬件完成了中断进入后，转到中断处理程序，进入软件中断处理过程。

• 保护线程和传递参数；
• 执行相应的中断（或自陷）处理程序；
• 恢复和退出中断。

第三章 用户界面

1. 作业，作业步及作业步之间的关系

• 作业：要求计算机系统按指定的步骤对原始数据进行处理，并得到计算结果的加工工作。

  在多道环境下，一个作业是一个单位，是一个用户的计算任务区别于其它用户的计算任务的一个计算单位。

• 作业步：对作业的加工工作中的一个步骤称为一个作业步。

  在操作系统中，把编好源程序后上机调试的工作分成四个步骤，称为四个作业步：

  • 编辑（修改）
  • 编译
  • 连接
  • 运行

  

• 作业步之间的关系：

  1. 每个作业步运行的结果产生下一作业步运行所需要的文件。
  2. 一个作业步能否正确执行，取决于前一作业步是否成功完成。

2. 作业的4种状态：

提交：

后备：

执行：

完成：

3. 系统调用概念，与一般过程调用的区别，实现机制。

系统调用概念：

• 所谓系统调用，就是用户在程序中调用操作系统所提供的一些子功能。
• 这是一种特殊的过程调用，这种调用同是由特殊的机器指令实现的。除了提供对操作系统子程序的调用外，这个指令还将系统转入特权方式。

与一般过程调用的区别：

• 运行在不同的系统状态：一般的过程调用，其调用程序和被调用程序都运行在相同的状态：核心态或用户态；而系统调用与一般调用的最大区别就在于：调用程序运行在用户态，而被调用程序则运行在核心态。
• 状态的转换：一般的过程调用不涉及系统状态的转换，但系统调用通常都是通过软中断机制先由用户态转换为核心态。
• 返回问题：一般的过程调用在被调用过程执行完后，将返回到调用过程继续执行。但系统调用结束后，系统将根据优先级进行调度。
• 嵌套调用：像一般过程一样，系统调用也允许嵌套调用，但每个系统对嵌套调用的深度都有一定的限制。

实现机制：

• 系统调用是通过访管指令实现的。在程序中，如果希望我i给你求操作系统的服务，就要执行一条访管指令，系统处理这个中断，即为用户提供相应的服务（或者称响应用户的请求）。
• 不同的操作系统，系统调用实现的具体方法有所不同，但其是指大的特点是相同的：
  • 每个系统调用对应一个系统调用号；
  • 每个系统调用有一个对应的执行程序段；
  • 每个系统调用要求一定数量的输入参数和返回值；
  • 整个系统有一个系统调用执行程序入口地址表；

第四章 并发处理

1. 程序顺序执行与并发执行各自的特点

顺序执行的特点：

• 顺序性：处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束；
• 封闭性：程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它；
• 可再现性：程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。

并发程序的特点：

• 失去了程序的封闭性和结果的可再现性
  • 如果程序执行的结果是一个与时间无关的函数，即具有封闭性。
  • 若一个程序的执行可改变另一个程序的变量，象二个并发程序完成誊抄的例子，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。

2. 进程的特征（最根本特征）

并发、动态

进程的基本特征：

• 并发性
  • 任何进程都可以同其它进程一起向前推进
• 动态性
  • 进程对应程序的执行
  • 进程是动态产生，动态消亡的
  • 进程在其声明周期内，在三种基本状态之间转换

进程的其它特征：

• 独立性
• 交互性
• 异步
• 结构性

进程的定义：

• 教材上给出的进程的定义：进程，即是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。

3. 进程状态与变迁

能画3~10种状态的变迁图

进程的基本状态：

• 进程在系统中的活动规律是：

  执行——>暂停——>执行

• 进程的三种基本状态：

• 运行状态

• 就绪状态

• 等待状态（又称阻塞、挂起、睡眠）

三状态进程模型：

• 其他状态
• 终止状态
• 挂起状态
• 创建（新new）状态

五状态进程模型：

七状态进程模型：

4. 进程和程序的区别

• 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件，是静态和可以复制的。
• 进程是暂时的，程序的永久的：进程是对应程序的执行过程过程，有一定的生命周期，而程序可长久保存。
• 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。
• 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
• 进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位，也是一个独立的运行单位。

进程实体的组成

1. 程序：表示改进程所要进行的操作；
2. 数据集合：程序加工的对象和场所、它包括操作的数据和程序自己的变量单元。
3. 进程控制块PCB：用于刻画一个进程在各个不同时期所处的状态的数据块。

进程=程序+数据+PCB

进程控制块PCB

​ 存放进程的管理和控制信息的数据结构称为进程控制块。它是进程管理和控制的最重要的数据结构，在创建时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。PCB就象我们的户口。

• 作用：用以标识一个进程的存在。是标识进程的唯一实体。

进程控制块（PCB）的作用：

1. PCB是进程组成中最关键部分。
2. 每个进程有惟一的进程控制块；
3. 操作系统根据PCB对进程实施管理和控制
4. 进程的动态、并发等特征是利用PCB表现出来的；
5. PCB是进程存在的惟一标志

5. 进程操作原语（4个）（进程控制）

进程创建、
进程阻塞、
进程撤销、
进程唤醒。

6. 互斥和同步的区分

6.1互斥

引例：

1. 宿舍电话的使用
2. 打印机的使用

临界资源：一次仅允许一个进程使用的资源成为临界资源

引力中的电话和打印机都属于临界资源。除此之外，还有内存变量、指针、数组等等也是临界资源。

临界区：

每个进程中访问临界资源的那段程序段称为临界区（临界段）。

6.2同步

​ 所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。

引例：两位同学约好星期天去东湖，早上8:00在校门口，不见不散。当一个同学先来到校门口，要等另一个同学，到齐后一道打的去东湖。

同步机制：实现同步的机制。常用的有信号灯机制和管程机制。

同步规则：同步的各进程之间应遵循的规则。

1. 空闲让进；
2. 忙则等待
3. 有限等待
4. 让权等待

6.3互斥与同步的区别

互斥：仅是让两个进程不能同时访问某资源；
同步：互斥且同步执行的各进程前后顺序有限制。

7. 进程通信

7.1进程通信的概念

1. 进程通信的方式
   1. 共享内存
      其大致又包括如下两类：
      • 基于共享数据结构的通信方式
        • 在这种通信方式中，要求诸进程共享某些数据结构，进程通过它们交换信息。
        • 只能传递少量数据，属于低级通信方式。
      • 基于共享存储区的通信方式
        • 为了传递大量数据，在存储器中划出一块共享存储区，诸进程可通过对共享存储区中的数据进行读写来实现通信。
        • 属于高级通信方式。
   2. 消息传递系统(Message passing system)
      • 不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。
      • 在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。
      • 消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种。
   3. 管道（Pipe）通信
      • 所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。
      • 向管道(共享文件)提供输入的发送进程(即写进程)， 以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。
      • 这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。
      • 为了协调双方的通信，管道机制必须提供以下三方面的协调能力：
        • 互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。
        • 同步，指当写(输入)进程把一定数量(如4 KB)的数据写入pipe，便去睡眠等待， 直到读(输出)进程取走数据后，再把它唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。
        • 确定对方是否存在，只有确定了对方已存在时，才能进行通信。
2. 进程间通信的类型
   • 低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和管程机制。优点的速度快。缺点是：
     • 传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。
     • 编程复杂：用户直接实现通信的细节，编程复杂，易出错。
   • 高级通信：能够传送任意数量的数据，包括三类：
     • 直接通信：消息缓冲机制
     • 间接通信：采用信箱为中介实现通信
     • 管道通信

8. 线程

概念

​ 线程是比进程更小的活动单位，它是进程中的一个执行路径。一个进程可以有多个线程。

线程的描述：

• 进程中的一条执行路径；
• 它有自己私用的堆栈和处理机执行环境（尤其是处理器寄存器）；
• 它与父进程共享分配给父进程的主存；
• 它是单个进程所创建的许多个同时存在的线程中的一个。

分类

特点

第五章 资源分配与调度

1. 资源的管理和目标

概念

资源：执行一个用户程序所需要的全部硬件设备、软件设施和数据。包括：

• 硬件资源：CPU、内存、各种I/O设备、存储设备、时钟等；
• 软件资源：系统程序、服务性程序、用户程序、语言处理程序等。

资源分配的方法

• 静态分配：在调用某作业时根据用户的需求分配资源，并在作业完毕后回收所有资源的方式；
• 动态分配：在某一进程运行过程中根据运行情况动态地分配、使用和释放其所需地资源地方式。

资源管理的目的

1. 保证资源的高利用率；
2. 在“合理”时间内使所有顾客有获得所需资源的机会；
3. 对不可共享的资源实施互斥使用；
4. 防止由资源分配不当而引起的死锁。

2. 资源分配机制

资源描述器

• 描述资源的管理和控制信息的数据结构称为资源分配的机构 。包括：资源描述器和 资源信息块
• 资源描述器（rd）：描述各类资源的最小分配单位的数据结构
• 资源描述器中存放的信息取决于资源的特性与对该资源的管理方式。最简单的资源描述器可以用一个二进制位来实现，它表示该资源是可用的，还是已分配的。

资源信息块

• 资源信息块（rib）用来说明资源、请求者以及实施分配所需信息。以实现对资源的有效分配。

• 对于每一类资源，存在两个队列：

  1. 可利用资源队列
  2. 该类资源的等待队列

• 在资源信息块中，分别由两个指针指向这两个队列。

• 另外还有一类为该类资源的分配程序入口地址。

• 资源信息快结构如下：

  rib
  等待队列头指针
  可利用资源队列头指针
  资源分配程序入口地址

3. 死锁的概念，产生原因，和必要条件

死锁的概念

1. 死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所处的一种系统状态。
2. 两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，每个进程都占用了一定的资源，但又都不能向前推进。这种现象称为死锁。

死锁的产生原因

1. 竞争资源
   • 在这两个进程并发执行时，当PA进程占有R1、PB进程占用R2时；
   • PA要求R2，由于PB已占有R2而得不到，PA进程只有等待；
   • PB申请R1，由于PA已占有R1，而得不到，PB进程只有等待；
   • 从而出现了死等的情况。
2. PV操作不当
3. 资源分配不当
   • 资源总数小于进程所要求的总数。则有可能死锁。
4. 临时性资源分配不当
   • 若P1等待P3的信件S3来到后再向进程P2发信件S1；
   • 若P2等待P1的信件S1来到后再向进程P3发信件S2；
   • 若P3等待P2的信件S2来到后再向进程P2发信件S3；

死锁的起因

1. 资源竞争
2. 进程推进顺序不当

死锁的必要条件

1. 互斥条件
2. 不可剥夺条件
3. 部分分配
4. 环路条件

4. 破坏死锁的4种策略

1. 死锁预防：预先设置一些条件限制去破坏四个必要条件之一 ，从而预防死锁。
   • 缺点：系统资源利用率、吞吐率降低。
2. 死锁避免：不预先采取条件限制，只是在 动态分配前提下，防止进入不安全状态，从而避免死锁。
   • 适当提高资源利用率，吞吐率。
3. 死锁检测：允许死锁发生，再去检测发生死锁的进程和资源，然后去消除死锁；
4. 死锁解除：取消或挂起相应发生死锁的进程，回收该进程资源，再分配给阻塞进程。
   • 发生死锁进程取消；
   • 发生死锁进程部分取消；
   • 重启动。

5. 死锁预防的四种策略

死锁的预防通常是破坏产生死锁的必要条件

1. 预先静态分配法(破坏部分分配条件)

   • 策略：作业调度时，仅当系统满足作业运行时所需的全部资源时，才把该作业调入内存运行。在作业运行前一次性将其所需的全部资源分配给它，于是在作业运行过程中不再会提出新的资源请求。
   • 缺点：
     • 降低了对资源的利用率，降低进程的并发程度；
     • 有可能无法预先知道所需资源；
     • 延长了作业的等待时间

2. 有序资源使用法：(破坏循环等待条件)

   • 策略：把系统中的全部资源分别分给一个特定的序号，并且要求每个进程均应严格地按照序号递增的次序请求资源。
   • 优点：基于动态分配方法，资源利用率较前法
   • 缺点：
     • 限制进程对资源的请求；
     • 资源的排序占用系统开销；
     • 资源序号尽可能反映多数作业的实际使用资源的顺序，但总有不合适
     • 的作业而造成资源浪费。

3. “可剥夺”资源使用法: (破坏“不可剥夺”条件)

   • 策略：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请；
   • 缺点：
     • 一个资源在使用一段时间后被释放，可能会造成前阶段工作的失效；
     • 可能会导致某进程重复多次申请和释放资源，从而延长了进程周转时间,并增加了系统开销,降低了系统吞吐量；
     • 只适用主存和处理器的分配,而不能对所有资源都适用。

4. 破坏“互斥”条件：

   • 就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般来说在所列的四个条件中，“互斥”条件是无法破坏的。因此，在死锁预防里主要是破坏其他几个必要条件，而不去涉及破坏“互斥”条件。

   注意：互斥条件不能被破坏，否则会造成结果的不可再现性。

第六章 处理机调度

1. 处理机的两级和三级调度

处理机的两级调度

• 在大多数多道程序系统中：处理机的调度分为两级：

1. 宏观上：作业调度—使该作业对应的进程（进入就绪态），具有使用CPU的权利。

   • 任务：将外存上的作业有选择地调入内存，建立作业对应的进程，使其投入运行。

2. 微观上：进程调度—从各就绪进程中选中一个，使其占有CPU开始执行。

   • 任务：在进入内存的所有进程中，确定哪个进程何时占有CPU ，使用多长时间。

• 在非多道程序系统中，进程调度和作业调度不作区别。

处理机的三级调度

• 在某些多道程序系统中，处理机的调度分为三级：

1. 高级调度（作业调度、宏观调度）

   • 按一定原则对外存输入井上的作业进行调度，并建立进程PCB。它决定允许哪些作业竞争系统资源。由于这种调度决定哪些作业可以进入系统，所以也称收容调度。作业一旦被系统收容，就便成进程或进程组。

2. 中级调度（交换调度）

   • 它决定允许哪些进程竞争处理机。中级调度通过使进程临时挂起和激活的方法对系统负载波动作出反映，以便获得平稳的系统操作和实现较好的系统综合性能目标，中级调度的作用使作为作业进入系统和将中央处理机分配给这些作业二者之间的一个缓冲。

3. 低级调度（进程调度）

   • 它决定了存在就绪进程时，哪一个就绪进程将分配到中央处理机，并且把中央处理机实际分配给这个进程（即低级调度是将处理机分配给进程）。低级调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻内存。

2. 作业控制块JCB

每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，主要信息见下图。

3. 作业调度

作业调度的主要任务: 完成作业从后备状态到执行状态和从执行状态到完成状态的转变。

作业调度功能：

• 确定数据结构（建立JCB，Job Control Block）；
• 确定调度算法，按该算法，从后备作业中选择一个或几个作业进入系统内存；
• 为被选中的作业创建进程，并且为其申请系统资源；
• 作业结束后作善后处理工作。

作业调度目标

1. 对所有作业应该是公平合理
2. 应使设备有高的利用率
3. 每天执行尽可能多的作业
4. 有快的响应时间

调度性能的衡量

• 通常采用平均周转时间和带权平均周转时间

  • 作业周转时间 = 作业完成时间 - 作业提交时间
  • 带权周转时间 = 作业周转时间 / 作业实际运行时间
  • 平均带权周转时间 = n个作业的带权周转时间之和 / n

  

作业调度算法

1. 先来先服务调度算法

   • 先来先服务算法是按作业来到的先后次序进行调度的，换句话说，调度程序每次选择的作业是等待时间最久的，而不管作业的运行时间的长短。
   • 优点：实现简单。
   • 缺点：效率较低。
   • 在一些实际的系统和一般应用程序中采用这种算法的较多。

2. 短作业优先调度算法

   • 短作业优先调度算法考虑作业的运行时间，每次总是选择一个运行时间最小的作业调入内存（系统）。
   • 优点:易实现,效率较高；
   • 缺点:只照顾短作业,而未考虑长作业。

   该调度算法有最短的作业平均周转时间。

3. 响应比高者优先调度算法

   • 先来先服务和短作业优先算法都有其片面性，先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间，短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业黪等待时间。响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法。

   

   • 算法的优缺点：
     • 这样算法从理论上讲是比较完备的，既照顾了短作业，又兼顾到了长作业；
     • 但作业调度程序要统计作业的等待时间，使用用户的估计的运行时间，并要作浮点运算（这是系统程序最忌讳的）浪费大量的计算时间，这是系统程序所不允许的。

4. 优先数调度算法

   • 优先数调度算法是终合考虑各方面的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。这种算法实现的困难在于如何终合考虑，这些因素之间的关系怎样处理。
   • 确定优先数的考虑因素：
     1. 作业要求运行的急切程度；
     2. 作业运行时间的长短；
     3. 对资源要求的多寡。

5. 均衡调度算法

   • 按作业本身的特性分类，作业调度程序轮流从这些不同类的作业中挑选作业运行。

   • 作业的分类方法之一：

     1. “短”作业：其特点是计算时间小于一定值，且无特殊的外设要求；
     2. “要用到磁带的作业”：要使用“一条或几条私用磁带
     3. “长”作业：作业所需的计算时间很长。

   • 一般，系统总是从每一类中挑选一个作业出来，使其投入运行，以保持机器中的各部件均处于忙碌状态

   • 分类方法之二：（按其输入输出的繁忙程度）

     1. A类：输入输出繁忙的作业：
     2. B类：输入输出与CPU均衡的作业；
     3. C类：CPU繁忙的作业：

   • 处理方法：系统总是力图保持运行作业中的A类与C类作业的数目相当，以使系统资源得到较均衡的使用。

   • 均衡调度算法的缺陷

     • 均衡调度算法就是一种更为理想化的调度算法，如何实现就更困难，并且算法本身的开销有时会远选大于先来先服务和小作业优先调度算法的不足，这也是这种算法很难被采用的最根本的原因。

进程调度的准则

1. CPU使用率——需要使CPU尽可能忙。其负荷应达到40%~90%；
2. 吞吐量——使其单位时间内完成的进程数量尽可能多
3. 周转时间——尽可能短（用于批处理系统）；
4. 响应时间——尽可能短（用于交互式系统）；
5. 等待时间——尽可能短（用于交互式系统）；

调度方式

调度方式：当一个进程正在处理机上执行时，若有某个更为“重要而紧迫”的进程需要进行处理时，亦即，若有优先级更高的进程进入就绪队列中时，如何分配处理机。

进程调度方式的分类：

1. 非剥夺方式
   • 分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。
   • 优点：简单，系统开销小；
   • 缺点：可能会使得紧急任务不能立即投入运行，以致延误时机。
2. 剥夺方式
   • 当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。
   • 剥夺原则有：
     • 优先权原则：优先权较高的进程可剥夺优先权低的进程而运行；
     • 短进程优先原则：短进程到达后可以剥夺长进程的运行；
     • 时间片原则：一个时间片用完后重新调度。

静态和动态优先数法区别

静态优先数法

在进程创建时指定优先数，在进程运行时优先数不变

• 确定进程优先数：
  • 系统确定：（运行时间、使用资源，进程的类型）
  • 用户确定：（紧迫程度，计费与进程优先数有关）
  • 系统与用户结合（用户可以为本用户的进程设置优先数，但不是作调度用，系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数）

动态进程优先数

• 系统在运行的过程中，根据系统的设计目标，不断地调整进程的优先数，这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标。如：
  1. 在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；
  2. 进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。

第七章

1. 主存管理功能

1. 映射逻辑地址到物理主存地址：
   • 将程序地址空间中使用的逻辑地址变换成主存中的地址。
2. 在多用户之间分配物理主存：
   • 按照一定的算法把某一空闲的主存区分配给作业或进程。
3. 对操作系统以及各用户的信息提供保护措施：
   • 保证用户程序(或进程映象)在各自的存储区域内操作，互不干扰。
4. 扩充逻辑主存区：
   • 提供虚拟存储技术，使用户程序的大小和结构不受主存容量和结构的限制，即使在用户程序比实际主存容量还要大的情况下，程序也能正确运行。

2. 实现虚存条件

1. 需要有相当容量的辅存；
2. 要有一定容量的主存；
3. 地址变换机构。引进虚存后必须在地址变换上花费开销，所以，在设计虚拟存储器时，应力求地址变换能快速进行。

3. 实现动态地址映射的条件

动态运行时的装入程序，在把装入模块装入内存时，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换，推迟到程序真正要执行时才进行。因此， 装入内存后的所有地址都仍是相对地址。

系统中设置了重定位寄存器。

动态地址映射技术能满足以下目标：

1. 具有给一个用户程序任意分配内存区的能力；
2. 可实现虚拟存储；
3. 具有重新分配的能力；
4. 对于一个用户程序，可以分配到多个不同的存储区。

• 优点：
  1. OS可以将一个程序分散存放于不连续的内存空间，装入后程序可以移动；
  2. 较容易实现几个进程对同一程序副本的共享使用
  3. 能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）；
  4. 能提供虚存功能
• 缺点：需要硬件支持（通常是CPU），OS实现较复杂。它是虚拟存储的基础。

4. 碎片，碎片的危害，怎么消除碎片

碎片

在已分配区之间存在着的一些没有被充分利用的空闲区。

碎片的危害

在按区分配方法中，根据申请按区分配主存，会把主存越分越零碎。在整个系统运行一段时间后，甚至会出现这样的局面：分布在主存各处的破碎空闲区占据了相当数量的空间，当一个作业申请一定数量的主存时，虽然此时空闲区的总和大于新作业所要的主存容量，但却没有单个的空闲区大到足够装下这个作业。

如何消除碎片

紧凑（拼接技术）：移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。

拼接时机的选择：

• 某个分区回收时立即进行；
  • 缺点：拼接频率过高，系统开销加大。
• 当找不到足够大的空白区，而空白区的存储容量总和却可以满足作业需要时进行。
  • 优点：拼接频率较小，系统开销较小；
  • 缺点：空白区管理较复杂。

拼接技术的缺点：

• 消耗系统资源；
• 拼接时必须停止所有其他的工作；
• 拼接需要重新定义已存入主存的作业。

5. 基本的放置策略

空闲区表的组织方法

• 按空闲区大小的升序（降序）组织；
• 按空闲区首址升序（降序）组织。

放置策略

1. 最佳适应算法
   • 最佳适应算法：
     • 最佳适应算法是将申请者放入与其大小最接近的空闲区中。切割后的空闲区最小，若系统中有与申请区大小相等的空闲区，这种算法肯定能将这种空闲区分配给申请者。
   • 最佳适应算法的空闲区表
     • 按空闲区大小升序方法组织。分配时，按申请的大小逐个与空闲区大小进行比较，找到一个满足要求的空闲区，就说明它是最适合的（即最佳的）。
   • 优点：
     1. 如果存储空间中具有正好是所要求大小的空白区，则它必然被选中；
     2. 如果不存在这样的空白区，也只是对比要求稍大的空白区进行划分，而绝不会去划分更大的空白区。从而，在遇到有大的存储要求时，就比较容易得到满足。
   • 缺点：
     1. 产生的空白区太小，不能使用；
     2. 回收分区时，将其插入到空白链中合适位置较费时
2. 首次适应算法：首次适应算法的表是按空闲区首址升序的（即空闲区表是按空闲区首址从小到大）方法组织的。
   • 首次适应算法:
     • 分配时从表首开始，以请求内存区的大小逐个与空闲区进行比较，找到第一个满足要求的空闲后，若空闲区大小与请求区的大小相等，则将该空闲区分配给请求者，并撤消该空闲区所在表目；若大于请求区，就将该空闲区的一部分分配给请求者，然后，修改空闲区的大小和首址。
   • 首次适应算法的实质
     • 是尽可能地利用低地址部分的空闲区，而尽量地保证高地址部分的大空闲区，使其不被切削成小的区，其目的是保证在有大的作业的到来有足够大的空闲区来满足请求者。
   • 回收时，
     • 首先考察释放区是否与系统中的某个空闲区相邻，若相邻则合并成一个空闲区，否则，将释放区作为一个空闲区按首址升序的规则插入到空闲区表适当的位置。
   • 优点：
     1. 算法简单，查找速度快；
     2. 高址部分空白区被划分的机会少，故大作业较易得到满足。
   • 缺点：
     1. 易造成很多“内 存碎片”；
     2. 查找较大的空白区通常在链的尾端才能发现，故查找速度降低。
3. 最坏适应算法
   • 最坏适应算法：
     • 为了克服最佳适应算法把空闲区切割得大小的缺点，人们提出了一种最坏适应算法，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区。避免了空闲区越分越小的问题。
   • 最坏适应算法的空闲区表
     • 是按空闲区大小降序的方法组织的（从大到小的顺序）。分配时总是取表中的第一个表目，若不能满足申请者的要求，则表示系统中无满足要求的空闲区，分配失败；否则，将从该空闲区中分配给申请者，然后修改空闲区的大小，并将它插入到空闲区表的适当位置。
   • 优点：
     • 使剩下的空闲区不至于太小，有可能仍能分配，对中小作业有利；
   • 缺点：
     • 会导致大作业的请求往往不能得到满足

6. 调入策略

• 预调
  • 系统根据作业（进程）运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。这样方法从表面上看起来很好，但系统无法预计系统中作业的运行情况，难以实现。
• 请调
  • 进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求。

7. 置换策略

1. 最佳算法（OPT算法）
   • 缺页中断率f’ = f/a， 则最佳算法是f’最小的调度算法
   • 当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。
   • 存在问题：由于无法预知哪个页面是未来最长时间内不被访问的，所以该算法只是一种理论上的算法。
2. 先进先出算法（FIFO算法）
   • 先进入内存的页，先退出内存。
   • 实质上是淘汰在内存驻留时间最长的页。
   • 其理由是：最早调入内存的页，不再被使用的可能性比近期调入内存的大。
   • 这种算法简单，实现容易。
3. 最久未使用淘汰算法（LRU算法）
   • 这种算法的实质：当需要淘汰一页时，选择最长时间未使用的页。
   • 依据的理论是如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。
   • LRU算法的缺点：
     • 在每次访问页面时都要修改有关信息，且需做连续修改，此工作由软件完成，代价太高；由硬件完成，大大增加成本。
     • 故此,真正的LRU算法用得最少，得到推广的仅是一种LRU近似算法（也被称为Clock置换算法，后续会讲到）。
4. 最不经常使用淘汰算法（LFU算法）
   • 实质：把最近应用次数最少的页淘汰掉；
   • 实现：为每一页设置一个计数器，初值为0。对每一页访问一次后，就将它相应计数器加1。过一定时间t后，将所有计数器一律清除。发生缺页中断时，选择计数器值最小的一页淘汰，同时将所有计数器清0。
   • 优点：容易实现
   • 缺点：代价较高
5. 简单的Clock置换算法
   • 这种算法，只要在存储分块表（或页表）中设一个“引用位”，当存储分块表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。这样，在一个时间周期T内，某些被访问过的页面其引用位为1，而未被访问过的页面其引用位为0。
   • 根据引用位的状态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用位为0的页，如下图所示的算法。
   • 缺点：
     1. 使所有块的引用位重置0的周期T大小难以确定。若太大：可能使所有块的引用位均为1，不知谁是最近以来没访问过的。若太小：可能引用位为0的块相当多，也不利于选择。
     2. 若缺页刚好发生在系统对所有引用位重置0之后，则几乎所有块的引用位为0，同样不利于选择。

8. 分页和分段

分页和分段的主要区别

1. 页是信息的物理单位，段是信息的逻辑单位；页的大小是由系统固定的，段的长度因段而异，由用户决定；
2. 分页的作业地址空间是一维的，分段的作业地址空间是二维的。

页表

页表是页式存储管理的数据结构，它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。

段表

第八章

1. 设备管理功能

• 状态跟踪
  • 设备控制块是存放设备管理和控制信息的数据结构。
  • 系统要掌握设备的状态。
• 设备存取
  • 实现对设备的存取操作。
• 设备分配
  • 在多用户的环境下，负责设备的分配和回收。
• 设备控制
  • 设备控制包括设备的驱动、完成和故障中断处理。

2. 设备独立性的概念，分类和实现

2.1 设备独立性的概念

• 设备独立性是指用户在编程序时所使用的设备与实际设备无关。
• 两类设备独立性：
  • 一个程序应独立于分配给它的某类设备的具体设备。即在用户程序中只指明I/O使用的设备类型即可。如在系统中配备了两台打印机，用户要打印时只要告诉系统要将信息送到打印机即可。
  • 程序要尽可能地与它使用的设备类型无关。即在用户程序中只要指出要输入或输出信息，至于信息I/O使用的设备不需用户指明。

2.2 设备独立性的实现

• 逻辑设备和实际设备的联系通常是由操作系统命令语言（作业控制语言、键盘命令或用户程序中的语言级）中提供的信息实现的。
• 采用高级语言级则通过软通道实现。
• 计算机系统中配置有各种不同类型的独占设备，每一类独占设备又可以有好多台。为了对这些设备进行管理，计算机系统对每一台设备都要进行登记，且为每一台设备确定一个编号，以便区分和识别．这个确定的编号称为设备的绝对号。
• 在多道程序设计系统中，因为用户无法知道哪台设备正在被其他用户占用，哪台设备当前是空闲的，所以用户中请分配设备时不能使用设备的绝对号。
• 当用户要使用独占设备时，只需向系统说明所要使用的设备类型，至于实际应该使用哪一台，由系统根据该类设备的分配情况来决定。有时用户可能要求同时使用几台同类型设备，为了避免使用时的混乱，用户可以把自己要求使用的若干台同类设备给出编号。由用户对自己需要使用的若干台同类设备给出的编号称为设备的相对号。
• 用户总是用“设备类相对号”来提出使用设备的要求。系统在为用户分配具体设备时就建立“绝对号”与“设备类相对号”的对应关系。根据这个对应关系，系统就能知道对用户要求使用的设备实际上应启动哪台设备。

3. 设备的分类

• 按传输速率分
  • 低速设备：几～几十字节/秒 键盘
  • 中速设备：几百～几千字节/秒 行式/激光打印机
  • 高速设备：上万～上百万字节/秒 磁盘驱动器
• 信息组织和处理方式
  • 块设备：信息按字符块组织和处理（面向块的设备：存储设备）
  • 字符设备：信息按字符组织和处理（面向字符的设备：I/O设备）
• 按从属关系分类
  • 系统设备：OS生成时已配置的各种标准设备
  • 用户设备：用户自己提供，由系统管理，非标准
• 按交互对象分类
  • 人机交互设备：视频显示器、键盘、鼠标、打印机
  • 与计算机或其他电子设备交互的设备：磁盘、磁带、传感器、控制器
  • 计算机间的通信设备：网卡、调制解调器
• 按资源分配方式
  • 独占设备：在一段时间内只能有一个进程使用的设备，一般为低速I/O设备。（如打印机，磁带等）
  • 共享设备：在一段时间内可有多个进程共同使用的设备，多个进程以交叉的方式来使用设备，其资源利用率高。（如硬盘）
  • 虚拟设备：用软件技术把慢速独占设备变成共享设备。一般是通过借用大容量共享设备的一部分空间来充当缓冲而实现的。把这部分空间称为“虚拟设备”。 （Spooling 技术）

4. 缓冲技术的概念，目的和分类

概念

是用来在两种不同速度的设备之间传输信息时平滑传输过程的常用手段。

引入缓冲的原因：

• CPU与各种外部设备的速度上的差异很大，设备与设备之间的速度的差异也很大。
• 系统有时会产生大量的数据需要I/O，有时又会很长时间没有I/O。造成I/O负荷的不均匀。

目的

• 缓和CPU与I/O设备间速度不匹配的矛盾
• 提高它们之间的并行性
• 减少对CPU的中断次数，放宽CPU对中 断响应时间的要求

分类

• 缓冲区设置

  • 硬缓冲：在设备中设置缓冲区，由硬件实现；

  • 软缓冲：在内存中开辟一个空间，用作缓冲区。

• 缓冲区管理

  • 单缓冲
  • 双缓冲
  • 环形缓冲
  • 缓冲池：多个缓冲区连接起来统一管理，常采用多缓冲管理

5. spoling的原理和结构

概念

• 利用CPU与通道可以并行工作的特点，原来在脱机系统中的预输入和缓输出工作全部由主机系统承担。
• 在操作系统设计了两个程序来代替两台卫星机的工作，这两个程序分别为“预输入程序”和“缓输出程序”在系统运行时形成进程工作。
• 同时在共享设备（磁盘）上开辟出两个称为“井”的特殊的区域来存放输入的信息和执行结果。

6. CPU和外设进行数据交换的方式

端口

1. 在计算机中，端口又被称为接口。其主要功能是：
   • 按照计算机主机与设备的约定格式和过程接收或发送数据和信号。
2. 分类：
   • 从数据传输方式分类：并行接口/串行接口
   • 从传送的同步方式来看：有异步和同步之分。

总线

设备控制器

7. 通道的作用和分类

作用

为了使CPU从I/O事务中解脱出来，同时为了提高CPU与设备，设备与设备之间的并行工作能力

分类

1. 字节多路通道
2. 选择通道
3. 成组多路通道

8. I/O请求的概念和实现

第九章

1. 文件系统功能

1. 提供用户对文件操作的命令；
2. 提供用户共享文件的机制；
3. 管理文件的存储介质；
4. 提供文件的存取控制的机制，保障文件及文件系统的安全性；
5. 提供文件及文件系统的备份和恢复功能；
6. 提供对文件的加密和解密功能。

2. 文件目录的概念，内容和作用：

概念

1. 文件目录也被称为文件说明或文件控制块（File Control Block，FCB）即文件名址录。它是一张记录所有文件名及其存放地址、文件的说明和控制信息的表格。
2. 一般情况下，每个文件占用一个表目，即每个文件有一个文件的目录项。

内容

1. 文件名
2. 文件的大小，单位：字节
3. 文件在物理存储介质中的位置。
   • 取决于文件的物理结构 。对于连续文件：文件起始块号（即文件的第一个物理块块号）；对于串联文件：指向第一个物理块的指针；对于索引文件：索引表。
4. 存取控制信息
   • 文件主和其它用户对该文件的访问权限。
5. 管理信息
   • 包含文件创建的日期和时间，最近修改该文件的日期和时间等。
6. 文件的类型

作用

• 实现“按名存取”。
• 提高对目录的检索速度。
• 文件共享。
• 允许文件重名。

分一级目录，二级目录和树形目录

3. 文件的2种逻辑结构，5/6种物理结构

文件逻辑结构

1. 无结构文件
2. 结构文件

文件物理结构

1. 直接地址结构
2. 索引文件结构
3. 计算寻址结构

4. 文件存储空间管理的4种策略

1. 看空闲文件项
2. 空闲文件目录
3. 空闲块链
4. 位示图

5. 文件共享的5种方式

1. 绕道法
2. 采用“链接技术”实现文件共享
3. 基本文件目录
4. 利用符号链实现问及那共享
5. 基于索引节点的共享方式

6. 存储保护的方式6种方式

1. 访问控制矩阵
2. 存取控制表
3. 用户权限表
4. 隐藏文件目录
5. 口令
6. 密码

6. 文件操作及实现流程

为方便用户使用文件，文件系统提供对文件的各种操作，形式分别为：

1. 系统调用或命令
2. 提供设置和修改用户文件的存取权限的服务
3. 提供建立、修改、改变、删除目录的服务
4. 提供文件共享，设置访问路径的服务
5. 提供创建、打开、读、写、关闭、撤消文件等服务
6. 文件系统维护
7. 文件系统的转储和恢复

最基本的操作是：打开、关闭、读、写文件等

7. 文件缓存

1. 全量缓存：把文件存储器中的所有文件定期复制到磁带上
2. 增量缓存：定期把所有修改过大的文件和新文件转储到磁带上

三、计算题：44分（6题）

第四章 2种

计算题（PV）
判断程序对错（违背“忙则等待”或“空闲让进”）

第五章 1种

1. 银行家算法

第六章 3种

1. 作业调度
2. 进程调度
3. 作业及进程混合调度

第七章 2种

1. 页式地址变换
2. 淘汰策略

第九章 3种

1. UNIX索引结构
2. 基于文件目录
3. 基于位示图计算

四、综合应用题：12分*1=12分