操作系统期末复习 | 批处理程序 | PV实现同步互斥 | 调度算法 | 页面置换算法 | 磁盘调度算法

操作系统引论

批处理程序

单道批处理：引入脱机输入/输出技术，并由监督程序负责控制作业的输入、输出。主要优点是缓解了一定程度的人机速度矛盾，资源利用率有所提升。主要缺点是内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU有大量的时间是在空闲等待1/0完成，资源利用率依然很低。

多道批处理：主要优点是多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大。主要缺点是用户响应时间长，没有人机交互功能（用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业执行。eg：无法调试程序/无法在程序运行过程中输入一些参数）。

分时系统

计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。主要优点是用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。主要缺点是不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户作业服务一个时间片，不区分任务的紧急性。及时性：用户程序是轮流执行CPU的一个时间片，但由于计算机的高速处理能力，能保证在较短和可容忍的时间内响应和完成处理用户请求。

实时系统

主要优点是能够优先响应一些紧急任务，某些紧急任务不需时间片排队。在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。

进程同步与互斥

进程的概念

进程是指计算机中已运行的程序，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。

1. 动态性：进程是程序的一次执行，它有着创建、活动、暂停、终止等过程，具有一定的生命周期，是动态地产生、变化和消亡的。动态性是进程最基本的特征。
2. 并发性：指多个进程实体，同存于内存中，能在一段时间内同时运行，并发性是进程的重要特征，同时也是操作系统的重要特征。引入进程的目的就是为了使程序能与其他进程的程序并发执行，以提高资源利用率。
3. 独立性：指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。
4. 异步性：由于进程的相互制约，使进程具有执行的间断性，即进程按各自独立的、 不可预知的速度向前推进。异步性会导致执行结果的不可再现性，为此，在操作系统中必须配置相应的进程同步机制。
5. 结构性：每个进程都配置一个PCB对其进行描述。从结构上看，进程实体是由程序段、数据段和进程控制段三部分组成的。

进程与程序的区别

1. 程序是永存的；进程是暂时的，是程序在数据集上的一次执行，有创建有撤销，存在是暂时的。
2. 程序是静态的观念，进程是动态的观念。
3. 进程具有并发性，而程序没有。
4. 进程是竞争计算机资源的基本单位，程序不是。
5. 进程和程序不是一一对应的。
6. 一个程序可对应多个进程即多个进程可执行同一程序。
7. 一个进程可以执行一个或几个程序。

进程的基本状态

进程在其生命周期内，由于系统中各进程之间的相互制约关系及系统的运行环境的变化，使得进程的状态也在不断地发生变化（一个进程会经历若干种不同状态）。通常进程有以下五种状态，前三种是进程的基本状态。

1. 运行状态：进程正在处理机上运行。在单处理机环境下，每一时刻最多只有一个进程处于运行状态。

2. 就绪状态：进程已处于准备运行的状态，即进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行。

3. 阻塞状态：又称等待状态：进程正在等待某一事件而暂停运行，如等待某资源为可用（不包括处理机）或等待输入/输出完成。即使处理机空闲，该进程也不能运行。

4. 创建状态：进程正在被创建，尚未转到就绪状态。创建进程通常需要多个步骤：首先申请一个空白的PCB，并向PCB中填写一些控制和管理进程的信息；然后由系统为该进程分 配运行时所必需的资源；最后把该进程转入到就绪状态。

5. 结束状态：进程正从系统中消失，这可能是进程正常结束或其他原因中断退出运行。当进程需要结束运行时，系统首先必须置该进程为结束状态，然后再进一步处理资源释放和回收等工作。

**作业2：**请简述进程发生状态变迁1、3、4、6、7的原因；系统中常常由于某一进程的状态变迁引起另一进程也产生状态变迁，这种变迁称为因果变迁。下述变迁是否为因果变迁：3-2,4-5,7-2,3-6，请说明原因。

进程同步与互斥

进程同步是指在多个进程或线程之间协调彼此的执行顺序，以避免出现竞态条件、死锁和其他并发问题。当多个进程或线程共享同一资源时，如果它们同时读取或写入该资源，可能会引发数据不一致的问题。为了解决这些问题，需要使用同步机制来协调它们的访问。

进程互斥指的是当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

临界资源

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。临界区指的是控制临界资源的代码。为实现对临界资源的互斥访问，必须遵循以下四个规则：

1. 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
2. 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
3. 有限等待：对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)。
4. 让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

P、V操作控制进程同步互斥

**作业3-1：**3 个进程 P1、P2、P3 互斥地使用一个包含 N（N ＞ 0）个单元的缓冲区。P1 每次用 produce() 生成一个正整数，并用 put() 将其送入缓冲区的某一空单元中 ；P2每次用 getodd() 从该缓冲区中取出一个奇数，并用 countodd() 统计奇数的个数 ；P3 每次用geteven() 从该缓冲区中取出一个偶数，并用 counteven() 统计偶数的个数。请用信号量机制实现这 3 个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

如下图所示，get、copy和put三个进程共用两个缓冲区s和t (其大小每次存放一个记录) ，get 进程负责不断地把输入记录输入缓冲区s 中，copy 进程负责从缓冲区s 中取出记录复制到缓冲区t 中，而put 进程负责从缓冲区t 中取出记录打印。试用PV 操作实现这三个进程之间的同步，并写出程序描述。

进程同步

死锁

在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进，此时每个进程都占用了一定的资源但又都不能向前推进，称这一组进程产生了死锁。

产生死锁的两个原因：

1. 系统资源不足。
2. 进程推进顺序非法。

产生死锁的四个必要条件：

1. 互斥条件：涉及的资源是非共享的。

2. 不剥夺条件：进程所获得的资源在未使用完毕之前不能被其它进程强行夺走。

3. 部分分配：进程每次申请它所需要的一部分资源，在等待新资源的同时继续占用已分配到的资源。

4. 环路条件：存在着一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程请求。

解决死锁的四种策略：

1. 预防：通过设置某些限制条件，以破坏产生死锁的四个条件中的一个或者几个，来防止发生死锁。
2. 避免：系统在分配资源时根据资源的使用情况提前作出预测，从而避免死锁的发生。
3. 检测：允许系统在运行的过程中产生死锁，但是，系统中有相应的管理模块可以及时检测出已经产生的死锁，并且精确地确定与死锁有关的进程和资源，然后采取适当措施，清除系统中已经产生的死锁。
4. 解除：与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来。

选择进程调度算法的准则：尽快响应交互式用户的请求、尽量提高处理机的利用率、 尽可能提高系统的吞吐量。如果所有进程同时到达，短进程优先算法使进程的平均周转时间最短。

银行家算法

设系统中有5个进程P1、P2、P3、P4、P5，有3种类型的资源A、B、C，其中A资源的数量是17，B资源的数量是5，C资源的数量是20，T0时刻系统状态如下表所示。

1. 计算每个进程还可能需要的资源，并填入表的“仍然需要资源数(Need)”的栏目。
2. 0时刻系统是否处于安全状态？为什么？
3. 如果T0时刻进程P2又有新的资源请求（0，3，4），是否实施资源分配？为什么？
4. 如果T0时刻，若进程P4又有新的资源请求（2，0，1），是否实施资源分配？为什么？
5. 在4的基础上，若进程P1又有新的资源请求（0，2，0），是否实施资源分配？为什么？

进程调度常用算法

在一个系统中，有5个进程进入系统，它们的提交时间、执行时间如下：

若系统分别采用先来先服务（FCFS）调度算法、短作业优先（SJF）和最高响应比（HRRN）调度算法进行上述进程调度，请计算几种算法的周转时间和带权周转时间并填写下表。

进程A、B、C、D先后在1、2、3、4时刻到达系统，需要运行的时间分别为6ms、5ms、3ms、4ms。如果时间片分别为2ms和5ms，计算各个进程的周转时间和带权周转时间并填写下表。

存储器管理

地址

1. 逻辑地址：用户程序的目标模块都以0为基地址顺序编址的，这种地址称为逻辑地址，也称为相对地址。

2. 物理地址：内存中各物理存储单元的地址是从统一的基地址开始顺序编址的，这种地址称为物理地址，也称为绝对地址。

3. 地址重定位：程序和数据装入内存时，需对目标程序中的地址进行修改。这种把逻辑地址转变为内存物理地址的过程称作重定位。

分区存储管理

在某个系统，存储管理方案采用动态分区方式。在某一时刻，主存中有两个空白区，分别为120kb和78kb。现有3个被调度执行的作业J1、J2和J3，对内存需求分别为50KB、60KB、70KB。若用首次适应算法和最佳适应算法来处理这个作业序列，试问哪一种算法可以满足三个作业的分配需求？请说明分配过程。

某页式存储管理系统，内存的大小为256KB，被分为128块，块号为0、1、2、……、127。设某进程有4页，其页号为0、1、2、3，被分别装入内存的4、5、18，9号块。该进程的大小是多少字节？请计算该进程每一页在内存的起始地址并填入下表。计算逻辑地址2176和6300对应的物理地址是多少？

页号	块号	内存起始地址
0	4
1	5
2	18
3	9

分页存储管理

请求页式存储管理基本思想：将程序的逻辑地址空间划分为一系列的固定大小的页面，每个页面通常包含多个字节，比如4KB或8KB。程序运行时，只加载当前需要执行的部分（即页面）到物理内存中，其余部分暂存在磁盘上。当程序试图访问某个地址时，系统首先检查这个地址是否在当前已加载的页面内。如果在，就直接执行；如果不在（即发生了“缺页”），系统会从磁盘上读取对应的页面并将其调入内存，然后再继续执行。这种管理方式允许程序动态地使用内存，并通过页面替换算法（如LRU、FIFO或最近最不经常使用等）来优化内存使用和提高效率。

内部碎片是由于采用固定大小的内存分区，当一个进程不能完全使用分给它的固定内存区域时就产生了内部碎片，通常内部碎片难以完全避免。

现在普遍采用的段页式内存分配方式就是将进程的内存区域分为不同的段，然后将每一段由多个固定大小的页组成。通过页表机制，使段内的页可以不必连续处于同一内存区域，从而减少了外部碎片，然而同一页内仍然可能存在少量的内部碎片，只是一页的内存空间本就较小，从而使可能存在的内部碎片也较少。

页面置换算法

有一个虚拟存储系统, 每个进程在内存分配3页数据区, 页面大小为1KB, 刚开始时数据区为空。假设该进程的虚地址访问流为：5200、1000、1300、200、2250、1022、1200、4350、600、3050、6010、2010、2300、4020

（1）请计算出该进程的页面访问序列。

（2）若系统采用先进先出(FIFO)淘汰算法置换页面，请分析并计算发生页面置换和缺页中断的次数。

（3）若系统采用最近最久未使用(LRU)淘汰算法置换页面，请分析并计算发生页面置换和缺页中断的次数。

抖动现象

抖动现象是指如果分配给进程的存储块数量小于进程所需要的最小值，进程的运行将会很频繁地产生缺页中断 ，这种频率非常高的页面置换现象称为抖动。

也可以说：页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行时间还多，此时系统效率急剧下降，导致系统崩溃。这种现象称为颠簸或抖动。

输入输出系统

设备独立性

设备独立性是指操作系统把所有外部设备统一当作成文件来看待，只要安装它们的驱动程序，任何用户都可以象使用文件一样，操纵、使用这些设备，而不必知道它们的具体存在形式。引入设备独立性后可以调高设备的利用率和分配时的灵活性；提高系统的可适应性和可扩展性；可以方便用户操作，易于实现IO重定向。

IO控制方式

程序直接控制方式

1. CPU向控制器发出读指令。于是设备启动，并且状态寄存器设为1（未就绪)。
2. 轮询检查控制器的状态(其实就是在不断地执行程序的循环，若状态位一直是1，说明设备还没准备好要输入的数据,于是CPU会不断地轮询)。
3. 输入设备准备好数据后将数据传给控制器，并报告自身状态。
4. 控制器将输入的数据放到数据寄存器中,并将状态改为0（己就绪)。
5. CPU发现设备已就绪，即可将数据寄存器中的内容读入CPU的寄存器中，再把CPU寄存器中的内容放入内存。
6. 若还要继续读入数据，则CPU继续发出读指令。

优点:实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可（因此才称为“程序直接控制方式”)。

缺点:CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于“忙等”状态，CPU利用率低。

中断驱动方式

1. 引入中断机制。
2. 由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待l/O的进程阻塞，先切换到别的进程执行。
3. 当I/O完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。
4. 处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器，再写入主存。
5. 接着，CPU恢复等待l/O的进程（或其他进程）的运行环境，然后继续执行。

优点：与“程序直接控制方式”相比，在“中断驱动方式”中，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率得到明显提升。

缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。

DMA控制方式

1. 数据的传送单位是“块”。不再是一个字、一个字的传送。
2. 数据的流向是从设备直接放入内存，或者从内存直接到设备。
3. 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。

优点：数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。

缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。
如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成。

通道控制方式

1. CPU向通道发出I/O指令。指明通道程序在内存中的位置，并指明要操作的是哪个I/O设备。之后CPU就切换到其他进程执行了。
2. 通道执行内存中的通道程序（其中指明了要读入/写出多少数据，读/写的数据应放在内存的什么位置等信息)。
3. 通道执行完规定的任务后，向CPU发出中断信号，之后CPU对中断进行处理。

优点：CPU、通道、I/O设备可并行工作，资源利用率很高。

缺点：实现复杂，需要专门的通道硬件支持。

Spolling技术

缓冲技术的作用：提高CPU与设备之间的并行程度，以空间代价换取时间代价。

共享打印机为例：

1. 在磁盘输出井中为进程申请一个空闲缓冲区(也就是说，这个缓冲区是在磁盘上的)，并将要打印的数据送入其中:
2. 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息的），再将该表挂到假脱机文件队列上。当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务。

设备控制器

接收和识别CPU发出的命令；向CPU报告设备的状态；数据交换；地址交换。

磁盘调度算法

磁盘请求的磁道号次序为：120,69,78,2,5,29,65,38,106,88寻道时每个磁道移动需要0.1ms，磁臂启动时间为2ms。试计算按以下算法调度时的平均寻道时间：先来先服务（FCFS）；最短寻道时间优先（SSTF）；扫描算法（SCAN）。