银行计算机考试资料 操作系统

2009硕士研究生入学考试辅导

操作系统原理

北京大学计算机科学技术系

PekingUniversity

内容提纲

■推荐参考书列表

■考试大纲概况

■考查内容及要求

■知识点及复习要点

■样题练习与讲解

参考书（1/2）

■陈向群、杨芙清编著，操作系统教程

（第2版），北京大学出版社，2006

■汤子瀛等编著，计算机操作系统（第3,

版），西安电子科技大学出版社，2007

参考书（2/2）

AndrewS・Tanenbaum著，陈向群，马洪兵

等译，现代操作系统（第2版），机械工业出

版社，2005

］本课程考试大纲概况

■考查目标

■了解操作系统在计算机系统中的作用、地位、

发展和特点。

■理解操作系统的基本概念、原理，掌握操作

系统设计方法与实现技术。

■能够运用所学的操作系统原理、方法与技术

分析问题和解决问题。

■操作系统34分

■单项选择题18分（9小题，每小题2分）

■综合应用题16分（2小题，每小题8分）

复习方法建议

■围绕大纲，系统地复习。既要建立系统的

概念原理体系，也要善于抓重点，把重点

学懂学透。

■抓住知识点，掌握正确的概念。

■适当做题，但不要被大量的样题扰乱

内容提纲

・推荐参考书列表

■考试大纲概况

■考查内容及要求

■知识点及复习要点

■样题练习与讲解

考查内容及要求

・1概述-4文件管理

■1.1操作系统基本概念■4.1文件管理概述

■L2操作系统的分类■4.2文件系统的实现

■1.3操作系统的运行环境-4.3磁盘组织与管理

-2进程管理■5输入输出（I/O）概述

■2.1进程与线程.5.1I/O管理概述

■2.2处理机调度■5.2I/O内核子系统

■2.3进程同步

■2.4死锁

■3存储管理

■3.1存储管理基础

■3.2虚拟页式存储管理方案

概述

操作系统的概念、特征、功能和提供的

服务

■掌握操作系统的定义，每个特征的含义，

操作系统功能和服务的主要内容

■例如操作系统管理哪些资源，如何管理；

提供接口有什么，如何提供

■要求对操作系统的基本概念有清晰的理解,

能够判断给出的说法的正误

概述

操作系统的发展与分类

■要求掌握操作系统的主要类型和发展历史,

特别是批处理、分时、分布式、嵌入式等

有代表性的操作系统的特点

■能够分辨说法的正误

■能够辨别任意两种操作系统的区别与优缺

占

八、、

概述

■操作系统的运行环境

■掌握计算机系统中关键的硬件特征及其与操作

系统的关系

■特别是处理器的特权级和特权指令、主要状态

寄存器的含义和功能，中断机制

■能够判断说法的正误

考查内容

-1概述-4文件管理

■1.1操作系统基本概-4.1文件管理概述

念■4.2文件系统的实现

■；2操作系统的分类

-4.3磁盘组织与管理

-1.3操作系统的运行■5输入输出(I/O)概述

环境■5.1I/O管理概述

■2进程管理-5.2I/O内核子系统

-2.1进程与线程

-2.2处理机调度

.2.3进程同步

■2.4死锁

■3存储管理

-3.1存储管理基础

-3.2虚拟页式存储管

例方窣

进程管理

进程与线程

■掌握进程概念，进程的状态与转换，进程控制,

进程组织，进程通信（共享内存，消息传递，

管道），线程概念与多线程模型

■特别是

■并发环境下的特点，引入进程的意义

■与进程状态相关的原理，如转换条件，等待与就绪

队列，控制原语的功能

■三种进程通信方法的特点，对比

■引入多线程的意义，进程和其中多线程之间的关系

■能够判断说法的正误

进程管理

■处理机调度

■掌握调度概念，调度时机、切换与过程，基本准则，

调度方式，典型调度算法

■先来先服务，短作业（短任务、短进程、短线程）优先，时

间片轮转，优先级，高响应比优先，多级反馈队列

■特别是

■调度方式：抢占■非抢占（剥夺■非剥夺）

.各种调度算法：调度的执行序列，算法的优缺点

■能够识别说法的正误

■能够按照要求的调度算法给出调度结果，计算调度算

法的平均响应时间等参数

■这部分内容的出题率近100%,重中之重

进程管理

■F程同步

-掌握进程同步的基本概念，实现临界区互斥的基本方

法（软件和硬件实现方法），信号量，管程，经典同

步问题（生产者■消费者问题，读者■写者问题，哲学家

进餐问题）

-特别是

■深刻理解同步互斥的含义

■准确理解信号量、PV原语的含义、功能

■解决同步互斥问题的基本思路和方法

-能够对一个问题进行判断属于哪类问题（同步互斥）

-能够用PV原语解决问题，要求清晰地定义信号量、其

含义，并给出初值；编写程序逻辑正确，不死锁

■这部分内容的出题率近100%,重中之重

进程管理

死锁

■掌握死锁的概念，处理策略，预防，避免，用银行家

算法判别系统安全状态，死锁检测和解除

■特别是

■死锁基本概念中涉及到的概念，如资源分类等

■用银行家算法判别系统安全状态

■四种处理策略的概念和相关的方法

■能够识别说法的正误

■能够用银行家算法解决判别系统安全状态的问题

考查内容

-1概述-4文件管理

■1.1操作系统基本概-4.1文件管理概述

念■4.2文件系统的实现

■；2操作系统的分类

-4.3磁盘组织与管理

-1.3操作系统的运行■5输入输出(I/O)概述

环境■5.1I/O管理概述

-2进程管理-5.2I/O内核子系统

-2.1进程与线程

-2.2处理机调度

■2.3进程同步

■2.4死锁

-3存储管理

-3.1存储管理基础

-3.2虚拟页式存储管

锂方窣

存储管理

■存储管理基础

■掌握内存管理概念，程序装入与链接，逻辑地址与物

理地址空间，内存保护，交换与覆盖，连续分配管理

方式，单一连续分配，分区分配，非连续分配管理方

式，分页管理方式，分段管理方式，段页式管理方式

■特别是

■地址空间及地址转换的概念和过程

■各种内存管理的特点和基本思想，实现过程，利用的硬件

分区管理，分页管理

■交换与覆盖，保护，链接

■能够判别说法的正误

■能够按照某种管理方法来解决回收、分配中的问题

-能够按照内存管理方式分析地址变换过程如

存储管理

虚拟页式存储管理方案

-掌握虚拟内存基本概念，请求分页管理，页面置

换算法（OPT,FIFO,LRU,时钟置换算法），

页面分配策略，抖动，工作集，请求分段管理方

式，请求段页式管理方式

-特别是

-虚拟内存概念及其相关概念，如局部性原理，工作集等

■页面置换算法，请求分页管理

-能够识别说法的正误

-能够根据要求分析给定页面访问序列下的缺页次

数、嵌页率，料药问题

-这部分内容的出题率很高

考查内容

-1概述-4文件管理

■1.1操作系统基本概■4.1文件管理概述

念■4.2文件系统的实现

■；2操作系统的分类

-4.3磁盘组织与管理

-1.3操作系统的运行■5输入输出(I/O)概述

环境■5.1I/O管理概述

-2进程管理-5.2I/O内核子系统

-2.1进程与线程

-2.2处理机调度

■2.3进程同步

■2.4死锁

■3存储管理

-3.1存储管理基础

-3.2虚拟页式存储管

例方窣

文件管理

■文件管理概述

-掌握文件概念，文件结构（顺序文件，索引文件,

索引顺序文件），目录结构（文件控制块和索引

节点，单级目录结构和两级目录结构，树形目录

结构，图形目录结构），文件共享（共享动机，

共享方式，共享语义），文件保护（访问类型，

访问控制）

-特别是

■不同文件结构的特点，不同目录结构的特点

-文件共享和保护的概念

-能够识别说法的正误，对基本概念进行辨识和定

义

文件管理

■文件系统的实现

■掌握文件系统层次结构，目录实现，文件实

现

■特别是

■目录实现的过程和特点，如按名存取，目录项分解,

相对路径，绝对路径

■文件操作的概念和实现过程

■能够对目录实现和文件实现中某个操作的功

能、结果、实现方法进行选择和辨识

文件管理

磁盘组织与管理

■掌握磁盘的结构，磁盘调度算法，磁盘的管理

■特别是

■几种磁盘调度算法（综合磁臂，磁头，扇区三个因素）

■磁盘的组织结构，优化方法

■能够根据要求计算给定磁盘访问序列的调度结果，分

析磁盘存取时间

-能够结合文件结构和目录结构分析磁盘访问次数

■能够根据给定参数分析磁盘空间利用率、磁盘块访问

时间，给出优化方案和结果

考查内容

-1概述-4文件管理

■1.1操作系统基本概-4.1文件管理概述

念■4.2文件系统的实现

■；2操作系统的分类

-4.3磁盘组织与管理

-1.3操作系统的运行■5输入输出(I/O)概述

环境■5.1I/O管理概述

-2进程管理-5.2I/O内核子系统

-2.1进程与线程

-2.2处理机调度

■2.3进程同步

■2.4死锁

■3存储管理

-3.1存储管理基础

-3.2虚拟页式存储管

例方窣

输入输出(I/O)概述

■I/O管理概述

■掌握I/O设备概念，I/O管理目标，I/O管理功

能，I/O应用接口，I/O控制方式

■特别是

■设备分类

■不同I/O控制方式的特点，如中断，DMA,通道

■能够辨识说法的正误

■能够选择或判断I/O处理过程和操作

输入输出(I/O)概述

■I/O内核子系统

■掌握I/O调度概念，高速缓存与缓冲区，设

备分配与回收，假脱机技术(SPOOLing),出

错处理

■特别是

■假脱机技术的概念和原理

-缓冲区概念和管理操作

■能够辨识说法的正误

■能够选择或判断某个过程或操作

内容提纲

I

■推荐参考书列表

■考试大纲概况

■考查内容及要求

■知识点及复习要点

■样题练习与讲解

知识点及复习要点

■概述♦

■进程线程

■内存管理

■文件管理

■设备管理

操作系统的定义

操作系统是计算机系统中的一个系统软件，是一些程序模

块的集合——

■它们能以尽量有效、合理的方式组织和管理计算机的软

硬件资源

■合理的组织计算机的工作流程，控制程序的执行并向用

户提供各种服务功能

■使得用户能够灵活、方便、有效的使用计算机，使整个

计算机系统能高效地运行

操作系统的特征

并发（concurrency）：处理多个同时性活动的能力

共享（sharing）：操作系统与多个用户的程序共同使

用计算机系统中的资源（共享有限的系统资源）

虚拟（Virtual）：一个物理实体映射为若干个对应的

逻辑实体一一分时或分空间。虚拟是操作系统管理系

统资源的重要手段，可提高资源利用率

随机性：操作系统必须随时对以不可预测次序发生的

事件进行响应

不确定性：由共享和并发引起

操作系统的功能和提供的服务

■进程（线程）管理

■协调多道程序，处理机分配调度策略、分配实施和回收

■存储管理

■分配回收，扩充，共享，保护

■文件管理

■文件的存储、检索，修改，共享、保密和保护

■设备管理

■I/O操作，外部设备的分配、启动和故障处理，提供一个

良好的界面

■用户接口

■向用户提供使用手段，系统调用，命令方式

4操作系统的分类

■批处理操作系统（多道批处理）

■分时系统

■实时操作系统■

■个人计算机操作系统

■网络操作系统

■分布式操作系统J

■嵌入式操作系统

批处理操作系统特点

■多道

内存中同时存放几个作业

某个作业占用CPU,若由于某种原因暂时

不用CPU,则系统让第二个作业占用CPU

.成批处理

用户自己不能干预自己作业的运行，一旦发现

作业错误不能及时改正，并延长开发软件时间，

所以适用于成熟的程序

批处理操作系统优缺点

优点：作业流程自动化-资源利用率高

吞吐量大---

单位时间内完成的工作总量大

缺点：用户交互性差，调试程序困难

（无交互手段：整个作业完成后或中间出错

时，才与用户交互，不利于调试和修改）

作业平均周转时间长

短作业的周转时间显著增长

分时操作系统特点

■多路性

-同时有多个用户使用一台计算机

■宏观上：是多个人同时使用一个CPU

■微观上：多个人在不同时刻轮流使用CPU

■交互性

-用户根据系统响应结果进一步

-提出新请求（用户直接干预每一步）

■“独占”性

-用户感觉不到计算机为其他人服务

■OS提供虚机器，各个用户的虚机器互不干扰

■及时性

-系统对用户提出的请求及时响应

I实时操作系统

■指使计算机能及时响应外部事件的请求，

在规定的严格时间内完成对该事件的处理,

并控制所有实时设备和实时任务协调一致

地工作的操作系统

■硬实时系统

■,某个动作绝对必须在规定的时刻或时间范围

完成

■软实时系统

■接受偶尔违反最终时限

实时操作系统

q时系统与批处理系统和分时系统的区别

■专用系统：许多实时系统是专用系统，而批处

理与分时系统通常是通用系统

■实时控制：实时系统用于控制实时过程，要求

对外部事件的迅速响应，具有较强的中断处理

机构

■高可靠性：实时系统用于控制重要过程，要求

高度可靠，具有较高冗余（如双机系统）

■事件驱动和队列驱动：实时系统的工作方式：

接受外部消息，分析消息，调用相应处理程序

进行处理。

分布式操作系统

分布式系统:处理和控制的分散（相对于集中

式系统）

分布式系统是以计算机网络为基础的9它的基

本特征是处理上的分布，即功能和任务的分布

分布式操作系统的所有系统任务可在系统中任

何处理机上运行，自动实现全系统范围内的任

务分配并自动调度各处理机的工作负载

r.分布式操作系统

W--------------------------------------------

特征：

1.是一个统一的操作系统

若干个计算机可相互协作共同完成一项任务

2.资源进一步共享

3.透明性：

资源共享，分布对用户来讲是不知道的

4.自治性：

处于分布式系统的多个主机处于平等地位，无主

从关系

5.处理能力增强、速度更快、可靠性增强

网络和分布式的比较

耦合程度

分布式系统是紧密耦合系统，分布式OS是在各机上

统一建立的，直接管理CPU、存储器和外设；统一进行

全系统的管理；网络通常容许异种OS互连，各机上各

种服务程序需按不同网络协议互操作

并行性

分布式OS可以将一个进程分散在各机上并行执行”

进程迁移“；网络则各机上的进程独立

透明性

用户是否知道或指定资源在哪个机器上

分布式系统的网络资源调度对用户透明，用户不了

解所占有资源的位置；网络操作系统中对网络资源的使

用要由用户明确指定

健壮性

分布式系统要求更强的容错能力（工作时系统重构）

嵌入式操作系统

■耿入式系统

■以应用为中心、以计算机技术为基础、软件硬件

可裁剪、适用于应用系统对功能、可靠性、成本、

体积、功耗严格要求的专用计算机系统

■限制条件：大小、内存、能源1

■嵌入式操作系统r

■安装在有限的内存里（ROM）

■运行在嵌入式系统环境中，对整个嵌入式系统以

及它所操作、控制的各种部件装置等等资源进行

统一协调、调度、指挥和控制的系统软件

处理器的特权指令和非特权指令

特权指令：只能由操作系统使用的指令

■使用多道程序设计技术的计算机指令系统必须要区

分为特权指令和非特权指令

■特权指令一般引起处理器状态的切换

-处理器通过特殊的机制将处理器状态切换到操作系统运行

的特权状态（管态）

■然后将处理权移交给操作系统中的一段特殊代码，这一个

过程称为陷入

］处理器的状态

根据运行程序对资源和机器指令的使用权限

将处理器设置为不同状态一一程序状态字PSW

多数系统将处理器工作状态划分为管态和目态

管态：操作系统管理程序运行的状态，较高的特权

级别，又称为特权态（特态）、核心态、系统态

目态：用户程序运行时的状态，较低的特权级别，

又称为普通态（普态）、用户态

具体处理器将CPU状态划分为两种、三种或四种

存储访问局部性原理

提高存储系统性能的关键：程序存储访问局部性原理

■程序执行时，有很多的循环和子程序调用，一旦进入

这样的程序段，就会重复存取相同的指令集合

■对数据存取也有局部性，在较短的时间内，稳定地保

持在一个存储器的局部区域

处理器主要和存储器的局部打交道

在经过一段时间以后，使用的代码和数据集合会改变

磁盘

控制器

总线

物理地址

MMU：内存管理单元

中断的概念

■CPU对系统发生的某个事件作出的一种反应

■CPU暂停正在执行的程序，保留现场后自动转去执

行相应事件的处理程序，处理完成后返回断点，继

续执行被打断的程序

特点：

引入中断的目的

■解决主机与外设的并行1）中断是随机的

工作问题2）中断是可恢复的

■实现实时控制3）中断是自动处理的

中断的概念

「I/O中断

「中断（外中断）

Y时钟中断

I硬件故障

广义中断V"系统调用

缺页异常

异常（内中断）断点指令

例外其他程序性异常

I（如算术溢出等）

中断（狭义）与异常的区别：

中断：与正执行指令无关，可以屏蔽

异常：与正执行指令有关，不可屏蔽

.中断类型

■强迫性中断

■正在运行的程序所不期望的，由于某种硬件故障或外部请

求引起的

・输入/输出（I/O）中断：主要来自外部设备通道

・程序性中断：运行程序中本身的中断，如溢出，缺页中断地址越界）

■时钟中断

■控制台中断

■自愿性中断

■用户在程序中有意识安排的中断，用户在编制程序时因为

要求操作系统提供服务，有意使用“访管”指令或系统调

用，使中断发生

■系统调用

■断点调试

知识点及复习要点

■概述1

■进程线程管理

■内存管理

■文件管理

■设备管理

发程序

并发环境:

一定时间内，物理机器上有两个或两个以

上的程序同时处于开始运行但尚未结束的

状态，并且次序不是事先确定的

ABAB

BA

BA

并发程序

CPUIDEVIICP【J,DEV2।CPU

A1O152O

—3040t(s)

-DEV1

B1----------H_CEU---------JEV2|CPUIDEV2।

1020253040

在顺序环境下，A先执行，B再执行

CPU利用率=40/80=50%

DEVI利用率=15/80=18.75%

DEV2禾用率=25/80=31.25%

并发程序

ACPUDEVIICPUDEV2CPU

1_11一十

1111111L

1)15253()：!54045

BDEVICPUDEV2CPUDEV2

在并发环境下CPU利用=40/45=89%

DEV1并发环境下利用==15/45=33%

DEV2并发环境下利用=25/45=56%

进程的概念

■定义

进程是具有独立功能的程序关于某个数据集合

上的一次运行活动，是系统进行资源分配和调

度的独立单位，又称任务(Task)

进程状态转换

状态转换：

在进程运行过程中，由于进程自身进展情况及

外界环境的变化，这三种基本状态可以依据一

定的条件相互转换

①就绪—运行

②运行—就绪

③运行一等待

④等待一就绪

、■进程转换原因

二

■就绪-->运行

-调度程序选择一个新的进程运行

■运行-->就绪

■运行进程用完了时间片

・一个高优先级进程处于就绪状态，中断正在运行的进程

■运行-->等待

■当一个进程必须等待时

・os尚未完成服务（系统调用）

■对一资源的访问尚不能进行（同步互斥）

・初始化I/O且必须等待结果（I/O）

■等待某一进程提供输入（IPC）

■等待一〉就绪

.当所等待的事件发生时

进程的其他状态

■创建状态

-OS已完成为创建一进程所必要的工作

■已构造了进程标识符

■已创建了管理进程所需的表格

■但还没有允许执行该进程（尚未同意）

-因为资源有限

■终止状态

■不再有执行资格，占有的资源将要被释放

■挂起（suspend）状态

■进程没有占用内存空间，处在挂起状态的进程映像在

磁盘上调节负载，对换）

调度的基本准则

■一般原则：

■公平：保证每个进程得到合理的CPU时间

■高效：CPU保持忙碌状态，CPU利用率高

■针对某类操作系统确定原则：

■响应时间：交互式系统，越短越好

■周转时间：使批处理用户等待时间尽可能短

■吞吐量：批处理系统情况下，单位时间内处

理的进程个数尽可能多

进程调度方式

两种占用CPU的方式：

可剥夺式（可抢占式Preemptive）：

当有比正在运行的进程优先级更高的进程就

绪时，系统可强行剥夺正在运行进程的CPU,提

供给具有更高优先级的进程使用

不可剥夺式（不可抢占式Non-preemptive）：

某一进程被调度运行后，除非由于它自身的

原因不能运行，否则一直运行下去

进程调度的时机

当一个进程运行完毕，或由于某种错误而终止运行

当一个进程在运行中处于等待状态（等待I/O）

时间片用完

当有一个优先级更高的进程就绪（可抢占式）

如：新创建一个进程；一个等待进程变成就绪

在进程通信中，执行中的进程执行了某种原语操作

（P操作，阻塞原语，唤醒原语）

进程中断/异常/系统调用返回到用户态时

进程切换

■『个进程让出处理器，由另一个进程占用处理器的过程

-进程的切换使系统中的各进程均有机会占用CPU

■进程的切换是由进程状态的变化引起的，而进程状态的变化又

与出现中断事件有关

■当有中断事件发生时，当前运行的进程被中断，中断响应后由

操作系统处理出现的中断事件。中断处理后，某些进程的状态

会发生变化，也可能又创建了一些新的进程。因此，要进行队

列的调整。然后，进程调度根据预定的调度算法从就绪队列选

一个进程占用CPU。这个占用CPU运行的进程可能仍是被中断的

进程，也可能是另一个进程

,何时切换进程?

■只要OS取得对CPU的控制，进程切换就可

能发生，如：

■系统调用

■来自程序的显式请求（如：打开文件），该进程通

常会被阻塞

■异常

■最末一条指令导致出错，会引起进程变为退出状态

■中断

■外部因素影响当前指令的执行，控制被转移至中断

处理程序

进程切换的过程

■保存处理器的上下文，包括程序计数器和其它寄存器

■用新状态和其它相关信息更新正在运行进程的PCB

-把原来的进程移至合适的队列—就绪、阻塞‘

■选择另一个要执行的进程.

■更新被选中进程的PCB”

■从被选中进程中重装入CPU上下文

线程的引入

■进程的缺点

■时间、空间开销大，限制了并发度的提高

■线程•

■也称轻量级进程

■进程中的一个运行实体，是一个CPU调度单位

■一个进程中的线程共享进程的资源（内存、文件等）

进程与线程

■引入线程的好处

■创建和终止一个线程花费时间少

■两个线程的切换花费时间少

■如果机器设有“存储I,恢复］所有寄存器”指令，则

整个切换过程用几条指令即可完成）

■线程之间相互通信无须调用内核

■同一进程内的线程共享内存和文件

■适合多处理机系统

4线程模型

二线程和进程的关系

■单线程进程

■多线程进程

多线程进程模型

单线程进程模型

用

线程

户控制块

栈PCB

核

用

户

心

栈

栈

用户地址空间用户

地址

空间

核

心

线程控制块栈

包含了寄存器映像，线程优先数和线程状态信息

线程模型（2/3）

单线程进程模型

PCB

用户地址空间

线程控制块

包含了寄存器映像，线程优先数和线程

状态信息

线程模型（3/3）

多线程进程模型

线程

控制块

PCB

用

户

用户栈

地址

空间核

心

栈

、■进程的同步与互斥

■进程的同步

■指系统中多个进程中发生的事件存在某种时序关系，

需要相互合作，共同完成一项任务。

■进程的同步

■由于各进程要求共享资源，而有些资源需要互斥使用,

因此各进程间竞争使用这些资源，进程的这种关系为

进程的互斥

■临界资源

■系统中某些资源一次只允许一个进程使用，称这样的

资源为临界资源或互斥资源

■临界区

■在进程中涉及到临界资源的程序段

.实现临界区互斥的方法

■软件解法

■定义变量，进入临界区前和退出后执行相应函数Paterson算法

■需要忙等待(busywaiting)

■实现过于复杂，需要高的编程技巧

■硬件解法：

■提供专门的硬件指令，允许对一个字的内容进行检测和修正，或交

换两个字的内容

■“测试并设置”(TS)指令，“交换”指令，“开关中断”指令

■目的：解决共享变量的完整性和正确性

■简单、有效，特别适用于多处理机

■缺点：(1)忙等待；(2)“饥饿”现象

信号量：seaphore

■是一个数据结构】)信号量的物理含义：

■定义如下：S>0表示有s个资源可用

strucsemaphores=o表示无资源可用

SVO则IS|表示S等待队列中的进程

(个数

intvalue;

pointer_PCBqueue;P(S)：表示申请一个资源

)"V(S)：表示释放一个资源

信号量的初值应该大于等于0

■信号量说明：

semaphores;

P操作和V操作

I)V(s)

(

s.value=s.value-1;s.value=s.value+1;

if(s.value<0)if(s.value<=0)

((,

该进程状态置为等待状态

将该进程插入等待队列末尾唤醒等待队列中等待的进程

重新调度改变为就绪态，并将其插入就绪队列

■P.V操作必须成对出现，有一个P操作就一定有一个V操作

■当为互斥操作时，它们同处于同一进程

■当为同步操作时，则不在同一进程中出现

■如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要，一个同

步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前

■而两个V操作的顺序无关紧要

空典的生产者一消费者问题(同步为主)

■P进程不能往“满”的缓冲区中放产品，

设置信号量为S1

■Q进程不能从“空”的缓冲区中取产品,

设置信号量S2

■S1初值为1,S2初值为0

注意：

while(true){while(true){

■私有信号量用于控制生产一个产品；P(s2);

进程执行顺序

P(s1);从缓冲区取产品;

■可以扩展理解为：

送产品到缓冲区;V(s1);

控制进程执行的次数

V(s2);消费产品；

■生产者比消费者多1

次，消费者比生产者)；

多。次

多个缓冲区的生产者和消费者（带互斥的同步）

■S1初值为工，S2初值为0

-mutextl用于生产者互斥写缓冲区，

初值为工

■mutext2用于消费者互斥读缓冲区，初

值为工

10,

i=0;j=o；

while(true){while(true){

注意：生产产品；P(S2);

■生产者消费者问题可P(S。；P(mutex2);

以扩展为仓库问题，P(mutex1);从Buffer。］取产品;

往Buffer［i］放产品;

商店卖货问题，零件j=(j+1)%n;

装配问题。i=(i+1)%n;V(mutex2);

V(mutex1);V(Si);

■数量限制引申为进程V(S2);消费产品；

的执行次数限制，当}；

作私有信号量的初值

商店卖食品问题

某商店有两种食品A和B,最大数量各为m个。该商店

将A、B两种食品搭配出售，每次各取一个。为避免食

品变质，遵循先到食品先出售的原则，有两个食品公司

分别不断地供应A、B两种食品(每次一个)。为保证正常

销售，当某种食品的数量比另一种的数量超过k(kvm)

个时，暂停对数量大的食品进货，补充数量少的食品。

-(1)问共需设置几个进程？

■(2)试用P、V操作解决上述问题中的同步和互斥关系。

商店卖食品问题

■这是一个三进程同步互斥问题，互相之间的制约可以看成是执行

次数的约束

■食品A和商店c之间同步，Sac=m,sca=O;

■食品B和商店c之间同步，Sbc=m,scb=O;

■食品A和食品B直接同步，Sab=k,sba=k;

■三者之间的对货架操作互斥，定义mutex=1；

B：

(

P(sac);P(sbc);P(sca);

P(sab);P(sba);P(scb);

p(mutex)；p(mutex)；p(mutex)；

store(A);store(B);take_A&B;

v(sca);v(scb);v(sac);

v(sba);v(sab);v(sbc);

v(mutext);v(mutext);v(mutext);

1；_____1；_____1；______

读者写者问题（互斥为主）

问题描述：

有两组并发进程：读者和写者，共享一组数据区

要求：

允许多个读者同时执行读操作

不允许读者、写者同时操作

不允许多个写者同时操作

第一类读写者问题：读者优先

■如果读者到：

-1）无读者、写者，新读者可以读

-2）有写者等，但有其它读者正在读，则新读者也可以读

・3）有写者写，新读者等

■如果写者到：

-1）无读者，新写者可以写

-2）有读者，新写者等待

-3）有其它写者，新写者等待

第一类读者写者问题的解法

读者：写者:

(

P(mutex);

readcount++;

if(readcount==1)P(w);

P(w);写

V(mutex);

读V(w);

P(mutex);

readcount｝；

if(readcount==0)

V(w);

V(mutex);

)；

第二类读者写者问题一写者优先

Integerrcount=0zwcount=0;

1）多个读者可以同Semaphoremutexl=mutex2=w=r=l;

时进行读

读者：

2）写者必须互斥写者：

(

（只允许一个写(

P(r)；P(w);

P(mutex1);

者写，也不能读P(mutex2)

者写者同时进行）rcount++;

if(rcount==1)P(w);wcount++;

3）写者优先于读者V(mutex1);If(wcount==1)P(r);

（一旦有写者，V(r);V(mutex2);

则后续读者必须读写

等待，唤醒时优P(mutex1);P(mutex2);

rcountwcount

先考虑写者）

if(rcount==0)V(w);If(wcount==0)V(r);

注意：V(mutex1);V(mutex2);

｝；

■读写者问题可以改为为V(w);

过桥问题，巴拿马运河｝；

问题等

■单向互斥或双向互斥

巴拿马运河问题

巴拿马运河建在太平洋和大西洋之间。由于太平洋和大

西洋水面高度不同，有巨大落差，所以运河中修建有T

(T>=2)级船闸，并且只能允许单向通行。船闸依次

编号为1,2,……，To由大西洋来的船需经由船闸T,

T-1,……，2,1通过运河到太平洋；由太平洋来的船

需经由船闸1,2,……，T-1,T通过运河到大西洋。

试用P,V操作正确解决大西洋和太平洋的船只通航问

题。

巴拿马运河问题

记录由太平洋往大西洋航行的船只，PtoAcnt=0

记录此船闸正由大西洋往太平洋航行的船只AtoPcnt=0

对PtoAcount互斥，Mutex1=1

对AtoPcount互斥，Mutex2=1

太平洋往大西洋方向的信号量

大西洋往太平洋方向的信号量E=1

PtoA：AtoP：

(｛

P(W);P(E)；

P(mutex1);P(mutex2);

PtoAcount++;AtoPcount++;

if(PtoAcount==1)P(E);if(AtoPcount==1)P(W);

V(mutex1);V(mutex2);

过闸过闸

P(mutex1);P(mutex2);

PtoAcountAtoPcount

if(PtoAcount==0)V(E);if(AtoPcount==0)V(W);

V(mutex1);V(mutex2);

｝；｝；

哲学家就餐问题（互斥为主）

问题描述:

■有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前

有一只空盘子，每两人之间放一只筷子

■每个哲学家的行为是思考，感到饥饿，然后吃通心粉

■为了吃通心粉，每个哲学家必须拿到两只筷子,并且每个人只能

直接从自己的左边或右边去取筷子

解法1:

为防止死锁发生可采取的措施：

#defineN5

-最多允许4个哲学家同时坐在桌子周围

voidphilosopher(inti){

-仅当一个哲学家左右两边的筷子都可用时，

while(true){才允许他拿筷子（4）

思考；-给所有哲学家编号，奇数号的哲学家必须首

取fork。］;Work［(i+1)%5］；先拿左边的筷子，偶数号的哲学家则反之

进食；为了避免死锁，把哲学家分为三种状态，思

放fork。］;放fork［(i+1)%5］；考，饥饿，进食，并且一次拿到两只筷子，

否则不拿

)

)

voidphilosopher(inti)

{while(true)

哲学家就餐问题解法（2）(

思考；

■#defineN5P(&mutex);

>#defineTHINKING0state[i]=HUNGRY;

・#defineHUNGRY1test(i);

>#defineEATING2V(&mutex);

■#typedefintsemaphore;P(&s[i])；

拿左筷子；拿右筷子；

■intstate[N];

进食；

■semaphoremutex=1;放左筷子；放右筷子;

■semaphores[N];叫&mutex)

voidtest(inti)state[i]=THINKING；

{test([i-1]%5);

if(state[i]==HUNGRY)test([i+1]%5);

&&(state[(i-1)%5]!=EATING)V(&mutex);

&&(state[(i+1)%5]!=EATING))

()

state[i]=EATING;state[i]=THINKING

V(&s[i]);

s[i]=0

}

}

理发师问题（多进程同步）

■题目：

■理发店里有一位理发师，一把理发椅和N把供等候理

发的顾客坐的椅子

■如果没有顾客，则理发师便在理发椅上睡觉。当一个

顾客到来时，他必须先唤醒理发师

■如果顾客到来时理发师正在理发，则如果有空椅子,

可坐下来等；否则离开

理发师问题

■定义

■理发师的私有信号量：等待理发的顾客c=0；

■顾客的私有信号量：等待顾客的理发师b=0;

■等待椅子的顾客数waiting=O；互斥访问waiting变

量的mutex=1；

Customer：Barber：注意：

(

P(mutex);P(c)；■理发师问题可以改为

if(waiting<N){P(mutex);牙医问题，网球场问

waiting++;waiting-题，学生上机问题，

V(c);v(b);银行柜员

V(mutex1);V(mutex);

P(b)；理发■可以采用计数器加互

理发；｝；斥信号量方法实现

}

else■也可以用私有信号量

V(mutex1);控制执行顺序

}；

阅览室问题

假定一个阅览室最多可容纳100人,读者进入

和离开阅览室时都必须在阅览室门口的一个登

记表上进行登记(进入时登记，离开时去掉登

记项)，而且每次只允许一人登记或去掉登记,

问：

(1)应编写几个程序完成此项工作，程序的

主要动作是些什么？应设置几个进程？进程与

程序间的对应关系如何？

(2)用P,V操作写出这些进程的同步通信

关系。

阅览室问题

定义登记过程的互斥信号量mutex=1

阅览室可进人数信号量mc=100；

所有学生进程共用一个程序

Student：

(

P(mc);

P(mutex);

登记；

V(mutex);

阅读；

P(mutex);

去除登记;

V(mutex);

V(mc);

L_________

网球场问题

■某高校有m个网球场，n个学生预约打网

球，有k个裁判。每两个学生组成一队，

占用一个网球场练习，并安排一个裁判进

行判分（没有安排时，裁判休息）。

■请用PV操作完成网球场的分配和学生练

习过程

网球场问题

■用私有信号量实现多个进程之间的同步，引入场地管理进程，完成分配场

地和安排裁判的功能

-定义私有信号量，分别是

■想打球学生数student=O;场地数site=m,裁判数judge=k；

・学生允许进场信号量enter=O；学生打球结束信号量finish=O；安排教练信号

量call；

Student：monitor：