第6章进程及处理机管理
现代操作系统的重要特点是程序的并发执行，及系统所拥有的资源被共享和系统用户随机地使用系统。采用一个什么样的概念，来描述计算机程序的执行过程和作为资源分配的基本单位才能充分反映操作系统的执行并发、资源共享及用户随机的特点呢？这个概念就是进程。
6．1 概述
6．1．1操作系统核心的功能和特点
1．进程与操作系统的关系：五大功能之一
（1）高级（宏）处理机管理
即作业调度，确定系统中哪些作业将获得CPU；
（2）低级（微）处理机管理
即进程调度，确定系统中哪个作业中的哪个进程将获得CPU。
2．什么是进程？
（1）进程的定义
进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。
进程是操作系统动态执行的基本单元，在传统的操作系统设计中，进程既是基本的分配单元，也是基本的执行单元。
（2）进程划分的原则
进程大小的“分割”设计，因不同的操作系统设计者而异。进程分得太大，极端情况就变成顺序执行的计算机，也就失去了并发性，也就降低了系统资源；但另一极端，进程分得太小，CPU为多个用户或一个用户的多个任务服务时，开销急剧增大。因为，在进程间的时空转换及工作量将大大增加。
3．操作系统核心功能
（1）调度进程，决定哪个进程运行、挂起、交换等；
（2）分配内存，哪个进程得到内存；
（3）管理和控制文件系统；检查“许可证”、修改目录、路径等；
（4）处理系统调用：由用户的进程发“请求”，系统根据资源的充分利用，统筹安排；
（5）处理输入输出的请求和工作。
总之，操作系统的五大功能都必须由核心负责协调工作。
4．操作系统核心的形式
（1）常驻内存：计算机启动后，操作系统核心常驻在内存
（2）操作系统核心是一组服务功能程序的集合，它由许多可执行的工作模块装配而成。操作系统中大量使用表格数据结构。通过大量内部表格内容的组合并发协调执行，大量工作是查表、修改和维护表格；
（3）操作系统设计有两种观点，即用户观点和资源观点。工作时有两大类表格：系统态和用户态。一类面对用户的“订单”，另一类由系统内部管理分工决定。
6．1．2为什么要引进进程概念
引入进程的概念，关键是共享资源引起的。在顺序执行模块的程序中，有如下特点：
（1）封闭性（closure property）；
（2）可再现性（re-appearable）；
（3）调试容易；
（4）设备利用率不高。
6．1．3顺序执行与并发执行
引入进程的关键是资源共享，而从资源的观点看，有效管理共享资源是计算机操作系统的最重要内容。
6．2 进程的定义和特征
在任务执行过程中切割成独立的单元涉及到进程(process)的组成内容、任务激活（active）以及线程（thread）。线程是近年来由进程发展而来，一般定义为程序执行中单个顺序的流控制，比进程优越之处是执行中占有相同的内存空间。
6．2．1 程序与进程
1．程序与进程的对比
2．程序与进程的类比
6．2．2 进程的五个基本特征
（1）动态性
进程是程序在并发系统的一次执行，一个进程有一个从产生到消失的生命期；
（2）并发性
正是为了描述程序在并发系统内执行的动态特征才引入了进程，没有并发就没有进程；
（3）独立性
每个进程的程序都是相对独立的顺序程序，可以按自己的方向和速度独立地向前推进；
（4）制约性
进程之间的相互制约，主要表现在互斥地使用资源和相关进程之间必要的同步和通讯；
（5）结构性
进程=PCB（进程控制块）+程序+数据集合。
6．2．3 进程与线程
1．线程的定义
简单地讲，进程就是程序的一次执行过程。而线程是由进程派生出来的一组代码（指令组）的执行过程。
2．线程的特点
线程是由进程派生出来的，一个进程可以产生多个线程，线程的特点是共享进程的内存空间，它们可以并发、异步地执行。
3．采用线程的优点
（1）使同一个程序能有几个并发执行的路径，提高了执行速度；
（2）线程需要的开销比进程小。
4．Windows的多任务调度
（1）Windows 3.x 采用协作式多任务
在Windows 3.x中，实行协作式的多任务方式，多个应用程序之间必须相互协调，依次实现操作系统的管理和控制。它并不是真正的多任务执行，为了让操作系统把控制权从一个程序转移到另一个程序，当前活动的程序就
必须周期地检查一个消息队列。如果一个程序不能检查消息队列，操作系统就不能实现控制权的转移。
（2）Windows 9x采用抢先式多任务
(a) 操作系统可以在需要时中断当前任务，再按照任务队列中各个任务
的优先级来进行多任务的调度。为兼容起见，基于Windows的16位（Win16）应用程序仍采用协作式；来完成多任务的执行。
(b) 在Windows 9x中，抢先式多任务的执行实际上就是抢先式多线程的实现。每个线程有一个优先值，范围从0到31，数字越大，则优先级越低。（3）在抢先式多任务中，基于Win32的应用程序不必让位给其它程序就能以友好的方式实现多任务。操作系统会根据系统的需要把控制权交给个运行中的任务，或从个运行中的任务移走控制权。
（4）在Windows 9x中，此种调度方式可能是系统不能稳定运行的原因之一。
6．3 进程调度
6．3．1进程的描述
1．多道程序并发执行的特点
（1）资源分配的动态性
多道程序在运行中可以提出分配资源的请求，操作系统酌情满足它，这就带来了资源分配的动态性。
（2）程序执行的间断性
在多道程序系统中，多个程序共享一个或多个CPU，一个程序在运行一段时间后便要让位给另一程序运行。因此，每个程序的运行都是处于“走走停停”的状态，这就是程序执行的间断性。
（3）程序间的通讯
如果多个程序之间有一种合作关系，例如共同求解一个题目，则它们在运行过程中就有可能互相传递数据，这就是程序间的通讯。
（4）程序间的同步和互斥
有合作关系的程序不仅要互相通讯，而且可能要调整它们之间的相对速度，比如一个程序必须等待另一个程序的结果才能继续运行。这就是程序间的同步。而由于多道程序系统中的资源共享，程序段之间对共享资源的竞争而导致了程序段之间的互斥。
2．进程的引入和构成
（1）进程的引进
上面所列的多道系统中的程序运行的新特点，程序本身是无法描述的，为此，当一个程序在并发系统中执行时，需引进一个新的数据结构来记录和描述这些特征。这样，新引进的数据结构与它所描述的程序便形成了一个有机体。这个有机体就称为进程。
（2）进程的构成
进程=PCB+程序+数据
其中，PCB（process control block）为记录程序在并发系统中执行时的动态特性的数据结构。
3．程序和进程的形象比较
（1）两个施工队按同一图纸在两个不同的地方建房，这是两个不同的进程；
（2）同一施工队按同一图纸在不同时间多次建房，这是多个进程。
由此可见，进程是一个与具体的时间和空间有关的动态概念。
4．进程的定义和特征
到目前为止，进程有多种定义，如：
（1）进程是程序的执行；
（2）并行程序称为进程；
（3）进程是可以和别的计算并发的计算；
（4）进程是一个数据结构及在其上进行操作的程序。
这些定义都从不同的侧面描述了进程的特征，都一定的道理，但我们认为下面的定义更全面和更准确：
进程是程序在一个数据集合上运行的过程，它是传统操作系统进行资源分配和调度的一个独立单位。此定义包含有如下的含义：
（1）进程是一个动态的概念，而程序是一个静态的概念；
（2）进程包含了一个数据集合和运行其上的程序；
（3）同一程序运行于若干不同的数据集合上时，它将属于若干个不同的进程，或者说，两个不同的进程可包含相同的程序；
（4）系统分配资源是以进程为单位的，所以只有进程才可能在不同的时刻处于几种不同的状态，即等待、就绪、运行。
（5）从微观上看，进程是轮换地占有处理机而运行的，从宏观上看，进程是并发地运行的。
6．3．2 进程的状态及转换
1．进程的状态
一般来说，一个进程在它的生命周期有三种基本状态，分别为就绪(ready)、执行(execute)和等待(waiting)。一个进程在刚创建初期处于“进入”状态，在运行终止后处于“完成”状态。
（1）就绪——进程具备运行条件，但尚未占用CPU；
（2）执行——进程正在占用CPU；
（3）等待——进程由于等待某一事件不能享用CPU。
进程的三种基本状态及关系如图6-1
图6-1 进程的三个基本状态示意图
2．引起进程状态转换的原因
（1）C PU调度（低级调度）：CPU调度按某种原则从就绪队列中调度一个进程到CPU上运行，该进程就从就绪状态变为运行状态；与此同时，原运行进程从运行状态变为就绪状态。因此，这两种状态变化是同时发生的。（2）进程在运行过程中需要等待某一事件，例如，等待分配某一资源，等待I/O操作完成等。一个进程在需要等待某一事件时主动退出CPU，并使自己处于阻塞状态，引起状态变化。
（3）如果进程所等待的事件发生了变化，例如，一次I/O完成了，于是进程便被解除阻塞状态，变为就绪状态。
（4）一个具体的进程在任何一个指定的时刻必须而且只能处于一种状态。3．进程状态转换的说明
（1）进程之间的状态转换并非都是可逆的
进程既不能从等待变为运行，也不能从就绪变为等待。
（2）进程之间的状态转换并非都是主动的，在很多情况下都是“它动的”事实上，只有运行到等待的转换是进程的主动行为（主动调用调度管理程序），其它都是它动的，例如，从执行到就绪，通常是时钟中断引起的，从等待到就绪，是一个进程把另一个进程唤醒。
6．3．3 进程控制
1、进程控制的任务
进程控制的任务就是系统使用一些具有特定功能的程序段来创建、撤消进程及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。
2、原语
一般，我们把系统态下执行的某些具有特定功能的程序段成为原语，原语可是机器指令级的扩充，其特点是执行期间不允许中断、它是一个不可分割的基本单位。它们都在系统态下执行，且都是为了完成某个系统管理所需要的功能和被高层软件调用。
在操作系统中，一般都把进程控制用的程序段做成原语，用于进程控制的原语有：创建原语、撤消原语、阻塞原语、唤醒原语等。
3、进程的创建与撤消
（1）进程的创建
进程创建的方式有两种：
（a）由系统程序模块统一创建。例如在批处理系统中，由操作系统的作业调度程序为用户进程创建相应的进程以完成用户作业所要求的功能。
（b）由父进程创建。例如在UNIX操作系统中，父进程创建子进程以完成并行工作。
（c）创建原语的流程图如图6-a
（2）进程撤消
（a）进程撤消的原因
1）该进程已完成所要求的功能而正常终止。
2）由于某种错误导致非正常终止。
3）祖先进程要求撤消某个子进程。
（b）撤消原语的流程如图6-b
4、进程的阻塞与唤醒
（1）进程的阻塞
阻塞原语在一个进程期待某一事件发生但发生条件尚不具备时，被该进程自己调用来阻塞自己。阻塞原语在阻塞一个进程时，由于该进程正处于执行状态，故应先中断出路机和保存该进程的处理机现场，然后被阻塞进程置阻塞状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。
阻塞原语的流程如图6-c
（2）进程的唤醒
（a）进程唤醒的两种方法
1）由系统进程唤醒
系统统一控制事件的发生并将“事件发生”这一消息通知等待进程。
2）由事件发生进程唤醒
在这种情况下，事件发生进程和唤醒进程之间是合作关系。
（b）唤醒原语的流程如图6-d
6．3．4 进程的调度算法举例
1．先来先服务（first come first service, FCFS）
将用户作业和就绪进程按提交顺序转变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最简单的方法。在没有特殊理由要优先调度某类作业或进程时，从处理的角度看，FCFS方式是一种最合适的方法，因为无论是追加还是取出一个队列元素在操作上都是最简单的。该算法的优点是实现简单，缺点是对那些执行时间较短的进程来说，将等待较长的时间，从而降低CPU的利用率。在实际操作系统中，FCFS算法常常和其它的算法配合起来使用，例如，基于优先级的调度算法就是对具有同样优先级的进程采用FCFS算法。
2．轮转法（round robin ,RR）
轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例。轮转法的基本概念是将CPU的处理时间分成固定大小的时间片，例如，几十毫秒到击败毫秒。如果一个进程在被调度选中之后用完了系统规定的时间片，但又未完成要求的任务，则它自行释放自己所占有的CPU 而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。显然，轮转法只能用来调度分配那些可以抢占的资源。这可以抢占的资源可以随时剥夺，而且可以将它们再分配给别的进程。CPU是可抢占的资源的一种。但打印机等是不可抢占的资源。另外，时间片长度的选择是根据系统对响应时间的要求和就绪队列中所允许的最大进程数确定的。
3．多级反馈轮转法（round robin with multiple feedback）
（1）在轮转法中，加入到就绪队列的进程有三种情况：
（a）分给它的时间片用完，但进程还未完成，回到就绪队列的末尾等待下次调度去继续执行；
（b）分给该进程的时间片未用完，只是因为请求I/O或由于进程的互斥与同步关系而被阻塞，当阻塞解除之后再回到就绪队列；
（c）新创建进程进入就绪队列。
（2）如果对这些进程区别对待，给予不同的优先级和时间片，可提高系统资源的利用率。例如，把就绪队列按照进程到达就绪队列的类型和进程被阻塞的原因分成不同的就绪队列，每个队列按FCFS原则排列，
不同队列中的进程享有不同的优先级，这样，当一个进程在执行完它的时间片之后，或从睡眠中被唤醒以及被创建之后，将进入不同的就绪队列。
（3）多级反馈轮转法与优先级法在原理上的区别是：一个进程在它执行结束之前，可能需要反复多次通过反馈循环执行，而不是优先级中的一次执行。
4．优先数法（priority）
1.所谓优先数法是指系统或用户按某种原则为进程指定一个优先级来表示该作业或进程所享有的调度优先权。该算法的核心是确定进程的优先级。
2.优先级的确定方法
优先级的确定方法有两种，分别为动态法和静态法，
（1）静态法根据进程的静态特征，在进程开始之前就确定它们的优先级，一旦开始之后就不能改变。
（2）动态法把进程的静态特征和动态特征结合起来确定作业或进程的优先级，随着进程的执行过程，其优先级不断变化。
3．静态优先级的确定原则
（1）作业调度中的优先级确定的原则
（a）由用户自己根据作业的紧急程度输入一个适当的优先级；
（b）由系统或操作员根据作业类型指定优先级；
（c）系统根据作业要求资源情况确定优先级。
（2）进程调度中的优先级确定的原则
（a）按进程的类型给予不同的优先级。一般地进程被分为系统进程和用户进程，对于用户进程和系统进程均可以再按照功能分为不同的类型并赋予不同的优先级。
（b）将作业的优先级作为它所属进程的优先级。
4．静态优先级的优缺点
基于静态优先级的调度算法的优点是实现简单，系统开销小；缺点是系统的效率底下，调度性能不高。
5．动态优先级的确定原则
（1）根据进程占有CPU的时间的长短来决定。
（2）根据就绪进程等待CPU的时间长短来决定。
6．动态优先级的优缺点
优点是调度性能高，系统资源的利用率高，缺点是系统开销大。6．3．5 进程控制块
1．进程控制块（process control block, PCB）是进程的重要组成部分，是操作系统能“感知”进程存在的唯一标志，它和进程是一一对应的，操作系统正是通过管理PCB来管理进程的。
2．PCB的数据结构
PCB是记录型的数据结构，其作用主要是描述进程的动态特征。主要内容有：
进程标识号—系统内部用于标识进程的整数；
进程状态—指进程当前所处的状态（就绪、运行、等待）；
进程标志—指是系统进程还是用户进程，程序实体是在内存还是在外存；
进程优先数—它是一个表示进程优先级的整数；
程序地址—指该进程的程序在内存或外存的地址；
现场保留区—在进程交换时保存其程序运行的CPU现场；
同步、互斥机构—同步和互斥的信号量；
通信结构—它包含一些指针，这些指针指向相应的通信队列或通信信箱；
家族联系—包含指向父进程和子进程的指针；
资源清单—本进程当前已分得的资源。
6．4 进程通信
6．4．1 进程的同步与互斥
1．进程同步
（1）进程同步的定义
进程同步是进程间共同完成一项任务是直接发生相互作用的关系，也就是说，这些具有伙伴关系的进程在执行时间次序上必须遵循确定的规律。（2）进程同步的例子
SPOOLing 系统中的输入功能可以由两个进程A和B完成，进程A负责从读卡机上把卡片上的信息读到一个缓冲区中，进程B负责把该缓冲区中的信息进行加工并写到外存输入井中。要实现两者的协同工作，两个进程必须满足如下的制约关系：只有当缓冲区的内容取空时，进程A才能向其中写入新信息；只有当缓冲区写满时，进程B才能从中取出内容作进一步加工和转送工作。可见，在缓冲区内容区空时，今晨B不应该继续运行，需要等待进程A向其中送入新的信息；反之，当缓冲区中的信息尚未取走时，进程A应等待，防止把原有的信息冲掉，造成丢失信息的结果。进程A和进程B就是一种同步关系。
2．进程互斥
（1）进程互斥的定义
一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。
进程的互斥是因为对同一物理资源的竞争而产生的相互制约关系。
（2）进程互斥的例子
两个进程使用一台打印机。
3、同步与互斥特点比较
6．4．2临界资源和临界区
我们包一次只允许一个进程使用的资源称为临界资源，而把在每个进程中访问临界资源的程序段称为临界区。要进入临界区的若干个进程必须满足如下关系： （1） 一次只允许一个进程进入临界区。 （2） 任何时候，处于临界区的进程不得多于一个。 （3） 进入临界区的进程要在有限的时间内退出。 （4） 如果不能进入自己的临界区，则应让出处理机资源。 6．4．3 同步、互斥机制的实现及应用 1、用锁操作原语实现互斥 （1）实现
为共享资源设置一把锁
W=0表示共享资源（分配表）可用；
W=1表示共享资源（分配表）不可用，已有一进程访问。 用类ALGOL 语言编程如下： 加锁原语LOCK
（W ）
L: if W=0 then W:=1 else goto L:
（说明：测试和设置指令；循环等待该资源释放） 开锁原语 UNLOCK （W ） W ：=0
加锁/开锁原语工作流程如图6-2
图6-2 加锁/开锁原语工作流程图
（2）局限性
只要有一个进程由于执行LOCK（W）而进入临界区，则其它进程在检查锁状态时都将反复执行LOCK（W）原语，从而导致处理机繁忙。现在一般采用硬件指令来解决互斥进入临界区问题。
2、信号量及P、V操作原语
P、V操作是荷兰科学家E.W.Dijkstra在1965年提出的一种解决同步、互斥问题的更通用的方法，并在THE操作系统中得以实现。P是荷兰语发信号的开头字母，V是等待的开头字母。
（1）信号量
信号量，也叫信号灯，一般是由两个成员组成的数据结构，其中一个成员S是整型变量，表示该信号量的值，另一个成员Q是指向PCB的队列。<信号量>=（S，Q）
信号量的值与相应资源的使用状态有关。当它的值>0时，它表示可用资源的数量；当它的值<0时，其绝对值表示等待使用该资源的进程个数，即在该信号量队列上排队的PCB的个数。信号量的一般数据结构及PCB队列如图6-e
图6-e 信号量的一般结构及PCB队列
（2）P、V操作
设信号量为S，对S的P操作记为P(S)，对它的V操作记为V(S)。P、V操作的含义是：
（a）P操作原语P(S)
P(S)操作顺序执行下述动作：
1）S=S-1
2）S>=0说明当前进程q有资源可执行；
3）S<=0 说明无资源，则当前进程刮起或封锁，将该进程插入排队到该信号量等待队列的队尾，并放弃处理机，进行等待（直到其它进程在S上执行V操作，把资源释放出来为止）。
流程图见图6-f
（b）V操作原语V(S)
V(S)操作顺序执行下述动作：
1）S=S+1；
2）如果S>0，则该进程继续运行；
3）如果S<=0，则释放信号队列上的第一个PCB（即信号量指针所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行V操作的进程继续运行。流程图见6-g
3、用P、V原语实现进程互斥
用P、V原语实现两并发进程P A，P B互斥的描述如下：
1）设sem为互斥信号量，其取值范围为（1，0，-1）。
其中sem=1表示进程P A，P B都未进入临界区S，sem=0表示进程P A或P B已进入临界区S，sem=-1表示进程P A和P B中，一个进程已进入临界区，而另一个进程等待进入临界区。
2）描述：
P A：
P(sem)
< S >
V(sem)
. . .
P B：
P(sem)
< S >
V(sem)
. . .
4、生产者—消费者问题
把并发进程的同步和互斥问题一般化，可以得到一个抽象的一般模型，即生产者—消费者问题。计算机系统中，每个进程都申请使用和释放各种不同类型的资源，这些资源即可以是象外设、内存及缓冲区等硬件资源，也包括临界区、数据、例程等软件资源。我们把系统中使用某一类资源的进程称为该资源的消费者，而把释放同类资源的进程称为该资源的生产者。
设有若干个生产者进程P1，P2，….PN，若干个消费者进程C1，
C2，…CM，它们通过一个有界缓冲池联系起来。
为了描述生产者—消费者问题，可以设置若干个信号量（semaphore）: full,empty和mutex。其中mutex是互斥信号量，full,empty 是同步信号量。编程示意如下：
semaphore full = 0;
semaphore empty = 0;
semaphore mutex = 1;
{
{/*生产者*/
P(empty);
P(mutex);
/*送数据入缓冲区某单元*/
V(mutex);
V(full);}
{/*消费者*/
P(full);
P(mutex);
/*取缓冲区中某单元数据*/
V(mutex);
V(empty);}
}
说明：
（1）它是一个同步问题
（a）消费者想要接收一个数据时，有界缓冲区中至少有一个单元是满的；（b）生产者想要发送一个数据时，有界缓冲区至少有一个是空的。
（2）它是一个互斥问题
由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程必须互斥执行。
5、进程通讯
（1）进程通讯及分类
进程通讯是指进程间的信息交换。进程通讯方式大致分为三类：共享存储器、消息传递和管道。
（2）消息传递
消息传递方式分为直接通信方式和间接通讯方式两种，而一直接通讯方式的消息缓冲为基本的进程通讯方式。
（3）消息缓冲
发送进程直接将消息挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中得到消息。基本的有发送（send）消息和读取（read）消息两条原语。
（a）send 用于进程发送信息。
例如，甲进程向乙进程发送消息的过程如下：
1）甲进程在发送消息前，在本进程所占空间中开辟一发送区；
2）使用send原语send(A);
3）send程序向系统申请一个消息缓冲区，将发送区中消息正文、长度和发送进程名填入；
4）将缓冲区挂到接收消息的乙进程消息链链尾；
5）退出send，甲进程继续执行。
（b）read用于进程接收消息。
例如，乙进程读甲进程发送的消息的过程如下：
1）乙进程在接收消息前，在本进程所占空间中开辟一接收区；
2）使用read原语read(B);
3）read程序将乙进程消息链区中第一个消息缓冲区中的内容、长度、本消息发送者名字，填入接收区；
4）将缓冲区从消息链中摘除，释放缓冲区；
5）退出read程序，乙进程继续执行。
详见图6-3所示。
6．5 死锁
6．5．1 死锁的概念
死锁是两个或两个以上的进程中的每一个都在等待其中另一个进程释放资源而被封锁，它们都无法向前推进，这种现象称为死锁。如图6-h 6．5．2 死锁的四个必要条件
1、死锁的起因
死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所需要的该类资源数。显然，由于资源的有限性，我们不可能为所要求资源的进程无限制地提供资源。但是，我们可以采用适当的资源分配算法，以达到消除死锁的目的。
2、产生死锁的必要条件
（1）互斥使用：在一段时间内，一个资源只能由一个进程独占使用，若别的进程也要求该资源，则须等待直至其占用者释放；
（2）保持和等待：允许进程在不释放其已分得的资源的情况下请求并等待分配新的资源；
（3）非剥夺性：进程所获得的资源在未使用完之前，不能被其它进程强行夺走，而只能由其自行释放；
（4）循环等待：存在一个等待进程集合，P0正在等待一个P1占用的资源，P1正在等待一个P2占用的资源，……..Pn正在等待一个P0占用的资源。
3、关于死锁的进一步说明
（1）死锁是进程之间的一种特殊关系，是由资源竞争引起的僵局关系，因此，当我们提到死锁时，至少涉及到两个进程。虽然单个进程也可能锁住自己，但那是程序设计错误而不是死锁；
（2）当出现死锁时，首先要弄清楚被锁的是哪些进程，因竞争哪些资源被锁；
（3）在多数情况下，一系统出现死锁，是指系统内的一些而不是全部进程
被锁，它们是因竞争某些而不是全部资源而进入死锁的，若系统的全部进程都被锁住，我们称系统处于瘫痪状态；
（4）系统瘫痪意味着所有进程都进入了睡眠（阻塞）状态，但所有进程都睡眠了，如果其中至少有一个进程可由I/O中断唤醒的话，这并不一定就是瘫痪状态。
6．5．3 死锁的表示
1、死锁的表示
死锁可以用有向图来表示，有向图形成环路则形成死锁。例如，有
P1，P2两个进程，共享一台打印机资源R1和一台输入机R2，在工作使用时，共享资源被独占。死锁的有向示意图见图6-4
图6-4 死锁有向示意图
2、死锁定理
（1）如果不出现任何环，则此时系统内不存在死锁；
（2）如果出现了环，且处于此环中的每类资源均只有一个实体时，则有环就出现死锁，此时，环是系统存在死锁的充分必要条件；
（3）如果系统资源分配图中出现了环，但处于此环中的每类资源的个数不全为1，则环的存在只是产生死锁的必要条件而不是充分条件。6．5．4 解决死锁问题的基本方法
解决死锁的方法一般可分为预防、避免、检测与恢复等三种。
1、死锁预防
死锁预防的方法主要是打破造成死锁的四个必要条件中的一个，如允许进程同时访问某些资源，然而，这种方法不能解决访问那些不允许被同时访问的资源带来的死锁问题，比如打印机等。另一种方法则是打破资源的部分分配这个死锁产生的必要条件。即预先分配各并发进程所需要的全部资源。
另一种死锁的预防方法是打破死锁的环路条件。即把资源分类按顺序排列，使进程在申请、保持资源时不形成环路。如有M中资源，则列出
R1 2、死锁避免 （1）静态预先分配所有资源，又称为银行算法。即事先静态说明而后静态分配，破坏部分分配条件，但这种方法的资源利用率低。 （2）受控资源分配法：1969年由Haberman提出，分配资源前先检查会不会发生死锁，要求各进程说明所需资源，将资源分类，按不同策略分配，又称为静态说明动态分配。 3、死锁检测与恢复 死锁的检测算法当进程进行资源请求时检查并发进程组是否构成资源的请求和保持环路。有限状态转移图和petriNet等技术都可用来有效地判断死锁的发生。死锁的恢复办法很多。最简单的办法是终止各锁住进程，或按一定的顺序中止进程序列，直至已释放到有足够的资源来完成剩下的进程为止，另外，也可以从萡锁住进程强迫剥夺资源以解除死锁。 4、处理死锁的综合措施 Howard在1973年提出将解决死锁的基本方法组合起来，并对由不同类资源竞争所引起的死锁采用对它来说是最佳的方法来解决，以此来全面解决死锁问题。这一个思想是基于以下事实：系统内的全部资源可按层次分成若干类，对于每一类，可以使用最适合它的办法来解决死锁问题。由于使用了资源分层技术，在一个死锁环中，通常只包含某一层次的资源，每一个层次可以使用一种基本的方法。因此，整个系统就不会受控于死锁了。 （1）资源分类 资源可分为如下几类： （a）内部资源：由系统本身使用的资源，例如，进程控制块PCB； （b）主存储器：主要指用户态程序空间； （c）作业资源：可分配的设备（如磁带机）和文件； （d）交换空间：存放用户作业的后援存储器空间。 （2）解决死锁的综合措施 对内部资源通过破坏“循环等待”条件，即给资源以线性编序的方法预防死锁；对主存储器通过剥夺资源的办法以防止死锁的产生。因为一个进程总是可以被对换出去的，并且主存储器空间本质上是可以被剥夺的；对作业资源使用死锁避免算法，关于作业要求多少资源的信息可以从作业控制卡中获得；对交换空间可以采用预分配措施。因为存储空间的最大需求量通常是知道的。 6．6 重点小结 1、进程是操作系统中最为重要的概念之一，进程和程序的重要区别是其动 态性，进程是程序在并发系统的一次执行，它有一个从产生到消失的生命期。 2、进程控制是系统使用一些具有特定功能的程序段（原语）来创建、撤消进程及完成进程各状态（就绪、执行、等待）间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。掌握常用的进程调度算法。 3、进程同步和互斥是进程管理的重要内容，掌握同步和互斥的概念，并能利用信号量和P、V原语来实现进程间的互斥和同步。 4、了解进程通讯的几种方式，掌握消息缓冲的实现方式。 5、了解死锁的起因及解决死锁的基本方法。 考研操作系统-操作系统概念与历史 (总分：246.00，做题时间：90分钟) 一、填空题(总题数：12，分数：12.00) 1.在操作系统中，不可中断执行的操作称为 1。 填空项1:__________________ （正确答案：原语操作） 原语操作的英文名称为Atomic Operation，有时也称为原子操作。原子在很长时间内被人类认为是不可分割的最小粒子，因此它引申的意思为不可分割或不可中断。原语操作是操作系统提供并发的基础。 2.UNIX操作系统在结构上分为两个部分： 1和 2。 填空项1:__________________ （正确答案：外壳(Shell)） 填空项1:__________________ （正确答案：内核(Kernel)） 操作系统的实体通常称为内核，它包括操作系统的所有功能构件，如进程管理、内存管理、文件系统等。这些功能构件并不能直接被一般用户使用。为了方便用户使用操作系统，操作系统设计者还为操作系统覆盖了一层外壳，用户通过外壳与操作系统打交道。这个壳可以看成是操作系统的用户界面。 3.特权指令能在 1下执行，而不能在 2下执行。 填空项1:__________________ （正确答案：内核态(Kernel Mode)、用户态(user Mode)） 顾名思义，特权指令具有特权，这个特权就是对计算机资源的访问权力。与此相对的是非特权指令，此种指令不能随意访问计算机的资源。操作系统为了实现特权和非特权指令而设计了内核态和用户态。凡是在内核态下执行的指令都是特权指令，在用户态下执行的指令都是非特权指令。 4.操作系统向用户提供了两类接口：一类是 1，另一类是 2。 填空项1:__________________ （正确答案：命令级接口(command Interface)、程序级接口(Programming Interface)） 对操作系统的使用有两种方式：直接向操作系统发出命令；编程序调用操作系统服务。前一种接口是所谓的命令接口，通过操作系统的壳实现；后一种接口是程序接口，通过操作系统调用(System call)和程序语言库函数实现。 5.分时系统中 1是衡量分时系统性能的一项重要指标。 填空项1:__________________ （正确答案：响应时间(Response Time)） 响应时间指的是在提交任务后，等待系统做出回应的时间。在分时系统下，多个用户分时共享同一个系统。每个用户在用完自己的分时时间段后需要等待别的用户用完它们的分时时间段，这个等待就是用户对系统的最直观感受，等待时间越长，用户感受越差。 6.操作系统的主要功能是 1和 2。 填空项1:__________________ （正确答案：管理(Management)） 填空项1:__________________ （正确答案：魔幻(Illusion)） 管理指的是管理计算机的软硬件资源，如CPU、内存、磁盘、各种表格和数据结构、软件原语等，以保证这些资源在不同用户或程序之间合理分配和使用。魔幻指的是将少变多，难变易，丑变美，如将单CPU通过进程模型虚拟成多个CPU，将有限内存通过虚存变为容量巨大的逻辑内存。 7.在现代操作系统中，资源分配的单位是 1，而处理机调度的单位是 2。 填空项1:__________________ （正确答案：进程(Process)） 填空项1:__________________ （正确答案：线程(Thread)） 在操作系统早期，调度单位和资源分配单位均是进程。随着操作系统的发展，线程作为进程中的一个指令执行序列而成为调度的单位。在线程模型下，进程并不运行，系统执行的是线程。 8.在操作系统中，一种用空间换取时间的资源转换技术是 1。 填空项1:__________________ （正确答案：缓冲技术(Buffering)） 通过提供缓冲区(Buffer)，可以让速度慢的设备与速度快的设备进行沟通与协作。 9.为实现CPU与外部设备的并行工作，系统引入了 1硬件机制。 填空项1:__________________ （正确答案：中断(Interrupt)） 在中断机制下，CPU在发出10命令后即继续执行别的任务。外部设备在完成10后便通过中断告诉CPU，CPU 通过响应中断来处理外部设备的中断请求。 第5章输入输出设备管理 本章是操作系统的第四大功能，属于对硬件的管理。主要内容有：外部设备的分类及安装、输入输出设备的分配算法、外部设备和CPU 之间的数据传送控制方式（程序直接控制方式、中断控制方式、DMA 方式和通道方式）和设备驱动程序等。 5．1 概述 5．1．1设备管理的任务与功能 1．设备管理的任务 （1）按用户需求提出的要求接入外部设备； （2）尽量提高输入输出设备的利用率。如，发挥主机与外设以及外设之间的真正并行工作能力。 2．设备管理的功能 （1）分配设备 按设备的不同类型和操作系统选用的算法分配，包括分配相应的通道、设备控制器以及对未分配的任务或作业进行排队等。 （2）控制和实现真正的输入输出并行操作 包括通道程序控制、启动设备、及时响应及处理中断讯号等。（3）对输入输出缓冲区进行管理 如：逻辑名的管理，多个缓冲区的分时及串并行操作，同类多个外部设备的均衡工作。 （4）在一些较大系统中实现虚拟设备技术。 5．1．2 发展历史 计算机的基本输入输出设备的发展共经过了三代 （1）第一代：键盘和打印机； （2）第二代：鼠标和调制解调器； （3）第三代：手写笔和扫描仪等。 5．1．2外部设备的分类 在现代计算机系统中，除了CPU和内存（也叫主存储器）外，其它大部分硬件设备都可统称为外部设备。其中包括常用的输入输出设备、外存设备和终端设备等，还包括将外设和主机连接起来的通道（channel）和控制器（controller）。在计算机系统中，从不同角度将设备划分成不同的类型加以管理和调度，归类后简化了设备管理程序，管理工作的关键之一是“分类”和“记录”。 1．按用户和用户分类 （1）系统设备（一般是标准设备） 注：所附答案为个人整理，不是标准答案，仅供参考。 2009年计算机专业考研真题——OS 23.单处理机系统中，可并行的是（）。 I.进程与进程II.处理机与设备 III.处理机与通道IV.设备与设备 A.I、II和III B.I、 C.I、III和IV 24. A.时间片轮转调度算法 B. ） 26.分区分配内存管理方式的主要保护措施是（）。 A.界地址保护 B.程序代码保护 C.数据保护 D.栈保护 27.一个分段存储管理系统中，地址长度为32位，其中段号占8位，则段长最大是（）。 A.2的8次方字节 B.2的16次方字节 C.2的24次方字节 D.2的32次方字节 28.下列文件物理结构中，适合随机访问且易于文件扩展的是（）。 A.连续结构 B.索引结构 C.链式结构且磁盘块定长 D.链式结构且磁盘块变长 29.假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35，45，12，68，110，180，170，195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是（）。 A.110，170，180，195，68，45，35，12 B.110，68，45，35，12，170，180，195 C.110，170，180，195，12，35，45，68 D.12，35，45，68，110，170，180，195 30.文件系统中，文件访问控制信息存储的合理位置是（）。 A.文件控制块 B. C.用户口令表 D. 31.设文件F1的当前引用计数值为1F3，然后删除F1。此时，F2和F3 N（N>0）个单元的缓冲区。P1每次用produce（）生成一 P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。 46.（8分）请求分页管理系统中，假设某进程的页表内容如下表所示。 页号页框号有效位（存在位） 0 101H 1 1 -- 0 2 254H 1 页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设 第一章操作系统引论 操作系统的定义：是计算机系统中的一个系统软件，管理和控制计算机系统中的硬件和软件资源，合理的组织计算机的工作流程，以便有效利用这些资源为用户提供一个功能强大、使用方便的工作环境，从而在计算机与用户之间起到接口的作用。 1.1操作系统的目标与作用 1.目标：有效性、方便性、可扩充性、开放性 2.作用：a. OS作为用户与计算机硬件系统之间的接口；b. OS作为计算机系统资源的管理者；c. 实现了对计算机资源的抽象 3.操作系统为用户提供三种类型的使用接口：1.命令方式；2.系统调用方式；3.图形、窗口方式 1.2操作系统的发展过程 无操作系统的计算机系统、批处理系统（单道、多道）、分时系统、实时系统 1.单道批处理系统特征：自动性、顺序性、单道性。 多道批处理系统的优缺点：优点：资源利用率高、系统吞吐量大；缺点：平均周转时间长、无交互能力。 2.分时系统和实时系统的特征： 分时系统的特征：多路性、独立性、及时性、交互性、可靠性 实时系统的特征：实时性、可靠性、安全性 3.分时系统和实时系统的比较：a.及时性：实时信息处理系统对实时性的要求与分时系统类似都以人所能接受的等待时间来确定，但实时控制系统的及时性则是以控制对象所要求的开始截止时间或完成截止时间来确定的；b.交互性：实时信息系统虽然也具有交互性，但其交互性仅限于访问系统中某些特定的专用服务程序，不像分时系统能向终端用户提供数据处理和资源共享等服务；c.可靠性：分时系统虽然也要求系统可靠，但相比实时系统则要求系统具有高度的可靠性。 1.3操作系统的基本特性 基本特性：并发性、共享性、虚拟技术、异步性 1.4操作系统的主要功能 操作系统的主要任务：为多道程序的运行提供良好的运行环境，以保证多道程序能有条不紊的、高效的运行，并能最大程度的提高系统中各种资源的利用率和方便用户的使用。 主要功能：处理机管理（进程管理、进程同步、进程通信、处理机调度） 存储器管理（内存分配、内存保护、地址映射、内存扩充） 设备管理（设备管理、设备分配、设备处理、虚拟设备） 文件管理（文件存储空间的管理、目录管理、文件读/写管理和保护） 1.5操作系统与用户之间的接口： 1.用户接口：供用户组织和控制作业的执行和管理计算机系统； 2.程序接口：供编程人员使用操作系统提供的系统调用来请求操作系统提供服务。 1.6OS结构设计 1.操作系统结构：无结构OS、模块化结构OS、分层式结构OS、微内核结构OS 2.微内核技术：把操作系统中更多的成分和功能放到更高的层次（用户模式）中去运行，而留下一个 尽可能小的内核，用它来完成操作系统最基本的核心功能，称之为微内核技术。 补1.计算机操作系统的性能指标 系统可靠性、系统吞吐量、资源利用率、周转时间、可移植性、可扩展性 系统吞吐量：指系统在单位时间内处理的信息量；周转时间：指用户从提交作业到得到计算结果这段时间，又称系统响应时间。 补2.硬件将处理机划分为两种状态即管态和目态 1：操作系统的目标：提高资源利用率，提高系统吞吐量，使用户使用更方便，兼容新的计算机硬件和软件。 2：操作系统的作用：用户和计算机硬件之间的接口，使用户方便的操纵硬件，计算机系统的管理者，对计算机资源进行抽象。 3：计算机系统的发展：人工操作方式（穿孔卡片），单道批处理系统（每次只从磁盘中调入一个程序进内存），多道批处理系统（调入多个程序，CPU可以切换），分时操作系统（将一台主机给多个用户使用）实时操作系统（响应快，同时面对大量的远程终端）。 4：操作系统特点：并发，共享，虚拟（空分，时分），异步。5：操作系统的功能：CPU管理（进程控制，同步，通信，调度），存储器管理（内存分配，内存保护，地址映射，内存扩充）设备管理（缓冲管理，设备分配，设备处理）文件管理（存储管理，目录管理，读写保护管理）接口（用户接口管理，程序接口管理） 6：操作系统结构：模块化操作系统，分层式操作系统，C/S 操作系统（分布式），微内核结构（建立在前三者的基础上，微内核只提高“最基本”的服务，进程调度、进程间通信、存储管理、处理I/O设备。其他服务，如文件管理、网络支持等通过接口连到微内核，微内核具有良好的移植性）。 7：传统操作系统中，进程是资源分配和独立运行的基本单 位。 8：为了并发才引入进程。 9：进程控制块PCB：是一个记录型数据结构，记录了操作系统所需的用户描述进程的当前状况和控制进程运行的全部信息，使一个在多道环境环境下不能独立运行的程序成为一个可以独立运行的基本单位。系统创建一个进程的时候就要顺带着创建PCB，OS要调用一个进程的时候就要先查看PCB，系统将PCB组织成若干个链队列或索引表，PCB中有进程标识符，处理机状态，进程调度信息，进程控制信息等。10：进程的特性：动态，并发，独立（独立运行，独立分配资源，独立接受调度），异步（不可预知的速度前进）。11：进程的三种基本状态：就绪，阻塞，执行（就绪到执行到阻塞再回到就绪，执行可以直接回到就绪），此外还有挂起，创建，终止。 12：进程的创建：申请PCB，为新进程分配资源（子进程可以继承父进程，比如父进程打开的文件，和父进程的缓冲区等），初始化PCB，把新的进程插入队列。 13：进程的终止：找出PCB，读出进程状态，若进程在执行，就终止进程，若进程有子孙进程，还要把子进程终止。收回资源，移出PCB。 14：进程的阻塞：停止执行，PCB插入阻塞队列，CPU给另外一个就绪进程。 操作系统概念背诵 一、进程管理 1.进程管理的功能 ①进程控制 ②进程同步 ③进程通信 ④进程（线程）调度 2.程序顺序执行时的特征：顺序性、封闭性、可再现性。 3.程序并发执行时的特征：间断性、失去封闭性、不可再现性。 4.进程由程序段、数据段和进程控制块（PCB）组成。 5.进程的定义 ①进程是程序的一次执行。 ②进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 ③进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。 ④进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。 6.进程的基本特征：动态性、并发性、独立性、异步性、结构特征（程序＋数据＋PCB） 7.进程的状态 三态：就绪状态、运行状态、阻塞状态。 五态：活动就绪、静止就绪、活动阻塞、静止阻塞、运行。 8.进程控制块（PCB）的组成：进程标识符、处理机状态、进程调度信息、进程控制信息。 9.临界区：进程中访问临界资源的那段代码叫做临界区。 10.同步机制必须遵循的原则：空闲让进、忙则等待、有限等待、让权等待。 11.P,V操作的定义 P(S)：S=S?1； 若S≥0，则当前进程继续运行； 若S＜0，则将当前进程插入到S的等待队列中去。 V(S)：S=S+1； 若S＞0，则当前进程继续运行； 若S≤0，则从S的等待队列中移出一个进程放到就绪队列中去。 12.信号量的物理意义 S=?n时，表示有n个等待进入临界区的进程，当前已有进程在临界区中访问临界资源； S=0时，表示不允许任何进程进入临界区，当前已有进程在临界区中访问临界资源； S=n时，表示临界区是空闲的，该类资源的可用数目为n，可以有n个进程访问该类资源。 13.高级通信机制有：共享存储器系统、消息传递系统、管道通信系统。 14.线程的定义：线程是进程内的一个实体，是处理机调度的基本单位，是程序内部一个单一的顺序控 制流。 15.引入进程的目的：是为了使多个程序并发执行，提高资源利用率和系统吞吐量。 16.引入线程的目的：是为了减少程序并发执行时的时空开销，使操作系统具有更好的并发性。 17.进程的基本属性 名校操作系统考研试题与解答 10.1北京大学1997年考研操作系统试题 (一)名词术语解释(每小题5分,共30分) 1.进程状态 2.快表 3.目录项 4.系统调用 5.设备驱动程序 6.微内核 (二)填空(每小题1分,共10分) 1.如果系统中有n个进程,则在等待队列中进程的个数最多为________个。 2.在操作系统中,不可中断执行的操作称为_________。 3.如果系统中的所有作业是同时到达的,则使作业平均周转时间最短的作业调度是_________。 4.如果信号量的当前值为-4,则表示系统中在该信号量上有________个等待进程。 5.在有m个进程的系统中出现死锁时,死锁进程的个数k应该满足的条件是_________。 6.不让死锁发生的策略可以分为静态和动态两种,死锁避免属于_________。 7.在操作系统中,一种用空间换取时间的资源转换技术是_________。 8.为实现CPU与外部设备的并行工作,系统引入了__________硬件机制。 9.中断优先级是由硬件规定的,若要调整中断的响应次序可通过_________。 10.若使当前运行的进程总是优先级最高的进程,应选择________进程调度算法。 (三)问答题(每小题15分,共30分) 1.消息缓冲通信技术是一种高级通信机制,由Hansen首先提出。 (1)试述高级通信机制与低级通信机制P、V原语操作的主要区别。 (2)请给出消息缓冲机制(有界缓冲)的基本原理。 (3)消息缓冲通信机制(有界缓冲)中提供发送原语Send(receiver,a),调用参数a表示发送消息的内存区首地址,试设计相应的数据结构,并用P、V原语操作实现Send原语。 2.在虚拟段式存储系统中,引入了段的动态链接。 (1)试说明为什么引入段的动态链接。 (2)请给出动态链接的一种实现方法。 (四)(共10分) 在实现文件系统时,为加快文件目录的检索速度,可利用"文件控制块分解法"。假设目录文件存放在磁盘上,每个盘块为512字节。文件控制块占64字节,其中文件名占8字节。通常将文件控制块分解成两个部分,第一部分占10字节(包括文件名和文件内部号),第二部分占56字节(包括文件内部号和文件其他描述信息)。 (1)假设某一目录文件共有254个文件控制块,试分别给出采用分解法前和分解法后,查找该目录文件的某一个文件控制块的平均访问磁盘次数。 (2)一般地,若目录文件分解前占用n个盘块,分解后改用m个盘块存放文件名和文件内部号部分,请给出访问磁盘次数减少的条件。 (五)(共10分〉 设系统中有三种类型的资源(A、B、C)和五个进程(P1、P2、P3、P4、P5),A资源的数量为17,B 资源的数量为5,C资源的数量为20。在T0时刻系统状态如表1和表2所示。系统采用银行家算法实施死锁避免策略。 ①T0时刻是否为安全状态? 若是,请给出安全序列。 ②在T0时刻若进程P2请求资源(0,3,4),是否能实施资源分配? 为什么? ③在②的基础上,若进程P4请求资源(2,0,1),是否能实施资源分配? 为什么? 计算机操作系统考研真题计算机综合硕士 真题 一、选择题真题解析 4某系统采用改进型CLOCK置换算法，页表项中字段A为访问位，M为修改位。A＝0表示页最近没有被访问，A＝1表示页最近被访问过。M＝0表示页没有被修改过，M＝1表示页被修改过。按（A，M）所有可能的取值，将页分为四类：（0，0）、（1，0）、（0，1）和（1，1），则该算法淘汰页的次序为（）。[2016年408统考] A．（0，0），（0，1），（1，0），（1，1） B．（0，0），（1，0），（0，1），（1，1） C．（0，0），（0，1），（1，1），（1，0） D．（0，0），（1，1），（0，1），（1，0） 【答案】A ~ @ 【解析】使用改进型CLOCK置换算法淘汰页面时，其原理是： （1）首先扫描访问位为0，修改位为0的页； （2）若（1）中没有找到，则重新扫描，查找访问位为0，修改位为1的页，此过程中将被跳过页的访问位设为0； （3）若（2）依旧没找到，则开始重复（1）开始查找、若没有则继续（2）查找。 因此该算法首先置换（0，0）、（0，1），若都没找到，此时（1，0）、（1，1）被更改为（0，0）、（0，1）进行查找，所以最后该算法淘汰页的次序为（0，0），（0，1），（1，0），（1，1）。 45使用TSL(Test and Set Lock)指令实现进程互斥的伪代码如下所示。 do{ … whlie(TSL(&lock)); critical; section; lock=FALSE; …}while(TRUE);下列与该实现机制相关的叙述中，正确的是（）。[2016年408统考] A．退出临界区的进程负责唤醒阻塞态进程 B．等待进入临界区的进程不会主动放弃CPU C．上述伪代码满足“让权等待”的同步准则 D．while(TSL(&lock))语句应在关中断状态下执行 【答案】B ~ @ 【解析】A项，TSL指令作用的进程都是短进程，不会出现阻塞情况，退出临界区的进程不需要负责唤醒阻塞态进程；C项，TSL指令作用的进程属于忙则等待的类型，运行的进程等待资源时，进入临界区的进程并不会主动放弃CPU。让权等待是指当进程不能进入临界区时，应立即释放CPU，与忙则等待相反；D项，在中断处理中，TSL是多处理器下的进程并发问题，采用PSW关中断/开中断方式是单处理器下的进程并发问题，两者不是混用的，即 while(TSL(&lock))语句不需要在关中断状态下执行。 46某进程的段表内容如表1-6所示。 表1-6 一、单项选择题 1）访管指令所引起的中断属于（C ）中断。 A．外中断 B．I/O中断 C．软中断 D．程序中断 2）资源静态分配法破坏了死锁产生的（ B ）条件来预防死锁的发生。 A．互斥控制 B．保持和等待 C．不可剥夺控制 D．循环等待 3）虚拟存储的基础是程序局部性理论，它的基本含义是（ B ）。 A．代码的顺序执行 B．程序执行时对内存访问的不均匀性 C．变量的连续访问 D．指令的局部性 4）关于SPOOLING系统（ D ）的描述是错误的。 A．不需要独占设备 B．加快了作业执行的速度 C．使独占设备变成了共享设备 D．利用了处理器与通道并行工作的能力 5）设系统中有m个同类资源数，n为系统中的并发进程数，当n个进程共享m个互斥资源时，每个进程的最大需求数是w，试问下列情况下系统会死锁的是（ D ）。 A．m=4，n=3，w=2 B．m=2，n=2，w=1 C．m=5，n=2，w=3 D．m=4，n=3，w=3 6）文件系统中实现按名存取的功能是通过查找（ B ）来实现的。 A．磁盘空间 B．文件目录 C．磁盘控制器 D．位示图 7）下面的叙述中，（ D ）不是设备管理中引入缓冲机制的主要原因。 A．缓和CPU和I/O设备间的速度不匹配问题 B．减少对CPU的中断频率和放宽对CPU响应时间的限制 C．提高CPU和I/O设备间的并行性 D．节省系统内存 8）下列操作系统强调交互性的系统是（ B ）。 A．批处理系统 B．分时系统 C．实时系统 D．网络操作系统 9）响应比高者优先作业调度算法是通过计算时间和（ D ）来实现的。 A．输入时间 B．完成时间 C．周转时间 D．等待时间 10）在可变分区管理方案中，若采用“最佳适应”分配算法，通常将空闲区按（ A ）排列。 A．容量递增 B．容量递减 C．地址递增 D．地址递减 11）下面关于操作系统的叙述中正确的是（ C ）。 A．从响应时间的角度来看，实时系统与分时系统无本质差别 B．多道运行是现代操作系统的特征之一，它是指宏观和微观上都并行 C．操作系统的特征是并行性、共享性、虚拟性和不确定性 D．在分时系统中，响应时间≈时间片×用户数，因此只要时间片足够小其响应时间一定能改善。 12）在进程状态的转换中，（ B ）是不可能的。 A．运行状态→就绪状态 B．阻塞状态→运行状态 C．运行状态→阻塞状态 D．阻塞状态→就绪状态 13）设系统中有m个同类资源数，n为系统中的并发进程数，当n个进程共享m个互斥资源时，每个进程的最大需求数是w，试问下列情况下系统会死锁的是（ D ）。 A．m=4，n=3，w=2 B．m=2，n=2，w=1 C．m=5，n=2，w=3 D．m=4，n=3，w=3 14）在有m个进程的系统中有死锁出现时，死锁进程的个数k应该满足的条件是（ B ）。 A．1≤k≤m B．2≤k≤m C． k=m＝1 D．k和m没有关系 15）在有n个进程共享一个互斥段，如果最多允许m个进程(m 汤子瀛《计算机操作系统》考研4版2021考研复习 笔记 第1章操作系统引论 1.1 复习笔记 一、操作系统的目标和作用 1操作系统的目标 （1）方便性。 （2）有效性。 （3）可扩充性。 （4）开放性。 2操作系统的作用 （1）OS作为用户与计算机硬件系统之间的接口。 （2）OS作为计算机系统资源的管理者。 （3）OS实现了对计算机资源的抽象。 二、操作系统的发展过程 1未配置操作系统的计算机系统 （1）人工操作方式。 （2）脱机输入/输出方式。 2单道批处理系统 3多道批处理系统 多道批处理系统特征：多道、宏观上并行、微观上串行。 4分时系统 分时系统的特征：多路性、独立性、及时性、交互性。 5实时系统 （1）实时系统的类型 ①工业（武器）控制系统，如火炮的自动控制系统、飞机的自动驾驶系统，以及导弹的制导系统等。 ②信息查询系统，如飞机或火车的订票系统等。 ③多媒体系统。 ④嵌入式系统。 （2）实时系统最主要的特征便是及时性与可靠性。 6微机操作系统的发展 微机操作系统按运行方式分为以下几类： （1）单用户单任务操作系统。 （2）单用户多任务操作系统。 （3）多用户多任务操作系统。 三、操作系统的基本特性 1并发（Concurrence） 区分并行与并发 （1）并行性是指两个或多个事件在同一时刻发生； （2）并发性是指两个或多个事件在同一时间间隔内发生。 2共享（Sharing） 目前实现资源共享的主要方式有以下两种： （1）互斥共享方式。 （2）同时访问方式。 3虚拟（Virtual） 4异步（Asynchronism） 并发和共享是多用户（多任务）OS的两个最基本的特征。 四、操作系统的主要功能 1处理机管理功能 对处理机的管理可归结为对进程的管理。处理机管理的主要功能有：（1）进程控制。 （2）进程同步。 （3）进程通信。 （4）调度。 2存储器管理功能 （1）内存分配。 （2）内存保护。 （3）地址映射。 （4）内存扩充。 3设备管理功能 （1）缓冲管理。 （2）设备分配。 （3）设备处理。 4文件管理功能 （1）文件存储空间的管理。 2010年统考计算机考研真题 一、单项选择题：1-40题，每题20分共80分。 1、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（） A、dcebfa B、cbdaef C、bcaefd D、afedcb 2、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺顺序是（） A、bacde B、dbace C、dbcae D、ecbad 3、下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（） 4、在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中， 关键字37所在结点的左、右子结点中保存的关键字分别是（） A、13，48 B、24，48 C、24，53 D、24，90 5、在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（） A、41 B、82 C、113 D、122 6、对n（n>=2）个权值均不相同的字符构成哈弗曼树，关于该树的叙述中，错误的是（） A、该树一定是一棵完全二交叉 B、树中一定没有度为1的结点 C、树中两个权值最小的结点一定是兄弟结点 D、树中任一非叶结点的权值一定不小于下一层任一结点的权值 7、若无向图G=（V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（） A、6 B、15 C、16 D、21 8、对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（） A、4 B、3 C、2 D、1 9、已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（） A、4 B、5 C、6 D、7 10、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（） A、递归次数于初始数据的排列次数无关 23.下列关于批处理系统的叙述中,正确的是 I.批处理系统允许多个用户与计算机直接交互 Ⅱ批处理系统分为单道批处理系统和多道批处理系统 Ⅲ.中断技术使得多道批处理系统的Io设备可与CPU并行工作 A.仅Ⅱ、Ⅲ B.仅Ⅱ C.仅1、Ⅱ D.仅1、Ⅲ 24.某单CPU系统中有输入和输出设备各1台,现有3个并发执行的作业,每个作业的输入计算和输出时间均分别为2ms、3ms和4ms,且都按输入、计算和输出的顺序执行,则执行完3个作业需要的时间最少是 A. 15 ms B. 17ms C. 22 ms D. 27 ms 25.系统中有3个不同的临界资源R1、R2和R3,被4个进程p1、p2、p3及p4共享。各进程对资源的需求为:p1申请R1和R2,p2申请R2和R3,p3申请R1和R3,p4申请R2。若系统出现死锁,则处于死锁状态的进程数至少是 A 1 B.2C.3D.4 26.某系统采用改进型CLOCK置换算法,页表项中字段A为访问位,M为修改位。A=0表示页最近没有被访问,A=1表示页最近被访问过。M=0表示页没有被修改过,M=1表示页被修改过。按(A,M)所有可能的取值,将页分为四类:(0,0)、(1,0)、(0,1)和(1,1),则该算法淘汰页的次序为 A.(0,0),(0,1),(1,0),(1,1) B.(0,0),(1,0),(0,1),(1,1) C.(0,0),(0,1),(1,1),(1,0) D.(0,0),(1,1),(0,1),(1,0) 27.使用TSL( Test and Set Lock)指令实现进程互斥的伪代码如下所示 while(Tsl(&lock)) critical section: lock=false } while(TRUE): 下列与该实现机制相关的叙述中,正确的是 A.退出临界区的进程负责唤醒阻塞态进程 B.等待进入临界区的进程不会主动放弃CPU C.上述伪代码满足“让权等待”的同步准则 D, while(TSL(&lock))语句应在关中断状态下执行 28.某进程的段表内容如下所示 段号段长内存起始地址权限状态 0 100 6000只读在内存 1 200 空读写不在内存 2 300 4000读写在内存 当访问段号为2、段内地址为400的逻辑地址时,进行地址转换的结果是 A.段缺失异常 B.得到内存地址4400 C.越权异常 D.越界异常 29.某进程访问页面的序列如下所示 若工作集的窗口大小为6,则在￡时刻的工作集为 考研操作系统-死锁 (总分：62.00，做题时间：90分钟) 一、单项选择题(总题数：8，分数：16.00) 1.以下关于资源分配图的描述中正确的是( )。 A.有向边包括进程指向资源类的分配边和资源类指向进程申请边两类 B.矩阵框表示进程，其中的圆点表示申请同一类资源的各个进程 C.圆圈结点表示资源类 D.资源分配图是一个有向图，用于表示某时刻系统资源与进程之间的状态√ 2.以下关于死锁的叙述中正确的是( )。 A.死锁的出现只与资源的分配策略有关 B.死锁的出现只与并发进程的执行速度有关 C.死锁是系统的一种僵持状态，任何进程无法继续运行 D.进程竞争互斥资源是产生死锁的根本原因√ 3.用银行家算法避免死锁时，检测到( )时才分配资源。 A.进程已占用的资源数与本次申请的资源数之和不超过对资源的最大需求量，且现存资源能满足本次申请量，但不能满足尚需要的最大资源量 B.进程首次申请资源时对资源的最大需求量超过系统现存的资源量 C.进程已占用的资源数与本次申请的资源数之和不超过对资源的最大需求量，且现存资源能满足尚需要的最大资源量√ D.进程已占用的资源数与本次申请的资源数之和超过对资源的最大需求量 4.通过终止进程或抢夺资源可以解除死锁，下面说法中错误的是( )。 A.一次终止一个进程比终止所有涉及死锁进程的耗费大√ B.检测死锁适用于不经常发生死锁的系统中，不适用于经常发生死锁的系统中 C.终止进程可以终止涉及死锁的所有进程或一次终止一个进程 D.抢夺资源时从执行时间短的进程中抢夺可以避免进程“死”现象 5.死锁的4个必要条件中，无法破坏的是( )。 A.环路等待资源 B.互斥使用资源√ C.占有且等待资源 D.非抢夺式分配 6.静态分配破坏了( )两个死锁的必要条件。 A.占有且等待资源和环路等待资源√ B.互斥使用资源和非抢夺式分配 C.占有且等待资源和互斥使用资源 D.环路等待资源和互斥使用资源 7.死锁的防止是根据( )采取措施实现的。 A.防止系统进入不安全状态 B.配置足够的系统资源 C.破坏产生死锁的四个必要条件之一√ D.使进程的推进顺序合法 8.按序分配资源是为了( )。 A.死锁的检测 B.死锁的防√ C.死锁的避免 D.死锁的解除 二、填空题(总题数：12，分数：12.00) 第七章操作系统结构和程序设计 7．1 操作系统的编程概念 1、操作系统编程的发展 在九十年代以前，程序员的精力集中于完成任务的过程，而不是用户与该过程的交互方式，过去评价一个软件的好坏往往是注意源程序的短小精悍和执行的快速性。快速的、清晰的编程是许多程序员努力要达到的理想境界。Windows操作系统将用户与计算机的交互方式的设计（即人机界面设计）放到了非常重要的位置。同时，Windows为不同形式的高层次交互提供了相应的机制：应用程序之间、操作系统和应用程序之间、公共的共享代码库和数据库之间。 2、编程语言简史 （1）机器语言：以二进制代码“0”、“1”组成的机器指令集合； （2）汇编（Assembler）语言：以助记符表示机器指令功能，例如，JOVIAL、forth； （3）高级语言：接近人类语言（英语）和数学语言的计算机语言，例如，BASIC、FORTRAN、Pascal、C、FoxBASE、ORACLE等； （4）进程（Process）概念:例如，UNIX Shell、TCL、PERL和Marvel等； （5）面向对象的语言：例如C++、Visual BASIC、java等； （6）新范例计算机语言：例如ML、Smalltalk、Eiffel等； 3、不同应用领域的计算机语言 （1）科学研究： 例如:FORTRAN、ALGOL、BASIC、APL、Pascal、C、C++、AUTOCAD等； （2）商业： 例如：COBOL、C、PL/I、4GLs、和spreadsheet等； （3）系统： 例如：Assembler、JOVIAL、Forth、C、C++、Ada、java等； （4）出版： 例如：TeX、Postscript、word、WPS、和processing等； （5）人工智能（AI，artificial intelligence）： 例如：LISP、SNOBOL和Prolog等。 7．2 结构设计的目标 计算机操作系统一般都有两种运行状态，即用户态（user mode）和核心态（kernel mode）。计算机操作系统的结构设计一般包括内结构和外结构两种结构。传统操作系统内结构是指内部程序模块的层次结构，每一层由若干数量不等的程序模块组成。例如，早期的UNIX操作系统版本，如图7-1所示。 《计算机操作系统》考研第4版考研复习与考点第1章操作系统引论 1.1 复习笔记 一、操作系统的目标和作用 1操作系统的目标 （1）方便性。 （2）有效性。 （3）可扩充性。 （4）开放性。 2操作系统的作用 （1）OS作为用户与计算机硬件系统之间的接口。 （2）OS作为计算机系统资源的管理者。 （3）OS实现了对计算机资源的抽象。 二、操作系统的发展过程 1未配置操作系统的计算机系统 （1）人工操作方式。 （2）脱机输入/输出方式。 2单道批处理系统 3多道批处理系统 多道批处理系统特征：多道、宏观上并行、微观上串行。 4分时系统 分时系统的特征：多路性、独立性、及时性、交互性。 5实时系统 （1）实时系统的类型 ①工业（武器）控制系统，如火炮的自动控制系统、飞机的自动驾驶系统，以及导弹的制导系统等。 ②信息查询系统，如飞机或火车的订票系统等。 ③多媒体系统。 ④嵌入式系统。 （2）实时系统最主要的特征便是及时性与可靠性。 6微机操作系统的发展 微机操作系统按运行方式分为以下几类： （1）单用户单任务操作系统。 （2）单用户多任务操作系统。 （3）多用户多任务操作系统。 三、操作系统的基本特性 1并发（Concurrence） 区分并行与并发 （1）并行性是指两个或多个事件在同一时刻发生； （2）并发性是指两个或多个事件在同一时间间隔内发生。 2共享（Sharing） 目前实现资源共享的主要方式有以下两种： （1）互斥共享方式。 （2）同时访问方式。 3虚拟（Virtual） 4异步（Asynchronism） 并发和共享是多用户（多任务）OS的两个最基本的特征。 四、操作系统的主要功能 1处理机管理功能 对处理机的管理可归结为对进程的管理。处理机管理的主要功能有：（1）进程控制。 （2）进程同步。 （3）进程通信。 （4）调度。 2存储器管理功能 （1）内存分配。 （2）内存保护。 （3）地址映射。 （4）内存扩充。 3设备管理功能 （1）缓冲管理。 （2）设备分配。 （3）设备处理。 4文件管理功能 （1）文件存储空间的管理。 （2）目录管理。 2021年计算机考研《计算机操作系统》考研历年真 题 第一部分考研真题精选 一、选择题 1下列关于线程的描述中，错误的是（）。[2019年408统考] A．内核级线程的调度由操作系统完成 B．操作系统为每个用户级线程建立一个线程控制块 C．用户级线程间的切换比内核级线程间的切换效率高 D．用户级线程可以在不支持内核级线程的操作系统上实现 【答案】B查看答案 【解析】用户级线程仅存在于用户空间中，与内核无关，其线程库对用户线程的调度算法与OS的调度算法无关，不需要操作系统为每个用户级线程建立一个线程控制块。 2下列选项中，可能将进程唤醒的事件是（）。[2019年408统考] Ⅰ．I/O结束 Ⅱ．某进程退出临界区 Ⅲ．当前进程的时间片用完 A．仅Ⅰ B．仅Ⅲ C．仅Ⅰ、Ⅱ D．Ⅰ、Ⅱ、Ⅲ 【答案】C查看答案 【解析】可能唤醒进程的事件包括I/O结束、某进程退出临界区等。当前进程的时间片用完会引起另一个进程的调度并运行，不是唤醒进程。 3下列关于系统调用的叙述中，正确的是（）。[2019年408统考] Ⅰ．在执行系统调用服务程序的过程中，CPU处于内核态 Ⅱ．操作系统通过提供系统调用避免用户程序直接访问外设 Ⅲ．不同的操作系统为应用程序提供了统一的系统调用接口 Ⅳ．系统调用是操作系统内核为应用程序提供服务的接口 A．仅Ⅰ、Ⅳ B．仅Ⅱ、Ⅲ C．仅Ⅰ、Ⅱ、Ⅳ D．仅Ⅰ、Ⅲ、Ⅳ 【答案】C查看答案 【解析】系统调用接口是连接操作系统和应用程序的桥梁，而接口是以具体程序中的函数实现的，称之为系统调用，在不同的操作系统中，具有不同的系统调用，但是它们实现的功能是基本相同的。 4下列选项中，可用于文件系统管理空闲磁盘块的数据结构是（）。[2019年408统考] Ⅰ．位图 Ⅱ．索引节点 Ⅲ．空闲磁盘块链 Ⅳ．文件分配表（FAT） A．仅Ⅰ、Ⅱ 考研操作系统-11 (总分：90.00，做题时间：90分钟) 一、单项选择题(总题数：5，分数：7.00) 1.在固定分区，可变分区，页式管理，段式管理，段页式管理，虚拟页式管理，虚拟段式管理和虚拟段页式中，同时需要设置段表和页表的存储管理方法的个数是( )。 A．2 B．3 C．4 D．5 （分数：2.00） A. B. √ C. D. 解析： 2.______不是设计实时操作系统主要的追求目标。 A．安全可靠 B．资源利用率 C．及时响应 D．快速处理 （分数：1.00） A. B. √ C. D. 解析：[解析] 实时系统最主要的特征就是快速的处理能力，适应这种实时性的要求。实时系统在设计时力求简单而实用。一般的实时操作系统都拥有高精度的实时时钟；具有快速的中断响应和中断处理能力；支持多道程序设计，任务调度算法简单实用，数据结构简洁明了，任务切换速度快，能够处理时间驱动的任务(周期性任务)和事件驱动的任务；可靠性高；具有较强的系统再生能力。 3.逻辑文件可以有流式文件和______这两种形式。 A．目录文件 B．永久文件 C．记录式文件 D．文本文件 （分数：1.00） A. B. C. √ D. 解析：[解析] 逻辑文件可以有两种形式，一种是流式文件，另一种是记录式文件。流式文件是指对文件内的信息不再划分单位，是依次的一串信息组成的。记录式文件是指用户还可把信息按逻辑上独立的涵义划分信息单位，每个单位称为一个逻辑记录(简称记录)，如数据库文件就是一种记录式文件。 4.UNIX操作系统是著名的______。 A．多道批处理系统 B．分时系统 C．实时系统 D．分布式系统 （分数：1.00）考研操作系统-操作系统概念与历史
计算机操作系统考研讲义
2009-2015计算机操作系统考研真题
考研计算机操作系统学习笔记
(考研复试)操作系统笔记
考研_计算机_操作系统_操作系统概念总结
名校操作系统历年考研试题(含解答)
计算机操作系统考研真题计算机综合硕士真题
考研学生复习资料操作系统Word版
汤子瀛《计算机操作系统》考研4版2021考研复习笔记
2010操作系统考研
2016计算机考研408统考操作系统真题及答案word版本
考研操作系统-死锁
计算机操作系统考研讲义(7)
《计算机操作系统》考研第4版考研复习与考点
2021年计算机考研《计算机操作系统》考研历年真题
考研操作系统-11
相关主题
文本预览