操作系统重点知识总结.doc

- .第一章 引论1、操作系统定义P1操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩大。是一组控制和管理计算机硬件和软件资源、合理地对各类作业进展调度以及方便用户使用的程序的集合。2、操作系统的作用P21. OS作为用户与计算机硬件系统之间的接口2. OS作为计算机系统资源的管理者3. OS实现了对计算机资源的抽象3、 推动操作系统开展的主要动力P41. 不断提高计算机资源的利用率2. 方便用户3. 器件的不断更新迭代4. 计算机体系构造的不断开展4、 多道批处理系统的特征及优缺点P8特征：多道性、无序性、调度性优点：1. 资源利用率高2. 系统吞吐量大缺点：1. 平均周转时间长2. 无交互能力单道、多道都是5、分时系统和实时系统特征的比拟P121. 多路性实时系统的多路性主要表现在系统周期性地对多路信息的采集、以及对多个对象或多个执行机制进展控制。 分时系统中的多路性那么和用户有关，时多时少。2. 独立性 3. 及时性:实时系统对及时性的要求更严格,实时控制系统以控制对象要求的开场截止时间或完成截止时间来确定。 4. 交互性:实时系统的交互性仅限于某些专用效劳程序。 5. 可靠性:实时系统对可靠性的要求更高,否那么经济损失及后果无法预料。6、操作系统的根本特征P14并发、共享、虚拟和异步 其中并发特征是操作系统最重要的特征是其他特征的前提1.并发性2. 共享性互斥共享方式、同时方式3. 虚拟性时分复用技术虚拟处理机技术、虚拟设备技术、空分复用技术虚拟磁盘技术、虚拟存储器技术4. 异步性进程的异步性：进程是以人们不可预知的速度向前推进的7、操作系统的主要功能P181. 处理机管理功能进程控制1、进程互斥方式：进程或者线程在对临界资源进展时，应采取互斥方式；2、进程同步方式：相互合作去完成共同任务的诸进程货线程、进程通信、调度作业调度、进程调度2. 存储器管理功能 存分配、存保护、地址映射、存扩大3. 设备管理功能缓冲管理、设备分配、设备处理4. 文件管理功能文件存储空间的管理、目录管理、文件的读/写管理和保护5. 用户接口命令接口联机用户接口、脱机用户接口、程序接口、图形接口第二章 进程管理1、程序顺序执行时的特征P341. 顺序性：严格按照程序所规定的次序执行。2. 封闭性：程序在封闭环境下运行，系统中所有资源的状态只有本程序才能改变它。3. 可再现性：只要初始条件一样，无论怎样执行，其结果都是一样的。2、程序并发执行时的特征提高了系统吞吐量P361. 连续性：并发执行的实体之间相互制约，造成程序的执行出现连续，而不连续。2. 非封闭性：多个程序共享系统资源，因而其状态有多个程序改变，从而失去封闭性。3. 不可再现性：封闭性的失去必然导致不可再现性。3、进程及其特征P37进程是进程实体的运行过程，是系统进展资源分配和调度的一个独立单位。进程是程序的一次执行进程实体：由程序段、相关的数据段和PCB构成特征：构造特征动态性进程最根本的特征并发性引人进程的目的：为了使其进程实体能和其他的进程实体并发执行；而程序没有建立PCB不能并发执行独立性异步性4、 进程的根本状态及其转换图P381. 就绪(Ready)状态2. 执行状态3. 阻塞状态 典型事例：请求I/O、申请缓冲空间等5、 引入挂起状态的原因P391. 终端用户的请求 2. 父进程请求 3. 负荷调节的需要 4. 操作系统的需要6、具有挂起状态的进程状态及其转换图7、 进程控制块及其作用P41PCB是一种数据构造，是进程实体的一局部，记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。作用：1. 使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的根本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进展控制和管理的。2. PCB是进程存在与否的唯一标志,随着进程的建立而建立,随着进程的撤消而撤消。创立进程就是创立PCB。8、 进程之间的两种制约关系P481. 间接制约竞争资源进程互斥2. 直接制约相互合作进程同步9、 临界资源P48OS中把一次只能被一个进程使用的资源成为临界资源。10、 临界区P50进程中临界资源的那段代码称为临界区。11、 同步机构应遵循的规那么P50空闲让进、忙那么等待、有限等待、让权等待12、 利用信号量实现前驱关系算法P( 54 ) P( 55 )13、 经典同步算法生产者消费者问题, 哲学家就餐问题和读者写者问题略14、 进程通信的类型P65 低级：信号量进程通信 共享存储器系统基于共享数据构造或存储区的通信方式高级 消息传递系统直接、间接 管道通信系统必须提供的协调能力：互斥、同步、确定对方是否存在15、 线程的定义P72现代OS引入的比进程更小的可以独立运行、调度的根本单位，是轻型实体，不拥有资源。16、 线程和进程比拟线程又称为轻型进程，通常一个进程都拥有假设干个线程，至少也有一个多线程OS中的进程不是一个可执行的实体1、调度：传统OS中，进程是拥有资源的根本单位，独立调度、分派的根本单位。引入线程后，那么把线程作为调度和分派的根本单位，而进程作为拥有资源的根本单位2、并发性：引入线程的OS中，进程之间可以并发执行，在一个进程中的多个线程之间也可以；这样使得OS具有更好的并发性，从而能更加有效的提高系统资源的利用率和吞吐量3、拥有资源：线程不能拥有资源4、系统开销：就切换代价而言，进程远高于线程17、 线程的属性P731. 轻型实体2. 独立调度和分派的根本单位3. 可并发执行4. 共享进程资源第三章 处理机调度与死锁1、高级调度P84又称为作业调度。即从外存的后备队列中选择一个作业，为它创立进程，分配必要的资源，并将新进程插入主存的就绪队列上。注意：分时系统和实时系统无作业调度。JCB作业控制块；是作业在系统中存在的标志，其中保存了系统对作业进展管理和调度所需的全部信息2、 低级调度P86又称进程调度或短程调度，即从就绪队列中选择一个进程进入运行状态非抢占方式、可抢占方式。调度的对象是进程多批道处理、分时、实时三种类型的OS中都有3、 中级调度P87中程调度为了提高存利用率和系统吞吐量引入目的，为此，应使那些暂时不能运行的进程不再占用存资源，而将它们调至外存。适当时机再将其调回存。这种调度称为中级调度。4、 进程调度的两种方式P861、非抢占方式一旦给进程分配处理机，一直让他运行下去，直到完成再把处理机分配给其他进程2、抢占方式允许调度程序根据某些原那么去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一个进程5、 抢占的原那么P871. 优先权原那么2. 短作业进程优先原那么3. 时间片原那么6、 操作系统选择调度方式和调度算法的假设干准那么P901. 面向用户的准那么周转时间短、响应时间快、截止时间的保证、优先权准那么2. 面向系统的准那么系统吞吐量高、处理机利用率好、各类资源的平衡利用7、周转时间P92周转时间：是指从作业被提交给系统开场，到作业完成为止的这段时间间隔周转时间 = 完成时间 - 到达时间待权周转时间 = 周转时间 / 效劳时间8、针对各种调度算法先来先效劳，短进程优先，优先权，计算周转时间、带权周转时间, 平均周转时间、平均带权周转时间9、吞吐量指在单位时间系统所完成的作业数10、多级反应队列调度算法的原理、性能该算法用于进程调度，主要是为解决前面各种进程调度算法存在的各种不同问题而设计的一种考虑综合因素的调度算法。其思想如下：1、设置多个就绪队列，不同队列具有不同优先级，第一个队列优先级最高，以后次之。给不同队列分配不同大小的时间片，第一个队列最小，以后次之皆为前者的二倍。有的系统也将最后一级队列不划分时间片。2、当有一个新进程进入存后，首先将它放入第一队列的末尾，按FCFS先来先效劳原那么排队等待调度。当轮到该进程执行时，如果它能在该时间片完成，便可准备撤离系统；假设不能那么将它放在第二列的队尾。3、仅当前一级队列为空时才调度下一级队列中的进程。算法采用抢占式调度策略。执行的进程在规定的时间片为执行完毕，那么进入下一级队列的队尾，新进程那么进入第一级队列的队尾。性能：较好的性能，能满足各种类型的用户1、终端型作业用户2、短批处理作业用户3、长批处理作业用户11、死锁、产生死锁原因、必要条件P103死锁是指两个或多个进程由于资源竞争而造成的一种僵局，假设无外力作用，这些进程将永远无法向前推进。产生死锁的原因：1. 竞争资源可剥夺和非剥夺性资源、竞争非剥夺性资源、竞争临时性资源2. 进程推进顺序非法请求和释放资源的顺序不当必要条件：1. 互斥条件：进程间必须互斥使用某些资源才可能产生死锁。2. 请求保持条件：进程已经占有至少一个资源，但又提出了新的资源请求。3. 不剥夺条件：进程已经获得的资源不能被剥夺。4. 环路等待条件：在发生死锁时，必然存在一个进程资源环形链。12、处理死锁的根本方法P1051. 预防死锁：通过设置某些限制条件，破坏四个必要条件中的一个或几个。该方法比拟简单，但由于限制条件过于严格，往往导致系统资源利用率和吞吐量低。2. 防止死锁：不需事先预防，但在资源的动态分配时，用某种方法防止系统进入不平安状态，从而防止死锁。该方法比拟难于实现，但往往可获得较高资源利用率和系统吞吐量。3. 死锁的检测与解除：允许系统产生死锁，但能及时检测出来，并通过某些措施解除。该方法实现难度最大，但往往可获得较好的资源利用率和系统吞吐量。13、预防死锁的方法P106预防死锁的方法是使四个必要条件中的第2、3、4个条件不能成立，来防止发生死锁。至于必要条件1，因为他是由设备固有性能决定的，不仅不能改变，还应加以保证。互斥条件破坏不了1. 摒弃“请求和保持条件：资源静态分配2. 摒弃“不剥夺条件：资源的动态分配 3. 摒弃“环路等待条件：资源有序分配14、平安状态P107 所谓平安状态，是指系统能按某种进程顺序(P1, P2, ，Pn)(称P1, P2, , Pn序列为平安序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个平安序列，那么称系统处于不平安状态。 15、银行家算法P( 109 )16、死锁定理P113S状态是死锁的充分条件是，当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理第四章 存储器管理1、程序装入的方式P1191. 绝对装入方式：完全按照目标程序中所给定的地址装入存，即目标程序中使用的是绝对地址。该绝对地址既可在编译或汇编是给出，也可由程序员直接赋予。2.可重定位装入方式：通常是把在装入时对目标程序中指令和数据的修改正程称为重定位 。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位3. 动态运行时装入方式：在这种方式下动态运行时的装入程序，在把装入模块装入存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进展。因此， 装入存后的所有地址都仍是相对地址。 显然为使指令的执行不受影响，进展这种地址的动态转换，就必须有专门的硬件机构解决2、重定位、静态重定位、动态重定位P119重定位：我们把装入时对目标程序中的指令地址和数据地址的修改正程称为重定位。静态重定位：如果重定位是在装入时由装入程序一次性完成的，那么称为静态重定位。动态重定位：在这种方式下动态运行时的装入程序，在把装入模块装入存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进展。3、 存的连续分配方式有哪些？P1211. 单一连续分配单道2. 固定分区分配3. 动态可变式分区分配4. 可重定位分区分配4、 动态分区分配算法P1231. 首次适应算法2. 循环首次适应算法3. 最正确适应算法4. 最坏适应算法5. 快速适应算法5、 对换技术P129对换技术，是指把存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的存空间，再把已具备运行条件的进程或进程所需的程序和数据调入存的方法。6、 紧凑或拼接技术P127紧凑技术，是指通过移动存中作业的位置，把原先分散的小分区拼接成一个大分区的方法。在每次拼接后，都必须对移动了的程序或数据进展重定位7、 根本分页管理原理、地址变换过程P( 130)8、 分段系统的根本原理、地址变换过程P( 136 )9、 分页与分段的主要区别P1381. 页是信息的物理单位，分页是为了实现离散分配方式，以消减存的外零头，提高存利用率，分页是由于系统管理的需要而不是用户的需要。段那么是信息的逻辑单位，分段的目的是为了能更好地满足用户的需要。 2. 页的大小固定且由系统决定；而段的长度却不固定， 取决于用户所编写的程序。3. 分页的作业地址空间是一维的，即单一的线性地址空间； 而分段的作业地址空间那么是二维的。10、 虚拟存储器的定义、特征P143定义：虚拟存储器就是仅把作业的一局部装入存便可运行的存储器系统，具体说就是指具有请求调入功能和置换功能，能从逻辑上对存容量进展扩大的一种存储器系统。特性：1. 离散性：即非连续性，这是实现虚拟存储器管理技术的前提；2. 屡次性：一个作业被分成屡次调入存；3. 对换性：允许在作业运行过程中换入、换出；4. 虚拟性：能够从逻辑上扩大存容量。11、 页面置换算法：计算缺页次数、置换次数、缺页率、置换率P( 150 )第五章 设备管理1、设备管理的对象：设备、设备控制器、通道2、 I/O控制方式及开展宗旨P167I/O系统是用于实现数据的输入，输出及数据存储的系统I/O控制方式：1. 程序I/O方式忙等待方式2. 中断驱动I/O方式3. 直接存储器DMA控制方式4. I/O通道控制方式开展宗旨：尽量较少主机对I/O控制的干预，把主机从繁杂的I/O控制事务中解脱出来，以便更多的去完成数据处理任务。3、 缓冲引入的原因P1721. 缓和CPU与I/O设备间速度不匹配的矛盾。 2. 减少对CPU的中断频率， 放宽对CPU中断响应时间的限制。 3. 提高CPU和I/O设备之间的并行性。 4、 设备独立性应用程序独立于具体使用的物理设备叫设备独立性，也称为设备无关性。5、 SPOOLING原理、组成、特点、共享打印机原理P190SPOOLING原理：在联机情况下实现的外围操作与CPU对数据的处理同时进展，称为假脱机操作，又叫Spooling。Spooling系统的组成：1. 输入井和输出井2. 输入缓冲区和输出缓冲区为了缓和CPU与磁盘之间速度不匹配的矛盾3. 输入进程和输出进程4. 请求打印队列SPOOLing系统的特点：1. 提高了I/O的速度。2. 将独占设备改造为共享设备。 3. 实现了虚拟设备功能。共享打印机原理：共享打印机技术已被广泛地用于多用户系统和局域网络中。 当用户进程请求打印输出时， SPOOLing系统同意为它打印输出， 但并不真正立即把打印机分配给该用户进程， 而只为它做两件事： 1. 由输出进程在输出井中为之申请一个空闲磁盘块区， 并将要打印的数据送入其中；2. 输出进程再为用户进程申请一空白的用户请求打印表，并将用户的打印要求填入其中， 再将该表挂到请求打印队列上。6、磁盘时间包括什么？P1931. 寻道时间Ts2. 旋转延迟时间T3. 传输时间Tt7、 磁盘调度算法：计算平均寻道长度P ( 194 )第六章 文件管理1、文件文件是指由创立者所定义的、 具有文件名的一组相关元素的集合，可分为有构造文件和无构造文件两种。在有构造的文件中，文件由假设干个相关记录组成；而无构造文件那么被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。2、 文件的逻辑构造及分类P208文件的逻辑构造分为两大类：1. 有构造文件：即记录式文件；记录的长度分为定长记录和变长记录2. 无构造文件：即流式文件被看成字符流。3、 文件的物理构造及分类P213文件的物理构造直接与外存分配方式有关。可分为：1. 连续分配方式时的顺序式文件构造。2. 分配方式时的式文件构造。3. 索引分配方式时的索引式文件构造。4、 文件外存分配方式P2131. 连续分配。2. 分配。3. 索引分配。5、文件目录，目录查询方式文件目录是一种数据构造，用于标识系统中的文件及其物理地址，供检索时使用，是文件数据块的有序集合。目录查询方式：1. 线性检索法2. Hash方法6、 目录管理的要求1. 实现“按名存取。2. 提高对目录的检索速度。3. 文件共享。4. 允许文件重名。7、文件控制块为了能对一个文件进展正确的存取，必须为文件设置用于描述和控制的数据构造，称之为文件控制块包含三大信息：根本信息、存取控制信息、使用信息8、 索引节点概念，为什么引入索引节点？索引节点：采用将文件名与文件描述信息分开的方法，将文件描述信息单独形成一个数据构造叫索引节点简称i节点。引入原因：由于检索目录文件只用到文件名，即用不到该文件的描述信息，且在检索目录时索引节点不用调入存，从而大大节省了系统开销。9、 文件存储空间的管理方法1. 空闲表法2. 空闲链表法3. 位示图法4. 成组法 空闲表法和空闲链表法都不适合大型文件系统10、 成组法的空闲盘块组织、分配回收过程(1) 顺序扫描位示图，从中找出一个或一组其值为“0的二进制位(“0表示空闲时)。 (2) 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0的二进制位，位于位示图的第i行、第j列，那么其相应的盘块号应按下式计算： b=n(i-1)+j 式中， n代表每行的位数。 (3) 修改位示图，令mapi,j=1。空闲盘块的分配与回收：当系统要为用户分配文件所需的盘块时，首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。 假设该盘块号已是栈底， 即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此， 须调用磁盘读过程，将栈底盘块号所对应盘块的容读入栈中，作为新的盘块号栈的容，并把原栈底对应的盘块分配出去。 在系统回收空闲盘块时，将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时， 表示栈已满，便将现有栈中的100个盘块号， 记入新回收的盘块中，再将其盘块号作为新栈底。 第七章 操作系统接口1、操作系统接口分为用户接口和程序接口概念。用户接口包括命令接口、图形接口等。2、 程序接口程序接口是由一组系统调用组成。系统调用是在OS核心设置的一组实现系统功能的子程序过程。第八章 网络操作系统1、网络操作系统的功能数据通信，网络资源共享，应用互操作，网络管理应用互操作包括：信息互通性和信息互用性。在Internet下，主要利用TCP/IP协议实现信息的互通性。2、 网络操作系统提供的效劳：域名效劳，目录效劳，Web效劳3、目录管理记录了网络中的三大资源物理设备，网络效劳和用户的名字，属性和位置。1、进程同步互斥问题* 信号量类型:整型(忙等待)、记录型、AND型、一般信号量集解决的问题：1、描述前趋关系：根据前趋图，各边分别设置信号量，初值为0；假设某边从某节点出发，在此节点操作后，对该边对应信号量作signal操作；假设某边指向某节点，在此节点操作前，对该边对应信号量作wait错作；Var a,b,c,d,e,f,g,h,i,j: semaphore:=0,0,0,0,0,0,0,0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e);signal(f); end; begin wait(c); S4;signal(g); end; begin wait(d); S5;signal(h); end; begin wait(e); S6; signal(i); end; begin wait(f); S7; signal(j); end;begin wait(g); wait(h); wait(i); wait(j); S8; end; parend end 2、进程互斥问题资源共享* 根据临界资源的种类设置信号量的个数，初值为各临界资源的可用数量；* 在临界资源前，对对应信号量作wait操作；在完毕后作signal操作，即将临界区放在wait和signal之间。3、进程同步相互合作* 为同步双方设置各自的信号量，初值为其初始状态可用的资源数(故该信号量称为资源信号量或私有信号量)；* 同步双方任一进程在进入临界区之前，应先对自己的信号量执行wait()操作，以测试是否有自己可用的资源。假设有资源可用，那么进入临界区，否那么阻塞；同步双方任一进程离开临界区后，应对合作方 (对方)的信号量执行signal()操作，以通知(假设对方处于阻塞状态，那么唤醒它)对方已有资源可用(对方已可进入临界区)。* 有一个阅览室，共有100个座位，读者进入时必须先在一登记表上登记，该表为每一个座位列一表目，包括座号和读者等，读者离开时要消掉登记的信息，试用wait,signal原语描述各个进程之间的同步互斥关系。Var s,mutax: semaphore:=100,1;Reader：BeginRepeatWait(s);Wait(mutex);登记；Signal(mutex);阅览图书；Wait(mutex);取消登记；Signal(mutex);Signal(s);Until fasleend桌上有一个盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放橘子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，爸爸妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出他们四人之间的同步关系程序。VAR s,so,sa:semaphore :=1,0,0;/s表示盘空，so表示橘子，sa表示苹果。parbeginFather:begin repeatwait(s); put apple();signal(sa);until false endMother:begin repeat wait(s); put orange(); signal(so); until false endSon:begin repaet wait(so); eat orange(); signal(s); until false end daughter:beginrepeat wait(sa); eat apple(); signal(s); until falseendparend2设公共汽车上有一位司机和一位售票员，它们的活动如下： 司机：启动车辆，行车，到站停车，售票员：售票；到站开门，关门请分析司机与售票员之间的同步关系，如何用PV操作实现。答：为了平安起见，显然要求：关车门后才能启动车辆；到站停车后才能开车门。所以司机和售票员在到站、开门、关门、启动车辆这几个活动之间存在着同步关系。用两个信号量S1、S2分别表示可以开车和可以开门，S1的初值为1，S2的初值为0。用PV操作实现司机进程和售票员进程同步的算法描述如下：司机： PS1 ；启动车辆 ；正常行车 ；到站停车；VS2； 售票员： 售票； PS2 ； 开车门； 关车门； VS1；生产者消费者问题三个进程两个缓冲区俩俩合作下页；设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1 加工一个车架放入货架A中；工人2、3分别加工车轮放入货架B中每人每次放入1个车轮；工人4从货架A中取一个车架，再从货架B中取两个车轮，组装成一辆自行车。试用PV操作实现四个工人的合作1、系统中有是三个进程GET，PRO和PUT，共用两个缓冲区BUF1和BUF2。假设BUF1中最多可放8个信息，BUF2中最多可放5个信息。GET进程负责不断地将信息送入BUF1中，PRO进程负责从BUF1中取出信息进展处理，并将处理结果送到BUF2中，PUT进程负责从BUF2中读取结果并输出。试用wait、signal原语P、V操作实现GET，PRO，PUT进程之间的同步算法。1、 var：mutex1，mutex2，empty1，empty2，full11，full2：=1，1，8，5，0，0；GET:begin repeatwait(empty1);wait(mutex1);送入BUF1；; signal(mutex1); signal(full);until false endPRO:begin repeat wait(full1); wait(mutex1); 从BUF1中取信息加工;signal(mutex1);signal(empty1);wait(empty2);wait(mutex2);将加工后的信息放入BUF2;signal(mutex2);signal(full2);until falseendPUT:begin repeat wait(full2);wait(mutex2);从BUF2中取信息输出;signal(mutex2);signal(empty2); until falseend【分析】设置资源信号量和互斥信号量如下： 信号量Aempty表示货架A的空位数，其初值为8； 信号量Afull表示货架A上存放的车架数，其初值为0； 信号量Bempty表示货架B的空位数，其初值为20； 信号量Bfull表示货架B上存放的车轮数，其初值为0； 信号量mutex用于互斥初值为1。 Var Aempty,Afull,Bempty,Bfull,mutex:semaphore; Aempty.value:=8; Afull.value:=0; Bempty.value:=20;Bfull.value:=0; mutext.value:=1; wheelcount:integer:=0;Begin parbegin worker1:begin repeat生产一个车架； wait(Aempty);/看看货架A上是否有空位置车架放到货架A上； signal(Afull);/货架A上的车架数增1，并通知工人4 until false; end Worker2，3:begin repeat生产一个车轮； wait(Bempty);/看看货架B上是否有空位置 wait(mutex);将车轮放到货架B上； signal(mutex); signal(Bfull);/货架B上的车轮数增1，并通知工人4 until false; end Worker4:begin repeat wait(Afull);wait(Bfull);wait(Bfull);取一个车架和两个车轮； signal(Aempty);signal(Bempty);signal(Bempty);组装一辆自行车； until false end parendend哲学家就餐问题非死锁算法 至多允许4个哲学家同时取左边的筷子，这样能至少保证一个哲学家能就餐，并在用毕后释放他用过的两只筷子，从而使更多的哲学家能够进餐。请学生考虑算法的描述 仅当哲学家左右两只筷子均可用时，才允许他拿起筷子进餐。用AND信号量机制 规定奇数号哲学家先拿左边筷子，然后再拿右边筷子；而偶数号哲学家先拿右边筷子，然后再拿左边筷子。1 var chopstick:array0,4 of semaphore := 1,1,1,1,1; Sm:semaphore := 4;beginrepeat wait(Sm); wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal(chopsticki); signal(chopstick(i+1) mod 5);signal(Sm);think;until falseEnd2 var chopstick:array0,4 of semaphore := 1,1,1,1,1; beginrepeat swait(chopsticki，chopstick(i+1) mod 5); eat; ssignal(chopsticki，chopstick(i+1) mod 5); think;until falseend3var chopstick:array0,4 of semaphore := 1,1,1,1,1;beginrepeat if i mod 2=0 then begin wait(chopsticki); wait(chopstick(i+1) mod 5); end;else begin wait(chopstick(i+1) mod 5); wait(chopsticki); end; eat; signal(chopsticki); signal(chopstick(i+1) mod 5);think;until falseEnd读者写者问题及变形-独木桥问题假定有如下独木桥问题：过桥时，同一方向的行人可连续过桥，当某一方有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。试用信号量机制解决。 答案： (1) 将独木桥的两个方向分别标记为A和B。用整型变量countA和countB分别 表示A、B方向上已在独木桥上的行人数。初值为0。需要设置三个初值都为1的互斥信号量：SA用来实现对countA的互斥，SB用来实现对countB的互斥，mutex用来实现对独木桥的互斥使用。 (2) A方向行人过桥： Begin P(SA); countA=countA+1; if (countA= =1) P(mutex); V(SA); 过桥； (SA); countA=countA-1; if(countA= =0) V(mutex); V(SA); End B方向行人过桥： Begin P(SB); countB=countB+1; if (countB= =1) P(mutex); V(SB); 过桥； P(SB); countB=countB-1; if(countB= =0) V(mutex); V(SB); End 处理机调度算法：1. 先来先效劳调度算法 该算法既可用于作业调度又可用于进程调度，用于前者时，每次调度都是从