P（S1）；

       从bufferl复制信息；

       V（Snl）；

       V（S1）；

       P（Sn2）；

       P（S2）；

      将复制的信息放入buffer2；

       V（Sm2）；

       V（S2）；

     goto L2

     End

    Process produce put

      Begin

        L3：P（Sm2）；

        P（S2）；

        从buffer2取信息；

        V（Sn2）：

        V（S2）；

        把信息从打印机输出；

        Goto L3

      End

     Coend；

    END

    八、（本题8分）

    设每个进程对共享资源的最大需求量为x（0<x≤m），由于每个进程最多申请使用x个资源，在最坏情况下，每个进程都得到了（x-1）个资源，并且都需申请最后一个资源。这时系统剩余资源数为：m-n（x-1）。只要系统还有一个资源可用，就可使其中的一个进程获得所需的全部资源，该进程运行结束后释放出它所占用的资源，其他进程的资源需求也可得到全部满足。因此，当m-n（x-1）≥1时，即x≤（m+n-1）/n时系统不会发生死锁。进而可得系统中所有进程最大需求量之和nx≤（m+n-1）时系统不会发生死锁。该题中，所有进程最大需求量之和小于m+n，所以，该系统是死锁无关的。

西北大学2000年研究生入学考试题参考答案

一、（每小题3分，共15分）

1．若干个事件在同一时刻发生称为并行；若干个事件在同一时间间隔内发生称为并发。并行是并发的特例，并发是并行的拓展。

2．对换是指把内存中暂时不能运行的进程或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程或进程所需的程序和数据换入内存。切换是指将CPU的使用权从一个进程转到另一个进程。在某些系统中，进程切换往往伴随着信息的对换。

3．管道（Pipe）是连接两个进程的一个共享文件，进程通过对该文件的读、写实现进程间的通信。管道文件实际上是一个临时文件，它以磁盘为中介实现进程间的通信，与内存相比，其通信速度较慢。通道（I/O处理机）是实现I/O操作的硬件装置。通道对管道的实现提供子硬件支持。  

4．消息系统有直接通信和间接通信之分。  

    （1）直接通信。直接通信方式有一个基本原则：进程在发送和接收消息时，必须指明接收者或发送者的名字。这种通信方式中Send和Receive原语定义如下：

    Send（P，message），将消息发送给进程P；

    Receive（Q，message），接收来自进程Q的消息。

    这种通信方式中通信链路具有如下特征：每一对欲通信的进程间自动建立了一条双向通信链，只需知道对方的标识信息便可进行通信；每条通信链路严格地对应两个进程；相互通信的一对进程之间存在一条通信链路。

    （2）间接通信。进程间通过信箱进行消息传递的通信方式称为间接通信，又称为“信箱通信”；信箱（Mailbox）可以抽象地看成是一个虚设备，进程可以把消息（也称信件）放入信箱，也可以从中取出一条消息。信箱必须有唯一的标识符。在这种通信方式中，某个进程可以通过一组不同的信箱同时与其他多个进程通信。两个进程之间只有当它们有一个可共享的信箱时才可进行通信。

    间接通信方式中的通信链路具有如下特征：只有当两个进程有了一个可共享的信箱时，通信链路才在两者之间建立；一条通信链路可以连接两个以上的进程；每一对通信进程之间可以有多条不同的通信链路，每一条链路对应一个信箱；通信链路可以是单向的，也可以是双向的。

    5.死锁是因竞争资源而引起的一种具有普遍性的现象，在多道程序系统中，由于多个并发进程共享系统的资源，如使用不当有可能造成一种僵局，即系统中两个或多个进程无限期地等待永远不会发生的条件，在无外力的干预下，这些进程都不能向前推进，我们称之为死锁。死锁不仅在两个进程之间发生，也可能在多个进程之间，甚至在系统全部进程之间发生。当死锁发生时，一定有一个资源被无限期地占用而得不到释放。  

    “饿死”是指系统中的每个资源占用者都在有限的时间内释放它所占用的资源，但是仍然存在申请者永远得不到资源的现象。因此，在操作系统中，不仅要考虑如：何防止“死锁”，还要考虑如何避免“饿死”。

    二、（10分）

    1.操作系统中有三级调度：高级调度（作业调度）、中级调度（交换调度）和低级调度（进程调度）。它们构成系统内的多级调度。不同类型的操作系统不一定完全都实现上述三种调度。  

    2.处理机三级调度发生的情况是：

    （1）高级调度。高级调度是根据系统内所有资源的使用情况，一旦可能便从后备作业中选择一道作业进入系统，并创建相应的进程，分配必要的系统资源，然后将进程“就绪”。

    （2）低级调度。低级调度即为CPU调度，它是根据CPU资源的使用情况及时分配CPU。即从“就绪”的进程中选择一个进程在CPU上“运行”。这种调度不仅要求调度算法本身的时间复杂度小，而且要求策略精良，因为低级调度直接影响着系统的整体效率。在多道程序系统中必须提供低级调度。

    （3）中级调度。在内存中常常有许多进程处于某种等待状态，这些进程在“等待”期间无谓地占用着内存资源。如将它们暂时换至外存，则所节省出来的内存空间可用以接纳新的进程，一旦换出外存的进程，具备运行条件时再将其重新换入内存。为此，在逻辑上将主存延伸，用一部分外存空间（称为交换区）替代主存，并且实施交换调度（中级调度）。在各种类型的操作系统中可以根据内存的配置、系统能承受的最大负载有选择地进行中级调度，或者不实施中级调度。

    3．高级调度完成作业调度，使“后备”状态的作业变为“执行”状态；中级调度完成内存和外存信息的交换调度；低级调度完成进程调度，使“就绪”的进程在CPU上“运行”。

    三、（10分）

    本题是典型的读者—写者问题。查询操作是读者，订票操作是写者，而且要求写者优先。

    为了达到这一控制效果，可以引入了一个变量rc，用于记录当前正在运行的读者进程数。每个读者进程进入系统后须对rc值加1。当rc值由0变为1时，说明是第一个读者进程进人，因此需要该读者进程对控制写者进程的信号量Srw进行P操作，以便与写者进程互斥运行；当rc值由非0值增加时，说明不是第一个读者进程，此时控制写者进程的信号量已经过P操作控制禁止写者进程进入，因此不需要再次对该信号量进行P操作。当读者进程退出时，须对rc做减1操作。如发现减1后rc值变为0，说明是最后一个读者进程退出，因此需要该读者进程对控制写者进程的信号量Srw进行V操作，以便使写者进程能够进入。资源计数变量rc也是一个临界资源，需要用信号量Src对它进行互斥访问控制。为了提高写者的优先级，我们还增加了一个信号量S，用以在写进程到达时封锁其后续的读者进程。用户查询与订票的逻辑框图如图附3—1所示(图略)。

    四、（10分）

    由于短作业优先算法会使系统平均响应时间最短，所以：

    当0<x<3，应该采用的运算顺序为：x，3，5，6，9；

    当3≤x≤5，应该采用的运算顺序为：3，x，5，6，9；

    当5<x<6，应该采用的运算顺序为：3，5，x，6，9；

    当6≤x≤9，应该采用的运算顺序为：3，5，6，x，9；

    当x>9，应该采用的运算顺序为：3，5，6，9，x。

    五、（10分）

    1．在分页存储管理中，当访问一条指令或数据时需要访问内存至少两次。一次是访问存放在内存的页表PMT，实现地址变换；另一次是访问所需的数据。

    在分段存储管理中，当访问一条指令或数据时，也需要访问内存至少两次。一次是访问存放在内存的段表SMT，实现地址变换；另一次是访问所需的数据。

    在段页式存储管理中，当访问一条指令或数据时，需要访问内存至少三次。一次是访问存放在内存的段表SMT，查找段号所对应的页表；再一次是访问存放在内存的页表PMT，实现地址变换；第三次是访问所需的数据。

    2．若快表的命中率是85％，则有效存取时间为：

0.85X1+（1—0.85）X（1+1）二1.15μs

若快表的命中率为50％，则有效存取时间为：0.5X1+（1—0．5）X（1+1）=1.5μs。

    六、（10分）

    1.内存利用率不高主要表现为以下方面：

    （1）内存中存在着大量的、分散的、难以利用的碎片；

    （2）暂时或长期不能运行的程序和数据占据了大量的内存空间；

    （3）当作业较大时内存只能装入少量的作业，当它们被阻塞时将使CPU空闲，从而也降低了内存的利用率；  

    （4）内存中存在着重复的拷贝。

    2.可采用下列方法和途径来提高内存利用率：

    （1）改连续分配方式为离散分配方式，以减少内存的碎片；

    （2）增加兑换机制，将那些暂时不用的程序和数据从内存换到外存；

    （3）采用虚拟存储管理技术，使更多的作业能装入内存，使CPU更加忙碌；

    （4）引入动态装入和连接机制，尽量避免装入本次运行中不用的程序；

    （5）引入存储器共享机制，允许一个正文段或数据段被若干个进程共享，以减少内存中的重复拷贝。

    七、（10分）

    1．两种常用的I/O调度算法是：

    （1）先请求先服务。当有多个进程对同一设备提出I/O请求时，该算法把所有I/O请求进程按请求顺序排成一个等待队列。I/O调度程序把该I/O设备分配给队列中的第一个进程。

    （2）优先权高者优先。该算法把所有I/0请求进程按优先权由高到低的顺序排成一个等待队列。I/0调度程序把该I/0设备分配给队列中的第一个（其优先权最高）进程。

    在I/0调度中不能采用时间片轮转法。因为在I/0操作中，有些设备的固有属性是独占性，一经某进程占用，便一直到使用完该设备才能释放。而且在由通道控制的I/O系统中，通道程序一经启动便一直进行下去，直到最后完成。在它完成之前不会产生中断。

    2．UNIX操作系统中调用getblk过程分配缓冲区。当要读磁盘数据时，核心首先检查要读入的盘块内容是否已在某个缓冲区中，若发现已在某个缓冲区中，便不必再从磁盘上读人。仅当数据未在任何缓冲区中时，核心才须从磁盘上将数据读入，这时才须为其分配一空闲缓冲区。类似地，当要把数据写入一特定盘块时，核心应先检查该块内容是否已在某缓冲区中，仅当该块内容不在缓冲区中时，才须分配一空闲缓冲区。获取空闲缓冲区时应提供的输入参数是文件系统号和磁盘块号；Getblk过程分配缓冲区时，可分为两种情况：

    （1）缓冲区在散列队列上。进入geblk过程后，首先根据文件系统号和盘块号去查找散列队列，若找到与文件系统号和块号相匹配的缓冲区，便可进一步检查该缓冲区是否空闲。若空闲，则应先上锁，以防止其他进程对它进行访问，然后把它从空闲链上摘下；若忙，则表明缓冲区已被其它进程上锁，因此，暂时不能对它进行访问而进入睡眠，直到该缓冲区变为空闲时再将它唤醒。

    （2）缓冲区不在散列队列上。若在散列队列中找不到与文件系统号及块号相匹配的缓冲区，便只有从空闲链表中找一个缓冲区。若空闲链表已空，则无法进行分配，进程睡眠，直到空闲链表中出现缓冲区为止；若空闲链表不空，这时可从链首摘下一缓冲区，若此缓冲区标记有“延迟写”，此时应将该缓冲区内容异步地写到磁盘上，再从空闲链表中摘下一个缓冲区，并调整该缓冲区所在的散列队列，即将该散列队列从原来的散列队列调整到新的散列队列中。因为当该缓冲区重新分配后，缓冲区对应的盘块号发生了变化，从而也相应地改变了其所在的散列队列。

    八、（10分）

    1.由于文件存储设备是分成若干个大小相等的物理块，并以块为单位来交换信息的，因此，文件存储空间的管理实质上是空闲块的组织和管理问题，它包括空闲块的组织、空闲块的分配与回收等。下面是三种在文件存储空间管理中常用的技术。

    （1）空闲文件目录   

    一个空闲文件是由文件存储器上连续的空闲块组成的。系统为所有的空闲文件建立一个单独的目录表。每个表目对应一个空闲文件，记录该空闲文件的起始块号和块数。

    空闲文件的分配与回收算法与内存管理中的可变式分区管理方法相似，同样可以采用最先适应算法、最佳适应算法；最坏适应算法等。   

    （2）；空闲块链

    空闲块链把文件存储设备上的所有空闲块链接在一起。当申请者需要空闲块时，分配程序从链首取下所需的空闲块，然后调整链首指针。反之，当回收空闲块时，把释放的空闲块逐个插入空闲链上。这种方法的优点是分配和回收一个空闲块的过程都非常简单，缺点是空闲块链可能很长。改进酌办祛是采用空闲盘区链接法或成组链接法。

  （3）位示图

     位示图利用一个二进制位来记载一个物理块的使用情况。系统为每个文件存储设备建立一张位示图，反映文件存储设备所有物理块的使用情况。每个物理块对应位示图上的一位，如果该位为0，则表示所对应的块是空闲的，反之，则表示所对应的块已被分配。利用位示图来进行空闲块分配时，只须查找图中为0的位，并将其置1；反之，回收时只须把相应的位由1改为0。由于位示图很小，可以将它保存在内存中。

    2.在UNIX操作系统中的文件存储介质可采用磁盘或磁带。通常把每个磁盘或磁带看作是一个文件卷，在每个文件卷上可以存放一个具有独立目录结构的文件系统。一个文件卷包含许多物理块。0^#块一般用于系统引导或空闲，1^#块称为超级块，用于存放文件卷的资源管理信息，从2^#块起开始的若干块用于存放磁盘索引节点（具体块数由文件系统的大小决定），以后各块存放文件数据。   

    UNIX操作系统采用成组链接法对空闲盘块加以组织。该方法首先把文件存储设备中的所有空闲块按50块（或100块，下同）划分为一组，组的划分按从后往前的顺序划分，每组的第一块用来存放前一组中各块的块号和总块数。由于第一组的前面再也没有其他组存在，因此第一组的块数为49块。最后一组可能不足50块，而且由于该组后再也没有其他组，所以，该组的物理块号与总块数只能存放在管理文件存储设备用的文件资源表（超级块的一部分）中。系统在初启时把文件资源表复制到内存，从而使文件资源表中存放有最后一组空闲块号和总

块数的堆栈进入内存，空闲块的分配与回收可在内存中进行。

    当申请者提出申请空闲块要求时，盘块分配程序从栈顶取出一空闲盘块号，将其对应的盘块分配，然后栈顶指针下移一格，总空闲块数减1。若该盘块是栈底，则将该块中存放的下一组的块号和总块数读人内存，然后才将该盘块分配，并重置栈顶指针。

    在系统回收空闲盘块时，栈顶指针加1，把回收的空闲块号填人栈顶位置，空闲块数加1。如果栈顶指针等于50，表示该组已满，须把当前栈所有的50个块号与块数写入新回收的空闲块中，重置栈顶指针。

九、（10分）

    1.在UNIX操作系统中，有下列三种类型的文件：

    （1）目录文件。目录文件是文件系统中树型结构的分支结点，它可以包含普通文件和次一级目录文件。目录文件也同普通文件一样存储在外存的文件系统存储区。

    （2）普通文件。普通文件是指系统程序或用户程序以及可执行的目标程序等。在详细列出文件内容时，在行首用“”符号表示是普通文件。普通文件按拥有的信息量大小又可分为小型文件、中型文件、大型文件和巨型文件四种。

    （3）特别文件。特别文件是与硬件有关的文件。在UNIX中每个I/0设备都被看成是一个特别文件，为了检索和处理方便，系统把所有I/0设备都放在/der目录文件中，例如打印机是一个特别文件，可以写成/dep/lp。特别文件不包含信息，他们是操作系统标准I/0设备的通道，是用户与硬件设备连接的桥梁。当用户将数据写到文件“/dev/lp”中时，操作系统核心截取了这些数据，并把它们输出到打印机上打印出来。对用户来说，对特别文件的操作与对普通文件的操作是一样的。用户不需要启动设备驱动程序。有关硬件设备的操作均由操作系统

完成。在目录表中，特别文件在行首用字母“b”表示。

    2．当用户不再使用一个已打开的文件时，应调用close过程将该文件关闭，即断开用户程序与该文件之间已建立的通路。在UNIX系统中，由于允许一个文件被多个进程所共享，故只有在没有进程需要此文件时，即文件索引节点中的引用计数减1后为0时，才能真正关闭该文件。其语法格式如下：

    in close（fd）；int fd；

其中，fd是文件打开操作返回的文件描述符。

    在执行close过程时，核心首先根据用户文件描述符fd从相应的用户文件描述符表中获得指向文件表项的指针，再对该文件表项的引用计数做减1操作。

    close的处理过程如下：

    （1）若其结果值不为0，表示仍有其他进程在使用该文件表项，不能回收该文件表项。此时，仅将fd所在的用户文件描述符表项置为空。

    （2）若其结果值为0，表示无用户使用该文件表项，核心便可将对应的文件表项置为空，并进一步对其内存索引节点的引用计数做减1操作。若结果不为0，表明仍有进程在访问该文件，故不能回收其内存索引节点。

    （3）仅当内存索引节点的引用计数为0时，才能回收该内存索引节点，即将指定文件关闭。

    3．UNIX系统的文件逻辑结构采用流式文件。根据逻辑文件的字节偏移量可计算出该字节所在的物理块号。计算过程分两步，第一步是将逻辑文件的字节偏移量转换为文件的逻辑块号和块内偏移量。其转换方法是：将逻辑文件的字节偏移量整除以盘块大小的字节数，所得的商即为文件的逻辑块号，余数就是块内偏移量。第二步是将文件的逻辑块号转换为物理块号。其转换方法是：使用多重索引结构，在索引节点中根据逻辑块号通过直接索引或间接索引找到相应的物理块号。

    因为L1=INT（9000，1024）=8，  B1=MOD（9000，1024）=808；

    L2=NT（18000，1024）=17，      B1=MOD（18000，1024）=592；

    L3=NT（420000，1024）=410，    B1=MOD（420000，1024）=160。

  所以，当文件的字节偏移量为9 000时，其逻辑块号为8，只需在该文件的索引节点中直接索引

  （1—addr[7]）即可找到相应的物理块号。当文件的字节偏移量为18 000时，其逻辑块号为17，需在该文件的索引节点中通过一次间接索引（1—addr[10]）即可找到逻辑块号相应的物理块号。当文件的字节偏移量为420000时，其逻辑块号为410，需要在该文件的索引节点中通过（1—addr[ll]）二次间接索引即可找到逻辑块号对应的物理块号。

    十、（5分）

    分布式操作系统是以实现并行任务分配、并行进程通信和分布控制的机构和实现分散资源管理等功能为目的的系统程序。网络操作系统是以资源共享和信息交换为目的的操作系统。分布式系统和网络操作系统都是多机系统的支撑软件，都基于I/O或网络互联，但在很多情况下，网络操作系统是在本机局部操作系统之上建立的，形成了两个层次，而分布式操作系统则是一个独立的整体。

    分布式操作系统与传统的集中式操作系统的主要区别表现在通信、资源管理和系统结构三个方面。因此，分布式操作系统在传统的操作系统管理模式上还应增加网络管理模块，即通讯软件和网络控制软件。

西安理工大学2000年研究生入学考试题参考答案

  一、名词解释（5X2分=10分）

    1．系统调用是用户在程序中能用“访管指令”调用的由操作系统提供的子功能的集合。每一个子功能称为一条系统调用命令（或广义指令）。系统调用是操作系统在程序级给用户提供的接口。

     2．多道程序设计是指在主存中同时存放多道用户作业，它们都处于执行的开始点和结束点之间。

    3．所谓周转时间是指作业从进入系统到处理完成所经历的时间。

    4．所谓碎片是指存储器上不能利用的空闲区。

    5．在分页存储系统中，将某一页从实存移到辅存为“出页”，从辅存调入主存为“入页”。刚“出页”的页又要“入页”，或刚“入页”的页又要“出页”。这种反复出入页的现象称为“抖动现象”或者“系统颠簸”。

    二、单项选择题（10X2分=20分）

    1．C    2．A    3．A    4．B    5．B    6．A    7．C    8．D    9．B    10．D

    三、填空题（每空1分，共10分）

    1．标志    实体

    2．磁带    磁盘

    3．CAW（通道地址字）    CSW（通道状态字）