V(wait[i]); end coend end

2．在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为4,3,2,1,4,3,5,4,3,2,1,5,当分配给该作业的物理块数M分别为3和4时，试画出访问过程中所发生的缺页位置，并计算缺页的次数和缺页率，比较所得的结果。 解

1)当分配给该作业的物理块数M=3时，其缺页时间如下：“▲”表示缺页的位置。 页面访问序列：4 3 2 1 4 3 5 4 3 2 1 5 物理内存：4 4 4 1 1 1 5 5 5 2 2 2 3 3 3 4 4 4 4 4 4 1 1 2 2 2 3 3 3 3 3 3 5 缺页标志：▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ 计算结果：缺页次数为10次，缺页率为5/6。

2)当分配给该作业的物理块数M=4时，其缺页时间描述如下：“▲”表示缺页的位置。 页面访问序列：4 3 2 1 4 3 5 4 3 2 1 5 物理内存：4 4 4 4 4 4 4 4 4 4 4 5 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 5 5 5 5 1 1 1 1 1 1 1 1 2 2 2 缺页标志：▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ 计算结果：缺页次数为8次，缺页率为2/3。

比较：当里程分配的内存块数较多时，进程的缺页率较低。

3．三个进程A、B、C，共享两个缓冲区B1和B2。缓冲区B1中可存放n件产品，缓冲区B2中可存放m件产品。进程A每次生产一件产品并将其存入缓冲区B1中；进程B每次从缓冲区B1中取出一件产品后再把它送到缓冲区B2中；进程C每次从缓冲区B2中取出一件产品去消费。为防止把产品存入已满的缓冲区，或从空的缓冲区取产品、或重复取产品，试用信号量机制实现它们之间的同步。 解：

（1）进程间关系为：A→B1→B→B2→C

A受B制约：当B未把B1信息取走，A不能输入下一信息。 C受B制约：当B未把B1信息送入B2，C不能打印B2信息。

B同时受A、C约束：把A未把信息写入B1；C未把B2信息印出，则B不能把B1信息送至B2。

（2）设四个信号量。它们初值均为0 A私用信号量S1空。（为“0”表示B1空） B私用信号量S1满。（为“1”表示B1满） B私用信号量S2空。（为“0”表示B2空） C私用信号量S2满。（为“1”表示B2满） PV原语同步算法如下：

A： 输入到B1→V（S1满）→P（S1空）过程循环往复

B： P（S1满）→B1的信息送入B2→V（S1空）→V（S2满）→P（S2空）过程循环往复

C： P（S2满）→B2的信息被打印→V（S2空）过程循环往复 4．假设有4道作业，它们的提交时间及执行时间由下表给出。 作业号 1 2 3 4 提交时刻（时） 10：00 10：20 10：40 10：50 执行时间（小时） 2 1 0.5 0.3 计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和带权平均周转时间，并指出它们的调度顺序。

假设作业i提交时间为Tsi，完成时间为Tei，执行时间为Ti，等待时间为Twi，周转时间为Tzi，带权周转时间为Wi，平均周转时间为T，平均带权周转时间为W。 1）先来先服务（FCFS）

顺序： 1. Ts1=10:00 Tw1=0 T1=2.0 Te1=12:00 Tz1=2.0 W1=1 2. Ts2=10:20 Tw2=2.0 T2=1.0 Te2=13:00 Tz2=5/3 W2=5/3 3. Ts3=10:40 Tw3=7/3 T3=0.5 Te3=13:30 Tz3=8/3 W3=16/3 4. Ts4=10:50 Tw4=8/3 T4=0.3 Te4=13:48 Tz4=89/30 W4=89/9 T=(2.0+5/3+8/3+89/30)/4=279/120=2.325 W=(1+5/3+16/3+89/9)/4=161/36=4.472 2)最短作业优先（SJF）

顺序： 1. Ts1=10:00 Tw1=0 T1=2.0 Te1=12:00 Tz1=2.0 W1=1 2. Ts4=10:50 Tw4=7/6 T4=0.3 Te4=12:18 Tz4=44/30 W4=44/9 3. Ts3=10:40 Tw3=49/30 T3=0.5 Te3=12:48 Tz3=64/3 W3=128/30 4. Ts2=10:20 Tw2=74/30 T2=1.0 Te2=13:48 Tz2=104/30 W2=104/30 T=(2.0+44/30+64/30+104/30)/4=272/120=2.267 W=(1+44/9+128/30+104/30)/4=1226/360=3.406

5．设有一台计算机有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠

卡片逐一输入到大小为n1缓冲区B1中，加工处理后在搬到大小为n2缓冲区B2中，并在打印机上印出，问：

①系统要设几个进程来完成这个任务？各自的工作是什么？ ②这些进程间有什么样的相互制约关系？ ③用P、V操作写出这些进程的同步算法。 ．解：

①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。

②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。

③6个信号量含义及初值：

full1—— 缓冲区B1满，初值为0； empty1——缓冲区B1空，初值为n1； full2—— 缓冲区B2满，初值为0； empty2——缓冲区B2空，初值为n2；

S1——对B1互斥访问的互斥信号量，初值为1； S2——对B2互斥访问的互斥信号时，初值为1； R、C、P同步的代码如下：

var s1,s2,full1,full2,empty1,empty2:semaphore:=1,1,0,0,n1,n2; begin parbegin

R:begin

repeat

从卡片输入机上读入卡片信息; P(empty1); P(s1);

将信息放入buff1中; V(s1); V(full1);

until false;

end C:begin

repeat

P(full1); P(s1);

从buff1中取出数据;

end

V(s1); V(empty1); 处理取出的数据; P(empty2); P(s2);

将数据处理结果送入buff2中; V(s2); V(full2);

until false

end P:begin

repeat

P(full2); P(s2);

从buffer2中取出数据; V(s2); V(empty2);

将信息从打印机输出;

until false;

end parend;

6．设有三个批作业JOB1、JOB2、JOB3，其到达时间、处理时间及完成时间如下： 作业 （时）

JOB1

作业到达时间（时）

15

开始处理时间（时）

18

处理完成时间

22