各个作业执行的时间如下图所示(灰色部分代表程序在执行)：
   
   注：深黑色表示作业独占CPU时间，浅灰色表示作业平分CPU时间，白色表示CPU空闲。
   在8:00，作业1到达，由于CPU空闲、内存空间充足且磁带机和打印机都空闲，作业1开始执行；在8:20，作业2和作业3到达，由于只有一台磁带机空闲，作业2无法执行，只能执行作业3，注意此时作业1和作业3平分CPU时间；在8:30，作业1执行完毕，作业4到达，由于此时内存情况无法满足作业2的需求，作业4开始执行；在8:35时刻，磁带机无法满足作业5，作业5无法执行；到9:00时刻，作业3完成，由于作业2先到达，系统先将资源分配给作业2，之后无法满足作业5需求，作业5无法执行；到9:10，作业4完成，但资源仍无法满足作业5；到9:15，作业2完成，系统将资源分配给作业5，作业5开始执行，到9:30，作业5完成。根据以上分析知：
   1)作业调度顺序为：1，3，4，2，5。
   2)全部作业运行结束的时刻为9:30。
   3)最大作业周转时间为55min。
   平均周转时间为：(30+55+40+40+55)/5=44。

抢占式优先级调度算法，三个作业执行的顺序如下图所示。
   
   作业P1的优先级最高，所以周转时间等于运行时间，T1=80ms；作业P2等待时间为10ms，运行时间为80ms，故周转时间T2=(10+80)ms=90ms；作业P3的等待时间为40ms，运行时间为50ms，故周转时间T3=90ms。
   三个作业从进入系统到全部运行结束，时间为90ms。CPU与外设都是独占设备，运行时间分别为各作业的使用时间之和：CPU运行时间为[(10+10)+20+30]ms=70ms，D1为(30+20+20)ms=70ms，D2为(30+40)ms=70ms。故利用率均为70/90=77.8%。

P1和P2两个并发进程的执行结果是不确定的，它们都对同一变量X进程操作，X是一个临界资源，而没有进行保护。例如：
   1)若先执行完P1再执行P2，结果是x=0，y=1，z=1，t=2，u=2。
   2)若先执行P1到“x=1”，然后一个中断去执行完P2，再一个中断回来执行完P1，结果是x=0，y=0，z=0，t=2，u=2。
   显然两次执行结果不同，所以这两个并发进程不能正确运行。可以将这个程序改为：
   

由于安全岛M仅仅允许两辆车停留，本应该作为临界资源而要设置信号量，但根据题意，任意时刻进入安全岛的车不会超过两辆(两个方向最多各有一辆)，因此，不需要为M设置信号量，在路口T和路口N都需要设置信号量，以控制来自两个方向的车对路口资源的争夺。这两个信号量的初值都是1。此外，由于从S到T的一段路只允许一辆车通过，所以还需要设置另外的信号量用于控制，由于M的存在，可以为两端的小路分别设置一个互斥信号量。
   
   

1)所有作业进入内存的时间及结束的时间见下表。

作业	到达时间	运行时间	优先数	进入内存时间	结束时间	周转时间
1	8:00	40min	5	8:00	9:10	70min
2	8:20	30min	3	8:20	8:50	30min
3	8:30	50min	4	9:10	10:00	90min
4	8:50	20min	6	8:50	10:20	90min

   2)平均周转时间为：(70+30+90+90)/4=70(min)。

将顾客号码排成一个队列，顾客进入银行领取号码后，将号码由队尾插入。柜员空闲时，从队首取得顾客号码，并且为这个顾客服务，由于队列为若干进程共享，所以需要互斥。柜员空闲时，若有顾客，就叫下一个顾客并为之服务。因此，需要设置一个信号量来记录等待服务的顾客数。
   

定义信号量S1控制P1与P2之间的同步：S2控制P1与P3之间的同步；empty控制生产者与消费者之间的同步；mutex控制进程间互斥使用缓冲区。程序如下：
   

多线程指的是在一个程序中可以定义多个线程同时运行它们，每个线程可以执行不同的任务。
   多线程与多任务区别：多任务是针对操作系统而言的，代表着操作系统可以同时执行的程序个数；多线程是针对一个程序而言的，代表着一个程序可以同时执行的线程个数，而每个线程可以完成不同的任务。

多级反馈队列调度算法能较好地满足各种类型用户的需要。对终端型作业用户而言，由于他们所提交的大多属于交互型作业，作业通常比较短小，系统只要能使这些作业在第1级队列所规定的时间片内完成，便可使终端型作业用户感到满意；对于短批处理作业用户而言，他们的作业开始时像终端型作业一样，如果仅在第1级队列中执行一个时间片即可完成，便可以获得与终端型作业一样的响应时间，对于稍长的作业，通常也只需要在第2级队列和第3级队列中各执行一个时间片即可完成，其周转时间仍然较短；对于长批处理作业用户而言，它们的长作业将依次在第1，2，…，直到第n级队列中运行，然后再按时间片轮转方式运行，用户不必担心其作业长期得不到处理。

顾客进店后按序取号，并等待叫号；销售人员空闲之后也是按序叫号，并销售面包。因此同步算法只要对顾客取号和销售人员叫号进行合理同步即可。我们使用两个变量i和j分别记录当前的取号值和叫号值，并各自使用一个互斥信号量用于对i和j的进行访问和修改。
   
   

电影院一次只能放映一部影片，希望观看的观众可能有不同的爱好，但每次只能满足部分观众的需求，即希望观看另外两部影片的用户只能等待。分别为三部影片设置三个信号量s0、s1、s2，初值分别为1、1、1。电影院一次只能放一部影片，因此需要互斥使用。由于观看影片的观众有多个，因此必须分别设置三个计数器(初值都是0)，用来统计观众个数。当然计数器是个共享变量，需要互斥使用。
   

父进程创建子进程后，父进程与子进程同时执行(并发)。主程序调用子程序后，主程序暂停在调用点，子程序开始执行，直到子程序返回，主程序才开始执行。

不发生死锁要求必须保证至少有一个进程可以得到所需的全部资源并执行完毕，当m＞=n(k-1)+1则一定不会发生死锁。

序号	m	n	k	是否会死锁	说明
1	6	3	3	可能会	6＜3(3-)+1
2	9	3	3	不会	9＞3(3-1)+1
3	13	6	3	不会	13=3(6-1)+{1

在本题中，当两个进程都执行完第一步后，即进程P1和进程P2都申请到了一个R1类资源时，系统进入不安全状态。随着两个进程向前推进，无论哪个进程执行完第二步，系统都将进入死锁状态。可能达到的死锁点是：进程P1占有一个单位的R1类资源及一个单位的R2类资源，进程P2占有一个单位的R1类资源，此时系统内已无空闲资源，而两个进程都在保持已占有资源不释放的情况下继续申请资源，从而造成死锁；或进程P2占有一个单位的R1类资源及一个单位的R2类资源，进程P1占有一个单位的R1类资源，此时系统内已无空闲资源，而两个进程都在保持已占有资源不释放的情况下继续申请资源，从而造成死锁。
   假定进程P1成功执行了第二步，则死锁点的资源分配如下图所示。
   

   执行一条命令或运行一个应用程序时，进程和程序之间形成一对一的关系。进程在执行过程中可以加载执行不同的应用程序，从而形成一对多的关系；当以不同的参数或数据多次执行同一个应用程序时，形成多对一的关系；当并发地执行不同的应用程序时，形成多对多的关系。

[解析] 从进程的概念、进程与程序之间的关系来考虑问题的解答。进程是程序的执行过程，进程代表执行中的程序，因此进程与程序的差别就隐含在“执行”之中。程序是静态的指令集合，进程是程序的动态执行过程。静态的程序除了占用磁盘空间外，不需要其他系统资源，只有执行中的进程才需要分配内存、CPU等系统资源。
   进程的定义说明了两点：
   1)进程与程序相关，进程包含了程序。程序是进程的核心内容，没有程序就没有进程。
   2)进程不仅仅是程序，还包含了程序在执行过程中使用的全部资源。没有资源，程序就无法执行，因此，进程是程序执行的载体。
   当运行一个程序时，操作系统首先要创建一个进程，为进程分配内存等资源，然后加入到进程队列中执行。当单个进程在某个时刻而言，一个进程只能执行一个程序，进程与程序之间是一对一的关系。但从整个系统中的进程集合以及进程的生命周期而言，进程与程序之间可以形成一对一、多对一、一对多、多对多的关系。

系统会死锁。因为对两个账户进行加锁操作是可以分割进行的，若此时有两个用户同时进行转账，P1先对账户A进行加锁，再申请账户B；P2先对账户B进行加锁，再申请账户A，此时产生死锁。解决的办法是：可以采用资源顺序分配法对A、B账户进行编号，用户转账时只能按照编号由小到大进行加锁；也可以采用资源预分配法，要求用户在使用资源之前将所有资源一次性申请到。

本题是生产者一消费者问题的变形，生产者“车间A”和消费者“装配车间”共享缓冲区“货架F1”；生产者“车间B”和消费者“装配车间”共享缓冲区“货架F2”。因此，可为它们设置6个信号量，其中，empty1对应货架F1上的空闲空间，其初值为10；full1对应货架F1上面的A产品，其初值为0；empty2对应货架F2上的空闲空间，其初值为10；full2对应货架F2上面的B产品，其初值为0；mutex1用于互斥地访问货架F1，其初值为1；mutex2用于互斥地方问货架F2，其初值为1。
   A车间的工作过程可描述为：
   
   B车间的工作过程可描述为：
   
   装配车间的工作过程可描述为：
   

每个进程有自己独立的地址空间。在操作系统和硬件的地址保护机制下，进程无法访问其他进程的地址空间，所以必须借助于操作系统的系统调用函数实现进程之间的通信。进程通信的主要方式有：

[解析] 在操作系统中，进程是竞争和分配计算机系统资源的基本单位。每个进程有自己的独立地址空间。为了保证多个进程能够彼此互不干扰地共享物理内存，操作系统利用硬件地址机制对进程的地址空间进行了严格的保护，限制每个进程只能访问自己的地址空间。
   1)共享内存区：通过系统调用创建共享内存区。多个进程可以(通过系统调用)连接同一个共享内存区，通过访问共享内存区实现进程之间的数据交换。使用共享内存区时需要利用信号量解决同步互斥问题。
   2)消息传递：通过发送/接收消息，系统调用实现进程之间的通信。当进程发送消息时，系统将消息从用户缓冲区复制到内核中的消息缓冲区中，然后将消息缓冲区挂入消息队列中。进程发送的消息保持在消息队列中直到被另一进程接收。当进程接收消息时，系统从消息队列中解挂消息缓冲区，将消息从内核的消息缓冲区中复制到用户缓冲区，然后释放消息缓冲区。
   3)管道系统：管道是先进先出(FIFO)的信息流，允许多个进程向管道写入数据，允许多个进程从管道读出数据。在读/写过程中，操作系统保证数据的写入顺序和读出顺序是一致的。进程通过读/写管道文件或管道设备实现彼此之间的通信。
   4)共享文件：利用操作系统提供的文件共享功能实现进程之间的通信。这时，也需要信号量解决文件共享操作中的同步和互斥问题。

在汽车行驶过程中，驾驶员活动与售票员活动之间的同步关系为：售票员关车门后，向驾驶员发开车信号，驾驶员接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时驾驶员停车，售票员在车停后开门让乘客上下车。因此，驾驶员启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与驾驶员停车取得同步。应设置两个信号量S1、S2：
   S1表示是否允许驾驶员启动汽车(其初值为0)。
   S2表示是否允许售票员开门(其初值为0)。
   
   

使用信号量mutex控制两个进程互斥访问临界资源(仓库)，使用同步信号量Sa和Sb(分别代表产品A和产品B的入库计数器)满足条件2和条件3。代码如下：
   

死锁检测方法可以获得最大的并发性。并发性排序：死锁检测方法、银行家算法、资源预分配法。

[解析] 死锁在系统里不可能完全消灭，但是我们要尽可能地减少死锁的发生。对死锁的处理有四种方法：忽略、检测与恢复、避免和预防，每一种方法对死锁的处理从宽到严，同时系统并发性由大到小。这里银行家算法属于避免死锁，资源预分配属于预防死锁。

FCFS调度算法的作业调度情况见下表：

作业	提交时问	运行时间	开始时间	结束时间	周转时间	带权周转时间
1	8.0	1.0	8.0	9.0	1.0	1.0
2	8.5	0.5	9.0	9.5	1.0	2.0
3	9.0	0.2	9.5	9.7	0.7	3.5
4	9.1	0.1	9.7	9.8	0.7	7.0

T=(1.0+1.0+0.7+0.7)/4=0.85 W=(1.0+2.0+3.5+7.0)/4=3.375 SJF调度算法的作业调度情况见下表：

作业	提交时间	运行时间	开始时间	结束时间	周转时间	带权周转时间
1	8.0	1.0	8.0	9.0	1.0	1.0
2	8.5	0.5	9.3	9.8	1.3	2.6
3	9.0	0.2	9.0	9.2	0.2	1.0
4	9.1	0.1	9.2	9.3	0.2	2.0

T=(1.0+1.3+0.2+0.2)/4=0.675 W=(1.0+2.6+1.0+2.0)/4=1.65 响应比高者优先：8.0时只有1号作业，所以肯定是1号得到CPU。9.0时1号作业执行完毕，2号作业响应比为(9.0-8.5+0.5)/0.5=2，3号作业响应比为(9.0～9.0+0.2)/0.2=1，2号的响应比大于3号，9.0时调度2号作业。9.5时2号作业执行完毕，此时3号作业响应比为(9.5-9.0+0.2)/0.2=3.5，4号作业响应比为(9.5-9.1+0.1)/0.1=5，4号的响应比大于3号，所以先调度4号作业。 高响应比优先调度算法的作业调度情况见下表：

作业	提交时间	运行时间	开始时间	结束时间	周转时问	带权周转时间
1	8.0	1.0	8.0	9.0	1.0	1.0
2	8.5	0.5	9.0	9.5	1.0	2.0
3	9.0	0.2	9.6	9.8	0.8	4.0
4	9.1	0.1	9.5	9.6	0.5	5.0

   T=(1.0+1.0+0.8+0.5)/4=0.825
   W=(1.0+2.0+4.0+5.0)/4=3.0

1)控制变量waiting用来记录等候理发的顾客数，初值为0，当进来一个顾客时，waiting加1，当一个顾客理发时，waiting减1；
   2)信号量customers用来记录等候理发的顾客数，并用做阻塞理发师进程，初值为0；
   3)信号量barbers用来记录正在等候顾客的理发师数，并用做阻塞顾客进程，初值为0；
   4)信号量mutex用于互斥，初值为1。
   
   

进程之间存在两种制约关系，即同步和互斥。
   同步是由于并发进程之间需要协调完成同一个任务时引起的一种关系，为一个进程等待另一个进程向它直接发送消息或数据时的一种制约关系。
   互斥是由于并发进程之间竞争系统的临界资源引起的，为一个进程等待另一个进程已经占有的必须互斥使用的资源时的一种制约关系。
   1)是互斥关系，同一本书只能被一个学生借阅，或者任何时刻只能有一个学生借阅一本书。
   2)是互斥关系，篮球是互斥资源。
   3)是同步关系，一个工序完成后开始下一个工序。
   4)是同步关系，生产商品后才能消费。

时间片轮转(RR)调度是轮流地调度就绪队列中的每个进程，进程每次占用CPU的时间长度限制为时间片的大小。当采用固定的时间片大小时，每个进程按照固定周期被循环执行。所以，进程的执行速度是由该进程的时间片大小在一个循环周期中所占的比例决定的，比例越高，进程的相对执行速度就越快。
   因为就绪进程队列的平均长度为5，单个RR调度循环周期的时间为
   (4×100+1×400)ms=800ms
   A类进程需要20个时间片的执行时间，B类进程需要5个时间片地执行时间(1s=1000ms)。
   A类进程的平均周转时间为
   20×0.8s=16s
   B类进程的平均周转时间为
   5×0.8s=4s

1)按照可抢先式短进程优先调度算法进程运行时间见下表。

进程	到达就绪队列时刻	预计执行时间	执行时间段	周转时间
P1	0	8	0～1:10～17	17
P2	1	4	1～5	4
P3	2	9	17～26	24
P4	3	5	5～10	7

时刻0，进程P1到达并占用处理器运行。 时刻1，进程P2到达，因其预计运行时间短，故抢夺处理器进入运行，P1等待。 时刻2，进程P3到达，因其预计运行时间长于正在运行的进程，进入就绪队对等待。 时刻3，进程P4到达，因其预计运行时间长于正在运行的进程，进入就绪队列等待。 时刻5，进程P2运行结束，调度器在就绪队列中选择短进程，P4符合要求，进入运行，进程P1和进程P3则还在就绪队列等待。 时刻10，进程P4运行结束，调度器在就绪队列中选择短进程，P1符合要求，再次进入运行，而进程P3则还在就绪队列等待。 时刻17，进程P1运行结束，只剩下进程P3，调度其运行。 时刻26，进程P3运行结束。 平均周转时间=[(17-0)+(5-1)+(26-2)+(10-3)]/4=13。 2)按照时间片轮转调度算法进程时间分配见下表。

进程	到达就绪队列时刻	预汁执行时间	执行时间段	剧转时间
P1	0	8	0～2；8～10；16～18；21～23	23
p2	1	4	2～4；10～12	11
P3	2	9	4～6；12～14；18～20；23～25；25～26	24
P4	3	5	6～8；14～16；20～21	18

   平均周转时间=((23-0)+(12-1)+(26-2)+(21-3))/4=19。