操作系统课件

操作系统引论1.0什么是操作系统1.0.1计算机系统的组成1.0.2操作系统的定义1.0.3操作系统在软硬件层次中的地位1.0.1计算机系统的组成

输入设备：键盘、鼠标、扫描仪

输出设备：显示器、打印机

外

存：软、硬盘、光盘、闪存

网络设备：网卡、调制解调器等

计算机系统软件外部设备系统软件应用软件硬件运算器控制器主机内存CPU随机存储器(RAM)只读存储器(ROM)高速缓冲存储器

操作系统：Windows、Unix、Linux语言处理程序：C、Pascal、VB等实用程序：诊断程序、排错程序等

办公软件包、数据库管理系统

1.0.2操作系统的定义

操作系统是计算机系统的一个系统软件，它直接控制和管理计算机系统中的硬件及软件资源，合理的组织计算机工作流程，以便有效的利用这些资源为用户提供一个功能强大、使用方便和可扩展的工作环境，从而在计算机与其用户之间起到接口的作用。操作系统（operatingsystem，简称OS）1.0.3操作系统在软硬件层次中的地位

裸机操作系统编译软件应用软件1.1操作系统的目标和作用1.1.1操作系统的目标1.1.2操作系统的作用1.1.3推动操作系统发展的主要动力1.1.1操作系统的目标

目前存在着多种类型的OS，不同类型的OS，其目标各有所侧重。通常在计算机硬件上配置的OS，其目标有以下几点：

1.方便性

2.有效性

3.可扩充性

4.开放性1.1.2操作系统的作用1.OS作为用户与计算机硬件系统之间的接口

OS作为用户与计算机硬件系统之间接口的含义是：OS处于用户与计算机硬件系统之间，用户通过OS来使用计算机系统。或者说，用户在OS帮助下，能够方便、快捷、安全、可靠地操纵计算机硬件和运行自己的程序。应注意，OS是一个系统软件，因而这种接口是软件接口。图1-1OS作为接口的示意图用户应用程序系统调用命令图标、窗口操作系统计算机硬件

(1)命令方式。这是指由OS提供了一组联机命令(语言)，用户可通过键盘输入有关命令，来直接操纵计算机系统。

(2)系统调用方式。OS提供了一组系统调用，用户可在自己的应用程序中通过相应的系统调用，来操纵计算机。

(3)图形、窗口方式。用户通过屏幕上的窗口和图标来操纵计算机系统和运行自己的程序。2.OS作为计算机系统资源的管理者

处理机管理，用于分配和控制处理机；

存储器管理，主要负责内存的分配与回收；

I/O设备管理，负责I/O设备的分配与操纵；

文件管理，负责文件的存取、共享和保护。

3.OS用作扩充机器

把覆盖了软件的机器称为扩充机器或虚机器。

OS包含了若干个层次，因此在裸机上覆盖OS后，便可获得一台功能显著增强，使用极为方便的多层扩充机器或多层虚机器。1.1.3推动操作系统发展的主要动力不断提高计算机资源利用率2.方便用户3.器件的不断更新换代4.计算机体系结构的不断发展1.2操作系统的发展过程1.2.1无操作系统的计算机系统1.2.2单道批处理系统1.2.3多道批处理系统1.2.4分时系统1.2.5实时系统1.2.1无操作系统的计算机系统1.人工操作方式电子管计算机时代（1945年到50年代中期），无操作系统。由手工控制作业的输入输出,通过控制台开关启动程序运行。用户使用计算机的过程大致如下：先把程序纸带装上输入机，启动输入机把程序和数据送入计算机，然后通过控制台开关启动程序运行，计算完毕后，用户拿走打印结果，并卸下纸带。缺点：(1)用户独占全机(2)CPU等待人工操作。2.脱机输入/输出(Off-LineI/O)方式

用户使用计算机的过程大致如下：先把程序纸带装上输入机，在外围机的控制下，输入到磁带上，当CPU需要时，从磁带高速调入内存。输出时，CPU直接高速把数据从内存送到磁带，然后在另一台外围机的控制下，将磁带上的结果通过输出设备输出。脱机输入/输出（Off－LineI/O）方式脱离主机的情况下输入输出程序和数据联机输入/输出（On－LineI/O）方式在主机的直接控制下输入输出程序和数据脱机I/O方式的主要优点如下：减少了CPU的空闲时间。(2)提高I/O速度。输入设备外围机磁盘主机外围机输出设备图1-2脱机I/O示意图1.2.2单道批处理系统(SimpleBatchProcessingSystem)1.单道批处理系统的处理过程图1-3单道批处理系统的处理流程把下一个作业的源程序转换为目标程序源程序有错吗？否装配目标程序还有下一个作业？是否停止运行目标程序是开始2.单道批处理系统的特征单道批处理系统是最早出现的一种OS，严格地说，它只能算作是OS的前身而并非是现在人们所理解的OS。尽管如此，该系统比起人工操作方式的系统已有很大进步。该系统的主要特征如下：

(1)自动性。

(2)顺序性。

(3)单道性。1.2.3多道批处理系统1.多道程序设计的基本概念

在单道批处理系统中，内存中仅有一道作业，它无法充分利用系统中的所有资源，致使系统性能较差。为了进一步提高资源的利用率和系统吞吐量，在60年代中期又引入了多道程序设计技术，由此而形成了多道批处理系统(MultiprogrammedBatchProcessingSystem)。在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。在OS中引入多道程序设计技术可带来以下好处：提高CPU的利用率。比较：图1-4(a)：单道程序的运行情况图1-4(b)：多道程序的运行情况（以四道为例）(2)可提高内存和I/O设备利用率。(3)增加系统吞吐量（在单位时间内完成的总工作量）。图1-4单道和多道程序运行情况(b)四道程序运行情况t1t2t3t4t5t6t7t8结束中断I/O

完成启动I/OI/O

中断请求I/O

完成启动

I/OI/O

中断请求用户程序监督程序I/O

操作(a)单道程序运行情况程序A程序AI/O请求程序AI/O完成程序B程序BI/O请求程序C程序CI/O请求程序D程序DI/O请求CI/O完成C再被调度程序BI/O完成程序A再被调度程序A程序B程序C程序D调度程序A完成结束中断2.多道批处理系统的特征多道性。(2)无序性。(3)调度性。3.多道批处理系统的优缺点资源利用率高。(2)系统吞吐量大。(3)平均周转时间长。(4)无交互能力。优点缺点

作业的周转时间：是指从作业进入系统开始，直至其完成并退出系统为止所经历的时间。4.多道批处理系统需要解决的问题处理机管理问题。(2)内存管理问题。(3)I/O设备管理问题。(4)文件管理问题。(5)作业管理问题。1.2.4分时系统1.分时系统(Time-SharingSystem)的产生

推动多道批处理系统形成和发展的动力是提高资源利用率和系统吞吐量。推动分时系统形成和发展的主要动力是用户的需要：（1）人机交互（2）共享主机（3）便于用户上机

分时系统是指在一台主机上连接多个带有显示器和键盘的终端，同时允许多个用户通过自己的键盘，以交互的方式使用计算机，共享主机中的资源。主机终端2.分时系统实现中的关键问题

如何使用户能与自己的作业进行交互，即当用户在自己的终端上键入命令时，系统应能及时接收并及时处理该命令，再将结果返回给用户。即使有多个用户同时通过自己的键盘键入命令，系统也应能全部地及时接收并处理。(1)及时接收（多路卡和缓冲区）(2)及时处理（作业直接进入内存，划分时间片）3.分时系统的特征多路性。(2)独立性。(3)及时性。(4)交互性。

1.2.5实时系统

实时系统(Real-TimeSystem)是指系统能及时(或即时)响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。1.应用需求实时控制：通常是指以计算机为中心的生产过程控制系统和武器控制系统。(2)实时信息处理：通常是指对信息进行实时处理的系统。2.实时任务1)按任务执行时是否呈现周期性来划分周期性实时任务外部设备发出周期性的激励信号。

(2)非周期性实时任务外部设备所发出的激励信号并无明显的周期性，但都必须联系着一个截止时间(Deadline)。它又可分为：

①开始截止时间——任务在某时间以前必须开始执行

②完成截止时间——任务在某时间以前必须完成

2)根据对截止时间的要求来划分

(1)硬实时任务(hardreal-timetask)。系统必须满足任务对截止时间的要求，否则可能出现难以预测的结果。

(2)软实时任务(Softreal-timetask)。它也联系着一个截止时间，但并不严格，若偶尔错过了任务的截止时间，对系统产生的影响也不会太大。3.实时系统与分时系统特征的比较多路性。(2)独立性。(3)及时性。(4)交互性。(5)可靠性。1.3操作系统的基本特性1.3.1并发（Concurrence）1.3.2共享（Sharing）1.3.3虚拟（Virtual）1.3.4异步性（Asynchronism）1.3.1并发(Concurrence)

所谓并发是指在内存中放多道作业，在一个时间段上来看，每一道作业都能不同程度地向前推进，但在任何一个时间点上只能有一道占用CPU。与并发相关的两个概念：串行：在内存中每次只能放一道作业，只有它完 全执行完后别的作业才能进入内存执行。并行：存在于有多个CPU的环境中，在内存中放 多道作业，在任一时间点上都可能有多道 作业在不同的CPU上同时执行。1.3.2共享(Sharing)

共享：系统中的资源可供内存中多个并发执行的进程（线程）共同使用。两种资源共享方式：互斥共享方式（临界/独占资源）同时访问方式并发与共享互为条件！1.3.3虚拟(Virtual)

虚拟是指通过某种技术，将一个物理实体变为若干个逻辑上的对应物。用来实现虚拟的技术，被称为虚拟技术。在现代OS中利用了多种虚拟技术，分别用来实现虚拟处理机、虚拟存储器和虚拟设备等。1.3.4异步性(Asynchronism)

异步性是指在多道程序的环境下，每个程序不知何时执行、何时暂停，即它们以不可预知的速度向前推进。但同时，操作系统应保证程序的执行结果是可再现的。即只要运行环境相同，一个作业的多次运行都会得到相同的结果。1.4操作系统的主要功能1.4.1处理机管理功能1.4.2存储器管理功能1.4.3设备管理功能1.4.4文件系统管理1.4.5用户接口1.4.1处理机管理功能

处理机是最重要的资源，现代操作系统允许多个程序共享处理机，按照某种算法（分时、优先级）交替地使用处理机。处理机管理包括以下几方面：进程控制进程同步（进程互斥方式、进程同步方式）进程通信调度1.4.2存储器管理功能

第二重要资源。存储器管理主要是为多道程序的运行提供良好的环境。存储器管理要具备下列功能：内存分配

内存保护：使多道程序间互不干扰

地址映射：把程序中的逻辑地址映射为物理地址内存扩充：用辅存扩充主存，实现“虚拟存储器”

最庞大、琐碎的部分，因为：

物理设备品种繁多、用法各异

各种外设能和主机并行工作主机与各类外设速度极不匹配，级差很大1.4.3设备管理功能

设备管理主要是完成用户的I/O请求。它的主要功能包括：缓冲管理：为设备提供缓冲区以缓和CPU同设备的I/O速度不匹配的矛盾。

设备分配

设备处理1.4.4文件管理功能

文件管理主要是使用户能方便、安全地使用各种信息资源。主要功能包括：

文件存储空间的管理目录管理文件的读/写管理和保护2.1进程的基本概念2.1.1前趋图2.1.2程序的顺序执行及其特征2.1.3程序的并发执行及其特征2.1.4进程的特征与状态2.1.5进程控制块2.1.1前趋图（PrecedenceGraph）

是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。P1P2P3P4P5P6P7P8P9结点有向边直接前驱直接后继初始结点终止结点重量例：具有九个结点的前趋图PiPj前趋关系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9

S1S2S3前驱图中不能存在循环关系。如：2.1.2程序的顺序执行及其特征各程序段间程序的顺序执行如图：

在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。一道程序执行完后另一道才能开始。I1P1O1I2P2O2作业1作业2一个程序段的多条语句的顺序执行：S1S2S3S1:a:=x+yS2:b:=a-5S3:c:=b+1程序顺序执行的特征：顺序性：一个程序开始执行必须要等到前一个程序已执行完成。封闭性：程序一旦开始执行，其计算结果不受外界因素影响。可再现性：程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果。2.1.3程序的并发执行及其特征1.程序的并发执行所谓程序的并发执行是指：若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。

I1I2I3C1C2C3P1P2P3I4C4P4一个程序段的多条语句的并发执行：S1:a:=x+2S2:b:=y+5S3:c:=a+bS4:d:=c+6S1S3S4S2程序并发执行的特征：间断性由于资源共享和相互合作，并发执行的程序间形成了相互制约关系，导致程序的运行过程出现“执行—暂停—执行”的现象。失去封闭性程序在并发执行时，是多个程序共享系统中的资源，因此这些资源的状态将由多个程序来改变。不可再现性由失去封闭性导致。同样的初始条件，一个程序的多次重复执行，可得到不同的结果。

例：程序A、B，共享变量N。代码如下：程序ABEGINREPEAT……N：=N+1……UNTILFALSEEND程序BBEGINREPEAT……PRINT(N)N:=0…UNTILFALSEEND两个程序以不同速度运行，可能出现三种情况：N:=N+1在Print(N)和N:=0之前

——N值分别为N+1，N+1，0N:=N+1在Print(N)和N:=0之后

——N值分别为N,0,1N:=N+1在Print(N)和N:=0之间

——N值分别为N,N+1，0思考：任何并发执行都是不可再现的吗？并发执行的条件：

并发执行的条件：达到封闭性和可再现性。并发执行失去封闭性的的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件。将程序中任一语句或程序段Pi划分为两个变量的集合，R(pi)和W(pi)。其中，

R(pi)={a1,a2,…an}，程序pi在执行期间引用的（读的）变量集，称为“读集”。

W(pi)={b1,b2,…bm}，程序pi在执行期间改变的（写的）变量集，称为“写集”。

Bernstein条件:

如果对于语句p1、p2，如果同时满足以下三个条件：R(p1)∩W(p2)={}R(p2)∩W(p1)={}W(p1)∩W(p2)={}

则语句p1、p2可以并发执行。例如，有如下四条语句：

S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1其中：R(S1)={x,y}W(S1)={a}R(S2)={z}W(S2)={b}R(S3)={a,b}W(S3)={c}R(S4)={c}W(S4)={w}对于S1和S2，有：

R(S1)∩W(S2)={}，R(S2)∩W(S1)={}，

W(S1)∩W(S2)={}结论：语句S1和S2满足Bernstein条件，可以并发执行。其他语句之间自己分析。2.1.4进程的特征与状态1.进程的定义

进程是操作系统中最基本、重要的概念。是多道程序系统出现后，为了刻画系统内部出现的动态情况，描述系统内部各道程序的活动规律引进的一个概念，所有多道程序设计操作系统都建立在进程的基础上。较典型的进程定义有：

(1)进程是程序的一次执行。

(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

(4)进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

(5)进程是一个具有一定独立功能的程序关于某个集合的一次运行活动。(我国78年庐山研讨会)

2.进程同程序的比较：进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。进程是暂时的，程序是永久的：进程是一个状态变化的过程，是有一定生命期的；而程序可以作为一种软件资料长久保存。进程与程序的组成不同：进程是由程序和数据、进程控制块三部分组成的。进程与程序的对应关系：同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程；一个进程的执行也可以涉及到一个或几个程序（调用）。3.进程的特征：结构特征：由程序段、数据段、进程控制块三部分组成；动态性：进程是程序的执行；并发性：多个进程可同存于内存中，能在一段时间内同时运行；独立性：独立运行的基本单位，独立获得资源和调度的基本单位；异步性：各进程按各自独立的不可预知的速度向前推进。4.进程的三种基本状态不同系统设置的进程状态数目不同。进程有三种基本状态：

1)就绪状态：进程已获得除CPU以外的所有必要资源，只要得到CPU，便可立即执行。2)执行状态：进程已得到CPU，其程序正在CPU上执行。3)阻塞状态：正在执行的进程因某种事件(如I/O请求)的发生而暂时无法继续执行，只有等相应事件完成后，才能去竞争CPU。进程的状态变迁图执行五状态进程模型进程正常结束，或因某种原因被取消后，OS释放出的进程。刚刚建立的进程，还未送入就绪队列。执行新建态终止态5.

七状态进程模型引入挂起状态的原因：终端用户的请求父进程请求负荷调节的需要操作系统的需要

“挂起”的实质是使进程不能继续执行，即使挂起后的进程处于就绪状态，它也不能参与对CPU的竞争。因此，称被挂起的进程处于静止状态，相反，没被挂起的进程则处于活动状态。而且，处于静止状态的进程，只有通过“激活”动作，才能转换成活动状态。进程挂起后,程序代码和数据集被调出到外存的交换区中,腾出来的内存空间供其它进程使用。激活挂起事件发生事件发生等待事件挂起调度超时释放激活挂起激活挂起事件发生事件发生等待事件挂起调度超时释放激活挂起七状态进程模型挂起就绪态挂起阻塞态就绪态阻塞态执行态终止态新建态就绪态（ready）:进程在内存且可立即进入运行状态。阻塞态（blocked）:进程在内存并等待某一个事件的出现。挂起就绪态（readysuspend）:进程在外存,但只要进入内存,即可运行。挂起阻塞态（blockedsuspend）:进程在外存并等待某一个事件的出现。【思考题】有没有这样的状态转换，为什么？ 阻塞—运行就绪—阻塞2.1.5进程控制块（ProcessControlBlock，PCB

）

1.进程控制块的作用

进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。进程与PCB是一一对应的。

PCB应常驻内存。2.进程控制块中的信息进程标识符：用于惟一地标识系统中的每个进程。另外，还可以用父进程的标识符及子进程的标识符来描述进程的家族关系。处理机状态：用于CPU切换时保存现场和恢复现场，主要由处理机中各种寄存器的内容组成。进程调度和控制信息：用于进程调度和控制，主要包括进程状态、优先级、等待和使用CPU的时间总和、程序和数据的地址、进程同步和通信信息、资源清单和进程队列指针等。3.进程控制块的组织方式图2-7PCB链接队列示意图

在一个系统中通常有许多的PCB，称为PCB集合。为了便于管理，系统必须用适当的方式将PCB组织起来，常用的方式有链接方式和索引方式。PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针…1)链接方式相同状态的进程PCB组成一个链表，不同状态对应多个不同的链表。空指针2)索引方式执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址。2.2进程控制2.2.1进程的创建2.2.2进程的终止2.2.3进程的阻塞与唤醒2.2.4进程的挂起与激活

进程控制是进程管理中最基本的功能，它用于创建和撤消进程，并对进程在整个生命周期中各种状态之间的转换进行有效控制。进程控制是由操作系统的内核通过原语来实现的。原语：系统状态下执行的某些具有特定功能的程序段称为原语。(原语的执行具有原子性，执行时不可分割)。2.2.1进程的创建1.进程图(ProcessGraph)：用于描述一个进程的家族关系的有向树。

DEFGHBCIJKLMA祖先进程父进程子进程

子进程可以继承父进程的所有资源，当子进程被撤消时，应将从父进程那里获得的资源归还给父进程。撤消父进程时也必须同时撤消其所有的子进程。2.引起创建进程的事件(1)用户登录。(2)作业调度。(3)提供服务。(4)应用请求。3.进程的创建(CreationofProgress)(1)申请空白PCB。

(2)为新进程分配资源。

(3)初始化进程控制块。

(4)将新进程插入就绪队列。创建新进程通过进程创建原语creat（）来完成。进程创建原语的主要任务是创建进程控制块PCB。入口查PCB链表有空PCB？取空PCB（i）将有关参数填入PCB（i）相应项PCB（i）入就绪队列PCB(i)入进程家族或进程链创建失败返回创建原语流程图NY2.2.2进程的终止

当某进程实现完成任务正常结束时，或在运行过程中遇到某些异常情况（如越界错误、非法指令、运行超时等），或外界干预需要结束时，应予以终止（撤消）。（参见P35）通过进程终止原语来终止进程。终止进程的实质是收回PCB。进程的终止过程：

(1)查找对应的PCB(2)终止该进程及子孙进程

(3)释放资源

(4)释放PCB

终止原语流程图入口查进程链表或进程家族有此PCB吗？释放该进程所占有的资源出错处理该PCB有子进程吗？释放该PCB结构本身YYNN返回2.2.3进程的阻塞与唤醒1.进程的阻塞当正在执行的进程需要等待某种事件的完成或本身无新工作可做时，应调用阻塞原语将自己从执行状态转换成阻塞状态。进程阻塞是进程的一种主动行为。通过阻塞原语block（）来完成。具体的操作过程是：停止进程的执行，将其状态改为阻塞状态，并把它的PCB插入相应的阻塞（等待）队列，转调度程序进行重新调度。阻塞原语流程图保存当前进程的CPU现场置该进程的状态被阻塞进程入阻塞队列转进程调度入口2.进程的唤醒当阻塞进程所等待的事件完成时，应调用唤醒原语将该进程的状态从阻塞状态转换成就绪状态。通过唤醒原语wakeup（）来完成。

处于阻塞状态的进程是绝不可能叫醒自己的，必须由它的合作进程用唤醒原语唤醒它。具体的操作过程是：在等待队列中移出该进程的PCB，将其置成就绪状态，并把它插入就绪队列。唤醒原语流程图从等待队列中摘下被唤醒进程将被唤醒进程置为就绪态将被唤醒进程送入就绪队列转进程调度或返回入口2.2.4进程的挂起与激活1、进程的挂起当出现了引起进程挂起的事件时，用户请求将自己挂起，或者父进程请求挂起自己的子进程。系统通过挂起原语suspend（）将指定进程挂起。具体的执行过程：检查被挂起进程的状态，如果处于活动就绪状态，就将它改为静止就绪；如果处于活动阻塞，则改为静止阻塞。将PCB复制到指定的内存区域供用户或父进程考查。若挂起前进程正在执行，则转调度程序重新进行进程调度。2、进程的激活当发生激活事件后，系统利用激活原语Active()将指定进程激活。具体的操作过程是：若进程处于静止阻塞状态，则将它转换成活动阻塞状态，否则将它转换成活动就绪状态。若进程转换成活动就绪状态，而系统又采用抢占调度策略，则应检查该进程是否有权抢占CPU，若有则应进行进程调度。2.3进程同步2.3.1进程同步的基本概念2.3.2信号量机制2.3.3信号量的使用

进程同步是指对多个相关进程在执行次序上进行协调。进程同步的主要任务是使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行具有可再现性。1.两种形式的制约关系

间接相互制约关系互斥关系，资源共享关系直接相互制约关系同步关系，相互合作关系2.3.1进程同步的基本概念2.临界资源

一次仅允许一个进程访问的资源。如：进程Ａ、Ｂ共享一台打印机，若让它们交替使用则得到的结果肯定不是我们希望的。临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。并发进程对临界资源的访问必须作某种限制，否则就可能出现错误，如：联网售票，会出现与时间有关的错误。例：两进程共享一个变量COUNTP1:R1:=COUNT;R1:=R1+1;COUNT:=R1;P2:P2:=COUNT;R2:=R2+1;COUNT:=R2;试比较两进程顺序执行和并发执行的结果。若P1、P2按如下顺序并发执行：P1:R1:=COUNT;P2:R2:=COUNT;P1:R1:=R1+1;COUNT:=R1;P2:R2:=R2+1;COUNT:=R2;

若P1、P2顺序执行：

P1:R1:=COUNT;R1:=R1+1;COUNT:=R1;P2:R2:=COUNT;R2:=R2+1;COUNT:=R2;3.临界区(CriticalSection)

每个进程中，访问临界资源的那段代码称为临界区。诸进程对临界资源的互斥访问就变为怎样使诸进程互斥地进入临界区。

互斥的实质就是同步，或者说，互斥是同步的一种特殊形式。

访问临界资源的循环进程描述如下：

REPEAT

ENTRYSECTIONCRITICALSECTIONEXITSECTIONREMAINDERSECTIONUNTILFALSE进入区临界区退出区剩余区4.同步机制应遵循的原则

用来实现互斥的同步机制必须遵循下述四条准则：

(1)空闲让进。

(2)忙则等待。

(3)有限等待。

(4)让权等待。2.3.2信号量机制

信号量机制是荷兰学者Dijkstra在1965年提出的一种卓有成效的同步工具，在长期且广泛的应用中，已由早期的整型信号量发展为记录型信号量，进而发展为信号量集。1.整型信号量

整型信号量是一个非负的共享整数，除了初始化外，它只能通过两个标准的原子操作wait和signal来访问，即P、V操作。

wait和signal操作可描述为：

wait(S):whileS≤0dono-op

S∶=S-1;

signal(S):S∶=S+1;

整型信号量的主要问题是，只要S≤0，wait操作就会不断地测试，因而，没能做到“让权等待”。2.记录型信号量

记录型信号量中除了一个整型变量value外，还增加了一个等待队列指针L。记录型信号量采用了记录型的数据结构，描述为：typesemaphore=record

value:integer;

L:listofprocess;

end

相应的wait和signal操作（即P、V操作）可描述为：procedureP(S)

varS:semaphore;

begin

S.value:=S.value-1;

ifS.value＜0thenblock(S.L)

end

当S.value＜0时，进程会立即将自己阻塞，因此解决了整型信号量的“忙等”问题，做到了“让权等待”。该进程状态置为阻塞状态；放弃处理机；将该进程的PCB插入链表S.L中。procedureV(S)

varS:semaphore;

begin

S.value:=S.value+1;

ifS.value≤0thenwakeup(S.L)

end

唤醒S.L链表中的第一个等待进程；改变状态为就绪态；将其插入就绪队列中。

一个信号量通常对应于一类临界资源，在使用前，信号量必须经过定义并赋适当的初值，初值表示系统中某类资源的数目。初值为1表示对临界资源进行访问，此时信号量转化为互斥信号量。每次对信号量进行wait操作意味着申请一个单位的该类资源，signal操作意味着归还一个单位的该类资源。当S.value＞0时，它的值表示系统中该类资源当前可用的数目；S.value≤0时，表示该类资源已分配完毕，其绝对值表示系统中因申请该类资源而阻塞在S.L队列上的进程数目。

必须注意的几个问题：2.3.3信号量的使用必须置一次且只能置一次初值初值为整数，且不能为负数

只能执行P、V操作1.用信号量实现进程互斥P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)PA:…P(mutex);criticalsection;V(mutex);…PB:…P(mutex);criticalsection;V(mutex);…mutex用于实现互斥，初值为1。在每个进程中将临界区代码置于P(mutex)和V(mutex)之间。模型：模拟执行：序号PAPBmutex说明011P(mutex)0PA进入，占资源2P(mutex)-1PB进入，无资源3V(mutex)0PA释放资源，PB解封4V(mutex)1PB释放资源0可反复执行

对于两个并发进程，互斥信号量的值仅取1、0和-1三个值：若mutex＝1表示没有进程进入临界区；若mutex＝0表示有一个进程进入临界区；若mutex＝-1表示一个进程进入临界区，另一个进程等待进入。当实现n个进程并发时，互斥信号量的取值为1、0、-1、…、-(n-1)。

P、V操作必须成对出现：遗漏P(mutex)将不能保证互斥访问，遗漏V(mutex)将不能再使用临界资源之后将其释放（给其他等待的进程）。PA:…L1：P(proceed)…2.用信号量实现同步PB:…L2：V(proceed)…proceed用于实现同步，初值为0。PA在L1点必须与PB在L2点同步，PA受PB的制约，而PB不受PA的制约，使非对称的。

P、V操作必须成对出现，当用于实现互斥时，它们同处于同一进程；当用于实现同步操作时，则不在同一进程中出现。模型：3.利用信号量描述前趋关系

信号量可用来描述程序或语句之间的前趋关系。若Pi是Pj的直接前趋，即Pi→Pj，则可设置一个初值为0的公用信号量S，并将V(S)操作放在Pi后，而在Pj前插入P(S)操作，以保证Pi在Pj开始执行之前完成。PiPjVara,b,c,d,e,f,g:semaphores;Beginparbeginbegins1;v(a);v(b);end;beginp(a);s2;v(c);end;beginp(c);s4;v(e);v(f);end;beginp(b);s3;v(d);end;beginp(e);s5;v(g);end;beginp(f);p(d);s6;v(h);end;beginp(g);p(h);s7;end;Parbeginends1s2s3s4s5s1s6s7abcdefgh例：2.4经典进程的同步问题2.4.1生产者—消费者问题2.4.2哲学家进餐问题2.4.3读者——写者问题2.4.1生产者—消费者问题放产品取产品一次只可放一个产品生产者消费者

只要仓库未满，生产者就可以把产品放入仓库。只要仓库未空，消费者就可以从仓库中取走物品。问题描述：inout01234567891011in:下一个可供投放产品的缓冲区,in:=(in+1)modn；

out:下一个可供获取产品的缓冲区,out:=(out+1)modn。若(in+1)modn=out，有界缓冲区满；若in=out，有界缓冲区空。环形缓冲池设一个长度为n的有界缓冲区：（以n=12为例）问题分析：这是一个同步与互斥共存的问题。1.生产者—消费者问题是一个同步问题。即生产者和消费者之间满足如下条件：消费者想接收数据时，有界缓冲区中至少有一个单元是满的。生产者想发送数据时，有界缓冲区中至少有一个单元是空的。故设置两个信号量：empty：说明空缓冲区的数目，初值为有界缓冲区的大小N。full：说明已用缓冲区的数目，初值为０。

2.

由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执行。故设置一个互斥信号量mutex，其初值为１。问题的解：Varmedex,empty,full:semaphore;buffer:array[0,1,…n-1]ofitem;in,out:integer;Beginmetex:=1;empty:=n;full:=0;in:=0;out:=0;Parbegin

procedure:……

consumer:……ParendendConsumer：

beginrepeat

P(full);P(mutex);

从Buffer[out]取产品;out=(out+1)modn;

V(mutex);V(empty);…

消费产品;…untilfalse;endProducter：

begin

repeat…

生产产品;

…

P(empty);P(mutex);

往Buffer[in]放产品;in=(in+1)modn;

V(mutex);V(full);untilfalse;end有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。2.4.2哲学家就餐问题问题描述：每个哲学家的行为是思考，感到饥饿，然后吃通心粉；吃完后继续思考。为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。问题的解：repeat

P(fork[i]);P(fork[(i+1)mod5])；

…

进食；

…

V(fork[i]);V(fork[(i+1)mod5])；

…

思考；

…untilfalse设fork[5]为5个信号量（分别表示每支筷子），初值均为1。此解可以保证互斥使用筷子，但会产生死锁。为防止死锁发生可采取的措施：

最多允许4个哲学家同时去拿左边的筷子；仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子进餐；（

）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之。信号量集——AND型信号量集AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配。AND型信号量集P原语为Swait；

AND型信号量集V原语为Ssignal。采用AND信号量集解决哲学家就餐问题repeat

Swait(fork[i],fork[(i+1)mod5])；

…

进食；

…

Ssignal(fork[i],fork[(i+1)mod5])；

…

思考；

…untilfalse设fork[5]为5个信号量（分别表示每支筷子），初值为均1。2.4.3读者-写者问题问题描述：

有两组并发进程——读者和写者，共享一组数据区。要求：允许多个读者同时执行读操作；任一写者在完成写操作之前不允许其它读者或写者工作(读写文件)；写者执行写操作前，应让已有的写者和读者全部退出。如果读者来：若无读者、写者，则新读者可以读；若有写者等待，但有其它读者正在读，则新读者也可以读；若有写者写，则新读者等待。如果写者来：若无读者，则新写者可以写；若有读者，则新写者等待；若有其它写者，则新写者等待。问题分析：问题的解：整形变量readcount表示正在读的读者数目，初值为0。信号量w用于保证读者和写者、写者和写者之间的互斥,初值为1。信号量mutex用于保证对readcount这个临界资源的互斥修改，初值为1。读者：beginrepeat

P(mutex);readcount:=readcount+1;ifreadcount=1thenP(w);

V(mutex); …

执行读操作；

…

P(mutex);readcount:=readcount-1;ifreadcount=0thenV(w);

V(mutex);untilfalseend写者：beginrepeat

P(w);

执行写操作；

V(w);untilfalseend【思考题】

桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步与互斥。提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。问题的解：Daughter:repeatP(Sa)；取苹果；

V(S);

吃苹果;untilfalseSon:repeatP(So)；取桔子；

V(S);

吃桔子;untilfalseFather:repeatP(S);

将水果放入盘中;if桔子

thenV(So);elseV(Sa);untilfalse

设置三个信号量S、So、Sa，初值分别为1、0、0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。【思考题】

有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）；（2）－N＜A产品数量－B产品数量＜M；其中，N和M是正整数。试用P、V操作描述产品A与B的入库过程。提示：设两个信号量Sa、Sb。Sa表示允许A产品比B产品多入库的数量；Sb表示允许B产品比A产品多入库的数量设两个信号量Sa、Sb，初值分别为M-1，N-1Sa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量设互斥信号量mutex，初值为1。问题的解：B产品入库进程：repeat

P(Sb);P(mutex);B产品入库

V(mutex);V(Sa);

…

消费产品;…untilfalseA产品入库进程：repeat…

生产产品;…

P(Sa);

P(mutex);A产品入库

V(mutex);

V(Sb);untilfalse2.5管程机制2.5.1管程的基本概念2.5.2利用管程解决生产者-消费者问题2.5.1管程的基本概念为什么引入管程？把分散在各进程中的临界区集中起来进行管理；防止进程有意或无意的违法同步操作；便于用高级语言来书写程序，也便于程序正确性验证。管程的基本概念：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。管程的特点：

(1)管程内的局部变量只能被局部于管程内的过程所访问；反之亦然，即局部于管程内的过程只能访问管程内的变量。

(2)任何进程只能通过调用管程提供的过程入口进入管程。

(3)任一时刻，最多只能有一个进程在管程中执行。typemonitor-name=monitorvariabledeclarations

procedureentryP1(…);

begin…end;

procedureentryP2(…);

begin…end;

…

procedureentryPn(…);

begin…end;

begin

initializationcode;

end管程的语法局部于管程的共享变量说明对该数据结构进行操作的一组过程对局部于管程的数据设置初始值管程的组成部分共享数据…一组操作过程初始化代码进入队列条件(不忙)队列管程的示意图：

当进程通过管程请求临界资源未能满足时，将排在队列上等待。等待的原因可能有多个，为了区分它们，引入条件变量condition。每个condition表示一种等待原因。

针对条件变量x，x.wait将自己阻塞在x队列中，x.signal将x队列中的一个进程唤醒。条件变量：2.5.2利用管程解决生产者-消费者问题PC管程描述：TypeProducer-Consumer=monitorVarbuffer：array[0,…,n-1]ofitem；count，in，out：integer；notempty，notfull：condition；procedureentryput(item);beginifcount>=nthennotfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1；

ifnotempty.queuethennotempty.signal;end;procedureentryget(item);beginifcount<=0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1；

ifnotfull.queuethennotfull.signal;end;Beginin:=0;out:=0;count:=0Endproducer：beginrepeatproduceanitem；

PC.put(item)；

untilfalse；endconsumer：beginrepeat

PC.get(item)；

consumetheitem；

untilfalse;end生产者和消费者描述：2.6进程通信2.6.1进程通信的类型2.6.2消息缓冲队列通信机制

进程之间互相交换信息的工作称为进程通信。进程通信的类型：低级通信：归结为进程之间的互斥和同步，一般只传送少量信息（信号量）。缺点：效率低，通信对用户不透明。高级通信：能够高效传输大量数量数据的通信方式。又分为三类：共享存储器系统、消息传递系统、管道通信系统。2.6.1进程通信的类型1.共享存储器系统

相互通讯的进程通过共享数据结构和共享存储区进行通讯，可进一步分为：

基于共享数据结构的通信方式进程之间通过某种数据结构，如缓冲池进行通信，属于低级通信方式。如生产者-消费者问题中的有界缓冲区。

基于共享存储区的通信方式为了传送大量信息，在存储器中划出一块共享存储区，诸进程可通过对共享存储区进行读或写来实现通信，属高级通信方式。2.消息传递系统

使用最广泛的一种进程通信机制。进程间的数据交换以消息或报文为单位，程序员直接利用一组通信命令（原语）来实现通信。操作系统隐藏了通信的实现细节，简化了通信程序编制的复杂性。（1）直接通信方式两条通信原语：Send（Receiver，message）;Receive（Sender，message）;

例如：Send（p2，m1）;Receive（p1，m1）;发送进程可直接将消息发送给目标进程。消息传递系统的分类：——直接通信方式和间接通信方式repeat

…

produceaniteminnextp;

…

send(consumer,nextp);

untilfalse;利用直接通信原语解决生产者-消费者问题：repeat

receive(producer,nextc);

…

consumetheiteminnextc;

untilfalse;producer：consumer：

（2）间接通信方式

进程间发送或接收消息通过信箱进行，消息可被理解成信件。也称信箱通信。两条通信原语：

Send（mailbox，message）；

Receive（mailbox，message）；注意：用户不必写出接收进程标识符，从而可以向不知名的进程发送消息；另外，消息在信箱中可以安全的保存，只允许核准的目标用户随时读取，可实现非实时通信。发送进程A

…邮箱体

邮箱头接收进程B

信箱由信箱头和由若干格子组成的信箱体组成。信箱中每个格子存放一封信，信箱中格子的数目和每格的大小在创建信箱时确定。进程间的通信要满足如下条件：

a.

发送进程发送消息时，邮箱中至少要有一个空格存放该消息。

b.

接收进程接收消息时，邮箱中至少要有一个消息存在。3.管道（Pipe）通信系统

所谓管道，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又称pipe文件。发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信。管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。读写进程相互协调，必须做到：

互斥：进程对通信机构的使用应该互斥，一个进程正在使用某个管道写入或读出数据时，另一个进程就必须等待。

同步：管道长度有限,发送信息和接收信息之间要实现正确的同步关系。当写进程把一定数量的数据写入pipe，就去睡眠等待，直到读进程取走数据后，把它唤醒。

确定对方是否存在：发送者和接收者双方必须能够知道对方是否存在，如果对方已经不存在，就没有必要再发送信息。写进程共享文件读进程管道通信的思想：（1）发送进程可以源源不断的从pipe一端写入数据流，在规定的pipe文件的最大长度（如4096字节）范围内，每次写入的信息长度是可变的；（2）接收进程在需要时可以从pipe的另一端读出数据，读出单位长度也是可变的。2.6.2消息缓冲队列通信机制

消息缓冲队列通信机制通过内存中公用的消息缓冲区进行进程通信，属于直接通信方式。发送进程利用send原语将消息直接发送给接收进程；接收进程利用receive原语接收消息。（1）消息缓冲区的数据结构typemessageBuffer=record

sender；发送者ID;size；消息长度;text；消息正文;next；消息队列指针;end1.消息缓冲队列通信机制中的数据结构（2）PCB中有关通信的数据项typePCB=record…mq;消息队列首指针;mutex;消息队列互斥信号量;sm;消息队列资源信号量;…end2.用P、V操作来实现Send原语proceduresend(receiver,a)

begin

getbuf(a.size,i);

i.sender:=a.sender;i.size:=a.size;

i.text:=a.text;

i.next:=0;

getid(PCBset,receiver.j);

P(j.mutex);

insert(j.mq,i);

V(j.mutex);

V(j.sm);

end根据a.size申请缓冲区i;将发送区a中的信息复制到消息缓冲区之中;获得接收进程内部标识符;将消息缓冲区插入消息队列;3.用P、V操作来实现Receive原语procedurereceive(b)

begin

j:=internalname;

P(j.sm);

P(j.mutex);

remove(j.mq,i);

V(j.mutex);

b.sender:=i.sender;b.size:=i.size;

b.text:=i.text;

releasei;end

j为接收进程内部的标识符；将消息队列中第一个消息移出；将消息缓冲区i中的信息复制到接收区b;

将消息缓冲i归还给系统;mqmutexsmSend(B,a)sender:Asize:5text:Hellosender:Asize:5text:Hellonext:0receive(b)sender:Asize:5text:Hello发送区a进程A进程B接收区bPCB(B)第一消息缓冲区ba2.7线程线程的引入:引入进程的目的是为了使多个程序并发执行，以改善资源利用率、提高系统吞吐量。引入线程则是为了减少程序并发执行时的所付出的时空开销。进程的两个基本属性：进程是一个可拥有资源的基本单位。进程同时又是一个可独立调度和分派的基本单位。线程的属性:轻型实体：线程自己基本不拥有系统资源，只拥有少量必不可少的资源：程序计数器、一组寄存器、栈。独立调度和分派的基本单位：在引入线程的OS中，线程是进程中的一个实体，是被系统独立调度和分派的基本单位。可并发执行：同一进程中的多个线程之间可以并发执行，不同进程中的线程也能并发执行。共享进程资源：它可与同属一个进程的其它线程共享进程所拥有的全部资源。引入线程的好处:创建一个新线程花费时间少（结束亦如此）；两个线程的切换花费时间少；因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核；适合多处理机系统。3.1处理机调度的基本概念3.1.1高级、中级和低级调度3.1.2调度队列模型3.1.3选择调度方式和调度算法的若干原则高级调度：又称为作业调度或长程调度。用于决定把后备队列中的哪些作业调入内存，为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。在批处理系统