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 & turn = 1) ; 临界区; flag0 = FALSE; void P1() /P1进程 while（TURE）flag1=TRUE;
2、turn = 0;while (flag0 & turn = 0) ; 临界区; flag1 = FALSE; 则并发执行进程P0和P1时产生的情况是：A不能保证进程互斥进入临界区、会出现“饥饿”现象B不能保证进程互斥进入临界区、不会出现“饥饿”现象C能保证进程互斥进入临界区、会出现“饥饿”现象D能保证进程互斥进入临界区、不会出现“饥饿”现象【答案】D2.有两个进程P1和P2描述如下:shared data：int counter = 6; P1 : Computing; counter=counter+1; P2 : Printing; counter=counter-2;两个进程并发执行，
3、运行完成后，counter的值不可能为 。 A. 4 B. 5 C. 6 D. 7【答案】C3.某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210字节，页表项大小为2字节，逻辑地址结构为：页目录号 页号 页内偏移量逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是A64 B128 C256 D512【答案】B4.在动态分区系统中，有如下空闲块:空闲块 块大小（KB） 块的基址1 80 602 75 1503 55 2504 90 350此时,某进程P请求50KB内存,系统从第1个空闲块开始查找，结果把第4个空闲块分配给了P进程 ，请问是用哪一种分
4、区分配算法实现这一方案?A. 首次适应 B. 最佳适应 C. 最差适应 D. 下次适应【答案】C5.在一页式存储管理系统中，页表内容如下所示。页号 帧号0 21 12 8若页大小为1K，逻辑地址的页号为2，页内地址为451，转换成的物理地址为（3） 8643 B. 8192 C. 2048 D. 2499【答案】A6.采用段式存储管理的系统中，若地址用32位表示，其中20位表示段号，则允许每段的最大长度是A 224 B. 212 C. 210 D. 232【答案】B7.在一段式存储管理系统中，某段表的内容如下: 段号 段首址 段长0 100K 35K1 560K 20K2 260K 15K3
5、670K 32K若逻辑地址为(2, 158)，则它对应的物理地址为_。A. 100K+158 B. 260K+158 C. 560K+158 D. 670K+158【答案】B8.一个分段存储管理系统中，地址长度为32位，其中段长占8位，则最大段长是A. 28字节 B. 216字节 C. 224字节 D. 232字节【答案】C9.有一请求分页式存储管理系统，页面大小为每页100字节，有一个5050的整型数组按行为主序连续存放，每个整数占两个字节，将数组初始化为0的程序描述如下：int A5050;for (int i = 0; i 50; i+) for (int j = 0; j 50; j+
6、) Ai,j = 0; 若在程执行时内存只有一个存储块用来存放数组信息，试问该程序执行时产生 次缺页中断。A1 B. 50 C. 100 D. 2500【答案】B 10.一台计算机有4个页框，装入时间、上次引用时间、和每个页的访问位R和修改位M，如下所示： 页 装入时间 上次引用时间 R M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1采用FIFO算法将淘汰 页；A. 0 B. 1 C. 2 D. 3【答案】C11.一台计算机有4个页框，装入时间、上次引用时间、和每个页的访问位R和修改位M，如下所示： 页 装入时间 上次引用时间
7、 R M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1采用NRU算法将淘汰 页；A. 0 B. 1 C. 2 D. 3【答案】A12.一台计算机有4个页框，装入时间、上次引用时间、和每个页的访问位R和修改位M，如下所示： 页 装入时间 上次引用时间 R M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1采用LRU算法将淘汰 页；A. 0 B. 1 C. 2 D. 3【答案】B 13.一台计算机有4个页框，装入时间、上次引用时间、和每个页的访问位R和修改位M，如下所示
8、： 页 装入时间 上次引用时间 R M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1 采用第二次机会算法将淘汰_页；A. 0 B. 1 C. 2 D. 3【答案】A二、综合题1.4在所列的两种设置中，哪些功能需要操作系统提供支持？ (a)手持设备(b)实时系统。 a. 批处理程序b. 虚拟存储器c. 分时1.4对于实时系统来说，操作系统需要以一种公平的方式支持虚拟存储器和分时系统。对于手持系统，操作系统需要提供虚拟存储器，但是不需要提供分时系统。批处理程序在两种环境中都是非必需的。1.17列出下列操作系统的基本特点：a.批处理b
9、.交互式c.分时d.实时e.网络f.并行式g.分布式h.集群式i.手持式b.a.批处理：具有相似需求的作业被成批的集合起来，并把它们作为一个整体通过一个操作员或自动作业程序装置运行通过计算机。通过缓冲区，线下操作，后台和多道程序，运用尝试保持CPU和I/O一直繁忙，从而使得性能被提高。批处理系统对于运行那些需要较少互动的大型作业十分适用。它们可以被更迟地提交或获得。c.b.交互式：这种系统由许多短期交易构成，并且下一个交易的结果是无法预知的。从用户提交到等待结果的响应时间应该是比较短的，通常为1秒左右。d.c.分时：这种系统使用CPU调度和多道程序来经济的提供一个系统的人机通信功能。CPU从一
10、个用户快速切换到另一个用户。以每个程序从终端机中读取它的下一个控制卡，并且把输出的信息正确快速的输出到显示器上来替代用soopled card images定义的作业。e.d.实时：经常用于专门的用途。这个系统从感应器上读取数据，而且必须在严格的时间内做出响应以保证正确的性能。f.e.网络：提供给操作系统一个特征，使得其进入网络，比如;文件共享。g.f.并行式：每一个处理器都运行同一个操作系统的拷贝。这些拷贝通过系统总线进行通信。h.g.分布式：这种系统在几个物理处理器中分布式计算，处理器不共享内存或时钟。每个处理器都有它各自的本地存储器。它们通过各种通信线路在进行通信，比如：一条高速的总线或
11、一个本地的网络。i.h.集群式：集群系统是由多个计算机耦合成单一系统并分布于整个集群来完成计算任务。j.i.手持式：一种可以完成像记事本，email和网页浏览等简单任务的小型计算机系统。手持系统与传统的台式机的区别是更小的内存和屏幕以及更慢的处理能力。2.3讨论向操作系统传递参数的三个主要的方法。1.通过寄存器来传递参数 2.寄存器传递参数块的首地址 3.参数通过程序存放或压进堆栈中，并通过操作系统弹出堆栈。2.12采用微内核方法来设计系统的主要优点是什么？在微内核中如何使客户程序和系统服务相互作用？微内核方法的缺点是什么？a）增加一个新的服务不需要修改内核 b) 在用户模式中比在内核模式中更
12、安全、更易操作 c) 一个简单的内核设计和功能一般导致一个更可靠的操作系统 用户程序和系统服务通过使用进程件的通信机制在微内核中相互作用，例如发送消息。这些消息由操作系统运送。微内核最主要的缺点是与进程间通信的过度联系和为了保证用户程序和系统服务相互作用而频繁使用操作系统的消息传递功能。3.2 问:描述一下内核在两个进程间进行上下文功换的动作.总的来说，操作系统必须保存正在运行的进程的状态，恢复进程的状态。保存进程的状态主要包括CPU寄存器的值以及内存分配，上下文切换还必须执行一些确切体系结构的操作，包括刷新数据和指令缓存。（书中答案）进程关联是由进程的PCB来表示的，它包括CPU寄存器的值和
13、内存管理信息等。当发生上下文切换时，内核会将旧进程的关联状态保存在其PCB中，然后装入经调度要执行的新进程的已保存的关联状态。3.4 如下所示的程序，说明LINE A可能会输出什么？#include #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 c
14、omplete */ 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(void *par
15、am); /* 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(&attr); pthread_create(&tid, &attr, runner, NULL); pthread_join(tid, NULL); printf(“CHILD: value = %d”, value); /* LINE C*/ else if (pid 0) /
16、* parent process */ wait(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.FCFSP1P2P3P4P512
17、345678910111213141516171819d.e.SJFP2P4P3P5P112345678910111213141516171819f.g.Non-preemptive PriorityP2P5P1P3P412345678910111213141516171819h.i.RR(quantum=1)P1P2P3P4P5P1P3P5P1P5P1P5P1P5P1P1P1P1P112345678910111213141516171819j.b.每个进程在每种调度算法下的周转时间是多少？Turnaround TimeProcessFCFSSJFNPPRR(quantum=1)P110191
18、619P211112P3134187P4142194P5199614Average13.47.2129.2c.每个进程在每种调度算法下的等待时间是多少？ProcessFCFSSJFNPPRR(quantum=1)P10969P210001P3112165P4131183P514419Average9.63.28.25.4d.哪一种调度算法的平均等待时间对所有进程而言最小？SJF5.5下面哪些算法会引起饥饿a.先来先服务b.最短作业优先调度c.轮转法调度d.优先级调度 最短作业优先调度和优先级调度算法会引起饥饿5.7考虑一个运行10个I/O约束（型）任务和一个CPU约束（型）任务的系统。假设，I
19、/O约束任务每进行1毫秒的CPU计算发射一次I/O操作，但每个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毫秒，然后承担上下
20、文切换的任务，而CPU限制任务的执行10毫秒在承担一个上下文切换之前) 。因此，CPU的利用率是20、21.1*100=94%。6.01在生产者和消费者问题中，信号量mutex，empty，full的作用是什么？如果对调生产者进程中的两个wait操作和两个signal操作，则可能发生什么情况？信号量mutex的作用是保证各生产者进程和消费者进程对缓冲池的互斥访问。信号量empty和full均是资源信号量，它们分别对应于缓冲池中的空闲缓冲区和缓冲池中的产品，生产者需要通过wait(empty)来申请使用空闲缓冲区，而消费者需要通过wait(full)才能取得缓冲中的产品，可见，这两个信号量起着同
21、步生产者和消费者的作用，它们保证生产者不会将产品存放到满缓冲区中，而消费者不会从空缓冲区中取产品。在生产者消费者问题中，如果将两个wait操作，即wait(full)和wait(mutex)互换位置，或者wait(empty)和wait(mutex)互换位置，都可能引起死锁。考虑系统中缓冲区全满时，若一生产者进程先执行了wait(mutex)操作并获得成功，当再执行wait(empty)操作时，它将因失败而进入阻塞状态，它期待消费者执行signal(empty)来唤醒自己，在此之前，它不可能执行signal(mutex)操作，从而使企图通过wait(mutex)进入自己的临界区的其他生产者和所
22、有的消费者进程全部进入阻塞状态，系统进入死锁状态。类似地，消费者进程若先执行wait(mutex)，后执行wait(full)同样可能造成死锁。signal(full)和signal(mutex)互换位置，或者signal(empty)和signal(mutex)互换位置，则不会引起死锁，其影响只是使某个临界资源的释放略为推迟一些。6.02 一组合作进程，执行顺序如下图。请用wait、signal操作实现进程间的同步操作。如图示并发进程之间的前趋关系，为了使上述进程同步，可设置8个信号量a、b、c、d、e、f、g、h，它们的初值均为0，而相应的进程可描述为（其中“”表示进程原来的代码）：mai
23、n( )cobeginP1( ) ; 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); ; coend6.03在生产者和消费者问题中，多个生产者进程（Producer Process）和多个消费者进程（Consumer Process）共享一个大小为8的
24、缓冲区，他们的信号量和共享变量设置如下：int nextc=0, nextp=0, buf8;semaphore full; empty; mutex;生产者进程和消费者进程问题的算法描述如下：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(mutex); 3 itemc=bufnextc;4 bufnextp=itemp;
25、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）生产者进程和消费者进程的临界区是哪些？生产者进程的临界区是第4行和第5行；消费者进程的临界区是第3行和第4行。（2）信号量full、empty和mutex的初值是多少?empty = 8 ， full = 0 , mutex = 1 。（3）如果对调生产者进程中的两个P操作即第2行和第3行，以及对调消费者进程中的两个P操作即第1行和第2行，如
26、下所示。可能发生什么情况？Producer Process Consumer Process 1 itemp = rand(); / Generate a number 1 wait(mutex);2 wait(mutex); 2 wait(full);3 wait(empty); 3 itemc=bufnextc; 系统可能会产生死锁。例如，生产者进程得到信号量mutex，但是没有空缓冲区即empty0时，此时生产者进程阻塞；而消费者进程又无法得到信号量mutex，此时消费者进程也阻塞，系统产生了死锁。 （4）上面的生产者和消费者同步算法有一个缺点，在有空缓冲区时，当消费者进程正在临界区时，
27、生产者进程必须等待，反之亦然。您如何可以解决这个问题，以提高生产者和消费者进程之间并发？写出新的生产者进程和消费者进程的同步算法。增加一个信号量mutex1，初值为1，其算法如下：Producer Process Consumer Processint 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);6 signal(mutex1); 6 signal(empty);7 signal(full); 7 cout itemc endl; 6.04有2个合作的进程P1、P2 。他们从一台输入设备读入数据, P1进程读入数据a，P2进程读入数据b。输入设备是一台独享设备 。两个
