2022年操作系统重点知识总结.docx

《2022年操作系统重点知识总结.docx》由会员分享，可在线阅读，更多相关《2022年操作系统重点知识总结.docx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习必备欢迎下载第一章 引论1、操作系统定义 （ P1 ）操作系统是配置在运算机硬件上的第一层软件,是对硬件系统的首次扩充；是一组掌握和治理运算机硬件和软件资源、合理地对各类作业进行调度以及便利用户使用的程 序的集合；2、操作系统的作用 （ P2 ）1. OS 作为用户与运算机硬件系统之间的接口2. OS 作为运算机系统资源的治理者3. OS 实现了对运算机资源的抽象3、推动操作系统进展的主要动力（ P4 ）1. 不断提高运算机资源的利用率2. 便利用户3. 器件的不断更新迭代4. 运算机体系结构的不断进展4、多道批处理系统的特点及优缺点（ P8 ）特点：多道性、无序性、调度性优点：1. 资源

2、利用率高2. 系统吞吐量大缺点：1. 平均周转时间长2. 无交互才能（单道、多道都是）5、分时系统和实时系统特点的比较（ P12 ）1. 多路性（实时系统的多路性主要表现在系统周期性地对多路信息的采集、以及对多个对象或多个执行机制进行掌握；分时系统中的多路性就和用户有关,时多时少； ）2. 独立性3. 准时性:（实时系统对准时性的要求更严格,实时掌握系统以掌握对象要求的开头截止时间或完成截止时间来确定；）4. 交互性 :实时系统的交互性仅限于拜访某些专用服务程序；5. 牢靠性 :实时系统对牢靠性的要求更高,否就经济缺失及后果无法预料；6 、操作系统的基本特点（ P14 ）（并发、共享、虚拟和异

3、步其中并发特点是操作系统最重要的特点是其他特点的前提）1. 并发性2. 共享性 （互斥共享方式、同时拜访方式）3. 虚拟性 （时分复用技术 （虚拟处理机技术、虚拟设备技术） 、空分复用技术 （虚拟磁盘技术、虚拟储备器技术） ）4. 异步性（进程的异步性： 进程是以人们不行预知的速度向前推动的）7 、操作系统的主要功能（ P18 ）1. 处理机治理功能 （进程掌握（ 1、进程互斥方式：进程或者线程在对临界资源进行拜访时,应 实行互斥方式； 2、进程同步方式：相互合作去完成共同任务的诸进程货线程） 、进程通信、 调度（作业调度、进程调度） ）2. 储备器治理功能（内存安排、内存爱护、地址映射、内存

4、扩充）3. 设备治理功能 （缓冲治理、 设备安排、 设备处理）4. 文件治理功能 （文件储备空间的治理、 目录治理、文件的读 /写治理和爱护）5. 用户接口 （命令接口 （联机用户接口、 脱机用户接口）、程序接口、图形接口）其次章 进程治理1 、程序次序执行时的特点（ P34 ）1. 次序性 ：严格依据程序所规定的次序执行；2. 封闭性 ：程序在封闭环境下运行, 系统中全部资源的状态只有本程序才能转变它；3. 可再现性 ：只要初始条件相同, 无论怎样执行,其结果都是相同的；2、程序并发执行时的特点（提高了系统吞吐量）（ P36 ）1. 间断性 ：并发执行的实体之间相互制约,造成程序的执行显现间

5、断,而不连续；2. 非封闭性 ：多个程序共享系统资源, 因而其状态有多个程序转变,从而失去封闭性；5 、引入挂起状态的缘由（ P39 ）1. 终端用户的恳求2. 父进程恳求3. 负荷调剂的需要4. 操作系统的需要6 、具有挂起状态的进程状态及其转换图3. 不行再现性 ：封闭性的失去必定导致不行再现性；3、进程及其特点 （ P37 ）进程是进程实体的运行过程, 是系统进行资源安排和调度的一个独立单位；进程是程序的一次执行进程实体 ：由程序段、相关的数据段和PCB构成特点：I/O求请活动就绪放释激活活动堵塞挂起执行挂起激活静止挂起就绪放静止释堵塞结构特点动态性（ 进程最基本的特点 ）并发性（ 引人

6、进程的目的：为了使其进程实体能和其他的进程实体并发执行；而程序（没有建立PCB）不能并发执行 ）独立性异步性4、进程的基本状态及其转换图（P38 ）1. 就绪 Ready状态2. 执行状态3. 堵塞状态 （典型事例：恳求I/O 、申请缓冲空间等）就 绪时间 片完7 、进程掌握块及其作用（ P41 ）PCB 是一种数据结构,是进程实体的一部分, 记录了操作系统所需的、用于描述进程的当前情形 以及掌握进程运行的全部信息；作用：1. 使一个在多道程序环境下不能独立运行的程序含数据 ,成为一个能独立运行的基本单位,一个能与其它进程并发执行的进程；或者说,OS 是依据 PCB 来对并发执行的进程进行掌握

7、和治理的；2. PCB 是进程存在与否的唯独标志 , 随着进程的建立而建立 ,随着进程的撤消而撤消； 创建进程就是创建 PCB；8 、进程之间的两种制约关系（P48 ）I/O完 成进 程 调度阻 塞执 行I/O 恳求1. 间接制约竞争资源进程互斥2. 直接制约相互合作进程同步9 、临界资源 （P48 ）OS 中把一次只能被一个进程使用的资源成为临界资源；10 、临界区 （ P50 ）进程中拜访临界资源的那段代码称为临界区；11 、同步机构应遵循的规章（ P50 ）闲暇让进、忙就等待、有限等待、让权等待12 、利用信号量实现前驱关系算法P 54 P 55 13 、经典同步算法（生产者消费者问题,

8、哲学家就餐问题和读者写者问题）略14 、进程通信的类型 （P65 ）低级：信号量进程通信共享储备器系统（基于共享数据结构 或储备区 的通信方式）高级消息传递系统（直接、间接）管道通信系统（必需供应的和谐才能：互斥、同步、确定对方是否存在）15 、线程的定义 （ P72 ）现代 OS 引入的比进程更小的可以独立运行、调度的基本单位,是轻型实体,不拥有资源 ；16 、线程和进程比较线程又称为轻型进程, 通常一个进程都拥有如干个线程,至少也有一个（多线程OS 中的进程不是一个可执行的实体）1、调度 ：传统 OS 中,进程是拥有资源的基本单位, 独立调度、 分派的基本单位； 引入线程后, 就把线程作为

9、调度和分派的基本单位,而进程作为拥有资源的基本单位2、并发性 ：引入线程的 OS 中,进程之间可以并发执行,在一个进程中的多个线程之间也可以；这样使得 OS 具有更好的并发性,从而能更加有效的提高系统资源的利用率和吞吐量3、拥有资源 ：线程不能拥有资源4、系统开销 ：就切换代价而言,进程远高于线程17、线程的属性 （ P73 ）1. 轻型实体2. 独立调度和分派的基本单位3. 可并发执行4. 共享进程资源第三章 处理机调度与死锁1 、高级调度 （P84 ）又称为 作业调度 ；即从外存的后备队列中挑选一个作业,为它 创建进程 ,安排必要的 资源,并将新进程 插入主存的 就绪队列 上；留意： 分时

10、系统和实时系统无作业调度 ；JCB （作业掌握块） ；是作业在系统中存在的标志,其中储存了系统对作业进行治理和调度所需的全部信息2 、低级调度 （P86 ）又称进程调度 或短程调度 ,即从就绪队列中挑选一个进程进入运行状态（非抢占方式、可抢占方式）；调度的对象是进程（多批道处理、分时、实 时三种类型的 OS 中都有）3 、中级调度 （P87 ）中程调度为了提高内存利用率和系统吞吐量（引入目的）,为此,应使那些临时不能运行的进程不再占用内存资源,而将它们调至外存；适当时机再将其调回内存；这种调度称为中级调度；4 、进程调度的两种方式（ P86 ）1、非抢占方式（ 一旦给进程安排处理机,始终让他运

11、行下去,直到完成再把处理机安排给其他 进程）2、抢占方式（ 答应调度程序依据某些原就去暂停某个正在执行的进程,将已安排给该进程的处理机重新安排给另一个进程）学习必备欢迎下载5、抢占的原就 （ P87 ）1. 优先权原就2. 短作业（进程）优先原就3. 时间片原就6、操作系统挑选调度方式和调度算法的如干准就 （P90 ）1. 面对用户的准就（周转时间短、 响应时间快、截止时间的保证、优先权准就）2. 面对系统的准就 （系统吞吐量高、 处理机利用率好、各类资源的平稳利用）7、周转时间 （P92 ）周转时间：是指从作业被提交给系统开头, 到作业完成为止的这段时间间隔周转时间= 完成时间- 到达时间待

12、权周转时间 = 周转时间/ 服务时间8、针对各种调度算法（先来先服务,短进程优先,优先权） ,运算周转时间、带权周转时间 , 平均周转时间、平均带权周转时间9、吞吐量指在单位时间内系统所完成的作业数10 、多级反馈队列调度算法的原理、性能该算法用于 进程调度 ,主要是为解决前面各种进程调度算法存在的各种不同问题而设计的一种考虑综合因素的调度算法；其思想如下：1、设置多个就绪队列,不同队列具有不同优先级,第一个队列优先级最高,以后次之；给不同队列安排不同大小的时间片, 第一个队列最小,以后次之（皆为前者的二倍） ；有的系统也将最终一级队列不划分时间片；2、当有一个新进程进入内存后,第一将它放 入

13、第一队列的末尾,按FCFS（先来先服务）原就排队等待调度；当轮到该进程执行时,假如它能在该时间片内完成,便可预备撤离系统；如不能就将它放在其次列的队尾； ；3、仅当前一级队列为空时才调度下一级队列中的进程；算法采纳抢占式调度策略；执行的进程在规定的时间片内为执行完毕,就进入下一级队列的队尾,新进程就进入第一级队列的队尾；性能：（较好的性能, 能满意各种类型的用户）1、终端型作业用户2、短批处理作业用户3、长批处理作业用户11、死锁、产生死锁缘由、必要条件（P103 ）死锁 是指两个或多个进程由于资源竞争 而造成的一种僵局,如无外力作用,这些进程将永久无法向前推动；产生死锁的 缘由：1. 竞争资

14、源 （可剥夺和非剥夺性资源、 竞争非剥夺性资源、竞争临时性资源）2. 进程推动次序非法（恳求和释放资源的次序不当）必要条件 ：1. 互斥条件：进程间必需互斥使用某些资源才可能产生死锁；2. 恳求保持条件：进程已经占有至少一个资源,但又提出了新的资源恳求；3. 不剥夺条件：进程已经获得的资源不能被剥夺；4. 环路等待条件：在发生死锁时,必定存在一个进程资源环形链；12、处理死锁的基本方法（ P105 ）1. 预防死锁 ：通过设置某些限制条件,破坏四个必要条件中的一个或几个；该方法比较简洁, 但由于限制条件过于严格,往往导致系统资源利用 率和吞吐量低；2. 防止死锁 ：不需事先预防,但在资源的动态

15、安排时,用某种方法防止系统进入担心全状态, 从而防止死锁 ；该方法比较难于实现,但往往可获得较高资源利用率和系统吞吐量；3. 死锁的检测与解除 ：答应系统产生死锁, 但能准时检测出来,并通过某些措施解除；该方法 实现难度最大,但往往可获得较好的资源利用率和 系统吞吐量；13 、预防死锁的方法 （P106 ）预防死锁的方法是使四个必要条件中的第2、3、4 个条件不能成立, 来防止发生死锁； 至于必要条件 1,由于他是由设备固有性能打算的,不仅不能转变,仍应加以保证； （互斥条件破坏不了）1. 摒弃“恳求和保持”条件：资源静态安排2. 摒弃“不剥夺”条件：资源的动态安排3. 摒弃“环路等待”条件：

16、资源有序安排14 、安全状态 （ P107 ）所谓安全状态 ,是指系统能按某种进程次序P1, P2, ,Pn称P1, P2, , Pn序列为安全序列 ,来为每个进程 Pi 安排其所需资源,直至满意每个进程对资源的 最大需求 ,使每个进程都可顺当地完成 ；假如系统无法找到这样一个安全序列,就称系统处于担心全状态；15 、银行家算法P 109 16 、死锁定理 （ P113 ）S 状态是死锁的 充分条件 是,当且仅当 S 状态的资源安排图是不行完全简化的；该充分条件被称为死锁定理第四章 储备器治理1、程序装入的方式 （ P119 ）1. 肯定装入方式 ：完全依据目标程序中所给定的地址装入内存,即目

17、标程序中使用的是肯定地址；该肯定地址 既可在编译或汇编是给出,也可由程序员直接给予；2. 可重定位装入方式：通常是把在装入时对目 标程序中指令和数据的修改过程称为重定位 ；又由于地址变换通常是在装入时一次完成的,以后不再转变,故称为 静态重定位3. 动态运行时装入方式 ：在这种方式下动态运行时的装入程序,在把装入模块装入内存后,并不 立刻把装入模块中的相对地址转换为肯定地址,而 是把这种地址转换推迟到程序真刚要执行时才进行；因此,装入内存后的全部地址都仍是相对地址； 明显为使指令的执行不受影响,进行这种地址的动态转换,就必需有特地的硬件机构解决2 、重定位、静态重定位、动态重定位（ P119

18、）重定位 ：我们把装入时对目标程序中的指令地址和数据地址的修改过程称为重定位；静态重定位 ：假如重定位是在装入时由装入程序一次性完成的,就称为静态重定位；动态重定位 ：在这种方式下动态运行时的装入程序,在把装入模块装入内存后,并不立刻把装入模块中的相对地址转换为肯定地址,而是把这种地址转换推迟到程序真刚要执行时才进行；3 、内存的连续安排方式有哪些？（ P121 ）1. 单一连续安排（单道）2. 固定分区安排3. 动态（可变式）分区安排4. 可重定位分区安排4 、动态分区安排算法 （ P123 ）1. 首次适应算法2. 循环首次适应算法3. 正确适应算法4. 最坏适应算法5. 快速适应算法5

19、、对换技术 （P129 ）对换技术 ,是指把内存中 临时不能运行 的进程或者临时不用 的程序和数据调出到外存上, 以便腾出足够的内存空间, 再把已具备运行条件的进程 或进程所需的程序和数据 调入内存的方法；6 、紧凑或拼接技术 （ P127 ）紧凑技术 ,是指通过移动内存中作业的位置,把原先分散的小分区拼接成一个大分区的方法；在每次拼接后,都必需对移动了的程序或数据进行重定位7、基本分页治理原理、地址变换过程P 1308、分段系统的基本原理、地址变换过程P 136 9、分页与分段的主要区分（ P138 ）1. 页是信息的物理单位 ,分页是为了实现离散安排方式,以消减内存的外零头,提高内存利用

20、率,分页是由于系统治理的需要而不是用户的需要；段就是信息的规律单位 ,分段的目的 是为了能更好地满意用户的需要；2. 页的大小固定且由系统打算；而段的长度却不固定 , 取决于 用户所编写的程序；3. 分页的作业地址空间是一维 的,即单一的线性地址空间；而分段的作业地址空间就是二维 的；10 、虚拟储备器的定义、特点（ P143 ）定义：虚拟储备器就是 仅把作业的一部分装入内存便可运行的储备器系统,详细说就是指 具有恳求调入功能 和置换功能 ,能从规律上对内存容量进行扩充的一种储备器系统；特性：1. 离散性 ：即非连续性,这是实现虚拟储备器治理技术的 前提；2. 多次性 ：一个作业被分成多次调入

21、内存；3. 对换性 ：答应在作业运行过程中换入、换出；4. 虚拟性 ：能够从规律上扩充内存容量；11、页面置换算法：运算缺页次数、 置换次数、缺页率、置换率P 150 第五章 设备治理1、设备治理的对象：设备、设备掌握器、通道2 、I/O 掌握方式及进展宗旨 （ P167 ）I/O 系统是用于实现数据的输入,输出及数据储备的系统I/O 掌握方式 ：1. 程序 I/O 方式（忙等待方式）2. 中断驱动 I/O 方式3. 直接储备器拜访 DMA 掌握方式4. I/O 通道掌握方式进展宗旨：尽量较少主机对 I/O 掌握的干预, 把主机从纷杂的 I/O 掌握事务中解脱出来,以便更多的去完成数据处理任务

22、；3 、缓冲引入的缘由 （ P172 ）1. 缓和 CPU 与 I/O 设备间速度不匹配的冲突；2. 削减对 CPU 的中断频率, 放宽对 CPU 中断响应时间的限制；3. 提高 CPU 和 I/O 设备之间的并行性；4 、设备独立性应用程序独立于详细使用的物理设备叫设备独立性,也称为设备无关性；5 、SPOOLING原理、 组成、 特点、 共享打印机原理 （ P190 ）SPOOLING原理： 在联机情形下实现的外围操作与 CPU 对数据的处理同时进行 ,称为 假脱机操作,又叫 Spooling；Spooling 系统的 组成：1. 输入井和输出井2. 输入缓冲区和输出缓冲区（为了缓和CPU

23、与磁盘之间速度不匹配的冲突）3. 输入进程和输出进程4. 恳求打印队列SPOOLing 系统的 特点 ：1. 提高了 I/O 的速度；2. 将独占设备改造为共享设备；3. 实现了虚拟设备功能；共享打印机原理：共享打印机技术已被广泛地用于多用户系统和局域网络中； 当用户进程恳求打印输出时,SPOOLing 系统同意为它打印输出, 但并不真正立刻把打印机安排给该用户进程, 而只为它做两件事：4 、文件外存安排方式 （ P213 ）1. 连续安排 ；2. 链接安排 ；3. 索引安排；5 、文件目录,目录查询方式1. 由输出进程在输出井中为之申请一个闲暇磁盘块区, 并将要打印的数据送入其中；2. 输出

24、进程再为用户进程申请一张空白的用户恳求打印表, 并将用户的打印要求填入其中,再将该表挂到恳求打印队列上；6、磁盘拜访时间包括什么？（ P193 ）1. 寻道时间 Ts2. 旋转推迟时间 T3. 传输时间 Tt7、磁盘调度算法：运算平均寻道长度P 194 第六章 文件治理1、文件文件是指由创建者所定义的、具有文件名的一组相关元素的集合 ,可分为 有结构文件 和无结构文件两种；在有结构的文件中,文件由如干个相关 记录组成；而无结构文件就被看成是一个字符流；文件在文件系统中是一个最大的数据单位,它描述了一个对象集；2、文件的规律结构及分类（ P208 ）文件的 规律结构 分为两大类：1. 有结构文件

25、 ：即记录式文件 ；记录的长度分为定长记录 和变长记录2. 无结构文件 ：即流式文件 （被看成字符流） ；3、文件的物理结构及分类（ P213 ）文件的 物理结构 直接与外存安排方式有关； 可分为：1. 连续安排 方式时的 次序式文件结构 ；2. 链接安排 方式时的 链接式文件结构 ；3. 索引安排 方式时的 索引式文件结构 ；文件目录 是一种数据结构, 用于标识系统中的文件及其物理地址,供检索时使用,是 文件数据块的有序集合 ；目录查询方式 ：1. 线性检索法2. Hash 方法6 、目录治理的要求1. 实现“按名存取” ；2. 提高对目录的检索速度；3. 文件共享；4. 答应文件重名；7

26、、文件掌握块为了能对一个文件进行正确的存取,必需为文 件设置用于 描述和掌握的数据结构 ,称之为 文件掌握块（包含三大信息：基本信息、存取掌握信息、使用信息）8 、索引节点概念,为什么引入索引节点？索引节点 ：采纳将文件名与文件描述信息分开的方法,将文件描述信息单独形成一个数据结构叫索引节点 简称 i 节点；引入缘由 ：由于检索目录文件只用到文件名, 即用不到该文件的描述信息,且在检索目录时索引 节点不用调入内存,从而大大节约了系统开销；9 、文件储备空间的治理方法1. 闲暇表法2. 闲暇链表法3. 位示图法4. 成组链接法 （闲暇表法和闲暇链表法都不适合大型文件系统）学习必备欢迎下载10 、

27、成组链接法的闲暇盘块组织、安排回收过程第七章 操作系统接口1、操作系统接口闲暇盘块号栈S.free10003001299982029920110010099分为用户接口和程序接口（概念）；用户接口40003997999包括命令接口、图形接口等；3004007900299399789979993012013017901780179012 、程序接口程序接口是由一组系统调用组成；系统调用是在 OS 核心设置的一组实现系统功能的子程序（过程）；第八章 网络操作系统1、网络操作系统的功能数据通信,网络资源共享,应用互操作,网络(1) 次序扫描位示图,从中找出一个或一组其值为“ 0”的二进制位 “ 0”

28、表示闲暇时 ；(2) 将所找到的一个或一组二进制位,转换成与之相应的盘块号；假定找到的其值为“0” 的二进制位,位于位示图的第i 行、第 j 列,就其相应的盘块号应按下式运算：b=ni-1+j式中, n 代表每行的位数；(3) 修改位示图,令 mapi,j =1；闲暇盘块的安排与回收： 当系统要为用户安排文件所需的盘块时,第一检查闲暇盘块号栈是否上锁,如未上锁,便从栈顶取出一闲暇盘块号,将与之对应的盘块安排给用户,然后将栈顶指针下移一格；如该盘块号已是栈底,即 S.free0, 这是当前栈中最终一个可安排的盘块号；由于在该盘块号所对应的盘块中记有下一组可用的盘块号, 因此, 须调用磁盘读过程,

29、将栈底盘块号所对应盘块的内容读入栈中,作为新的盘块号栈的内容, 并把原栈底对应的盘块安排出去；在系统回收闲暇盘块时, 将回收盘块的盘块号记入闲暇盘块号栈的顶部,并执行闲暇盘块数加 1 操作；当栈中闲暇盘块号数目已达100 时, 表示栈已满,便将现有栈中的100 个盘块号, 记入新回收的盘块中,再将其盘块号作为新栈底；治理应用互操作包括：信息互通性和信息互用性； 在 Internet 下,主要利用 TCP/IP 协议实现信息的互通性；2 、网络操作系统供应的服务：域名服务,目录服务, Web 服务3 、目录治理记录了网络中的三大资源物理设备,网络服务和用户的名字,属性和位置；1、进程同步互斥问题

30、* 信号量类型 : 整型 忙等待 、记录型、 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; beginparbeginbegin S1; signala; signalb; end;beginwaita;S2;signalc;signald;end;beginwaitb;S3;signale

31、;signalf;end;begin waitc; S4;signalg;end; begin waitd; S5;signalh;end; begin waite; S6; signali; end; begin waitf; S7; signalj; end;begin waitg; waith; waiti; waitj;S8; end; parendend2、进程互斥问题（资源共享）* 依据临界资源的种类设置信号量的个数,初值为各临界资源的可用数量；* 在拜访临界资源前,对对应信号量 作 wait 操作；在拜访终止后作signal 操作, 即将临界区放在 wait 和 signal 之

32、间；3、进程同步（相互合作）* 为同步双方设置各自的信号量,初 值为其初始状态可用的资源数 故该信号量称为资源信号量或私有信号量；* 同步双方任一进程在进入临界区之前,应先对自己的信号量执行wait操作,以测试是否有自己可用的资源；如有资源可用,就进入临界区, 否就堵塞；同步双方任一进程离开临界区后,应对合作方 对方 的信号量执行signal 操作,以通知 如对方处于堵塞状态,就唤醒它 对方已有资源可用 对方已可进入临界区 ；* 有一个阅览室,共有100 个座位, 读者进入时必需先在一张登记表上登记, 该表为每一个座位列一表目,包括座号和读者姓名等, 读者离开时要消掉登记的信息,试用 wait

33、,signal 原语描述各个进程之间的同步互斥关系；Var s,mutax: semaphore:=100,1; Reader：BeginRepeat Waits; Waitmutex;登记；Signalmutex;阅览图书；Waitmutex;取消登记； Signalmutex; Signals;Until fasle end学习必备欢迎下载waitso; eat orange; signals; until falseend daughter:begin repeatwaitsa;eat apple;桌上有一个盘子,每次只能放一个水果,爸爸专向盘中放苹果,妈妈专向盘中放橘子,儿子专等end

34、signals; until false吃盘里的桔子,女儿专等吃盘里的苹果；只要盘子空,爸爸妈妈可向盘中放水果,仅当盘中有自己需要的水果时,儿子或女儿可从中取出,请给出他们四人之间的同步关系程序；VAR s,so,sa:semaphore :=1,0,0;/s表示盘空, so表示橘子, sa 表示苹果；parbegin Father:beginrepeat waits;put apple; signalsa; until falseend Mother:beginrepeatparend2设公共汽车上有一位司机和一位售票员, 它们的活动如下：司机：启动车辆,行车,到站停车, 售票员：售票；到站

35、开门,关门请分析司机与售票员之间的同步关系,如何用PV 操作实现；答：为了安全起见,明显要求：关车门后才能启动车辆；到站停车后才能开车门；所以司机和售票员在到站、开门、关门、启动车辆这几个活动之间存在着同步关系；用两个信号量S1、S2 分别表示可以开车和可以开门,S1 的初值为 1,S2 的初值为 0；用 PV 操作实现司机进程和售票员进程同步的算法描述如下：司机：waits;P（ S1）；put orange;启动车辆；signalso;正常行车；until false到站停车；endV （S2）；售票员：Son:beginrepaet售票；P（ S2） ；开车门； 关车门； V（ S1）；

36、生产者消费者问题三个进程两个缓冲区俩俩合作（下页）；设自行车生产车间有两个货架, 货架 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进程负责

37、不断地将信息送入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 （repeatwaitempty1; waitmutex1; 送入 BUF1 ；;signalmutex1;signalfull; until false endPRO:be

38、ginrepeat waitfull1; waitmutex1;从 BUF1 中取信息加工 ;signalmutex1; signalempty1; waitempty2; waitmutex2;将加工后的信息放入BUF2;signalmutex2; signalfull2; until falseend PUT:beginrepeat waitfull2; waitmutex2;从 BUF2 中取信息输出 ;signalmutex2; signalempty2;until falseend【分析】设置资源信号量和互斥信号量如下：信号量 Aempty 表示货架 A 的空位数,其初值为 8；信号

39、量 Afull 表示货架 A 上存放的车架数,其初值为0；信号量 Bempty 表示货架 B 的空位数,其初值为 20；信号量 Bfull 表示货架 B 上存放的车轮数,其初值为0；信号量 mutex 用于互斥（初值为 1）；Var Aempty,Afull,Bempty,Bfull,mutex:sem aphore;Aempty.value:=8; Afull.value:=0;Bempty.value:=20;Bfull.value:=0; mutext.value:=1;wheelcount:integer:=0;Beginparbegin worker1:beginrepeat生产一个

40、车架；waitAempty;/ 看看货架A 上是否有空位置车架放到货架A 上；signalAfull;/ 货架 A 上的车架数增 1,并通知工人4until false; endWorker2,3:beginrepeat生产一个车轮；waitBempty;/ 看看货架B 上是否有空位置waitmutex;将车轮放到货架 B 上；signalmutex;signalBfull;/ 货架 B 上的车轮数增1,并通知工人4until false; end Worker4:beginrepeatwaitAfull;waitBfull;waitBfull;取一个车架和两个车轮；signalAempty;

41、signalBempty;signalBempty;组装一辆自行车；until false endparend end哲学家就餐问题（非死锁算法） 至多答应 4 个哲学家同时取左边的筷子, 这样能至少保证一个哲学家能就餐,并在用毕后释放他用过的两只筷子,从而使更多的哲学家能够进餐； （请同学考虑算法的描述） 仅当哲学家左右两只筷子均可用时,才答应他拿起筷子进餐； （用 AND信号量机制） 规定奇数号哲学家先拿左边筷子,然后再拿右边筷子；而偶数号哲学家先拿右边筷子,然后再拿左边筷子；（ 1 ）varchopstick:array0, ,4of semaphore := 1,1,1,1,1;Sm:

42、semaphore := 4; beginrepeatwaitSm; waitchopsticki;waitchopsticki+1 mod 5; eat;signalchopsticki; signalchopsticki+1 mod 5; signalSm;think; until false End（ 2）var chopstick:array0,o,f4 semaphore := 1,1,1,1,1;begin repeatswaitchopsticki , chopsticki+1 mod 5;eat;ssignalchopsticki ,chopsticki+1 mod 5; think;until false end（3）var chopstick:array0,4 of semaphore :=1,1,1,1,1;be