浙大操作系统原理离线作业.doc

1、浙江大学远程教育学院 操作系统原理课程作业 姓名： 王海清 学 号： 714073012001 年级： 14 秋 学习中心： 厦门 一 、 单选 题 7 进程 P0 和 P1 的共享变量定义及其初值为 boolean flag2； int turn=0； flag0=FALSE； flag1=FALSE； 若进程 P0 和 P1 访问临界资源的类 C 代码实现如下： void P0() /P0进程 while（ TURE） flag0=TRUE; turn = 1; while (flag1 临界区 ; flag0 = FALSE; void P1() /P1进程 while（ TURE） f

2、lag1=TRUE; turn = 0; while (flag0 临界区 ; flag1 = FALSE; 则并发执行进程 P0 和 P1 时产生的情况是： A不能保证进程互斥进入临界区、会出现“饥饿”现象 B不能保证进程互斥进入临界区、不会出现“饥饿”现象 C能保证进程互斥进入临界区、会出现“饥饿”现象 D能保证进程互斥进入临界区、不会出现“饥饿”现象 【答案】 D 2.有两个进程 P1 和 P2 描述如下 : shared data： int counter = 6; P1 : Computing; counter=counter+1; P2 : Printing; counter=co

3、unter-2; 两个进程并发执行，运行完成后， counter 的值不可能为 。 A. 4 B. 5 C. 6 D. 7 【答案】 C 3.某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为 210 字节，页表项大小为 2 字节，逻辑地址结构为： 页目录号 页号 页内偏移量 逻辑地址空间大小为 216 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是 A 64 B 128 C 256 D 512 【答案】 B 4.在动态分区系统中，有如下空闲块 : 空闲块 块大小（ KB） 块的基址 1 80 60 2 75 150 3 55 250 4 90 350 此 时 ,某进程

4、P 请求 50KB 内存 ,系统从第 1 个空闲块开始查找，结果把第 4 个空闲块分配给了 P 进程 ，请问是用哪一种分区分配算法实现这一方案 ? A. 首次适应 B. 最佳适应 C. 最差适应 D. 下次适应 【答案】 C 5.在一 页式 存储管理系统中，页表内容如下所示。 页号 帧号 0 2 1 1 2 8 若页大小为 1K，逻辑地址的页号为 2，页内地址为 451，转换成的物理地址为 （ 3） 8643 B. 8192 C. 2048 D. 2499 【答案】 A 6.采用段式存储管理的系统中，若地址用 32 位 表示，其中 20 位表示段号，则允许每段的最大长度是 A 224 B. 2

5、12 C. 210 D. 232 【答案】 B 7.在一段式存储管理系统中，某段表的内容如下 : 段号 段首址 段长 0 100K 35K 1 560K 20K 2 260K 15K 3 670K 32K 若逻辑地址为 (2, 158)，则它对应的物理地址为 _。 A. 100K+158 B. 260K+158 C. 560K+158 D. 670K+158 【答案】 B 8.一个分段存储管理系统中，地址长度为 32 位，其中段长占 8 位，则最大段长是 A. 28 字节 B. 216字节 C. 224字节 D. 232 字节 【答案】 C 9.有一请求分 页式 存储管理系统，页面大小为每页

6、100 字节，有一个 5050 的整型数组按行为主序连续存放，每个整数占两个字节，将数组初始化为 0 的程序描述如下： int A5050; for (int i = 0; i #include #include int value=8; int main() pid_t pid; /* fork a child process */ pid = fork(); if (pid = 0) /* child process */ value +=15; else /* parent process */ /* parent will wait for the child to complete

7、*/ wait(NULL); printf(“ Parent :value= %dn“,value);/*LINE A*/ exit(0); Parent :value=8。 4.4 在多线程程序中，以下哪些程序状态组成是被线程共享的？ a.寄存值 b.堆内存 c.全局变量 d.栈内存 一个线程程序的线程共享堆内存和全局变量，但每个线程都有属于自己的一组寄存值和栈内存。 4.7 由图 4.11 给出的程序使用了 Pthread 的应用程序编程接口（ API），在程序的第 c 行和第p 行分别会输出什么？ #include #include int value=0; void *runner(v

8、oid *param); /* the thread */ int main(int argc, char *argv) int pid; pthread_t tid; pthread_attr_t attr; pid = fork(); if (pid = 0) /* child process */ pthread_attr_init( pthread_create( pthread_join(tid, NULL); printf(“CHILD: value = %d”, value); /* LINE C*/ else if (pid 0) /* parent process */ wa

9、it(NULL); printf(“PARENT: value = %d”, value); /* LINE P */ void *runner(void *param) value=10; pthread_exit(0); 答： c行会输出 10， p行会输出 0. 5.4 考虑下列进程集，进程占用的 CPU 区间长度以毫秒来计算： 假设在时刻 0 以进程 P1， P2， P3， P4， P5的顺序到达。 a. 画出 4 个 Gantt 图分别演示用 FCFS、 SJF、非抢占优先级（数字小代表优先级高）和 RR（时间片 1）算法调度时进程的执行过程。 b. a.甘特图 c. FCFS P1

10、 P2 P3 P4 P5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 d. e. SJF P2 P4 P3 P5 P1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 f. g. Non-preemptive Priority P2 P5 P1 P3 P4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 h. i. RR(quantum=1) P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1 P1 P1 P1

11、 P1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 进程 区间时间 优先级 P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2 j. b.每个进程在每种调度算法下的周转时间是多少？ Turnaround Time Process FCFS SJF NPP RR(quantum=1) P1 10 19 16 19 P2 11 1 1 2 P3 13 4 18 7 P4 14 2 19 4 P5 19 9 6 14 Average 13.4 7.2 12 9.2 c.每个进程在每种调度算法下的等待时间是多少？ Process

12、FCFS SJF NPP RR(quantum=1) P1 0 9 6 9 P2 10 0 0 1 P3 11 2 16 5 P4 13 1 18 3 P5 14 4 1 9 Average 9.6 3.2 8.2 5.4 d.哪一种调度算法的平均等待时间对所有进程而言最小？ SJF 5.5 下面哪些算法会引起饥饿 a.先来先服务 b.最短作业优先调度 c.轮转法调度 d.优先级调度 最短作业优先调度和优先级调度算法会引起饥饿 5.7 考虑一个运行 10 个 I/O 约束（型）任务和一个 CPU 约束（型）任务的系统。假设， I/O约束任务每进行 1 毫秒的 CPU 计算发射一次 I/O 操作

13、，但每个 I/O 操作的 完成需要 10 毫秒。同时，假设上下文切换要 0.1 毫秒，所有的进程都是长进程。对一个 RR 调度来说，以下情况时 CPU 的利用率是多少： a.时间片是 1 毫秒 b.时间片是 10 毫秒 答： a.时间片是 1毫秒：不论是哪个进程被调度，这个调度都会为每一次的上下文切换花费一个 0.1毫秒的上下文切换。 CPU的利用率是 1/1.1*100=92%。 b.时间片是 10 毫秒：这 I/O 限制任务会在使用完 1毫秒时间片后进行一次上下文切换。这个时间片要求在所有的进程间都走一遍，因此， 10*1.1+10.1(因为每个 I / O限定任务 执行为 1 毫秒，然后

14、承担上下文切换的任务，而 CPU限制任务的执行 10毫秒在承担一个上下文切换之前 ) 。因此， CPU的利用率是 20、 21.1*100=94%。 6.01 在生产者和消费者问题中，信号量 mutex， empty， full 的作用是什么？如果对调生产者进程中的两个 wait 操作和两个 signal 操作，则可能发生什么情况？ 信号量 mutex 的作用是保证各生产者进程和消费者进程对缓冲池的互斥访问。信号量empty 和 full 均是资源信号量，它们分别对应于缓冲池中的空闲缓冲区和缓冲池中的产品，生产者需要通过 wait(empty)来申请使用空闲缓冲区，而消费者需要通过 wait(

15、full)才能取得缓冲中的产品，可见，这两个信号量起着同步生产者和消费者的作用，它们保证生产者不会将产品存放到满缓冲区中，而消费者不会从空缓冲区中取产品。 在生产者 消费者问题中，如果将两个 wait 操作，即 wait(full)和 wait(mutex)互换位置，或者 wait(empty)和 wait(mutex)互换位置，都可能引起死锁。考虑系统中缓冲区全满时，若一生产者进程先执行了 wait(mutex)操作并获得成功，当再执行 wait(empty)操作时，它将因失败而进入阻塞状态，它期待消费者执行 signal(empty)来唤醒自己，在此之前，它不可能执行 signal(mut

16、ex)操作，从而使企图通过 wait(mutex)进入自己的临界区的其他生产者和所有的消费者进程全部进入阻塞状态，系统进入死锁状态。类似地，消费者进程若先执行wait(mutex)，后执行 wait(full)同样可能造成死锁。 signal(full)和 signal(mutex)互换位置，或者 signal(empty)和 signal(mutex)互换位置，则不会引起死锁，其影响只 是使某个临界资源的释放略为推迟一些。 6.02 一组合作进程，执行顺序 如下图 。请用 wait、 signal 操作实现进程间的同步操作。 如图 示并发进程之间的前趋关系，为了使上述进程同步，可设置 8 个

17、信号量 a、 b、 c、d、 e、 f、 g、 h，它们的初值均为 0，而相应的进程可描述为（其中“”表示进程原来的代码）： main( ) cobegin P1( ) ; signal(a); signal(b); P2( ) wait(a); ; signal(c); signal(d); P3( ) wait(b); ; signal(e); signal(f); P4( ) wait(c); wait(e); ; signal(g); P5( ) wait(d); wait(f); ; signal(h); P6( ) wait(g); wait(h); ; coend 6.03 在生

18、产者和消费者问题中，多个生产者进程（ Producer Process） 和多个消费者进程（ Consumer Process） 共享一个大小为 8 的缓冲区，他们的信号量和共享变量设置如下： 各进程的执行顺序 P6 P5 P2 P1 P3 P4 合作进程 的前趋图 h g f e d c b a P1 P4 P5 P6 P3 P2 int nextc=0, nextp=0, buf8; semaphore full; empty; mutex; 生产者进程和消费者进程问题的算法描述如下： Producer Process: Consumer Process: int itemp; int i

19、temc; while(1) while(1) 1 itemp = rand(); / Generate a number 1 wait(full); 2 wait(empty); 2 wait(mutex); 3 wait(mutex); 3 itemc=bufnextc; 4 bufnextp=itemp; 4 nextc=(nextc+1)%8; 5 nextp=(nextp+1)%8; 5 signal(mutex); 6 signal(mutex); 6 signal(empty); 7 signal(full); 7 cout itemc endl; （ 1） 生产者进程和消费者进

20、程的临界区是哪些？ 生产者进程的临界区是第 4行和第 5行；消费者进程的临界区是第 3行和第 4行。 （ 2） 信号量 full、 empty和 mutex的初值是多少 ? empty = 8 ， full = 0 , mutex = 1 。 （ 3）如果对调生产者进程中的两个 P操作即第 2行和第 3行，以及对调消费者进程中的两个 P操作即第 1行和第 2行，如下所示。可能发生什么情况？ Producer Process Consumer Process 1 itemp = rand(); / Generate a number 1 wait(mutex); 2 wait(mutex); 2

21、 wait(full); 3 wait(empty); 3 itemc=bufnextc; 系统可能会产生死锁。例如，生产者进程得到信号量 mutex，但是没有空缓冲区即 empty 0时，此时生产者进程阻塞；而消费者进程又无法得到信号量 mutex，此时消费者进程也阻塞，系统产生了死锁。 （ 4）上面的生产者和消费者同步算法有一个缺点，在有 空缓冲区时，当消费者进程正在临界区时，生产者进程必须等待，反之亦然。您如何可以解决这个问题，以提高生产者和消费者进程之间并发？写出新的生产者进程和消费者进程的同步算法。 增加一个信号量 mutex1，初值为 1，其算法如下： Producer Process Consumer Process int itemp; int itemc; while(1) while(1) 1 itemp = rand(); / Generate a number 1 wait(full); 2 wait(empty); 2 wait(mutex); 3 wait(mutex1); 3 itemc=bufnextc; 4 bufnextp=itemp; 4 nextc=(nextc+1)%8; 5 nextp=(nextp+1)%8; 5 signal(mutex);