计算机学科专业基础综合计算机操作系统-8
(总分：99.99，做题时间：90分钟)
一、综合应用题(总题数：25，分数：100.00)
1.A和B两个程序，程序A顺序执行情况如下：计算20s，使用设备10s，计算10s，使用设备20s，计算10s；程序B顺序执行情况如下：使用设备20s，计算20s，使用设备10s，计算10s，使用设备20s。比较单道和多道程序(不考虑管理开销，设备和CPU都必须互斥使用)情况下CPU和设备各自的利用率是多少? （分数：4.00）
__________________________________________________________________________________________ 单道程序情况下，CPU和设备利用率均为（分数：4.00）
__________________________________________________________________________________________ 内核支持线程是在内核支持下实现的，即每个线程的线程控制块设置在内核中，所有对线程的操作(如创建、撤销和切换等)，都是通过系统功能调用由内核中的相应处理程序完成。而用户级线程仅存在于用户空间中，即每个线程的控制块设置在用户空间中，所有对线程的操作也在用户空间中完成，而无需内核的帮助。 可从以下几个方面比较内核支持线程和用户级线程：
(1)内核支持。用户级线程可在一个不支持线程的OS中实现，而内核支持线程则不然，它需要得到OS内核的支持。
(2)处理器的分配。在多处理机环境下，对纯粹的用户级线程来说，内核一次只为一个进程分配一个处理机，即进程无法享用多处理机带来的好处。而在设置有内核支持线程时，内核可调度一个应用中的多个线程同时在多个处理机上并行运行，从而提高程序的执行速度和效率。
(3)调度和线程执行时间。对设置有内核支持线程的系统，其调度方式和算法与进程的调度相似，只不过调度的单位是线程。而对只设置了用户级线程的系统，调度的单位则仍为进程。因此，在条件相同的情况下，内核支持的线程通常比用户级线程得到更多的CPU执行时间。
(4)切换速度。用户级线程的切换，通常发生在一个应用程序的多个线程之间，由于不需陷入内核，而且切换的规则也相当简单，因此切换速度比内核支持线程至少快一个数量级。
(5)系统调用。在典型的OS中，许多系统调用都会引起阻塞。当一个用户级线程执行这些系统调用时，被阻塞的将是整个进程。而当一个内核支持线程执行这些系统调用时，内核只阻塞这个线程，但仍可调度其所属进程的其他线程执行。
3.什么是线程?进程和线程是什么关系? （分数：4.00）
__________________________________________________________________________________________ 线程可定义为进程内的一个执行单位，或者定义为进程内的一个可调度的实体。
在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。一个进程可以有多个线程，而且至少有一个可执行的线程。 进程和线程的关系是：
(1)线程是进程的一个组成部分；
(2)进程的多线程都在进程的地址空间活动；
(3)资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源配额中扣除并分配给它；
(4)处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程； (5)线程在执行过程中，需要同步。
4.进程和程序之间可以形成一对一、一对多、多对一、多对多的关系，请分别举例说明在什么情况下会形成这样的关系。 （分数：4.00）
__________________________________________________________________________________________
多道程序情况下，CPU和设备利用率均为 2.什么是内核支持线程和用户级线程?并对它们进行比较。
执行一条命令或一个应用程序时，进程和程序之间形成一对一的关系；进程在执行过程中可以加载执行不同的应用程序，从而形成一对多的关系；当以不同的参数或数据多次执行同一个应用程序时，形成多对一的关系；当并发地执行不同的应用程序时，形成多对多的关系。 [解析] 从进程的概念、进程与程序之间的关系来考虑问题的解答。进程是程序的执行过程，进程代表执行中的程序，因此进程与程序的差别就隐含在“执行”之中。程序是静态的指令集合，进程是程序的动态执行过程。静态的程序除占用磁盘空间外，不需要其他系统资源，只有执行中的进程才需要分配内存、CPU等系统资源。 进程的定义说明了两点：
(1)进程与程序相关，进程包含了程序。程序是进程的核心内容，没有程序就没有进程。
(2)进程不仅仅是程序，还包含了程序在执行过程中使用的全部资源，没有资源程序就无法执行，因此。进程是执行程序的载体。
当运行一个程序时，操作系统首先要创建一个进程，为进程分配内存等资源，然后将程序加载到进程中执行。就单个进程某个时刻而言，一个进程只能执行一个程序，进程和程序之间是一对一的关系。但从整个系统中的进程集合以及进程的生命周期而言，进程和程序之间可以形成一对一、一对多、多对一、多对多的关系。
5.为什么进程之间的通信必须借助于操作系统内核功能?简单说明进程通信的几种主要方式。 （分数：4.00）
__________________________________________________________________________________________ 每个进程有自己独立的地址空间。在操作系统和硬件的地址保护机制下，进程无法访问其他进程的地址空间，所以必须借助于操作系统的系统调用函数实现进程之间的通信。进程通信的主要方式有：
(1)共享内存区：通过系统调用创建共享内存区。多个进程可以(通过系统调用)连接同一个共享内存区，通过访问共享内存区实现进程之间的数据交换。使用共享内存区时需要利用信号量解决同步互斥问题。 (2)消息传递：通过发送/接收消息系统调用实现进程之间的通信。当进程发送消息时，系统将消息从用户缓冲区拷贝到内核中的消息缓冲区中，然后将消息缓冲区挂入消息队列中。进程发送的消息保持在消息队列中直到被另一进程接收。当进程接收消息时，系统从消息队列中解挂消息缓冲区，将消息从内核的消息缓冲区中拷贝到用户缓冲区，然后释放消息缓冲区。
(3)管道通信：管道是一个先进先出(FIFO)的信息流，允许多个进程向管道写入数据，允许多个进程从管道读出数据。在读/写过程中，操作系统保证数据的写入顺序与读出顺序是一致的。进程通过读/写管道文件或管道设备实现彼此之间的通信。
(4)共享文件：利用操作系统提供的文件共享功能实现进程之间的通信。这时，也需要利用信号量解决文件共享操作中的同步互斥问题。 [解析] 在操作系统中，进程是竞争和分配计算机系统资源的基本单位。每个进程有自己独立的地址空间。为了保证多个进程能够彼此互不干扰地共享物理内存，操作系统利用硬件地址机制对进程的地址空间进行了严格的保护，限制每个进程只能访问自己的地址空间。 6.线程和进程有什么区别?举例说明它们分别适用的系统环境。 （分数：4.00）
__________________________________________________________________________________________ 进程是程序的执行过程，是竞争和分配计算机系统资源的基本单位。线程是进程中的一个程序执行单元。一个进程可以包含多个线程，进程中的程序可以由多个线程并发地执行，因此线程是进程中的并发执行机制。进程中的多个线程共享进程的地址空间和其他资源。线程和进程之间的最大区别是它们的运行、管理和通信开销。创建进程需要建立进程的地址空间，而线程不需要，因为它共享进程的地址空间。在处理机调度过程中，进程切换包括切换CPU执行现场和进程地址空间，而同一进程下的线程切换只需要切换CPU执行现场。由于共享进程的地址空间，同一进程下的线程之间可以直接进行数据交换，不需要调用操作系统的内核通信函数。
多线程并行程序适用于共享存储结构的多处理机系统(SMP)，因为这类系统能够很好地支持线程对进程地址空间和资源的物理共享，而多进程并行程序适用于松散耦合的多处理机系统。 [解析] 需要了解和掌握线程、进程的基本概念以及它们之间的关系。操作系统为了支持多道程序的运行和管理，引入了进程概念和进程管理机制。为了加快应用程序的执行速度，提出了并行程序的设计思想。将一个大的应用程序或大作业分解成若干个能够并行处理的子任务，由执行主程序的进程创建多个子进程，每个子进程执行一个子任务。利用进程的并发性，使得多个子进程的I/O过程与CPU计算过程相互重叠，从而提高处理机利用率，加快应用程序的运行速度。
在多处理机系统中，为了进一步提高并行程序的运行效率。引入了线程概念和线程管理机制。线程是进程中的一个程序执行单元。线程包含CPU执行线程和执行堆栈，可以独立地执行程序。进程中的程序可以由多个线程并发地执行，进程中的多个线程共享进程的地址空间和其他资源，包括程序、数据、文件、通信端口等。正是由于线程对进程的地址空间和资源的共享，明显地减少了并行开销(包括线程创建、切换和通信)，非常有利于并行程序的开发和运行。 7.下面的进程状态转换可能发生吗?为什么? ①阻塞→运行；②就绪→阻塞；③就绪→退出。 （分数：4.00）
__________________________________________________________________________________________ 阻塞到运行状态是不可能的，因为必须经就绪状态；就绪到阻塞状态是不可能的；就绪到退出状态也是不可能的，中间必须经过执行状态。
8.Windows XP采用了动态优先级的调度算法对下面的进程的优先级进行提高。试分析这样做的原因和结果，由此说明Windows XP的调度策略。 ●完成I/O操作的进程； ●信号量或事件等待结束的进程； ●前台进程(线程)完成一个等待操作； ●由于窗口活动而被唤醒的应用程序进程； ●进程(线程)在就绪队列中的等待时间过长。 （分数：4.00）
__________________________________________________________________________________________ 第1种情况是因为进程完成I/O后，需要提高优先级，这是一种照顾I/O为主进程的策略；后4种情况均是因为它们长时间没有得到运行的机会，需要提高优先级，这是一种典型的动态优先级策略。 9.实现多进程并行程序的好处是什么?多线程并行程序对于多进程并行程序有哪些优势?原因是什么? （分数：4.00）
__________________________________________________________________________________________ 线程并行相对于进程并行可以降低上下文的切换开销。
10.为什么说ULT不能实现在多个CPU上的真正并行，而混合实现线程则可以? （分数：4.00）
__________________________________________________________________________________________ 多CPU的调度依赖于操作系统内核的调度，而ULT不能影响操作系统的调度策略，因此不能实现真正的并行。
11.在多处埋机调度中，为什么需要让进程中的多个线程同时被调度执行? （分数：4.00）
__________________________________________________________________________________________ 提高并行执行的程度。
12.设系统中有下述解决死锁的办法： ●银行家算法；
●检测死锁，终止处于死锁状态的进程，释放该进程所占有的资源； ●资源预分配。
简述哪种办法允许最大的并发性，也即哪种办法允许更多的进程无等待地向前推进?请按“并发性”从大到小的顺序对上述3种办法进行排序。 （分数：4.00）
__________________________________________________________________________________________ 死锁检测方法可以获得最大并发性。并发性排序：死锁检测方法、银行家算法、资源预分配法。 13.什么是饥饿?死锁和饥饿的主要差别是什么? （分数：4.00）
__________________________________________________________________________________________
饥饿是系统并没有死锁，但至少有一个进程被无限期地推迟的现象。饥饿不同于死锁。死锁是这样一种情形：其中某进程正等待一个绝不会发生的事件；而饥饿现象是指某进程正等待这样一个事件：它发生了但总是受到其他进程的影响，以致一直轮不到(或很难轮到)该进程。
14.假设某操作系统采用RR调度策略，分配给A类进程的时间片为100ms，分配给B类进程的时间片为400ms，就绪进程队列的平均长度为5(包括正在运行的进程)，其中A类进程有4个，B类进程有1个，所有进程的平均服务时间为2s，问A类进程和B类进程的平均周转时间各为多少?(不考虑I/O情况)。 （分数：4.00）
__________________________________________________________________________________________ 因为就像进程队列的平均长度为5，单个RR调度循环周期的时间为： 4×100+1×400=800(ms)
A类进程需要20个时间片的执行时间，B类进程需要5个时间片的执行时间(1s=1000ms)。A类进程的平均周转时间为：20×0.8=16(s)
B类进程的平均周转时间为：5×0.8=4(s) [解析] 时间片轮转调度(RR)是轮流地调度就绪队列中的每个进程，进程每次占用CPU的时间长度限制为时间片的大小。当采用固定的时间片大小时，每个进程按照固定周期被循环地执行。所以，进程的执行速度是由该进程的时间片大小在一个循环周期中所占的比例决定的，比例越高，进程的相对执行速度就越快。
15.某多道程序设计系统中配有一台处理器CPU和两台输入/输出设备IO 1 、IO 2 ，现有优先级由高到低的3个进程P 1 、P 2 、P 3 同时存在，它们使用资源的先后顺序和占用时间分别是： 进程P 1 ：IO 2 (30ms)，CPU(10ms)，IO 1 (30ms)，CPU(10ms)，IO 2 (10ms)。 进程P 2 ：IO 2 (20ms)，CPU(20ms)，IO 1 (40ms)。 进程P 3 ：CPU(30ms)，IO 2 (20ms)。
若进程调度采用“可抢占的最高优先级”调度算法，且忽略调度等所需的时间，请回答下列问题： (1)进程P 1 、P 2 、P 3 从开始到完成所用的时间分别是多少?(要求用坐标画出进程P 1 、P 2 、P 3 的工作过程，其中横坐标表示时间，纵坐标表示CPU和I/O设备)。
(2)这三个进程从开始到全部完成时CPU的利用率为多少?IO 1 、IO 2 的利用率为多少? （分数：4.00）
__________________________________________________________________________________________ 根据“可抢占的最高优先级”调度算法画出进程P1、P2、P3的工作过程。(如下图所示)
进程P1、P2、P3
进程P 1 、P 2 、P 3 从开始到完成所用的时间分别是90ms、110ms、80ms。这三个进程从开始到全部完成时的时间为110ms，在此期间内： CPU的利用率=(30+20+10+10)÷110=63.3% IO 1 的利用率=(20+30+40)÷110=81.8%
IO 2 的利用率=(30+20+10)÷110=54.5% [解析] 在“可抢占的最高优先级”调度中，任何时刻内核都将处理机分配给当前最高优先级的就绪进程。也就是说，只有当高优先级进程主动放弃CPU时，低优先级进程才有机会运行，并且，一旦高优先级进程需要使用CPU时，内核就会剥夺低优先级进程的CPU，分配给它使用。
在本题中，由于进程P 1 和P 2 在开始执行时先需要进行I/O，所以最低优先级的进程P 3 获得了CPU。但是，P 3 运行了20ms后就被P 2 抢占了CPU，因为P 2 刚好完成了I/O，并且P 2 的优先级大于P 3 。同样的原因，P 2 运行了10ms后，就被P 1 抢占了CPU。P 1 在CPU上运行10ms之后再次需要进行I/O而放弃CPU，于是，P 2 、P 1 获得继续运行的机会。以此方式，P 1 、P 2 和P 3 相继完成自己的运行过程。 16.许多操作系统采用动态优先级调度算法，即当一个“阻塞”进程变成“就绪”时提高该进程的优先级。为什么采用这种方法? （分数：4.00）
__________________________________________________________________________________________ 进程进入“阻塞”状态，是因为进程需要等待某种资源。当进程获得资源时，进程被唤醒，变成“就绪”状态。这时提高该进程的优先级可以使进程尽快地完成慢速设备的I/O过程。这样，一方面提高了I/O设备的利用率，另一方面，设备的I/O活动能够与CPU执行其他进程的计算工作充分地并行，从而提高整个
系统的性能。[解析] 在操作系统中，多个进程共享系统的资源必然发生资源的竞争。进程在运行过程中，如果需要使用的资源(如I/O设备)正被其他进程占用，该进程就会进入“阻塞”状态，等待资源的释放。如果某种资源的使用时间比较长(例如慢速的I/O设备)，就会发生许多进程等待该资源的情况，而CPU时常处于空闲状态。这时，慢速的I/O设备成为阻碍系统性能的瓶颈。提高设备的利用率和提高设备与CPU的并行度是解决瓶颈问题的方法之一。
17.论述一下解决双进程临界区问题的软件算法是错误的。 Process P0: do {
flag[0]=true; ① while(flag[1]); ③ 临界区 Flag[0]=false; } while(1); Process P1: do {
flag[1]=true; ② while(flag[0]); ④ 临界区 Flag[1]=false; } while(1); （分数：4.00）
__________________________________________________________________________________________ 通过使用标志牌flag[0]和flag[1]能够保证满足“互斥”条件。但是，当两个进程按照①②③④的顺序执行程序时，它们各自举起标志牌，同时都因为观察到对方也举起了标志牌而等待在while语句中。由于两个进程都不会放下自己的标志牌，因此都无法进入临界区，不能满足“有限等待”的条件。所以，上述解决双进程临界区问题的算法是错误的。 [解析] 在算法中，两个进程P 和P 各自拥有自己的标志牌flag[0]1 2 和flag[1]。当进程需要进入临界区时，举起标志牌(设置值为true)。然后观察对方是否举起标志牌，是则等待并继续观察(while语句)，直到对方放下标志牌(设置值为false)。这时，进程才进入临界区。进程退出临界区时，放下标志牌(设置值为false)。
18.在具有N个进程的系统中，允许M个进程(N≥M≥1)同时进入他们的共享区，其信号量s的值的变化范围是 1，处于等待状态的进程数最多是 2个。 （分数：4.00）
(M-N，M)；N-M。 [解析] 信号量s及其P操作、V操作具有资源管理的内涵： s＞0：表示有s个资源可用。 s=0：表示无资源可用。
s＜0：表示有|s|个进程在等待资源。 P(s)：表示申请一个资源。 V(s)：表示释放一个资源。
信号量必须置一次且只能置一次初值。互斥信号量的初值为1，同步信号量的初值为0，代表多个资源的信号量的初值为正整数，即为可用的资源总数。
在本题中，允许M个进程同时进入它们的共享区，可以看作有M个可用的资源总数。信号量s的最大值是可用资源总数M，最小值是当N个进程都需要使用共享区时的值，这时有|M-N|个进程需要等待进入共享区。 19.有3个并发进程通过使用缓冲区buf1、buf2以及信号量none1、nonf1、none2、nonf2，协作完成如图所示的任务，buf1、buf2的大小分别为n1、n2，S1和S2的初值都为1。
这3个进程的程序如下，试补充完整(初值：none1=none2=0；nonf1=n1，nonf2=n2)。 输入进程： While (1) { __①__ ;
计算机学科专业基础综合计算机操作系统-8
