苏州科技大学-操作系统复习JU-JI自整

考试题型选择题 40分 20题名词解释题 20分 5题4分简答题 30分 5题6分分析题 10分 1题2021-7-5真题名词解释操作系统操作系统是一组控制和管理计算机硬件和软件资源，合理的对各类作业进行调度，以及方便用户使用的程序的集合。死锁多个进程在运行过程中因争夺资源而造成的一种僵局。临界资源将一次仅允许一个进程使用的资源称为临界资源。文件文件是由创建者所定义的、具有文件名的一组相关元素的集合。虚拟盘解答进程调度计算题缺页置换计算题分页存储管理是什么，地址转换图分页式存储管理是将用户程序的地址空间分为若干个固定大小区域，称为“页”或“页面”。相应的，也将内存空间分为若干个物理块或页框，页和块的大小相同。这样可将用户程序的任一页放入任一物理块中，实现了离散分配。实现分页式存储管理所需的数据结构：页表。利用地址变换机构实现从逻辑地址到物理地址的转变换，通过页表来实现从页号到物理块号的变换，将逻辑地址中的页号转换为内存中的物理块号。文件主要操作1、文件存储空间的管理2、目录管理3、文件的读、写管理和存取控制设备管理器功能1、缓冲管理2、设备分配3、设备处理4、设备独立性和虚拟设备分析题什么是SPOOLing系统，打印机后台进行打印时，SPOOLing提供了哪些功能？通过SPOOLing技术便可将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备。在实现后台打印时，SPOOLing系统应为请求I/O的进程提供以下服务：（1）由输出进程在输出井中申请一空闲盘块区，并将要打印的数据送入其中；（2）输出进程为用户进程申请空白用户打印表，填入打印要求，将该表挂到请求打印队列。（3）一旦打印机空闲，输出进程便从请求打印队列的队首取出一张请求打印表，根据表中要求将要打印的数据从输出井传送到内存缓冲区，再由打印机进行打印。

考试知识点整理操作系统引论操作系统的定义操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。操作系统的目标有效性(提高资源利用率和系统吞吐量)、方便性、可扩充性、开放性。系统调用用户在程序中调用操作系统所提供的相关功能。操作系统的作用OS作为用户与计算机硬件系统之间的接口;

用户可以通过三种方式使用计算机(命令方式;系统调用方式;图标-窗口方式)OS作为计算机系统资源的管理者;OS实现了对计算机资源的抽象OS的发展过程无操作系统的计算机系统→单道批处理系统→多道批处理系统→分时系统→实时系统→微机操作系统多道批处理系统、分时系统、实时系统的特点单道批处理系统自动性顺序性单道性多道批处理系统特点多道宏观上并行微观上串行。分时操作系统特点同时性(多路性)交互性独立性及时性。实时操作系统特点及时性可靠性。操作系统的基本特征(4)并发性：两个或多个事件在同一时间间隔内发生共享性：系统中资源可供内存中多个并发执行的进程(线程)共同使用互斥共享方式：一段时间只允许一个进程访问该资源(打印机)同时访问方式：允许若干个用户同时访问该文件(磁盘设备)虚拟性：通过某种技术把一个物理实体变为若干个逻辑上的对应物。时分复用技术(处理器的分时共享)空分复用技术(虚拟存储器)异步性：进程以不可预知的速度向前推进，多道程序设计固有的特点。OS的主要功能(5)处理机管理(进程管理)功能；存储器管理功能；设备管理功能；文件管理功能；操作系统与用户之间的接口。

进程管理进程的定义进程是程序的一次执行。进程是一个程序及其数据在处理机上顺序执行时所发生的活动。进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。进程与线程的基本概念进程是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量。线程是为了减少程序在并发执行时所付出的空间开销，使OS具有更好的并发性。进程和线程的区别调度：线程作为调度和分派的基本单位；进程作为资源拥有的基本单位。并发性：进程之间可以并发执行，进程中的诸线程之间也可并发执行。拥有资源：进程拥有资源，线程无资源，但可以访问所属进程的资源。系统开销：创建和撤销进程的代价比创建和撤销线程的代价大的多。进程的特征结构特征：由程序段、相关的数据项和PCB三部分构成了进程实体。动态性：指从创建、调度执行到撤销的过程是动态的。并发性：是指多个进程实体同存于内存中。独立性：因为有PCB，可以独立运行、独立分配资源、独立接受调度等功能。异步性：各进程按各自独立、不可预知的速度向前推进。进程的三种基本状态就绪状态：除CPU外，已占有其他必要的资源的进程。执行状态：指进程已获得CPU，其程序正在执行的状态。阻塞状态：因事故是正在执行的进程停止，并让出CPU。引入挂起状态后的进程进程状态转换的原因？举例进程在运行过程中会经常发生状态的转换。例如，处于就绪状态的进程，在调度程序为之分配了处理机之后便可执行，相应地，其状态就由就绪态转变为执行态；正在执行的进程如果因分配给它的时间片已完而被剥夺处理机暂停执行时，其状态就由执行转为就绪；如果因发生某事件，致使当前进程的执行受阻，使之无法继续执行，则该进程状态将由执行转变为阻塞。引起进程挂起状态的原因终端用户的请求；父进程请求；负荷调节的需要；操作系统的需要。进程同步机制进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则共享系统资源，并能很好的相互合作，从而使程序的执行具有可再现性。原语是由若干条机器指令所构成，用以完成特定功能的一段程序。，它的特点是执行时不可中断。信号量机制信号量机制是一种卓有成效的进程同步工具。整型信号量记录型信号量AND型信号量信号量集经典的进程同步问题生产者消费者问题哲学家进餐问题读者-写者问题进程通信的类型共享存储器系统；基于共享数据结构的通信方式基于共享存储区的通信方式管道通信系统；消息传递系统；直接通信方式间接通信方式客户机-服务器系统。前趋图是用来描述进程之间执行的前后关系的。进程控制块：是为使多个程序能并发执行而为每个程序所配置的一个数据结构，PCB是进程存在的唯一标志。

处理机调度与死锁批量型作业如何获得处理机？批量型作业通常需要经历作业调度(高级调度或长程调度)和进程调度(低级调度和短程调度)两个过程后方能获得处理机。处理机调度层次高级调度(作业调度)：把外存上处于后备队列中的那些作业调入内存。中级调度(内存调度)：内存中不能有太多的进程，把进程从内存移到外存，当内存有足够空间时，再将合适的进程换入内存，等待进程调度。目的是提高内存利用率和系统吞吐量。低级调度(进程调度|短程调度)：它决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。对象是进程。功能是：保存处理机现场信息(PCB)；按某种算法选取进程；把处理器分配给进程。方式分为非抢占方式和抢占方式。常见的几种调度算法先来先服务算法FCFS：先来的先服务短作业优先算法SJF：找服务时间最短的，从短到长时间片轮转算法：按来到时间(到达时间加服务完后再排队时间)排队执行优先权调度算法：非抢占式、抢占式。优先权：静态、动态。死锁、活锁概念死锁：多个进程在运行过程中因争夺资源而造成的一种僵局。活锁：多个进程在运行过程中因相互谦让而造成的一种僵局。产生死锁的原因竞争资源进程间推进顺序非法产生死锁的必要条件互斥条件：临界资源的互斥访问；请求和保持条件：占着自己的资源不放，又去请求别人的；不可抢占条件：进程没有完成则不是放占有的资源；循环等待条件：发生死锁指必然存在一个资源环形链。处理死锁的基本方法预防死锁避免死锁检测死锁解除死锁银行家算法(避免死锁)先看是否超过还需要的资源数量，再看是否超过系统还有的资源数量，都满足尝试分配给该进程，找安全序列即它运行完后的资源能不能有一个顺序让其他进程都能顺利运行结束。安全序列安全序列：是指系统能够找到一个进程序列(P1、P2……Pn)，来为每个进程Pi分配所需资源，直到满足每个进程的最大需求，使每个进程能够顺利完成，则P1、P2……Pn即为安全状态。资源分配图(检测死锁)用资源分配图对死锁进行检测，消去途中的所有边，若节点为孤立节点，则为可完全简化。死锁的解除剥夺资源：从其他进程剥夺足够数量的资源给死锁进程，以解除死锁状态；撤销进程：一种方法是夭折全部进程；另一种方法是按某个顺序逐个撤销进程，直到死锁状态被解除。临界资源将一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等可以被若干进程共享，也属于临界资源。临界区临界区是指进程中访问临界资源的那段程序代码。

存储器管理连续分配方式(一个用户程序分配一个连续的内存空间)单一连续分配：一个程序装入其他程序就不允许被装入。只是用于单用户单任务的OS中。固定分区分配：把内存分为若干个固定大小的区域，每个分区装入一个作业，允许并发执行。动态分区分配：根据实际需要，动态地为之分配内存空间。动态重定位分区分配：通过重定位寄存器把相对地址转化成物理地址，此转化过程是在程序执行期间，随着每条指令或数据的访问自动进行的，故称为动态重定位。分区分配算法首次适应算法(以地址递增次序访问)循环首次适应算法(从上一次分配处开始查找)最佳适应算法(小内存到大内存依次查找)最坏适应算法(每次分配从大内存开始割让)快速适应算法(对空闲分区进行分类，并建立索引表，选最适合的控件分配给请求的进程)重定位：作业的地址空间与存储空间不一致时，所进行的地址调整以便作业能够执行的过程称为重定位。内存碎片：指内存中很多容量太小，无法被利用的空闲块。对换：把暂时不运行的程序调到外存，需要时再调到内存。

有整体对换和页面对换两种类型。地址变换机制地址变换机制：将用户地址空间中的逻辑地址变换为内存空间中的物理地址。分页式存储管理在该方式中，将用户程序的地址空间分为若干个固定大小的区域，称为“页”。相应地，也将内存空间分为若干个物理块或页框，页和块的大小相同，这样可将用户程序的任一页放任一物理块中，实现了离散分配。组成：页、块、页表，页的大小，页号、页内地址、物理块号。分段式存储管理在该方式中，将用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。在存储器分配时，以段为单位，这些段在内存中可以不相邻接，同样实现了离散分配。(段表用于实现从逻辑段到物理内存区的映射)组成：段、段表，段的大小，段号、段内地址。引入分段存储管理方式的目的主是为了满足用户在编程和使用上多方面的要求。段页式存储管理分段和分页相结合，先将用户程序分成若干个段，再把每个段分成若干个页，并为每个段赋予一个段名。其地址结构由段号、段内页号和页内地址组成。分页和分段的主要区别两者都采用离散分配方式，且都要通过地址映射机构来实现地址变换；页是物理单位，分页是为了有效管理内存；

段是逻辑单位，分段是为了维护信息完整性和独立性；页大小固定且由系统决定，段大小不固定且由用户编写程序决定；分页作业地址空间是一维的，

分段作业地址空间是二维的。虚拟存储器的基本概念所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定。特征：离散性、多次性、对换性、虚拟性局部性原理局部性原理：早在1968年，Denning.P就曾指出：程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5。程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。局限性还表现在：时间局限性和空间局限性抖动刚被调出的页面立即要用而装入，而装入后不久又被调出，如此反复，使调度非常频繁，这种现象称为抖动。请求分页存储管理方式基本工作原理、调页策略。缺页中断与一般中断的区别。请求分页系统是建立在基本分页基础上，为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能，每次调入调出基本单位都是长度固定的页面。调页策略：调入页面的时机：预调页策略、请求调页策略确定从何处调入页面页面调入过程缺页中断与一般中断的区别：在指令执行期间产生和处理中断信号一条指令在执行期间，可能产生多次缺页中断

请求分页式存储管理中的页面置换算法最佳置换算法(OPT)先进先出置换算法(FIFO)最近最久未使用置换算法(LRU)Clock置换算法例：设有8页的逻辑地址空间，每页有1024字节，它们限制到32块的物理存储区中，试问：逻辑地址应占多少位？物理地址就占多少位？解：因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示(32=25)。(1)页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。(2)页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。

设备管理I/O系统I/O系统是用于实现数据输入、输出及数据存储的系统。I/O设备类型按使用特性分类存储设备I/O设备按传输速率分类低速设备中速设备高速设备按信息交换的单位分类块设备字符设备按共享属性分类独占设备共享设备 虚拟设备设备与控制器之间的接口数据信号线：设备和设备控制器之间传送数据信号；控制信号线：设备控制器向I/O设备发送控制信号的通路；状态信号线：传送指示设备当前状态的信号。设备控制器设备控制器主要职责是控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换。它是CPU和I/O设备的接口，通过接收CPU指令去控制I/O设备工作，从而减轻处理机的工作量。设备控制器控制字符设备控制器控制块设备的控制器设备控制器的基本功能接收和识别命令数据交换标识和报告设备的状态地址识别(CPU通过地址控制设备)数据缓冲区差错控制饥饿：当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿。I/O通道I/O通道是一种特殊的处理机，它具有执行I/O指令的能力，可以控制I/O操作。I/O通道字节多路通道数组选择通道数组多路通道如何解决“瓶颈”问题解决“瓶颈”问题的最有效的方法是增加设备到主机间的通路而不增加通道。I/O控制方式使用轮询的可编程I/O方式使用中断的可编程I/O方式直接存储器访问方式(DMA)I/O通道控制方式SPOOLing技术通过SPOOLing技术便可将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备。SPOOLing系统的应用：共享打印机实现的基本原理。SPOOLing系统的组成输入井和输入井输入缓冲区和输出缓冲区输入进程和输出进程井管理程序SPOOLing系统的特点提高了I/O的速度；将独占设备改造为共享设备；实现了虚拟设备功能。磁盘性能与调度磁盘性能：数据的组织、磁盘的类型和访问时间(寻道时间、旋转延迟时间、传输时间)磁盘调度的主要目标：使磁盘的平均寻道时间最少。常用的磁盘调度算法先来先服务FCFS(适合进程较少的场合)最短寻道时间优先SSTF(要访问的磁道与当前磁头所在磁道距离最近。会导致进程“饥饿”现象)扫描算法SCAN(考虑访问的磁道与当前磁头所在磁道距离最近和磁头当前移动的方向)循环扫描算法CSCAN(规定磁头单向移动)NSPetpSCAN和FSCAN调度算法文件管理文件逻辑结构的类型有结构文件(由一个以上的记录构成的文件，又称记录式文件)

大量的数据结构比如数据库是采用有结构的文件形式无结构文件(由字符流构成的文件，又称流式文件)

而大量的源代码、可执行文件、库函数等采用无结构文件。记录式文件的长度定长记录变长记录按文件的组织方式分类顺序文件索引文件索引顺序文件顺序文件的优缺点适合进行批量存取；存取效率是所有逻辑文件中最高的；也只有顺序文件才能存储在磁带上，并能有效的工作；不适合查找或修改单个记录；增加或删除一个记录时比较困难。索引文件的缺点除了有主文件外，还须配置一张索引表，而且每个记录都要有一个索引表，因此提高了存储费用。哈希文件是键值通过Hash函数指向目录表，该表目的内容指向记录所在的物理块。外存的组织方式连续组织方式链接组织方式FAT技术NTFS的文件组织方式索引组织方式连续分配的优缺点优点顺序访问容易顺序访问速度快缺点要求有连续的存储空间必须实现知道文件的长度链接分配中的链接方式隐式链接显式链接为新建文件分配存储空间有哪些方式？为新建文件分配存储空间的方式分为连续和离散的分配方式。前者具有较高的文件访问速度，但可能产生较多的外存零头。后者能有效的利用外存空间，但访问速度较慢。无论哪种方式，存储空间的基本分配单位都是磁盘块而非字节。文件存储空间(外存空间)管理的方法空闲表法和空闲链表位示图法成组链接法空闲表法和空闲链表法都不适用于大型文件系统，可使用成组链接法。文件共享有向无循环图符号链文件保护保护域访问矩阵文件控制块： 每个文件应配置一个文件控制块，用来保存文件名、存取控制信息、物理地址、其他有关控制信息及文件说明的数据结构。

操作系统模拟试卷操作系统操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。操作系统是一组控制和管理计算机硬件和软件资源，合理的对各类作业进行调度，以及方便用户使用的程序的集合。临界资源将一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等可以被若干进程共享，也属于临界资源。临界区是指进程中访问临界资源的那段程序代码。设备独立性设备独立性指用户设备独立于所使用的具体物理设备。即在用户程序中要执行I/O操作时，只需用逻辑设备名提出I/O请求，而不必局限于某特定的物理设备。死锁多个进程在运行过程中因争夺资源而造成的一种僵局。FATFAT文件分配表，文件分配表是盘片内部管理文件分配存储单元的一种系统，它记录着盘片的容量，文件存储空间的分配情况，哪些扇区已被数据使用，哪些扇区没有被数据占用，都会记录在FAT表内。引入挂起状态后的进程有哪几种基本状态、状态转换的条件是什么？画出状态转换图。引入挂起状态后的进程有创建状态、活动就绪状态、静止就绪状态、活动阻塞状态、静止阻塞状态、执行状态、终止状态。当一个新进程产生时，该进程处于创建状态；在当前系统的性能和内存容量均允许的情况下，完成对进程的必要操作后转为活动就绪状态；考虑到系统当前资源状况和性能的要求，不分配给新建进程所需资源，主要是内存，相应的系统将进程状态转为静止就绪状态并将其安置在外存，不参与调度；当一个进程已完成或者出现了无法克服的错误此时进程状态转换为终止状态。

四选一试用前趋图描述4＊100M接力赛，用整型信号量描述该算法。beginS1,S2,S3;semaphore;S1=S2=S3=0;cobeginprocessP1begin跑100米；V(S1);endprocessP2beginP(S1)跑100米；V(S2);endprocessP3beginP(S2)跑100米；V(S3);endprocessP4beginP(S3)跑100米；V(S3);endcoendend

试利用记录型信号量写出一个不会出现死锁的哲学家进餐问题的算法。intin=0,out=0;itembuffer[n];semaphoremutex=1,empty=n,full=0;voidproceducer(){do{produceanitemnextp;…wait(empty);wait(mutex);buffer[in]=nextp;in=(in+1)%n;signal(mutex);signal(full);}while(True);}voidconsumer(){do{wait(full);wait(mutex);nextc=buffer[out];out=(out+1)%n;signal(mutex);signal(empty);consumetheiteminnextc;…}while(True);}voidmain(){cobeginproceducer();……;consumer();coend)试用整型信号量，写一个解决生产者－消费者问题的算法。

设数据采集系统中有一个单缓冲区，数据采集与数据处理共享该缓冲区，试用整型信号量写一个该系统中数据采集进程与数据处理进程的同步算法。intse=1;intsf=0;main(){cobeginget();compute();coend}get(){while(采集工作未完成){采集一个数据；p(se);将数据送入缓冲区；v(sf);}}compute(){while(计算工作未完成){p(sf);从缓冲区中取出数据；v(se);进行数据计算；}}

何为分页式存储管理？实现分页式存储管理所需的数据结构是如何的？如何实现逻辑地址到物理地址的变换？分页式存储管理是将用户程序的地址空间分为若干个固定大小区域，称为“页”或“页面”。相应的，也将内存空间分为若干个物理块或页框，页和块的大小相同。这样可将用户程序的任一页放入任一物理块中，实现了离散分配。实现分页式存储管理所需的数据结构：页表。利用地址变换机构实现从逻辑地址到物理地址的转变换，通过页表来实现从页号到物理块号的变换，将逻辑地址中的页号转换为内存中的物理块号。何谓死锁？产生死锁的原因和必要条件是什么？死锁指多个进程在运行过程中因争夺资源而造成的一种僵局。产生死锁的原因：①竞争资源；②进程间推进顺序非法产生死锁的必要条件：互斥条件：临界资源的互斥访问；请求和保持条件：占着自己的资源不放，又去请求别人的；不可抢占条件：进程没有完成则不是放占有的资源；循环等待条件：发生死锁指必然存在一个资源环形链。试述设备的分配过程。设备分配的过程主要是:从系统设备表SDT中找到需要的物理设备的设备控制表DCT;若设备闲,则分配,然后从设备控制表DCT中找到控制器控制表指针所指出的控制器控制表COCT;若控制器闲,则分配,然后从控制器控制表COCT中找到通道控制表指针所指出的通道控制表CHCT;根据通道控制表CHCT中的状态信息来判断是否可以启动I/O设备传送信息,若闲则可以,若忙则把该进程插入到等待通道的队列中去。试简述UNIX中用成组链接法如何实现空间的管理？从空闲盘号栈顶取出一个空闲盘块号进行分配，空闲盘块数减1；如果已经是栈底元素，则从该盘块中读出内容作为新的空闲盘号栈，然后将该块分配。

假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1，分别采用最佳置换算法和LRU算法，共缺页多少次(含最初的3次)？缺页率是多少？OPT算法缺页率为45%LRU算法缺页率为60%FIFO算法缺页率为75%在LINUX环境下，试编写二个程序(进程)，使用消息队列进行数据通信，分别实现消息的发送与接收，进程间通信的信息结构如下：structMSG{charcName[8];intiAge;}接收信息的程序源文件为msgreceive.c的源代码/*使用消息队列通信*/#include<unistd.h>#include<stdlib.h>#include<stdio.h>#include<string.h>#include<errno.h>#include<sys/msg.h>structMSG{charcName[8];intiAge;};intmain(){intrunning=1;intmsgid=-1;structMSGdata;longintmsgtype=0;//注意1//建立消息队列msgid=msgget((key_t)1234,0666|IPC_CREAT);if(msgid==-1){fprintf(stderr,"msggetfailedwitherror:%d\n",errno);exit(EXIT_FAILURE);}//从队列中获取消息，直到遇到end消息为止while(running){if(msgrcv(msgid,(void*)&data,BUFSIZ,msgtype,0)==-1){fprintf(stderr,"msgrcvfailedwitherrno:%d\n",errno);exit(EXIT_FAILURE);}printf("Youwrote:%s\n",data.text);//遇到end结束if(strncmp(data.text,"end",3)==0)running=0;}//删除消息队列if(msgctl(msgid,IPC_RMID,0)==-1){fprintf(stderr,"msgctl(IPC_RMID)failed\n");exit(EXIT_FAILURE);}exit(EXIT_SUCCESS);}发送信息的程序的源文件msgsend.c的源代码#include<unistd.h>#include<stdlib.h>#include<stdio.h>#include<string.h>#include<sys/msg.h>#include<errno.h>#defineMAX_TEXT512structmsg_st{longintmsg_type;chartext[MAX_TEXT];};intmain(){intrunning=1;structmsg_stdata;charbuffer[BUFSIZ];intmsgid=-1;//建立消息队列msgid=msgget((key_t)1234,0666|IPC_CREAT);if(msgid==-1){fprintf(stderr,"msggetfailedwitherror:%d\n",errno);exit(EXIT_FAILURE);}//向消息队列中写消息，直到写入endwhile(running){//输入数据printf("Entersometext:");fgets(buffer,BUFSIZ,stdin);data.msg_type=1;//注意2strcpy(data.text,buffer);//向队列发送数据if(msgsnd(msgid,(void*)&data,MAX_TEXT,0)==-1){fprintf(stderr,"msgsndfailed\n");exit(EXIT_FAILURE);}//输入end结束输入if(strncmp(buffer,"end",3)==0)running=0;sleep(1);}exit(EXIT_SUCCESS);}

计算题信号量某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。定义信号量S，初值为20。当S>0时，表示可以继续进入购票厅的人数；当S=0时，表示厅内已有20人正在购票；当S<0时，|S|表示正等待进入的人数。VarS:semaphore;S=20;cobeginprocedureP_i;beginP(S);…Enterandbutticket;…V(S);endcoend若欲购票者最多为n个人，写出信号量可能的变化范围最大值和最小值)。最大值为20，最小值为20-N一个司机与售票员的例子，在公共汽车上，为保证乘客的安全，司机和售票员应协调工作；停车后才能开门，关车门后才能行车。用PV操作来实现他们之间的协调。S1：是否允许司机启动汽车的变量S2：是否允许售票员开门的变量driver(){while(1){P(S1);启动汽车;正常行车;到站停车;V(S2);}}busman(){while(1){关车门;V(S1);售票;P(S2);开车门;上下乘客;}}有一阅览室，共有100个座位。读者进入时必须先在一种登记表上登记，该表为每一座位列一个表目，包括座号和读者姓名。读者离开时要注销掉登记内容。试用wait和signal原语描述读者进程的同步问题。semaphoreempty=100;semaphoremutex=100;voidreader(){while(true){wait(empty);wait(mutex);signal(mutex);wait(mutex);signal(mutex);signal(empty);}}试写出相应程序来描述下图所示的前驱关系。semaphorea=b=c=d=e=f=g=h=0;S1(){……;signal(a);signal(b);}S2(){wait(a);……signal(c);signal(d);}S3(){wait(b);……;signal(e);}S4(){wait(c);……;signal(f);}S5(){wait(d);……;signal(g);}S6(){wait(e);……;signal(h);}S7(){wait(f);wait(g);wait(h);……;}main(){cobeginS1();S2();S3();S4();S5();S6();S7();coend}进程调度假定在单CPU条件下有下列要执行的作业：作业运行时间优先级1102243330作业到来的时间是按作业编号顺序进行的(即后面作业依次比前一个作业吃到一个时间单位)。用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？作业到达时间运行时间完成时间周转时间带权周转时间1010101012141716432313113.7平均周转时间平均带权周转时间12.32.9

假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：作业进入系统时间估计运行时间/分钟18:004028:203038:301249:001859:105如果应用先来先服务的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:00408：008：404028:20308：409：105038:30129：109：225249:00189：229：404059:1059：409：4535作业平均周转时间T=43.4217如果应用最短作业优先的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:00408：008：404028:20308：529：226238:30128：408：522249:00189：279：454559:1059：229：2717作业平均周转时间T=37.2186

缺页置换在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为3、4时，试计算采用下述页面淘汰算法时的缺页次数(假设开始执行时主存中没有页面)，并比较所得结果。最佳置换法(OPT)物理块为3时，缺页次数为7物理块为4时，缺页次数为6先进先出法(FIFO)物理块为3时，缺页次数为9物理块为4时，缺页次数为10

某采用页式存储管理的系统，接收了一个共7页的作业，作业执行时依次访问的页为：1、2、3、4、2、1、5、6、2、1、2、3、7。当内存块数量为4时，请分别用先进先出(FIFO)调度算法和最近最少使用(LRU)调度算法，计算作业执行过程中会产生多少次缺页中断？写出依次产生缺页中断后应淘汰的页。(所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算过程)FIFO，共产生10次缺页中断，依次淘汰1、2、3、4、5、6LRU，共产生8次缺页中断，依次淘汰3、4、5、6在一个请求分页系统中，假定系统分配给一个作业的物理块数为3，并且此作业的页面走向为2、3、2、1、5、2、4、5、3、2、5、2.试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数。FIFO，缺页次数为9LRU，缺页次数为7

有一个虚拟存储系统。分配给某进程3页内存，开始时内存为空，页面访问序列如下：6、5、4、3、2、1、5、1、5、2、1、2、1、2、1、6、5若采用先进先出的页面置换算法(FIFO)，缺页次数为多少？FIFO，缺页次数为8次若采用最近最少使用的页面置换算法(LRU)，缺页次数为多少？LRU，缺页次数为9次

地址变换在一个段式存储管理系统中，段表内容如下：段号内存起始地址段长02105001235020210090313505904193895试求下述逻辑地址对应的物理地址是什么？由于第0段内存始址为210，段长为500，故逻辑地址[0,430]是合法地址，逻辑地址[0,430]对应物理地址为210+430=640由于第1段内存始址为2350，段长为20，故逻辑地址[1,10]是合法地址，逻辑地址[1,10]对应物理地址为2350+10=2360由于第2段内存始址为100，段长为90，故逻辑地址[2,500]是非法地址由于第3段内存始址为1350，段长为590，故逻辑地址[3,400]是合法地址，逻辑地址[3,400]对应物理地址为1350+400=1750由于第4段内存始址为1938，段长为95，故逻辑地址[4,112]是非法地址由于系统中不存在第5段，所给逻辑地址[5,32]非法一个由3个页面(页号为0、1、2)，每页有2048个字节组成的程序，假定在某时刻调入8个物理块的内存，其页面的页号和物理块号的对照表如下：请根据页表，计算下列给出的逻辑地址对应的绝对地址。绝对地址=块号*块长+页内地址100100的页号=100/2048=0，页内地址为100%2048=100；查表得主存块号为4，于是绝对地址=4*2048+100=829226172617的页号=2617/2048=1，页内地址为2617%2048=569；查表得主存块号为7，于是绝对地址=7*2048+569=1490551965196的页号=5196/2048=2，页内地址为5196%2048=1100；查表得主存块号为1，于是绝对地址=1*2048+1100=3148在请求分页系统中，某用户的编程空间为16个页面，每页1K，分配的内存空间为8K。假定某时刻该用户的页表如下图所示，试问：页号块号0317243141259661720逻辑地址084B(H)对应的物理地址是多少？(用十六进制表示)页长为1KB，所以页内地址为10位分配内存空间为8K，故物理地址为13位(084B)16=(0100001001011)2页面号为(010)2=2，对应块号4=(100)20001000001001011=104B逻辑地址5000(十进制)对应的物理地址是多少？(用十进制表示)(5000)10=(1388)16=(1001110001000)2页面号为(100)2=4，对应块号12=(1100)211001110001000=13192当该用户进程欲访问24A0H单元时，会出现什么现象？24A0H=010010010100000页面号=1001=9，而其页面当前不在内存，所以会发一个缺页中断，请求系统调页。

磁盘调度若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。先来先服务算法(FCFS)4020444048012762024436766864共移动(20+24+4+36+76+68+64)=292个柱面3*292=876毫秒最短寻找时间优先算法(SSTF)404044201247680042488724共移动(4+24+8+8+72+4)=120个柱面3*120=360毫秒若磁头的当前位置为100磁道，磁头正向磁道号增加方向移动。现有一磁盘读写请求队列：23，376，205，132，19，61，190，398，29，4，18，40。若采用先来先服务、最短寻道时间优先和扫描算法，试计算出平均寻道长度各为多少。先来先服务(FCFS)1002337620513219611903982941840773531717311342129208369251422移动磁道数总数：(77+353+171+73+113+42+129+208+369+25+14+22)=1596平均寻道长度：1596/12=133最短寻道时间(SSTC)100132190205614029231918437639832581514421116411437222移动磁道数总数：(32+58+15+144+21+11+6+4+1+14+372+22)=700平均寻道长度：700/12=58.3扫描算法(SCAN)100132190205376398614029231918432581517122337211164114移动磁道数总数：(32+58+15+171+22+337+21+11+6+4+1+14)=692平均寻道长度：692/12=57.7

银行家算法在银行家算法中，若出现了下述资源分配情况，试问：ProcessAllocationNeedAvailablep0003200121622p110001750p213542356p303320652p400140656资源进程该状态是否安全？资源进程WorkNeedAllocationWork+AllocationFinishp01622001200321654truep31654065203321986truep419860656001419910truep1199101750100029910truep229910235613543121414true因为存在一个安全序列<p0,p3,p4,p1,p2>，所以系统处于安全状态。若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？1222<23561222<1622P2=1622-1222=0400P2=1354+1222=2576P2=2356-1222=1134看Request是否≤Need，若不是则失败看Request是否≤Available，若不是则等待尝试分配，并将Available，Allocation，Need修改，并判断是否安全

Available=Available–Request

Allocation=Allocation+Request

Need=Need–Request

最后冲刺名词解释题操作系统操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。操作系统是一组控制和管理计算机硬件和软件资源，合理的对各类作业进行调度，以及方便用户使用的程序的集合。临界资源将一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。临界区临界区是指进程中访问临界资源的那段程序代码。设备独立性设备独立性指用户设备独立于所使用的具体物理设备。即在用户程序中要执行I/O操作时，只需用逻辑设备名提出I/O请求，而不必局限于某特定的物理设备。死锁多个进程在运行过程中因争夺资源而造成的一种僵局。活锁多个进程在运行过程中因相互谦让而造成的一种僵局。FATFAT文件分配表是盘片内部管理文件分配存储单元的一种系统，它记录着盘片的容量，文件存储空间的分配情况，哪些扇区已被数据使用，哪些扇区没有被数据占用，都会记录在FAT表内。系统调用用户在程序中调用操作系统所提供的相关功能。进程进程是一个程序及其数据在处理机上顺序执行时所发生的活动。进程同步机制进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则共享系统资源，并能很好的相互合作，从而使程序的执行具有可再现性。原语原语是由若干条机器指令所构成，用以完成特定功能的一段程序。，它的特点是执行时不可中断。进程控制块进程控制块是为使多个程序能并发执行而为每个程序所配置的一个数据结构，PCB是进程存在的唯一标志。安全序列安全序列：是指系统能够找到一个进程序列(P1、P2……Pn)，来为每个进程Pi分配所需资源，直到满足每个进程的最大需求，使每个进程能够顺利完成，则P1、P2……Pn即为安全状态。重定位作业的地址空间与存储空间不一致时，所进行的地址调整以便作业能够执行的过程称为重定位。碎片指内存中很多容量太小，无法被利用的空闲块。对换把暂时不运行的程序调到外存，需要时再调到内存。(整体对换和页面对换)地址变换机制将用户地址空间中的逻辑地址变换为内存空间中的物理地址。虚拟存储器虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定。特征：离散性、多次性、对换性、虚拟性抖动刚被调出的页面立即要用而装入，而装入后不久又被调出，如此反复，使调度非常频繁，这种现象称为抖动。设备控制器设备控制器主要职责是控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换。它是CPU和I/O设备的接口，通过接收CPU指令去控制I/O设备工作，从而减轻处理机的工作量。饥饿当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿。如何解决“瓶颈”问题解决“瓶颈”问题的最有效的方法是增加设备到主机间的通路而不增加通道。SPOOLing通过SPOOLing技术便可将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备。SPOOLing系统的应用：共享打印机实现的基本原理。文件控制块每个文件应配置一个文件控制块，用来保存文件名、存取控制信息、物理地址、其他有关控制信息及文件说明的数据结构。流式文件流式文件是指文件内的数据不再组成记录，只是依次的一串信息集合，可以看成是只有一个记录的记录式文件。记录式文件记录式文件是一种有结构的文件，包含若干逻辑记录，逻辑记录是文件中按信息在逻辑上的独立含意划分的信息单位。信号量信号量是一种特殊变量，用来表示系统中资源的使用情况。页快表快表是一块小容量的相联存储器，由高速缓存器组成，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。文件目录计算机系统建立文件的索引，即文件名和文件物理位置之间的映射关系，这种文件的索引称为文件目录。局部性原理对于绝大多数程序来说，程序所访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的。程序访问的局部性包含两个方面：时间局部性和空间局部性。缓冲区缓冲区是用来保存两个设备之间或在设备和应用程序之间所传输数据的内存区域

简答题引入挂起状态后的进程有哪几种基本状态、状态转换的条件是什么？画出状态转换图。引入挂起状态后的进程有创建状态、活动就绪状态、静止就绪状态、活动阻塞状态、静止阻塞状态、执行状态、终止状态。当一个新进程产生时，该进程处于创建状态；在当前系统的性能和内存容量均允许的情况下，完成对进程的必要操作后转为活动就绪状态；考虑到系统当前资源状况和性能的要求，不分配给新建进程所需资源，主要是内存，相应的系统将进程状态转为静止就绪状态并将其安置在外存，不参与调度；当一个进程已完成或者出现了无法克服的错误此时进程状态转换为终止状态。设数据采集系统中有一个单缓冲区，数据采集与数据处理共享该缓冲区，试用整型信号量写一个该系统中数据采集进程与数据处理进程的同步算法。intse=1;intsf=0;main(){cobeginget();compute();coend}get(){while(采集工作未完成){采集一个数据；p(se);将数据送入缓冲区；v(sf);}}compute(){while(计算工作未完成){p(sf);从缓冲区中取出数据；v(se);进行数据计算；}}试用前趋图描述4＊100M接力赛，用整型信号量描述该算法。beginS1,S2,S3;semaphore;S1=S2=S3=0;cobeginprocessP1begin跑100米；V(S1);endprocessP2beginP(S1)跑100米；V(S2);endprocessP3beginP(S2)跑100米；V(S3);endprocessP4beginP(S3)跑100米；V(S3);endcoendend

何为分页式存储管理？实现分页式存储管理所需的数据结构是如何的？如何实现逻辑地址到物理地址的变换？分页式存储管理是将用户程序的地址空间分为若干个固定大小区域，称为“页”或“页面”。相应的，也将内存空间分为若干个物理块或页框，页和块的大小相同。这样可将用户程序的任一页放入任一物理块中，实现了离散分配。实现分页式存储管理所需的数据结构：页表。利用地址变换机构实现从逻辑地址到物理地址的转变换，通过页表来实现从页号到物理块号的变换，将逻辑地址中的页号转换为内存中的物理块号。何谓死锁？产生死锁的原因和必要条件是什么？死锁指多个进程在运行过程中因争夺资源而造成的一种僵局。产生死锁的原因：①竞争资源；②进程间推进顺序非法产生死锁的必要条件：互斥条件：临界资源的互斥访问；请求和保持条件：占着自己的资源不放，又去请求别人的；不可抢占条件：进程没有完成则不是放占有的资源；循环等待条件：发生死锁指必然存在一个资源环形链。试述设备的分配过程。设备分配的过程主要是:从系统设备表SDT中找到需要的物理设备的设备控制表DCT;若设备闲,则分配,然后从设备控制表DCT中找到控制器控制表指针所指出的控制器控制表COCT;若控制器闲,则分配,然后从控制器控制表COCT中找到通道控制表指针所指出的通道控制表CHCT;根据通道控制表CHCT中的状态信息来判断是否可以启动I/O设备传送信息,若闲则可以,若忙则把该进程插入到等待通道的队列中去。试简述UNIX中用成组链接法如何实现空间的管理？从空闲盘号栈顶取出一个空闲盘块号进行分配，空闲盘块数减1；如果已经是栈底元素，则从该盘块中读出内容作为新的空闲盘号栈，然后将该块分配。虚拟存储器的基本特征是什么？虚拟存储器的容量主要受到哪两方面的限制？①虚拟扩充②部分装入③离散分配④多次对换虚拟存储器的容量主要受到指令中表示地址的字长和外存的容量的限制。什么是中断？中断处理的一般过程分为哪几个阶段？中断是指CPU对系统发生的某个事件作出的一种反应：CPU暂停正在执行的程序，保留现场后自动地转去执行相应的处理程序，处理完该事件后再返回断点继续执行被“打断”的程序。中断处理的一般过程分为以下阶段：保存现场，分析原因，处理中断，返回断点。创建进程需要执行哪些操作？申请空白PCB为新进程分配资源初始化PCB将PCB插入队列缺页率与哪些因素有关？页面大小进程所分配物理块的数目页面置换算法程序固有特性什么是段式存储管理？它从逻辑地址到物理地址是怎么变换的？把程序按内容或构成关系分成段，每段有自己的名字。一个用户作业或进程包含的段对应于一个二维虚拟储存器。以段为单位分配内存，然后通过地址映射机构把逻辑地址转换成物理地址。只将那些经常访问的段驻留内存，其他的段放在外存，待需要时自动调入。地址变