当前位置：文档之家 › 操作系统第四章1

操作系统第四章1

  • 格式：ppt
  • 大小：365.50 KB
  • 文档页数：82

下载文档原格式

  / 82

合集下载

操作系统-第4章复习题答案

操作系统-第4章复习题答案

操作系统-第4章复习题答案操作系统第四章复习题⼀、选择题1、在可变式分区分配⽅案中，某⼀作业完成后系统收回其主存空间，并与相邻空闲区合并，为此修改空闲区表，造成空闲区数减⼀的情况是（ D ）。

A ⽆上邻空闲区，也⽆下邻空闲区B 有上邻空闲区，但⽆下邻空闲区C 有下邻空闲区，但⽆上邻空闲区D 有上邻空闲区，也有下邻空闲区2、分区式存储器管理⽅式，每个程序（B）。

A ⼀定在分区中连续，部分存放B ⼀定在分区中连续，整体存放C 可以在分区中不连续，整体存放D 可以在分区中连续，部分存放3、下列选项中对分段存储管理叙述正确的是（B）A 分段存储管理中每个段必须是⼤⼩相等的。

B 每⼀段必须是连续的存储区C 每⼀段不必是连续的存储区D 段间的存储区必须是连续的4、下列对重定位的叙述中，正确的选项是（B）。

A 经过静态重定位后，指令代码并不发⽣变化。

B 经过静态重定位后，数据地址和指令地址发⽣了变化C 经过动态重定位后，指令代码中的操作码和操作数地址都要发⽣变化。

D经过动态重定位后，数据地址发⽣了变化⽽指令地址没有发⽣变化。

5、虚拟存储器功能的管理⽅法包括（C）。

A 可变分区存储管理B 基本分页存储管理C 请求分段存储管理D 段页式存储管理6、虚拟存储器的最⼤容量（C）。

A 由作业的地址空间决定B 是任意的C 由计算机的地址结构决定的D 为内、外容量之和7、操作系统为（ C ）分配内存空间。

Ａ线程Ｂ⾼速缓冲存储器（Cache）C 进程 D 块表8、下⾯的页⾯置换算法中会产⽣所谓Belady异常现象的是（B）。

A 最佳页⾯置换算法（OPT）B 先进先出页⾯置换算法(FIFO)C 最近最久未使⽤页⾯置换算法(LRU)D 最少使⽤页⾯置换算法（LFU）9、采⽤（ B ）不会产⽣内部碎⽚。

A 分页式存储管理B 分段式存储管理C 固定分区式存储管理D 段页式存储管理10、最佳适应算法的空闲区是（B）。

A 按⼤⼩递减顺序连在⼀起B按⼤⼩递增顺序连在⼀起C 按地址由⼩到⼤排列D 按地址由⼤到⼩排列11、在可变式分区存储管理中的拼接技术可以（A）。

《操作系统》第三版第四章课后答案

《操作系统》第三版第四章课后答案
设备驱动程序是驱动外部设备和相应的控制器等，使其可以直接和内存进行I/O操作的子程序的集合。它是I/O进程与设备控制器之间的通信程序
２、Ｓｐｏｏｌｉｎｇ技术
也备的技术
六、简答题
１、操作系统设备管理的目标是什么？
＊提高I/O设备和CPU的利用率
＊提高I/O速度
＊为用户使用设备提供方便、统一的界面
３、引入Ｓｐｏｏｌｉｎｇ系统有哪些好处
＊提高了I/O速度，将独占设备改造成共享设备，实现了虚拟设备功能，提高了系统的并行性，减少了用户进程的等待时间，提高了进程的推进速度。
５、什么是设备独立性？引入设备独立性有哪些好处？
＊设备独立性也称设备无关性，指应用程序与实际使用的物理设备无关，亦即它独立于具体的物理设备。用户程序中使用逻辑设备，由操作系统完成逻辑设备到物理设备的映射
第四章（与磁盘相关不做）
一、填空题
1：字符、块、字符
2：设备驱动
3：缓冲
５：输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程
６：中断源
７：中断、DMA、通道
二、单项选择题
１、B
２、B C
６、C
７、Ａ
三、多项选择题
１、BC
２、AB
３、AB DE
四、判断题
１、×
２、√
３、√
４、×
五、名词解释
１、设备驱动程序
＊好处：设备分配时的灵活性、易于实现I/O重定向、方便用户编程

操作系统习题第四章

操作系统习题第四章

第四章互斥、同步与通讯一、单项选择题1.一个正在访问临界资源的进程由于申请等待I/O操作而被中断时，__________.A.可以允许其他进程进入与该进程相关的临界区B.不允许其他进程进入任何临界区C. 可以允许其他就绪进程抢占处理器，继续运行D.不允许任何进程抢占处理器2.两个并发进程之间______A 一定存在互斥关系B 一定存在同步关系C 一定彼此独立无关D 可能存在同步或互斥关系3.为了使两个进程能同步运行，最少需要_______个信号量。

A 一B 二C 三D 四4.共享变量是指__________访问的变量。

A. 只能被系统进程B. 只能被多个进程互斥C. 只能被用户进程D. 可被多个进程5.临界区是指并发进程中访问共享变量的__________.A．管理信息 B.数据 C.信息存储 D.程序段6．设有三个进程共享一个资源，如果每次只允许一个进程使用该资源，则用PV操作管理时信号量S的可能取值是___________A.1,0,-1,-2B.2,0,-1,-2C.1,0,-1D.3,2,1,07.进程的并发执行是指若干个进程__________.A. 同时执行B. 在执行的时间上是重叠的C. 在执行的时间上是不可重叠的D. 共享系统资源8.在进程通信中，__________常用信件交换信息。

A．低级通信 B.高级通信 C.消息通信 D.管道通信9.实现进程同步时，每一个消息与一个信号量对应，进程_________可把不同的消息发送出去。

A.在同一信号量上调用P操作B.在不同信号量上调用P操作C.在同一信号量上调用V操作D.在不同信号量上调用V操作10．_________是只能有P和V操作所改变的整形变量。

A.共享变量B.锁C.整型信号量D.记录型信号量11．在执行V操作时，当信号量的值_________时，应释放一个等待该信号量的进程。

A.大于0B.小于0C.大于等于0D.小于等于012．进程和程序的主要区别是__________.A.占用处理器和不占用处理器B.占用主存和不占用主存C.动态和静态D.连续执行和非连续执行13．有三个进程P1,P2,P3共享同一个程序段，而每次最多允许两个进程进入该程序段，则信号量S的初值为___________.A. 0B. 1C. 2D. 314．若P、V操作的信号量S初值为2，当前值为-1，则表示有_________等待进程。

操作系统基础(修改)及答案

操作系统基础(修改)及答案

第四章操作系统基础一、选择题1．软件通常被分成_________ 和应用软件两大类。

A.高级软件 B．系统软件 C．计算机软件 D．通用软件2．软件由程序、_________和文档三部分组成。

A. 计算机 B．工具 C．语言处理程序 D．数据3．在下列操作系统中，属于分时系统的是_________。

A．UNIX B．MS DOS C．Windows 2000/XP D．Novell NetWare4．在搜索文件或文件夹时，若用户输入“*.*”，则将搜索_________。

A. 所有含有*的文件 B．所有扩展名中含有*的文件C．所有文件 D．以上全不对5．Windows操作系统中规定文件名中不能含有的符号是_________。

A．＼／: * ? # < > $ B．＼／: ? ” < > $C．＼／： * ? ” < > | @ D．＼／： * ? ” < > |6．以下_________文件被称为文本文件或ASCII文件。

A．以EXE为扩展名的文件 B．以TXT为扩展名的文件C．以COM为扩展名的文件 D．以DOC为扩展名的文件7．关于Windows直接删除文件而不进入回收站的操作中，正确的是_________。

A．选定文件后，按Shift+Del键B．选定文件后，按Ctrl+Del键C．选定文件后，按Del键D．选定文件后，按Shift键，再按Del键．8．在Windows中，各应用程序之间的信息交换是通过_________进行的。

A.记事本 B．剪贴板 C．画图 D．写字板9．要选定多个连续文件或文件夹的操作为：先单击第一项，然后_________再单击最后一项。

A．按住Alt键 B．按住Ctrl键 C．按住Shift键 D．按住Del键10．下列有关Windows菜单命令的说法，不正确的有_________。

A. 带省略号…，执行命令后会打开一个对话框，要求用户输入信息B．前有符号√，表示该命令有效C．带符号当鼠标指向时，会弹出一个子菜单D．带省略号…，当鼠标指向时，会弹出一个子菜单11．以下有关Windows删除操作的说法，不正确的是_________。

操作系统第4章答案(上)

操作系统第4章答案(上)

赵盈盈2011210593 第四章作业上1. 解释名词：程序的顺序执行；程序的并发执行。

答：程序的顺序执行：一个具有独立功能的程序独占cpu直到得到最终结果的进程。

程序的并发执行：两个或两个以上程序在计算机系统中同时处于一开始执行且尚未结束的状态。

2. 什么是进程？进程与程序的主要区别是什么？答：进程：进程是具有独立功能的程序关于某个数据集合的一次运行活动，进程是系统进行资源分配和调度的独立单元。

进程和程序的区别：●程序是静态的，进程是动态的●进程有程序和数据两部分组成●进程具有生命周期，有诞生和消亡，是短暂的；而程序是相对长久的●进程能更真实的描述并发，而程序不行。

●一个进程可以对应多个程序。

一个程序可以对应多个进程●进程可以创建其他进程，程序不能3. 图1所示，设一誊抄程序，将f中记录序列正确誊抄到g中，这一程序由get、copy、put三个程序段组成，它们分别负责获得记录、复制记录、输出记录。

请指出这三个程序段对f中的m个记录进行处理时各种操作的先后次序，并画出誊抄此记录序列的先后次序图（假设f中有1，2，…，m个记录，s,t为设置在主存中的软件缓冲区，每次只能装一个记录）。

图1 改进后的誊抄过程答：4. 进程有哪几种基本状态？试画出进程状态变迁图，并标明发生变迁的可能原因。

答：进程基本状态：运行、就绪、等待就绪到运行：调度程序选择一个新的进程运行 运行到就绪：运行进程用完了时间片或运行进程被中断，因为一个高优先级的进程处于就绪状态运行到等待：OS 尚未完成服务或对一资源的访问尚不能进行或初始化I/O 且必须等待结果 或等待某一进程提供输入（IPC ）等待到就绪：当所有的事件发生时5. 什么是进程控制块？它有什么作用？答：PCB ：为了便于系统控制和描述进程的活动过程，在操作系统核心中为进程定义的一个专门的数据结构。

作用：系统用PCB 来控制和管理进程的调用，PCB 也是系统感知进程存在的唯一标志GCGPCP G… CP6. n 个并发进程共用一个公共变量Q ，写出用信号灯的p 、v 操作实现n 个进程互斥时的程序描述，并说明信号灯值的取值范围。

计算机操作系统(第四版)1-8章-课后答案(全)

计算机操作系统(第四版)1-8章-课后答案(全)

计算机操作系统(第四版)1-8章-课后答案(全)第四版计算机操作系统课后答案第一章1. 操作系统的定义操作系统是一种软件，它管理着计算机系统的硬件和软件资源，并为用户和应用程序提供接口，以方便他们的使用。

2. 操作系统的功能操作系统具有以下功能：- 进程管理：负责创建、执行和终止进程，并管理它们的资源分配。

- 存储管理：管理计算机系统的内存资源，包括内存分配、虚拟内存和页面置换等。

- 文件系统管理：管理计算机系统中的文件和文件夹，包括文件的存储、读写和保护等。

- 设备管理：负责管理计算机系统中的各种设备，如打印机、键盘和鼠标等。

- 用户接口：提供用户与计算机系统进行交互的接口，如命令行界面和图形用户界面。

3. 操作系统的类型操作系统可以分为以下类型：- 批处理操作系统：按照一系列预先定义的指令集来运行任务。

- 分时操作系统：多个用户可以同时使用计算机系统。

- 实时操作系统：对任务的响应时间要求非常高，用于控制系统和嵌入式系统。

- 网络操作系统：支持多台计算机之间的通信和资源共享。

- 分布式操作系统：在多台计算机上分布式地管理和调度任务。

第二章1. 进程与线程的区别进程是计算机系统中正在运行的程序实例，而线程是进程内的一个执行单元。

进程拥有独立的地址空间和资源，而线程共享进程的地址空间和资源。

多个线程可以在同一进程内并发执行，从而提高系统的效率和资源利用率。

2. 进程的状态转换进程可以处于以下状态：- 创建状态：进程正在被创建。

- 就绪状态：进程准备好执行，等待分配CPU资源。

- 运行状态：进程占用CPU资源执行。

- 阻塞状态：进程等待某种事件发生。

- 终止状态：进程完成执行或被终止。

3. 进程调度算法操作系统使用进程调度算法来决定哪个进程应该被执行。

常见的调度算法有：- 先来先服务（FCFS）调度算法：按照进程到达的顺序进行调度。

- 最短作业优先（SJF）调度算法：选择运行时间最短的进程进行调度。

计算机操作系统(习题集)第四章 答案

第四章存储器管理一、单项选择题1、存储管理的目的是（C ）。

A.方便用户B.提高内存利用率C.方便用户和提高内存利用率D.增加内存实际容量2、在（ A）中，不可能产生系统抖动的现象。

A.固定分区管理B.请求页式管理C.段式管理D.机器中不存在病毒时3、当程序经过编译或者汇编以后，形成了一种由机器指令组成的集合，被称为（B ）。

A.源程序B.目标程序C.可执行程序D.非执行程序4、可由CPU调用执行的程序所对应的地址空间为（D ）。

A.符号名空间B.虚拟地址空间C.相对地址空间D.物理地址空间5、存储分配解决多道作业[1C]划分问题。

为了实现静态和动态存储分配，需采用地址重定位，即把[2C]变成[3D]，静态重定位由[4D]实现，动态重定位由[5A]实现。

供选择的答案：[1]：A 地址空间 B 符号名空间 C 主存空间 D 虚存空间[2]、[3]： A 页面地址 B 段地址 C 逻辑地址 D 物理地址 E 外存地址 F 设备地址[4]、[5]： A 硬件地址变换机构 B 执行程序 C 汇编程序D 连接装入程序E 调试程序F 编译程序G 解释程序6、分区管理要求对每一个作业都分配（A ）的内存单元。

A.地址连续B.若干地址不连续C.若干连续的帧D.若干不连续的帧7、（C ）存储管理支持多道程序设计，算法简单，但存储碎片多。

A.段式B.页式C.固定分区D.段页式8、处理器有32位地址，则它的虚拟地址空间为（ B）字节。

A.2GBB.4GBC.100KBD.640KB9、虚拟存储技术是（ A）。

A.补充内存物理空间的技术B.补充相对地址空间的技术C.扩充外存空间的技术D.扩充输入输出缓冲区的技术10、虚拟内存的容量只受（ D）的限制。

A.物理内存的大小B.磁盘空间的大小C.数据存放的实际地址D.计算机地址字长11、虚拟存储技术与（A ）不能配合使用。

A.分区管理B.动态分页管理C.段式管理D.段页式管理12、（B ）是指将作业不需要或暂时不需要的部分移到外存，让出内存空间以调入其他所需数据。

操作系统第四章习题

一、选择1. 可变分区存储器管理系统中，若采用最佳适应分配算法，“空闲区表”中的空闲区可按（ A ）顺序排列。

A.长度递增B.长度递减C.地址递增D.地址递减2. 虚拟存储技术是—B—。

A. 扩充内存物理空间技术B. 扩充内存逻辑地址空间技术C.扩充外存空间技术D. 扩充I/O缓冲区技术3. 很好地解决了“零头”问题的存储管理方法是—A—。

A.分页存储管理方法B.分段存储管理方法C.多重分区管理D.可变式分区管理4. 系统“抖动”现象的发生是由—B—引起的。

A.交换的信息量过大B.置换算法选择不当C.内存容量不足D.请求分页管理方案5. 虚拟存储管理系统的基础是程序的—C—理论。

A. 全局性B. 虚拟性C. 局部性D. 动态性6. 分页系统中页面是为（ B ）的。

A、用户所感知B、操作系统所感知C、编译系统所感知D、连接装配程序所感知7.下列—A—存储方式不能实现虚拟存储器。

A.分区B.页式C.段式D.段页式8. 操作系统处理缺页中断时，选择一种好的调度算法对内存和外存中的信息进行高效地调度，尽可能避免—D—。

A. 碎片B.CPU空闲C. 多重中断D. 抖动9. 分页式存储管理的主要特点是—C—。

A. 要求处理缺页中断B. 要求扩充内存容量C. 不要求作业装入到内存的连续区域D. 不要求作业全部同时装入内存10. LRU页面调度算法淘汰—B—的页。

A. 最近最少使用B. 最近最久未使用C. 最先进入内存D. 将来最久使用11.虚拟存储器实际容量受—B—限制。

A.物理内存大小B.计算机的地址结构C.磁盘容量D.数据存放的绝对地址12. 分区管理要求对每一个作业都分配—A—的内存单元。

A. 地址连续B. 若干地址不连续C. 若干连续的页D. 若干不连续的帧13.页面置换算法中—A—不是基于程序执行的局部性理论。

A.先进先出调度算法B. LRUC. LFUD.最近最不常用调度算法14. 在存储管理中，采用覆盖与交换技术的目的是—A—。

操作系统-第四章

第四章一、选择题1、在请求分页系统中，主要的硬件支持有请求分页的页表机制、缺页中断机构和（ C）。

A 、时间支持B 、空间支持C 、地址变换机构D 、虚拟存储2、从下列关于虚拟存储器的论述中，选出一条正确的论述。

(B)A.要求作业运行前，必须全部装入内存，且在运行中必须常驻内存；B.要求作业运行前，不必全部装入内存，且在运行中不必常驻内存；C.要求作业运行前，不必全部装入内存，但在运行中必须常驻内存；D. 要求作业运行前，必须全部装入内存，且在运行中不必常驻内存；3、请求分页存储管理方案的主要特点是（C ）。

A.不要求将作业装入内存B.不要求使用联想存储器C.不要求将作业全部装入内存D.不要求缺页中断的处理4、在下列特性中，哪一个不是进程的特性（ C ）。

A.异步性B. 并发性C. 静态性D. 动态性5、通常，用户编写的程序中所使用的地址是( A )。

A.逻辑地址B.物理地址C.绝对地址D.内存地址二．填空题1.引入分段系统，主要是为了满足用户的一系列要求，主要包括了（便于访问）、（分段共享）、（分段保护）、（动态链接）几个方面。

2.设访问页面顺序为：1，3，2，4，1，2，驻留集大小为3，按LRU策略控制上述访问串，应发生（5）次页故障。

# 3、在段页式系统中无快表，为获得一条指令或数据，都需三次访问内存。

第一次从内存中取得（页表起始地址），第二次从内存中取得（物理块号），第三次从内存中取得（指令和数据）。

#4、虚拟存储器的基本特征是（多次性）和（对换性），因而决定了实现虚拟存储器的关键功能是（请求调页和页置换）功能。

**5．在段式存储管理中, 若逻辑地址的段内地址大于段表中该段的段长, 则发生（地址越界）中断。

6. 在存储管理中, 为进程分配内存时, 取满足申请要求且长度最大的空闲区域, 这一算法称为（最坏适应算法）7 在页式存储管理中，由（操作系统）将用户程序划分为若干相等的页.8. 在操作系统的存储管理中，由于进行动态不等长存储分配，在内存中形成一些很小的空闲区域，称之为（碎片）。

操作系统考试必备第四章习题(存储器管理)

一、单项选择题1．在存储管理方案中，可与覆盖技术配合。

A. 页式管理B．段式管理C．段页式管理D．可变分区管理2．在存储管理中，采用覆盖与交换技术的目的是。

A. 节省主存空间B．物理上扩充主存容量C. 提高CPU效率D．实现主存共享3．动态重定位技术依赖于。

A. 重定位装入程序B．重定位寄存器C. 地址机构D．目标程序4. 虚拟存储器的最大容量。

A. 为内外存容量之和B．由计算机的地址结构决定C．是任意的 D. 由作业的地址空间决定5．在虚拟存储系统中，若进程在内存中占3块(开始时为空)，采用先进先出页面淘汰算法，当执行访问页号序列为1、2、3、4、l、2、5、1、2、3、4、5、6时，将产生次缺页中断。

A．7 B．8 C．9 D．106．很好地解决了“零头”问题的存储管理方法是。

A. 页式存储管理B．段式存储管理C. 多重分区管理D．可变式分区管理7．系统“抖动”现象的发生是由引起的。

A. 置换算法选择不当B．交换的信息量过大C. 内存容量不足D. 请求页式管理方案8．分区管理中采用“最佳适应”分配算法时，宜把空闲区按次序登记在空闲区表中。

A. 长度递增B．长度递减C. 地址递增D. 地址递减9．在固定分区分配中，每个分区的大小是。

A. 相同B.随作业长度变化C. 可以不同但预先固定D．可以不同但根据作业长度固定10．实现虚拟存储器的目的是。

A. 实现存储保护D．实现程序浮动C．扩充辅存容量D．扩充主存容量11．采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是。

A．224B．216C．28D．23212．作业在执行中发生了缺页中断，经操作系统处理后，应让其执行指令。

A. 被中断的前一条B．被中断的C．被中断的后一条D．启动时的第一条13．把作业地址空间中使用的逻辑地址变成内存中物理地址的过程称为。

A. 重定位B．物理化C．逻辑化D．加载14．首次适应算法的空闲区是。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第四章 互斥、同步与通讯
并发进程(concurrent processes) 进程互斥(mutual exclusion) 进程同步(synchronization) 进程高级通讯(communication)

4.1 并发进程

4.1.1 顺序性与并发性
– 顺序性

内部顺序性：P1: a1,a2,a3;
s.queue链头PCB出等待队列，进入就绪队列（状态改为 就绪）。
规定和结论

对于信号灯变量的规定：
– 必须置一次初值，只能置一次初值，初值>=0; – 只能执行P操作和V操作，所有其它操作非法。
信号灯变量
Var S:semaphore; S.value S.queue
S.value S.queue
PCB
PCB FIFO
PCB
P操作原语
P操作原语： Procedure P(var s:semaphore) s.value:=s.value-1; If s.value<0 Then Primitive: a piece of code asleep(s.queue) un-interruptible End

“运行”或“就绪”
Busy waiting
Lamport面包店算法
算法思想：设置一个发号者，按0,1,2,…, 发号。想进入临 界区的进程抓号，抓到号之后按由小到大的次序依次进入。 Problem: 两个进程可能抓到相同的号。 Why? 为保证抓到不同的号，需要互斥机制。 Resolution: 若抓到相同的号，按进程编号依次进入。 Definition: (a,b)<(c,d) iff (a<c)or(a=c and b<d)
P1: synchronize 先 后 P2:
4.3.2 进程同步机制

定义：用于实现进程同步的工具称为同 步机制（synchronization mechanism）

同步机制要求：
– 描述能力够用; – 可实现; – 高效; – 使用方便.
典型同步机制
信号灯与PV操作(semaphore and PV operations) 管程(monitor) 会合(rendezvous) 条件临界区(conditional critical region) 路径表达式(path expression) 事件(traditional UNIX)
4.2.3 进程互斥的实现

Framework
Repeat
entry section
critical section
exit section
remainder section Until false
4.2.3 进程互斥的实现

需求:
– mutual exclusion: 一次只允许一个进程活动在关于
P2: b1,b2,b3 b1,b2,b3,a1,a2,a3
外部顺序性：a1,a2,a3,b1,b2,b3;
– 并发性

内部并发性：P2: b1,b2,b3;
P2: b1,b3,b2 b1,b2,a1,b3,a2,a3
外部并发性：a1,b1,b2,a2,a3,b3;
4.1.2 与时间有关的错误
CR
lock=0;
4.3 进程同步
4.3.1 进程同步的概念
例：司机-乘客问题 司机活动：(P1) do{ 启动车辆 正常行驶 到站停车 while(1)
乘客活动：(P2) do{ 上 车 投 币 乘 车 下 车 while(1)
4.3.1 进程同步的概念
定义：一组进程，为协调其推进速度，在某些 关键点处需要相互等待与相互唤醒，进程之间 这种相互制约的关系称为进程同步。
asleep(s.queue):
(1) 执行此操作进程的PCB入s.queue尾（状态改为等待）； (2) 转处理机调度程序。
V操作原语
V操作原语： Procedure V(var s:semaphore) s.value:=s.value+1; If s.value<=0 Then Primitive: a piece of code wakeup(s.queue) un-interruptible End wakeup(s.queue)
Lamport面包店算法
VAR choosing: Array[0,…,n-1]Of Boolean;（false) number: Array[0,…,n-1]Of integer; (0) Pi 进入： (1)P1抓到1未赋值 1. choosing[i]:=true; 2. number[i]:=max{number[0],…,number[n-1]}+1; 3. choosing[i]:=false; 4. For j:=0 To n-1 Do 5. While choosing[j] Do skip; 6. While (number[j]<>0)and 7. (number[j],j)<(number[i],i) Do skip 8. Endfor (2)P2抓到1进入临界区 (3)P3抓到2进入临界区
turn: 0..n-1; 初始任意
flag[i]=idle: 进程Pi不想进入临界区
flag[i]=want_in: 进程Pi想进入临界区 flag[i]=in_cs: 进程Pi想进入或已进入临界区 0 i turn n-1
先于i
先于i
Eisenberg/Mcguire算法
Pi进入: Repeat flag[i]:=want_in; j:=turn; While j<>i do If flag[j]<>idle Then j:=turn Else j:=(j+1)mod n; flag[i]:=in_cs; j:=0; While (j<n)and(j=i or flag[j]<>in_cs) do j:=j+1; Until (j=n)and(turn=i or flag[turn]=idle); turn:=i;

4.2.1 共享变量与临界区域


共享变量（shared variable）
– 多个进程都需要访问的变量。
临界区域（critical region）
– 访问共享变量的程序段。
一组公共变量
…….
CR1
CR2
CRn
表示
共享变量: shared <一组变量>
临界区域: region <一组变量> do <语句＞ 例子：shared B:array[0,..,n-1]of integer; region B do region B do
4.2.3.2 进程互斥的硬件实现
2. 硬件提供“交换”指令 Procedure swap(var a,b:boolean) var temp: boolean; Begin temp:=a; a:=b; b:=temp End; 对一组公共变量：var lock: boolean(初始=false); 对一个进程空间：var key: boolean; Pi进入：key:=true; Repeat swap(lock,key) Until key=false; Pi离开：lock:=false;
例：图书借阅系统 终端1： CYCLE 等待借书者； IF x>=1 Then Begin x:=x-1; 借书 End Else 无书 End （x:某种书册数，设当前x=1.） 终端2： CYCLE 等待借书者； IF x>=1 Then Begin 1 x:=x-1; 借书 3 End Else 无书 End
关中断
{ Critical Region}
开中断 Remarks: (1) 开关中断只在单CPU系统中有效;(why?)
(2) 影响发性。
4.2.4 多处理机环境下互斥
CPU1 内存
Word 1000 initial: 0
CPU2
1. Read 0
2. Read 0
Bus
3. Write 1
4. Write 1
4.2.3.2进程互斥的硬件实现
Remarks：
(1) test_and_set指令和swap指令是原子的， 不可中断的。 (2) test_and_set实际上是：将内存中一个单 元的内容取出，再送一个新值。 (3) swap实际上是：交换内存两个单元的内容。
4.2.3.2进程互斥的硬件实现
3. 硬件提供“关中断”和“开中断”指 令
begin
…… (访问B） end;
begin
…..（访问B）. end;
4.2.2 临界区域与进程互斥
定义：多个进程不能同时进入关于同一组共享变量的临 界区域，否则可能发生与时间有关的错误，这种现象称 为进程互斥。
二层涵义：
（1）任何时刻最多只能有一个进程处于同一组共 享变量的相同的临界区域；
（2）任何时刻最多只能有一个进程处于同一组共 享变量的不同的临界区域。

4.3.3 信号灯与PV操作
4.3.3.1 信号灯与PV操作的定义
TYPE semaphore=RECORD value: integer; queue: PCB pointer; END; VAR s: semaphore; 备注: (1) semaphore 是一个提前定义好的数据类型. (2) s 是一个信号灯变量,使用前必须先声明. 例如: var s1,s2:semaphore;
Lamport面包店算法(Cont.)
Pi离开： number[i]:=0： 可能按P2,P3,P1次序进入！ 变量choosing的作用： P1：抓到1;