考试时间：4.19 13:00-14:00

考试范围：操作系统前三章（引论，进程管理，处理机调度与死锁）

考试题型：5简答+2计算+1编程

以下所有内容均为题目预测，如有雷同，纯属巧合

简答题

1. 设计现代OS的主要目标是什么？OS的作用可以表现在哪三个方面？

2. OS有哪几大特征，其最基本的特征是什么？

3. 简述OS应具有的五大功能。

4. 简述批处理系统、分时系统以及实时系统各自的特点。

5. 试说明推动批处理系统和分时系统形成和发展的主要动力是什么？

6. 为什么要引入实时操作系统？

7. 试从交互性、及时性以及可靠性方面，将分时系统与实时系统进行比较。

8. 在操作系统中为什么要引入进程的概念？它会产生什么样的影响？

9. 进程由哪三部分组成？进程控制块的组织方式有哪几种？它提供了进程管理和进程调度所需要的哪些信息？

10. 进程在三个基本状态之间转换的典型原因？

11. 什么是进程？什么是线程？进程与线程有何区别？

12. 什么是死锁？产生死锁的原因和必要条件是什么？简述预防死锁方法与必要条件的关系。

13. 处理机调度分为哪三级？简述三种调度的区别，再描述从装入一个作业开始到执行此作业的整个详细的调度过程。

14. 按调度方式可将实时调度算法分为哪几种？抢占调度方式中，抢占的原则是什么？

计算题1：调度算法

1. 根据不同的调度算法，给出相应的调度过程，并计算相关的平均周转时间和平均带权周转时间。（先来先服务、最短作业优先、轮转法、高响应比优先算法）

   进程	就绪时间	服务时间
   P1	0	3
   P2	2	6
   P3	4	4
   P4	6	5
   P5	8	2

   FCFS：P1->P2->P3->P4->P5

   SJF：P1->P2->P5->P3->P4

   HRN：P1->P2->P3->P5->P4

   轮转法：一个时间片结束后，默认新到达的进程先进入就绪队列，然后时间片结束但还没有完成的进程再加入队列末尾。

   时间片为1时

   进程	完成时间	周转时间	带权周转时间
   P1	4	4	1.33
   P2	18	16	2.67
   P3	17	13	3.25
   P4	20	14	2.8
   P5	15	7	3.5

   时间片为4时

   进程	完成时间	周转时间	带权周转时间
   P1	3	3	1
   P2	17	15	2.5
   P3	11	7	1.75
   P4	20	14	2.8
   P5	19	11	5.5

   平均时间请自行计算。

2. 各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。分别使用非抢占式和抢占式的优先级调度算法，分析进程运行情况。（注:优先数越大，优先级越高)

   进程	到达时间	运行时间	优先数
   P1	0	7	1
   P2	2	4	2
   P3	4	1	3
   P4	5	4	2

   非抢占式：P1->P3->P2->P4

   抢占式：

   0-2:P1

   2-4:P2

   4-5:P3

   5-7:P2（P2比P4先到达）

   7-11:P4

   11-16:P1

3. 各进程到达就绪队列的时间、需要的运行时间如下表所示。使用多级反馈队列调度算法，分析进程运行的过程。第1级队列时间片为1，第2级队列时间片为2，第3级队列时间片为4，以此类推。

   进程	到达时间	运行时间
   P1	0	8
   P2	1	4
   P3	5	1

   答案：P1(1)->P2(1)->P1(2)->P2(1)->P3(1)->P2(2)->P1(4)->P1(1)

   重要提醒：在5时刻P3到达，P2必须立刻被放入第二队列的末尾，然后让P3先运行！

4. 最早截止时间优先算法EDF：

   根据任务的截止时间来确定任务的优先级。截止时间越早，其优先级越高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序，调度程序在选择任务时总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。
   EDF算法既可以用于抢占式调度，也可用于非抢占式调度。

5. 最低松弛度优先算法LLF：该算法是根据任务紧急（或松弛）的程度，来确定任务的先级。任务的紧急程度越高，为之赋予的优先级就越高。

   该算法主要用于抢占调度方式中。

   松弛度 = 完成截止时间 - 需要运行时间 - 当前时刻
   当某一时刻算出某一进程的松弛度为0，代表着这个进程必须马上执行！

计算题2：银行家算法

1. 在银行家算法中，若出现下述资源分配情况，试问：
   （1）该状态是否安全？
   （2）若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？

   Process	Allocation	Need	Available
   P0	0032	0012	1622
   P1	1000	1750
   P2	1354	2356
   P3	0332	0652
   P4	0014	0656

   （1）对该状态进行安全性检查：

   Process	Work	Need	Allocation	Work+Allocation	Finish
   P0	1 6 2 2	0 0 1 2	0 0 3 2	1 6 5 4	true
   P3	1 6 5 4	0 6 5 2	0 3 3 2	1 9 8 6	true
   P1	1 9 8 6	1 7 5 0	1 0 0 0	2 9 8 6	true
   P2	2 9 8 6	2 3 5 6	1 3 5 4	3 12 13 10	true
   P4	3 12 13 10	0 6 5 6	0 0 1 4	3 12 14 14	true

   由安全性检查得知，可以找到一个安全序列{P0、P3、P1、P2、P4}，因此系统是安全的。
   （2）P2提出Request(1，2，2，2)，系统按银行家算法进行检查：Request(1，2，2，2) ≤ Need(2，3，5，6)，P2请求是合理的；
   Request(1，2，2，2)≤Available(1，6，2，2)，P2请求是可以满足的；
   系统暂时先为进程P2试行分配资源，并修改有关的确数据，如下图所示：

   Process	Allocation	Need	Available
   P0	0 0 3 2	0 0 1 2	0 4 0 0
   P1	1 0 0 0	1 7 5 0
   P2	2 5 7 6	1 1 3 4
   P3	0 3 3 2	0 6 5 2
   P4	0 0 1 4	0 6 5 6

   再利用安全性算法检查系统是否安全，可利用资源Available（0，4，0，0）已不能满足任何进程的需要，故系统进入不安全状态，此时系统不能将资源分配给P2。

   注意事项：需求矩阵是尚需的各类资源数，最大需求矩阵是对资源的最大需求数。

   工作向量WORK表示系统可提供给进程继续运行所需的各类资源数目

   当进程i获得资源后，应执行：work[j] = work[i] + allocation[i, j]

   要必须会填安全性检查表！

2. 设系统中有 3 种类型的资源（ A ， B ， C ）和 5 个进程 P1、P2、P3、P4 、P5 ，初始时A资源的数量为 17 ，B 资源的数量为 5 ,C 资源的数量为 20 。在T0时刻系统资源状态如下表所示。系统采用银行家算法实施死锁避免策略。

   

   问：（1）T0时刻是否为安全状态？若是，请给出安全序列。

   （2）在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？

   （3）在（2）的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？

   答案：（1）安全，一个安全序列是：P4,P2,P3,P5,P1

   ​ （2）不能分配，因为 request2>available

   ​ （3）可以分配，安全序列是：P4,P2,P3,P5,P1

   在答题时最好画出表格，像上题一样

编程题：信号量机制

1. 有一单车道隧道实施单向放行，隧道长度最多能容纳N辆车，在两边端口A和B各设置一个红绿灯控制车流。当隧道内车辆全部开出后，反方向车辆才能进入，否则会死锁。在无车时两边均为绿灯。假设每辆车到达隧道口时都会触发管理这2个红绿灯的控制器主机产生一个子进程，实现灯光控制管理。请使用信号量写出控制器程序（伪代码），能够避免隧道内死锁的发生。（20分）

   int leftcount = 0, rightcount = 0; //隧道中车的数量
   semaphore mutex = 1; //公用信号量
   semaphore leftmutex = 1, rightmutex = 1; 
   void left2right() {
       while(true) {
           if(leftcount == 0) {
           	P(mutex);
           	P(rightmutex);
       	}
           P(leftmutex);    
           leftcount++; 
           V(leftmutex); 
           //左至右过洞；
           P(leftmutex);
           leftcount--；
           if(leftcount == 0) {
               V(mutex);
               v(rightmutex);
           }
           V(leftmutex);
       }
   
   }
   
   void right2left() {
       while(true) {
           if(rightcount == 0) {
           	P(mutex);
           	P(leftmutex);
           }
           P(rightmutex);    
           rightcount++; 
           V(rightmutex); 
           //右至左过洞；
           P(rightmutex);
           rightcount--；
           if(rightcount == 0) {
               V(mutex);
               v(leftmutex);
           }
           V(rightmutex);
       }   
   }
   
   void main() {
       left2right();
       right2left();
   }
   
   

2. 设有4个进程A、B、C、D共享一个缓冲区(大小为1)，进程A负责循环地从文件读一个整数并放入缓冲区，进程B从缓冲区循环读入MOD 3为0的整数并累计求和，进程C从缓冲区循环地读入MOD 3为1的整数并累计求和，进程D从缓冲区中循环地读入MOD 3为2的整数并累计求和。请用P、V操作写出能够正确执行的程序。

   Sempty :=1 
   SB、SC、SD := 0
   
   Process PA
   Begin 
        P(Sempty);
        <写入num至缓冲区>
        if（num MOD 3 = 0)
               V(SB);
        if（num MOD 3 = 1)
               V(SC);
        else
               V(SD);
   end
   
   Process PB
   Begin 
        P(SB);
        <从缓冲区读入num并累计求和>
        V(Sempty);
   end
   
   Process PC
   Begin 
        P(SC);
        <从缓冲区读入num并累计求和>
        V(Sempty);
   end
   
   Process PD
   Begin 
        P(SD);
        <从缓冲区读入num并累计求和>
        V(Sempty);
   end
   
   

3. 系统中有三个进程 GET、PRO 和 PUT，共用两个缓冲区 BUF1 和 BUF2。

   假设 BUF1 中最多可放 11 个信息，现已放入了两个信息；BUF2 最多可放 5 个信息。

   GET 进程负责不断地将输入信息送入 BUF1 中，

   PRO 进程负责从 BUF1 中取出信息进行处理，并将处理结果送到 BUF2 中，

   PUT 进程负责从 BUF2 中读取结果并输出。

   试写出正确实现 GET、PRO、PUT 的同步与互斥的算法

   （要求：（1）用类 C 语言描述，条理清楚，注释恰当；（2）信号量原语统一使用 wait 和 signal。）

   semaphore
   empty1=9；//空 buf1 的数目
   full1=2;	//有数据的 buf1 的数目
   empty2=5; //空 buf2 的数目
   full1=0;	//有数据的 buf2 的数目
   mutex1=mutex2=1; //互斥信号量
   int main(){
   Cobegin	//并发开始
   GET();
   PRO();
   PUT();
   Coend	//并发结束
   return 0;	}	(3 分)
    
    
   //GET 进程
   void GET（）{
   while(1)
   {
   …
   wait(empty1);
   wait(mutex1);
   将信息送入buf1;
   signal(mutex1);
   signal(full1);
   …
   }
   }	(3 分)
    
    
   //PRO 进程
   void PRO（）{
   while(1)
   {
   wait(full1);
   wait(mutex1);
   从 buf1 中取出信息;
   signal(mutex1);
   signal (empty1);
   wait(empty2);
   wait(mutex2);
   将信息送入 buf2;
   signal(mutex2);
   signal(full2);
   }
   }	(4 分)
    
    
   //PUT 进程
   void PUT（）{
   while(1)
   {
   wait(full2);
   wait(mutex2);
   从 buf2 中取出信息;
   signal(mutex2);
   signal (empty2);
   }	(3 分)