解答题

1.某分时系统的进程出现如下图所示的状态变化。试问：（1）你认为该系统采用的是哪一种进程调度算法？（这一问要等学习了第3章处理机调度后回答）（2）写出图中所示的每一个状态变化的原因（从①到⑥）。③⑤⑥①②就绪进程队列④某分时系统的进程状态变化1.解：（1）该分时系统采用的进程调度算法是时间片轮转法。（2）状态变化的原因如下：①进程被选中，变成运行态；②时间片到，运行的进程排入就绪队列尾部；③运行的进程启动打印机，等待打印；④打印工作结束，阻塞的进程排入就绪队列尾部；⑤等待磁盘读文件工作；⑥磁盘传输信息结束，阻塞的进程排入就绪队列尾部。2.设有无穷多个信息，输入进程把信息逐个写入缓冲区，输出进程逐个从缓冲区中取出信息。设缓冲区是环形的，编号为0n-l，in和out分别是输入进程和输出进程使用的指针，初值都是0。试分别回答下列问题：(1)输入、输出两组进程读/写缓冲区需要什么条件？(2)根据下面输入、输出进程的同步算法，给出信号量含义、初值并填写相应的P、V操作。2.解：（1）针对容量为n的环形缓冲区，输入、输出两组进程读/写缓冲区需要的条件为：①输入进程和输出进程需同步执行，即输入进程写缓冲区后，输出进程才可以读；②由于缓冲区容量有限，因此任一时刻所有输入进程存放信息的单元数不能超过缓冲区的总容量（n）；③同理，所有输出进程取出信息的总量不能超过所有输入进程当前写入信息的总数。（2）为使两类进程实行同步操作，应设置三个信号量：两个计数信号量full和empty，一个互斥信号量mutex。full：表示放有信息的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为n。mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。A：P(empty);B：P(mutex);C：V(mutex);D：V(full);E：P(full);F：P(mutex);G：V(mutex);H：V(empty);3.假定在单CPU条件下有下列要执行的作业，如下表所示。作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。作业运行时间优先级1103211323414552（1）用一个执行时间图描述在执行非抢占式优先级行算法时这些作业的情况。（注意，数字大的优先级高）（2）计算作业的周转时间、平均周转时间、带权周转时间和平均带权周转时间。3.解：（1）非抢占式优先级的执行时间图，如下图所示。作业1作业4作业3作业5作业201011131819t（2）作业到达时间运行时间完成时间周转时间带权周转时间101010101.0211191818.032213115.54311188.054518142.8平均周转时间12.2平均带权周转时间7.064.某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一位用户的页表中，已调入内存页面的页号和物理块号的对照表如下：计算逻辑地址0A5C(H)所对应的物理地址（要求写出分析过程）。页号物理块号0511024374.解：页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知页内地址占10位。由“内存为16KB”，可知有16块，块号为4位。逻辑地址0A5C（H）所对应的二进制表示形式是：000101001011100，根据上面的分析，下划线部分为页内地址，编码“00010”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：0100，拼接块内地址1001011100，得物理地址为01001001011100，即125C（H）。5.考虑下面存储访问序列，该程序大小为460字：10，11，104，170，73，309，185，245，246，434，458，364设页面大小是100字，请给出该访问序列的页面走向。又设该程序基本可用内存是200字，如果采用先进先出置换算法(FIFO)、最佳置换算法（OPT），缺页率是多少？（注：缺页率＝缺页次数/访问页面总数，要求写出计算过程）5.解：根据已知条件页面大小是100字，将页面访问序列简化为：0，0，1，1，0，3，1，2，2，4，4，3又因为该程序基本可用内存是200字，可知内存块数为2。采用先进先出置换算法(FIFO)，共有6次缺页，缺页率为6/12=50%，具体算法如下：页面走向001103122443块1003344块211223缺页缺缺缺缺缺缺采用最佳置换算法（OPT），共有5次缺页，缺页率为5/12=41.6%，具体算法如下所示。OPT置换算法页面走向001103122443块100333块21124缺页缺缺缺缺缺6.设Linux文件系统中的目录结构如下图所示：(1)Linux的文件系统采用的是哪一种目录结构？有什么优点？(2)设当前工作目录是/usr，那么，访问文件m1.c的绝对路径名和相对路径名各是什么？(3)现在想把工作目录改到liu，应使用什么命令（写出完整命令行）?(4)如果用ls–l/usr/mengqc/mub1命令列出指定目录的内容，其中有如下所示的一项：-rw-r-----2mengqcgroup198Jun232013m2.c那么，该文件m2.c对文件主、同组用户、其他用户分别规定了什么权限？6解：(1)UNIX的文件系统采用的是带链接的树形目录结构，即非循环图目录结构。其优点是易于实现文件共享。(2)访问文件m1.c的绝对路径名是：/usr/mengqc/mub1/m1.c访问文件m1.c的相对路径名是：mengqc/mub1/m1.c(3)cd/usr/liu或者cdliu(4)文件主权限是可读、可写，但不可执行；同组用户权限是只可读：其他用户权限是无，即不能读、写成执行。图1所示为进程状态转换图。试回答：什么事件引起每次显著的状态变迁？就绪→运行：CPU空闲，就绪态进程被调度程序选中。运行→就绪：正在运行的进程用完了本次分配给它的CPU时间片。运行→阻塞：运行态进程因某种条件未满足而放弃对CPU的占用，如等待读文件。阻塞→就绪：阻塞态进程所等待的事件发生了，例如读数据的操作完成。图1所示为进程状态转换图，试回答下述状态变迁因果关系能否发生？为什么？(A)21(B)32(C)41下述状态变迁：(A)32：不可以。任何时候一个进程只能处于一种状态，它既然由运行态变为阻塞态，就不能再由运行态变为就绪态。(B)41:可以。某一阻塞态进程等待的事件出现了，而且此时就绪队列为空，该进程进入就绪队列后马上又被调度运行。运行等待打印机输出结果等磁盘读文件