《操作系统应用题剖析》由会员分享，可在线阅读，更多相关《操作系统应用题剖析（21页珍藏版）》请在金锄头文库上搜索。
1、应 用 题61、 设系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P、V操作写出这些进程使用打印机的算法。解： 因为打印机是一种临界资源，所以这三个进程只能互斥使用这台打印机，即一个用户的计算结果打印完之后，另一个用户再打印。设三个进程分别为A、B和C。设一个互斥信号量mutex，其初值1。 A进程 B进程 C进程 P(mutex) P(mutex) P(mutex) 使用打印机 使用打印机 使用打印机 V(mutex) V(mutex) V(mutex) 2、判断下面的同步问题的算法是否正确？
2、若有错，请指出错误原因并予以改正。（1）设A、B两进程共用一个缓冲区Q，A向Q写入信息，B则从Q读出信息，算法框图如图所示。注：信号量S的初值为0（2）设A、B为两个并发进程，它们共享一临界资源。其运行临界区的算法框图如图所示。注：信号量S1、S2的初值均为0解： 这个算法不对。因为A、B两进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从Q中读出完整的信息。改正：A、B两进程要同步使用缓冲区Q。为此，设立两个信号量： empty表示缓冲区Q为空，初值为1; full表示缓冲区Q为满，初值为0。 算法框图如图1所示。 这
3、个算法不对。因为A、B两个进程是并发的，它们共享一个临界资源，所以二者应互斥地使用该临界资源，在进入临界区时不存在A先B后的时序关系，而是哪个进程先到一步就先进入自己的临界区。改正：A、B两个进程应互斥地进入临界区。为此，设立一个信号量：互斥信号量mutex，其初值为1。 算法框图如图2所示。 A进程 B进程 A进程 B进程 P(empty) P(full) P(mutex) P(mutex) P(mutex) 向Q写入信息 从Q中读出信息 临界区代码CSa 临界区代码CSb V(full) V(empty) V(mutex) V(mutex) V(mutex) 图1 图 2 3、设有一台计算
4、机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后在搬到缓冲区B2中，并在打印机上印出，问：系统要设几个进程来完成这个任务？各自的工作是什么？这些进程间有什么样的相互制约关系？用P、V操作写出这些进程的同步算法。解：系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。R进程受C进程影响，B1放满信息后R进程要等待等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P
5、进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。信号量含义及初值：B1full 缓冲区B1满，初值为0；B1empty缓冲区B1空，初值为0；B2full 缓冲区B2满，初值为0；B2empty缓冲区B2空，初值为0；4、设有三个批作业JOB1、JOB2、JOB3，其到达时间、处理时间及完成时间如下：作业 作业到达时间（时） 开始处理时间（时） 处理完成时间（时）JOB1 15 18 22JOB2 18 21 23JOB3 17 19 21试计算：（1）各个作业的周转时间；
6、（2）所有作业的平均周转时间；解： 作业 周转时间 等待时间 JOB1 7 3 JOB2 5 3 JOB3 4 2所有作业的平均周转时间5.335、假定在单CPU条件下有下列要执行的作业：作业 运行时间 优先级1 10 22 4 33 3 5作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？解：(1) 非抢占式优先级算法 作业1 作业3 作业2 | |
7、 | | t 10 13 17 (2) 和（3） 作业到达时间运行时间完成时间周转时间带权周转时间101010101.021417164.032313113.7平均周转时间12.3平均带权周转时间2.96、某段表内容如下：段号 段首地址 段长度0 120K 40K1 760K 30K2 480K 20K3 370K 20K一逻辑地址为（2，154）的实际物理地址是多少？ 解：480K+154。7、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号 物理块号0 31 72 113 8则逻辑地址0A5C(H
8、)所对应的物理地址是什么？要求：写出主要计算过程。解：逻辑地址0A5C(H)所对应的二进制表示形式是： 0000 1010 0101 1100 所对应的页号是： 2 （十进制） 查页表，得到物理块号是： 11 （十进制） 拼接后，得到物理地址： 2E5C(H)8、对于如下的页面访问序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）解：FIFO淘汰算法： 内存块为3时，缺页中断（或称缺页次数、页面故障）为9；内存块为4时，缺页
9、中断为10。（这似乎是一个奇怪的现象，同时也告诉我们，操作系统是一个复杂的机构，直观是靠不住的！）LRU淘汰算法：内存块为3时，缺页中断为10；内存块为4时，缺页中断为8。9、试以某航空公司为两旅行社a和b的顾客预订飞机票为例，说明互斥的含义。 答 某航空公司为两旅行社a和b的顾客预订飞机票，飞机票是互斥内容。假设为a订完了机票，b就不能再订票。10、试以生产者-消费者问题为例，用操作说明进程同步问题的实质。 答 一个生产者，一个消费者和一个产品之间关系是典型的进程同步问题。设信号量s为仓库内产品，p-v操作配对进行缺一不可。生产者进程将产品放入仓库后通知消费者可用；消费者进程在得知仓库有产品
10、时取走，然后告诉生产者可继续生产。 11、在UNIX 系统中，其进程调度方式是什么？引起进程调度的时机有那些？解 UNIX系统中，进程的调度采用多级反馈队列轮转调度方式。引起进程调度的时机有：（1）当前进程的时间片用完，由核心将当前进程放入下一级的优先级队列的末尾，并调度另一进程运行；（2）在当前进程执行了sleep例程，进入睡眠状态而放弃处理机时；（3）进程通过核心执行了自我终止的系统调用exit时；（4）在执行完系统调用而返回到用户态时，如果此时系统中已出现了更高优先级的进程在等待运行，此时核心将剥夺当前进程的执行；（5）当核心完成中断处理，控制被返回到用户态而要执行原进程时，若有更高优先
11、级的进程在等待运行，等等。12、为什么要打开文件？叙述在UNIX文件系统，打开文件/home/user01/myfile的过程？解：当用户要求对一个文件实施多次读/写或其他操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，在大多数OS中都引入了“打开”（open）这一文件系统调用，当用户第一次请求对某文件进行操作时，先利用open系统调用将该文件打开。在UNIX文件系统，打开文件/home/user01/myfile的过程四步：（1）检索目录 核心先调用检索目录过程namei从根目录或从当前目录开始，沿目录树查找指名文件的索引结点。在查找时，利用线性检索法，将文件路径名中的各分量名，与相应目录文件中的文件名逐一进行比较。若未找到指名文件，或者该文件不允许存取，便做出错处理；否则，进入第二步。（2）分配内在索引结点如果该文件已被其他用户打开，此时只需对在第一步中所找到的i结点，执行其引用计数加1的操作；否则，应为被打开文件分配一内存i结点，并调用磁盘读过程将磁盘i结点的内容拷贝到内存 i 结点中，并设置i.count为1。（3）分配文件表 这是指为已打标开的文件分配一个文件表项,使文件表项中的 f. node指向内存索引结点。通常还将读写指针f.offset置为 0，以表示从头开始读写此文件；置读写标志 fflag，及将文件的引用计数fcount加 1，并记入该表项的首
