操作系统大题

第一章：

1-1设有三道程序A,B,C，它们共同使用一个设备进行I/O操作，并按照A,B,C的优先次序执行，这三个程序的计算和I/O操作时间表如下表所示，假设调度时间可忽略不计，分别画出单道程序环境和多道程序环境下，它们的运行的时间关系图。并比较运行时间。（抢占和非抢占）。（单位ms）

程 作 操 序 A 30 40 10 B 60 30 10 C 20 40 20 计算 I/O 计算

1-2.一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A先开始做，程序B后开始做。

程序A的运行轨迹是：计算50ms，打印100ms，再计算50ms，打印100ms，结束。 程序B的运行轨迹是：计算50ms,输入80ms，再计算100ms，结束。 试说明：

1.两道程序运行时，CPU有无空等待？若有，在哪段时间内等待？ 2.程序A,B有无等待CPU的情况？若有，指出发生等待的时间 解：

解：1.有 100ms---150ms

2.程序A没有，程序B有，在180ms---200ms时程序B等待，由于此时程序A已经占用CPU。

第二章：

2-1 试画出下面四条语句的前驱图： S1: a∶=x+2 S2: b∶=a+4 S3: c∶=a+b

S4: d∶=x+b

解：前趋关系：S1-->S2,S1-->S3,S2-->S3,S2-->S4,S3-->S4。（PS：前趋图的线不能交叉。） S2 S4 S1 前趋图： S3

1. 设有8个程序段P1，P2，…,P8，它们在并发执行时有如下图所示的制约关系，试用信号量实现这些程序段之间的同步。

解：将上图转换为前趋关系

Var a,b,c,d,e,f,g,h,i,j,k;

Semaphore:=0,0,0,0,0,0,0,0,0,0,0; Begin Parbegin

Begin P1; signal(a); signal(b); signal(c); end; Begin P2; signal(d); signal(e); signal(f); end; Begin wait(a); wait(d); P3; signal(g); end;

Begin wait(b); wait(e); P4; signal(h); end; Begin wait(c); wait(f); P5; signal(i); end; Begin wait(g); P6; signal(j); end; Begin wait(i); P7; signal(k); end;

Begin wait(h); wait(j); wait(k); P8; end; Parend end

2-3以下为记录型信号量两个原子操作：

Wait(s) //申请资源 Signal(s) //释放资源

s.count:=s.count - 1; S.count:=s.count +1;

if s.count<0 If s.count<=0 //表示有阻塞队列

then begin Then begin

进程阻塞； 唤醒队首进程；

进程进入s.quene队列； 将该进程从s.quene队列中移出；

End; End;

2.一个生产者，一个消费者，公用n个环形缓冲区（可能考小题）

伊利牛奶厂生产很多牛奶，放在永辉超市多个分店销售，小明可以从任一间超市买到牛奶，同样，只有当厂商把牛奶放在某一分店时，小明才可以从分店中买到牛奶。

分析：与情况一不同，情况二有N个分店（即N个缓冲区形成一个环形缓冲区），所以要利用指针，要求厂商必须按一定的顺序将商品依次放到每一个分店中。 缓冲区对的指向则通过模运算得到。

解：定义两个同步信号量

Empty：表示缓冲区是否为空，初值为n(缓冲区的数量). Full:表示缓冲区是否为满，初值为0.

设缓冲区编号0--（n-1），定义两个指针in和out。

In：指示下一个可投放产品的缓冲区，每为生产者生产并投放一个产品，指针+1， in=（in+1）mod n. ----取模运算

Out：指示下一个可获取产品的缓冲区，每当消费者取走一个产品，指针+1， out=（out+1）mod n. ----取模运算 生产者进程

消费者进程

While(true){

While(true){

生产一个产品；

P(full);

P（empty）；

从缓冲区中取产品；

产品送往缓冲区（Buffer）；

out=（out+1）mod n.

in=（in+1）mod n.

V（empty）；

V(full);

消费产品；

}

3.一组生产者，一组消费者，公用N个环形缓冲区（可能考小题）

有伊利、蒙牛、光明等多家生产厂家，消费者也不只小明一人，有很多消费者，不同厂家把产品放在永辉超市不同分店中销售，不同的消费者可以去不同大的分店中购买。当某一个分店已放满某个厂家的商品时，下一个厂家只能把商品放在下一家分店中。

分析：

生产者和消费者之间是同步关系。

各个生产者之间、各个消费者之间是互斥关系，互斥访问缓冲区。

解：定义4个信号量：

Empty：表示缓冲区是否为空，初值为n(缓冲区的数量). Full:表示缓冲区是否为满，初值为0. Mutex1:生产者之间的互斥信号量，初值为1 Mutex2:消费者之间的互斥信号量，初值为1.

设缓冲区编号0--（n-1），定义两个指针in和out。

In：指示下一个可投放产品的缓冲区，每为生产者生产并投放一个产品，指针+1， in=（in+1）mod n. ----取模运算

Out：指示下一个可获取产品的缓冲区，每当消费者取走一个产品，指针+1，

本文来源：https://www.bwwdw.com/article/uh5o.html