操作系统习题课

操作系统原理习题课,作业存在的问题习题讲解,作业存在的问题,部分同学的作业明显是应付，抄袭别人作业前2次作业基本没有大的问题第3，4次作业（CPU调度，进程同步）问题比较多，第3次作业中练习一90%的同学都做错了,CPU调度习题,一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，如下表的作业序列（表中所有作业优先数即为进程优先数，数值越小优先级越高）。要求：（1）列出所有作业进入内存时间及结束时间（2）计算平均周转时间作业名到达时间估计运算时间优先数A10：0040分5B10：2030分3C10：3050分4D10：5020分6,10:00A作业到达,作业A调入内存，进程调度程序调度A运行10:20B作业到达,作业B调入内存,抢占进程A的处理机,A回到就绪队列,A还需运行20分钟10:30C作业到达,在后备队列中等待10:50B运行30分钟后结束运行,D作业到达,后备队列中有C,D两个作业等待调度,根据短作业优先原则,D调入内存.内存中,A在就绪队列上已等待了30分钟,A的优先级高于D,A运行,D就绪.此时C在后备队列中已等待了20分钟并继续等待.,11:10A运行结束,C装入内存,C的优先权高于D,C运行,D继续等待,此时D已等待了20分钟.12:00C运行结束,D运行12:20D运行结束,作业名进入内存时间结束时间A10:0011:10B10:2010:50C11:1012:00D10:5012:20各作业的周转时间为:A:70B:30C:90D:90平均周转时间为(70+30+90+90)/4=70,一个四道作业的操作系统中，设在一段时间内先后到达6个作业，它们的提交时间和运行时间见下表,作业号提交时间运行时间,JOB1JOB2JOB3JOB4JOB5JOB6,8:008:208:258:308:358:40,60352025510,系统采用SJF算法，作业被调度进入运行后不再退出，但当一作业进入运行时，可以调整运行的优先次序。1分别给出上述6个作业的执行时间次序2计算作业的平均周转时间,CPU调度习题,【解析】四道的系统,作业调度最多可选择四道作业进入内存,以进程的形式运行;进程调度采用可抢占的短作业优先调度原则,8：00J1到达，无竞争者，进入内存。8：20J1运行20分钟，剩余40分钟；J2到达，运行时间为35分钟，小于J1，取代J1运行。8：25J1剩余40分钟，J2剩余30分钟；J3到达，运行时间为20分钟，取代J2运行。8：30J1剩余40分钟，J2剩余30分钟，J3剩余15分钟，J4到达，运行时间为25分钟，J3继续运行。8：35J3剩余10分钟，J5到达，运行时间为5分钟，尽管最短，但内存已经有四道作业，因此，J5不可进入内存，J3继续运行。,08：40J3剩余5分钟；J6到达，同理不可以进入内存，J3继续运行。08：45J3运行结束，离开主存。J5最短，进入内存。08：50J5结束，离开。J6进入，运行时间为10分钟，为最短，开始运行。09：00J6结束，离开。J1剩余40分钟，J2剩余30分钟，J4剩余25分钟，J4最短，开始运行。09：25J4结束，离开。J2最短，开始运行。09：55J2结束，J1运行。10：35J1结束。,每道作业的周转时间=结束时间-提交时间J1：8：0010：35周转时间155分钟J2：8：2009：55周转时间95分钟J3：8：2508：45周转时间20分钟J4：8：3009：25周转时间55分钟J5：8：3508：50周转时间15分钟J6：8：4009：00周转时间20分钟平均周转时间：3606=60分钟。,进程同步练习题,并发进程之间有哪几种制约关系？同步与互斥有何区别？答：进程之间的制约关系有两种：间接制约和直接制约。间接制约是由于共享系统资源而导致的制约关系，两个进程之间的同步需要另外的系统进程协调；直接制约是指两个进程在逻辑上有某种关系，两个进程之间的同步通过使用信号量等机制相互制约，而无需通过操作系统的其他进程来协调。例如；两个进程要同时使用同一个打印机，需要通过操作系统的专门进程来协调，这是间接制约。又如；两个进程同时要访问一个共享变量，可以通过使用信号量的方式解决，这是直接制约。,续上页,所谓进程同步是指进程之间存在的一种时序上的等待关系；所谓进程互斥是指进程之间存在的种竞争关系。例如：进程A等待进程B发送给它的消息，这是A与B同步，它们之间没有竞争关系，只有一种时序上的等待关系。又如：进程A要修改共享变量X，进程B此时也要对x进行修改为了保证x的结果正确则A和B需要互斥访问x，所以，A和B此时存在一种对x的竞争关系。,有一阅览室，共有100个座位。读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记内容。试用Pv操作描述读者进程的同步结构。解析：定义信号量以及相应变量mutex:semaphore;互斥信号量full:semaphore;同步信号量table:array0.n-1ofitem;,Procedurereader;beginP(full);P(mutex);Register-name(table);V(mutex);Reading;P(mutex);Delet-name(table);V(mutex);V(full);end,beginSeminitsal(mutex,1;full,100)CobeginReader;Reader;coendend,有一个理发店，有几张椅子和一个理发师。当没有顾客时，理发师睡觉；当有顾客到来时，若发现理发师在睡觉，则唤醒理发师为其理发；如果顾客到来时，理发师正忙着理发，则顾客坐在椅子上等待，如果已没有空闲椅子，则顾客离开。用P/V操作描述理发师和顾客之间的制约关系。,varmutex,customers,barbers:semaphore;waiting,chairs:integer;procedurebarber:beginwhile(true)beginp(customers);p(mutex);waiting:=waiting1;v(mutex);cuthair();v(barbers);endend,procedurecustomer;beginp(mutex);if(waitingchairs)thenbeginwaiting:=waiting+1;v(customers);v(mutex);p(barbers);get-haircut()endelsebeginv(mutex);endend,beginseminitial(mutex,1;barbers,0;customers,0);waiting=0;chairs=10;cobeginbarber;customer;.customer;coendend,把学生和监考老师都看作进程,学生有N人,教师1人.考场门口每次只能进出一个人,进考场原则是先来先进.当N个学生都进入考场后,教师才能发卷子.学生交卷后可以离开考场.教师要等收上来全部卷子并封装卷子后才能离开考场.问题:问共需设置几个进程?试用P、V操作解决上述问题中的同步和互斥关系.,【解析】：定义一个共享变量StudentCounter=N定义三个信号量：M1=1，实现对StudentCounter的互斥问；M2=1，表示学生是否到齐了，教师是否可以发试卷；M3=1，表示试卷是否收齐了，教师是否可以离开共需设置二个进程：学生进程，教师进程,学生：P（M1）；StudentCounter：=StudentCounter-1；IfStudentCounter=0V(M2);V(M1);答题；P（M1）；StudentCounter：=StudentCounter+1；IfStudentCounter=NV(M3);交试卷；离开考场；V(M1);,教师：P（M2）；发试卷；巡视考场；收试卷；P（M3）；离开,流水线问题某流水线有4个并发工序P1、P2、P3、P4，他们执行情况如下：P1先执行；P1结束后，P2，P3同时开始执行，P2，P3都结束后，P1才能继续下一次执行，同时P4开始执行。试用PV操作实现他们之间的同步。,【解析】：SA12,SB12,SA13,SB13,SB24,SB34;SemophoreSA12:=SA13:=1;SB12:=SB13:=SB24:=SB34:=0;,ProcessPCBeginP(SB13)执行P3V(SB34)V(SA13)End;(PC),ProcessPBBeginP(SB12)执行P2V(SB24)V(SA12)End;(PB),ProcessPDBeginP(SB24)P(SB34)执行P4End;(PD),ProcessPABeginP(SA12)P(SA13)执行P1V(SB13)V(SB12)End;(PA),某数据库有一个写进程，N个读进程，他们之间读写操作的互斥要求是：（1）写进程正在写该数据库时，不能有其他进程读该数据库。（2）读进程之间不互斥，可以同时读该数据库。（3）如果有若干进程正在读该数据库，一个写进程正在等待写，则随后欲读的进程也不能读该数据库，需等待写进程先写。,解法一：Rc=0；wc=0;/共享变量Mutex=1;wr=1/互斥信号量READER：Whilewc=1doskip;-若有写进程请求，则后续读不响应P(mutex);Rc:=Rc+1;IfRc=1thenP(wr);-若是第一个读进程，则要看有无写进程V(mutex);READINGP(mutex);Rc:=rc-1;Ifrc=0thenV(wr);-若所有读进程都执行完，可以让其它进程读写V(mutex)WRITER：Wc:=1;P(wr);WRITING;Wc:=0;V(wr),解法二：另外设置一个信号量w=1；用于写进程到达后封锁后续读进程READER：P(w);P(mutex);Rc:=rc+1;Ifrc=1thenP(wr);-若是第一个读进程，则要看有无写进程V(mutex);V(w);READINGP(mutex);Rc:=rc-1;Ifrc=0thenV(wr);-若所有读进程都执行完，可以让其它进程读写V(mutex)WRITER：P(w);P(wr);WRITING;V(wr)V(w);,隧道问题：一座山中有一条隧道，规定每次只允许一辆车过隧道。现在山南、山北都有车要过隧道，如果把每个过隧道者看作一个进程，为保证安全，请用PV操作实现正确管理。,beginS:semaphore;S:=1;cobeginprocess(S-N)i(i=1,2)beginP(S);过隧道;V(S);end;process(N-S)i(i=1,2)beginP(S);过隧道;V(S);end;,设在公共汽车上，司机和售票员的活动分别如下：司机的活动：启动车辆；正常行车；到站停车。售票员的活动：关车门；售票；开车门。问题:在汽车不停地到站、停车以及行驶的过程中，司机和售票员之间的活动有什么同步关系？,解答：首先分析两个进程之间的同步关系。汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号司机接到开车信号后起动车辆在汽车正常行驶过程中售票员售票到站时司机停车售票员在车停后开车门让乘客下车定义两个信号量s1：表示是否允许司机起动车辆，s2：表示是否允许售票员开门。初值为0。,请将以下描述这两个活动的PV操作补充完整：,Semaphores1=0;Semaphores2=0;main()cobegindriver();conductor();Coend;,driver()while(1)p(s1);启动车辆；