《操作系统》期末复习提纲
重磅资料，ppt集大成者
【知识点】
一、 课件第1章 操作系统引论
- 操作系统类型（单/多道批处理系统、分时系统、实时系统）及其各自特点。
答：一、批处理阶段（操作系统开始出现）
为了解决人机矛盾及CPU和I/O设备之间速度不匹配的矛盾，出现了批处理系统。它按发展历程又分为单道批处理系统、多道批处理系统（多道程序设计技术出现以后）。
1) 单道批处理系统
系统对作业的处理是成批进行的，但内存中始终保持一道作业。该系统是在解决人机矛盾和CPU与I/O设备速率不匹配的矛盾中形成的。单道批处理系统的主要特征如下：
自动性。在顺利的情况下，在磁带上的一批作业能自动地逐个依次运行，而无需人工干预。 '
顺序性。磁带上的各道作业是顺序地进入内存，各道作业的完成顺序与它们进入内存的顺序，在正常情况下应完全相同，亦即先调入内存的作业先完成。
单道性。内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入内存运行，当该程序完成或发生异常情况时，才换入其后继程序进入内存运行。
此时面临的问题是：每次主机内存中仅存放一道作业，每当它运行期间（注意这里是“运行时”，并不是“完成后”）发出输入/输出请求后，高速的CPU便处于等待低速的I/O完成状态。为了进一步提高资源的利用率和系统的吞吐量，引入了多道程序技术。
2) 多道批处理系统
多道程序设计技术允许多个程序同时进入内存并运行。即同时把多个程序放入内存，并允许它们交替在CPU中运行，它们共享系统中的各种硬、软件资源。当一道程序因I/O请求而暂停运行时，CPU便立即转去运行另一道程序。它没有用某些机制提高某一技术方面的瓶颈问题，而是让系统的各个组成部分都尽量去“忙”，花费很少时间去切换任务，达到了系统各部件之间的并行工作，使其整体在单位时间内的效率翻倍。
多道程序设计的特点有：
多道：计算机内存中同时存放多道相互独立的程序。
宏观上并行：同时进入系统的多道程序都处于运行过程中，即它们先后开始了各自的运行，但都未运行完毕。
微观上串行：内存中的多道程序轮流占有CPU，交替执行。
多道程序设计技术的实现需要解决下列问题：
如何分配处理器。
多道程序的内存分配问题。
me/O设备如何分配。
如何组织和存放大量的程序和数据，以便于用户使用和保证其安全性与一致性。
在批处理系统中釆用多道程序设计技术，就形成了多道批处理操作系统。该系统把用户提交的作业成批地送入计算机内存，然后由作业调度程序自动地选择作业运行。
优点是资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分利用；系统吞吐量大，CPU和其他资源保持“忙碌”状态。缺点是用户响应的时间较长。不提供人机交互能力，用户既不能了解自己程序的运行情况，也不能控制计算机。
二、分时操作系统
在操作系统中釆用分时技术就形成了分时系统。所谓分时技术就是把处理器的运行时间分成很短的时间片，按时间片轮流把处理器分配给各联机作业使用。若某个作业在分配给它的时间片内不能完成其计算，则该作业暂时停止运行，把处理器让给其他作业使用，等待下一轮再继续运行。由于计算机速度很快，作业运行轮转得很快，给每个用户的感觉好像是自己独占一台计算机。
分时操作系统是多个用户通过终端同时共享一台主机，这些终端连接在主机上，用户可以同时与主机进行交互操作而互不干扰。所以，实现分时系统最关键的问题是如何使用户能与自己的作业进行交互，即当用户在自己的终端上键入命令时，系统应能及时接收并及时处理该命令，再将结果返回用户。分时系统也是支持多道程序设计的系统，但它不同于多道批处理系统。
多道批处理是实现作业自动控制而无需人工干预的系统，而分时系统是实现人机交互的系统，这使得分时系统具有与批处理系统不同的特征，其主要特征如下：
同时性。同时性也称多路性，指允许多个终端用户同时使用一台计算机，即一台计算机与若干台终端相连接，终端上的这些用户可以同时或基本同时使用计算机。
交互性。用户能够方便地与系统进行人-机对话，即用户通过终端釆用人4^1对话的方式直接控制程序运行，与同程序进行交互。
独立性。系统中多个用户可以彼此独立地进行操作，互不干扰，单个用户感觉不到别人也在使用这台计算机，好像只有自己单独使用这台计算机一样。
及时性。用户请求能在很短时间内获得响应。分时系统釆用时间片轮转方式使一台计算机同时为多个终端服务，使用户能够对系统的及时响应感到满意。
虽然分时操作系统比较好地解决了人机交互问题，但是在一些应用场合，需要系统能对外部的信息在规定的时间（比时间片的时间还短）内作出处理（比如飞机订票系统或导弹制导系统)。因此，实时系统应运而生。
三、实时操作系统
为了能在某个时间限制内完成某些紧急任务而不需时间片排队，诞生了实时操作系统。这里的时间限制可以分为两种情况：如果某个动作必须绝对地在规定的时刻（或规定的时间范围）发生，则称为硬实时系统。例如，飞行器的飞行自动控制系统，这类系统必须提供绝对保证，让某个特定的动作在规定的时间内完成。如果能够接受偶尔违反时间规定，并且不会引起任何永久性的损害，则称为软实时系统，如飞机订票系统、银行管理系统。
在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完接收的事件。实时橾作系统的主要特点是及时性和可靠性。
---------------------
作者：dmfrm
来源：CSDN
原文：https://blog.csdn.net/u010889616/article/details/48424501
版权声明：本文为博主原创文章，转载请附上博文链接！
- 操作系统的4个特征，其中最基本的是哪两个。
链接：[https://www.nowcoder.com/questionTerminal/fd330a8327464f20b672cd8d13bacf42?toCommentId=25073](https://www.nowcoder.com/questionTerminal/fd330a8327464f20b672cd8d13bacf42?toCommentId=25073)
来源：牛客网
1、并发性：指多个进程实体同存于内存中，且在一段时间内同时运行。并发性是进程的重要特征，同时也成为操作系统的重要特征。
2、动态性：进程的实质是进程实体的一次执行过程，因此，动态性是进程最基本的特征。
3、独立性：进程实体是一个独立运行、独立分配资源和独立接受调度的基本单位。
4、异步性：指进程按各自独立的、不可预知的速度向前推进，或者说实体按异步方式运行
- 操作系统的5个主要功能。
（1）作业管理：包括任务、界面管理、人机交互、图形界面、语音控制和虚拟现实等；
（2）文件管理：又称为信息管理；
（3）存储管理：实质是对存储“空间”的管理,主要指对主存的管理；
（4）设备管理：实质是对硬件设备的管理,其中包括对输入输出设备的分配、启动、完成和回收；
（5）进程管理：实质上是对处理机执行“时间”的管理,即如何将CPU真正合理地分配给每个任务
- 用户可以通过哪3种方式使用操作系统提供的服务。
操作系统作为用户与计算机硬件系统之间的接口，用户可通过三种方式使用计算机：命令方式、系统调用方式、图标-窗口方式
1.命令方式：典型的命令行方式有DOS系统和Unix系统等
2.系统调用方式：（system call)为了达到这个目的，内核提供一系列具备预定功能的多内核函数，通过一组称为系统调用的接口呈现给用户。系统调用把应用程序的请求传给内核，调用相应的的内核函数完成所需的处理，将处理结果返回给应用程序
3.图标-窗口方式：操作系统所提供的图形化界面
---------------------
作者：柳婼
来源：CSDN
原文：https://blog.csdn.net/liuchuo/article/details/51986071
版权声明：本文为博主原创文章，转载请附上博文链接！
二、 课件第2章 进程管理
- 程序和进程的主要区别。
进程和程序区别和联系表现在以下方面：
1)程序只是一组指令的有序集合，它本身没有任何运行的含义，它只是
一个静态的实体。而进程则不同，它是程序在某个数据集上的执行。
进程是一个动态的实体，它有自己的生命周期。它因创建而产生，因
调度而运行，因等待资源或事件而被处于等待状态，因完成任务而被
撤消。反映了一个程序在一定的数据集上运行的全部动态过程。
2)进程和程序并不是一一对应的，一个程序执行在不同的数据集上就成
为不同的进程，可以用进程控制块来唯一地标识每个进程。而这一点
正是程序无法做到的，由于程序没有和数据产生直接的联系，既使是
执行不同的数据的程序，他们的指令的集合依然是一样的，所以无法
唯一地标识出这些运行于不同数据集上的程序。一般来说，一个进程
肯定有一个与之对应的程序，而且只有一个。而一个程序有可能没有
与之对应的进程(因为它没有执行),也有可能有多个进程与之对应(运
行在几个不同的数据集上)。
3)进程还具有并发性和交往性，这也与程序的封闭性不同。
- 进程的3个基本状态及其转换。
进程的基本状态：
**①就绪（Ready）状态**
当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行，进程这时的状态就称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将他们排成一个队列，称为就绪队列。
**②执行状态**
进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；在多处理机系统中，则有多个进程处于执行状态。
**③阻塞状态**
正在执行的进程，由于等待某个事件发生而无法执行时，便放弃处理机而处于阻塞状态。引起进程阻塞的事件可有多种，例如，等待I/O完成、申请缓冲区不能满足、等待信件(信号)等。
进程三种状态间的转换:
①**就绪→执行**处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。
②**执行→就绪**处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。
③**执行→阻塞**正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。
④**阻塞→就绪**处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。
- 进程控制块PCB的作用。
PCB 可以被操作系统中的多个模块读或修改，如被调度程序、资源分配 程序、中断处理程序以及监督
和分析程序等读或修改。
OS是根据 PCB来对 并发执行的进程进行控制和管理
是操作系统中最重要的记录型数据结构
Linux 系统中用 task_struct 数据结构，
Windows：执行体进程块(EPROCESS)
使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，
一个能与其它进程并发执行的进程
（第四版）
1、作为独立运行基本单位的标志
2、能实现间断性运行方式
3、提供进程管理所需要的信息
4、提供进程调度所需要的信息
5、实现与其他进程的同步与通信
---------------------
作者：一叶hu
来源：CSDN
原文：https://blog.csdn.net/canyanruxue/article/details/78439934
版权声明：本文为博主原创文章，转载请附上博文链接！
- 使用信号量解决进程同步问题。
用信号量解决进程的同步与互斥
- 进程和线程的主要区别。
进程和线程的区别？
进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。
1) 简而言之,一个程序至少有一个进程,一个进程至少有一个线程.
2) 线程的划分尺度小于进程，使得多线程程序的并发性高。
3) 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。
4) 线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
5) 从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。
三、 课件第3章 处理机调度与死锁
- 处理机调度的3个层次（进程调度、作业调度、页面调度）作用及频繁程度。
1.高级调度：高级调度又称为长程调度或作业调度，它的调度对象是作业。其主要功能是根据某种算法，决定从外存中处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中，而在实时和分时系统中不设置高级调度。
2.低级调度：低级调度又称为进程调度或短程调度，其所调度的对象是进程。其主要功能是，根据某种算法，决定就绪队列中哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度，在多道批处理系统、实时和分时操作系统中，都必须配置这级调度。
3.中级调度：中级调度又称为内存调度。引入中级调度的主要目的是，提高内存利用率和系统吞吐量。中级调度实际上就是存储器管理中的对换功能。
---------------------
作者：ckwbeyond
来源：CSDN
原文：https://blog.csdn.net/u012571415/article/details/40663051
版权声明：本文为博主原创文章，转载请附上博文链接！
- 处理机调度算法及作业周转时间、带权周转时间和平均周转时间的计算：先来先服务算法、短作业优先算法。
这三个概念需要特别理解清楚。
周转时间=作业完成时间−作业提交时间周转时间=作业完成时间−作业提交时间
特别注意作业提交时间不是作业进内存的时间，而是发出请求，提交就开始计时，如果无法安排进内存，那么就等待，等待的这部分时间也要计数。
平均周转时间=作业1的周转时间+...+作业n的周转时间n平均周转时间=作业1的周转时间+...+作业n的周转时间n
带权周转时间=作业周转时间作业实际运行时间带权周转时间=作业周转时间作业实际运行时间
平均带权周转时间=作业1的带权周转时间+...+作业n的带权周转时间n平均带权周转时间=作业1的带权周转时间+...+作业n的带权周转时间n
这些是对细节的把握，需要熟练掌握并且能够快速回测。
---------------------
作者：QUETAL
来源：CSDN
原文：https://blog.csdn.net/u011240016/article/details/53199183
版权声明：本文为博主原创文章，转载请附上博文链接！
- 死锁的4个必要条件。
产生死锁的四个必要条件：
（1） 互斥条件：一个资源每次只能被一个进程使用。
（2） 占有且等待：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3）不可强行占有:进程已获得的资源，在末使用完之前，不能强行剥夺。
（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之
一不满足，就不会发生死锁。
- 预防死锁的常用方法及其破坏的是哪一项必要条件。
处理死锁的基本方法：
*死锁预防：通过设置某些限制条件，去破坏死锁的四个条件中的一个或几个条件，来预防发生死锁。但由于所施加的限制条件往往太严格，因而导致系统资源利用率和系统吞吐量降低。
*死锁避免：允许前三个必要条件，但通过明智的选择，确保永远不会到达死锁点，因此死锁避免比死锁预防允许更多的并发。
*死锁检测：不须实现采取任何限制性措施，而是允许系统在运行过程发生死锁，但可通过系统设置的检测机构及时检测出死锁的发生，并精确地确定于死锁相关的进程和资源，然后采取适当的措施，从系统中将已发生的死锁清除掉。
*死锁解除：与死锁检测相配套的一种措施。当检测到系统中已发生死锁，需将 进程从死锁状态中解脱出来。常用方法：撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程。死锁检测盒解除有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。
下面才是答案：
二 死锁预防：破坏死锁的四个条件中的一个或几个。
(1)互斥：它是设备的固有属性所决定的，不仅不能改变，还应该加以保证。
(2)占有且等待：
为预防占有且等待条件，可以要求进程一次性的请求所有需要的资源，并且阻塞这个进程直到所有请求都同时满足。这个方法比较低效。
(3)不可抢占：
预防这个条件的方法：
*如果占有某些资源的一个进程进行进一步资源请求时被拒绝，则该进程必须释放它最初占有的资源。
*如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另外一个进程，要求它释放资源。
(4)循环等待：通过定义资源类型的线性顺序来预防。
*如果一个进程已经分配了R类资源，那么接下来请求的资源只能是那些排在R类型之后的资源类型。该方法比较低效。
- 采用银行家算法判断系统安全性及避免死锁。+
【操作系统】银行家算法避免死锁
四、 课件第4章 存储器管理
- 内存连续分配时使用的几种分区分配算法要点及其优缺点：首
次适应算法、循环首次 适应法、最佳适应算法、最差适应算法。
循环首次适应算法(Next Fit)：
该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。
一、首次适应算法（First Fit）：该算法从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链 中。
特点： 该算法倾向于使用内存中低地址部分的空闲区，在高地址部分的空闲区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。
缺点：低地址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低地址部分开始，会增加查找的开销。
二、最佳适应算法（Best Fit）：该算法总是把既能满足要求，又是最小的空闲分区分配给作业。为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算法似乎是最优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。
特点：每次分配给文件的都是最合适该文件大小的分区。
缺点：内存中留下许多难以利用的小的空闲区。
三、最坏适应算法（Worst Fit）:最坏适应算法是将输入的作业放置到主存中与它所需大小差距最大的空闲区中。空闲区大小由大到小排序。
特点：尽可能地利用存储器中大的空闲区。
缺点：绝大多数时候都会造成资源的严重浪费甚至是完全无法实现分配。
---------------------
作者：莫顾尔在
来源：CSDN
原文：https://blog.csdn.net/weixin_39282491/article/details/81045441
版权声明：本文为博主原创文章，转载请附上博文链接！
- 分页式存储管理模式下的地址变换过程。
页式虚拟存储系统的逻辑地址是由页号和页内地址两部分组成，地址变换过程如图7-3所示。假定页面的大小为4K，图7-3中所示的十进制逻辑地址8203经过地址变换后，形成的物理地址a应为十进制。
- 程序的局部性原理，时间局部性和空间局部性的含义。
程序局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。
相应地，执行所访问的存储空间也局限于某个内存区域，
具体来说，局部性通常有两种形式：时间局部性和空间局部性。
时间局部性：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。
空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。
作者：上善若水
链接：https://www.zhihu.com/question/25142664/answer/273783470
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 虚拟存储器的实现原理。
程序局部性原理：基于大量的程序运行特征的观察发现在一段时间内
，一个程序的执行往往是呈现高度的局部性。
表现在以下两个方面：
时间局部性：若一条指令被执行，那么不就的将来它很有可能再被执行。
空间局部性：若内存单元被使用，则在一定时间内它及其相邻单元很可能被再次使用。
虚拟存储技术：
由程序局部性原理可以发现，程序装入内存的时候，没必要一下子全部装入，
所以作业提交给系统时，首先进入辅存，
运行时，只将其有关部分信息装入内存，大部分仍然在外存中，
当运行过程中需要用到不在内存的信息时，再把它们调入，由外存和内存结合在一起，向用户提供一个其认为有的、但实际上不存在的大容量的内存，称为虚拟存储器。这样虚拟存储器就成了一个将内、外存结合在一起，容量接近外存，速度接近内存的存储器。
实现虚拟存储技术的主要方法有，请求分页存储管理、请求分段存储管理和请求段页存储管理
- 虚拟存储器的页面置换算法：最佳置换算法OPT、最近最久未使用算法LRU。
操作系统页面置换算法
五、 课件第5章 设备管理
-
4种I/O控制方式原理及典型代表：程序的I/O、中断驱动的I/O、DMA、通道。
image.png 设备缓冲区的作用。
对缓冲区的理解
1、设备独立性的概念
---- 为了提高OS的可适应性和可扩展性，在现代OS中都毫无例外地实现了设备独立性（Device Independence），也称为设备无关性。
---- 其基本含义是：应用程序独立于具体使用的物理设备。为了实现设备独立性而引入了逻辑设备和物理设备这两个概念。
---- 在应用程序中，使用逻辑设备名称来请求使用某类设备；而系统在实际执行时，还必须使用物理设备名称。
因此，系统需具有将逻辑设备名称转换为某物理设备名称的功能，这非常类似于存储器管理中介绍的逻辑地址和物理地址的概念。
---- 在应用程序中所使用的是逻辑地址，而系统在分配和使用内存时，必须使用物理地址。
在实现了设备独立性的功能后，可带来以下两方面的好处。
1）设备分配时的灵活性
当应用程序（进程）以物理设备名称来请求使用指定的某台设备时，如果该设备已经分配给其他进程或正在检修，而此时尽管还有几台其它
的相同设备正在空闲，该进程却仍阻塞。但若进程能以逻辑设备名称来请求某类设备时，系统可立即将该类设备中的任一台分配给进程，仅
当所有此类设备已全部分配完毕时，进程才会阻塞。
2）易于实现I/O重定向
所谓I/O重定向，是指用于I/O操作的设备可以更换（即重定向），而不必改变应用程序。例如，我们在调试一个应用程序时，可将程序的所有
输出送往屏幕显示；而在程序调试完后，如需正式将程序的运行结果打印出来，此时便需将I/O重定向的数据结构---逻辑设备表中的显示终端
改为打印机，而不必修改应用程序。
---------------------
作者：cany1000
来源：CSDN
原文：https://blog.csdn.net/dongyanxia1000/article/details/51879454
版权声明：本文为博主原创文章，转载请附上博文链接！
- 设备分配过程：设备分配、控制器分配、通道分配。
[操作系统]设备分配中的数据结构:设备控制表（DCT）、控制器控制表（COCT）、通道控制表（CHCT）和系统设备表（SDT）
这网页真特么好看
- 磁盘访问时间的构成：寻道时间、旋转延迟时间、数据传输时间。
- 磁盘调度算法：先来先服务FCFS、最短寻道时间优先SSTF、扫描/电梯调度算法SCAN。
磁盘调度算法剖析(FIFO、SSTF、SCAN、CSCAN、FSCAN)
六、 课件第6章 文件管理
- 几种外存分配方式的原理及优缺点：连续分配、链接分配（隐式链接、显式链接）、索引分配。
浅谈外存分配的几种方式-连续分配、链式分配、索引分配
- 系统分别采用一级索引和二级索引时，所允许的最大文件长度的计算。
索引练习题
- 文件目录的3种结构原理及优缺点：单级目录、二级目录、树形目录。
文件目录结构：单级、两级、多级(树形)和无环图目录结构
- 位示图的实现原理及相关计算。
基本法求解位示图编号问题
【应用题复习】
第二章
下面是一个从键盘输入到打印机输出的数据处理流图，其中键盘输入进程通过缓冲区 buf1 把输入数据传送给计算进程，计算进程把处理结果通过缓冲 buf2 传送给打印进程。buf1 和 buf2 为临界资源，试写出键盘输入进程，计算进程及打印进程间的同步算法伪码。
输入进程 → buf1 → 计算进程 → buf2 → 打印进程
第三章
- 假设系统中有5个进程，已知其到达时间和服务时间，忽略I/O及其他开销，分别按照先来先服务算法、非抢占的短进程优先调度算法对这5个进程实施调度，请填表计算各个进程的开始时间、完成时间、周转时间、带权周转时间和平均带权周转时间。
进程名 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间
A 0
3
B 2 6
C 4 4
D 6 5
E 8 2
平均带权周转时间为： 。
- 在银行家算法中，若出现下述资源分配情况：
Process Allocation Need Available
P0 0,0,3,2 0,0,1,2 1,6,2,2
P1 1,0,0,0 1,7,5,0
P2 1,3,5,4 2,3,5,6
P3 0,3,3,2 0,6,5,2
P4 0,0,1,4 0,6,5,6
(1) 该系统拥有的4种资源的总量分别是多少？
(2) 当前状态是一个安全状态，请填写下表，找出一个安全序列。
资源
进程 Work Need Allocation Work+Allocation Finish
ture
ture
ture
ture
ture
(3) 若进程P2提出请求Request（1，2，2，2），系统能否将资源分配给它？为什么？
第四章
在一个请求分页系统中，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，当分配给该作业的物理块数为3时，试计算分别采用LRU和OPT页面置换算法时，访问过程中所发生的缺页次数。
① 采用最近最久未用（LRU）页面淘汰算法时，会产生多少次缺页中断？
页面走向 4 3 2 1 4 3 5 4 3 2 1 5
页框 2
1
0
是否缺页
换出页
缺页中断次数为：
② 采用最佳置换 （OPT）页面淘汰算法时，会产生多少次缺页中断？
页面走向 4 3 2 1 4 3 5 4 3 2 9
1 5
页框 2
1
0
是否缺页
换出页
缺页中断次数为：
第五章
磁盘请求以10、22、20、2、40、6、38柱面的次序到达磁盘驱动器。移动臂移动一个柱面需要7ms，实行以下磁盘调度算法时，请给出磁盘的磁道访问顺序，计算磁头的平均寻道时间。假定磁臂起始时定位于柱面20，并刚刚完成了18号柱面的服务请求。
（a）先来先服务；（b）最短寻道时间优先；（c）电梯算法。
