第2章进程的描述与控制2

1第二章进程控制与描述2.5经典进程同步问题2.6进程通信2.7线程的基本概念2.8线程的实现22.5

经典进程的同步问题

1.生产者—消费者问题2.哲学家进餐问题3.读者—写者问题通过对经典问题的研究和学习，可以帮助我们更好地理解进程同步的概念及实现方法P6032.5.1生产者—消费者问题

Producer-consumerproblem，又称有限缓冲问题（Bounded-bufferproblem)两个共享固定大小缓冲区的进程—“生产者”和“消费者”42.5.1生产者—消费者问题

Theyare,相互合作进程关系1.用记录型信号量解决

2.

用AND信号量解决3.利用管程解决生产者-消费者问题单缓冲区情况生产者P和消费者C共用一个缓冲区，P生产产品放入缓冲区，C从缓冲区取产品来消费。多个缓冲区情况生产者和消费者通过一个有界缓冲池(n个)相互联系。

5单缓冲区情况单缓冲区的同步问题

生产者P进程不能往“满”的缓冲区中放产品，设置信号量为empty（初值为1）消费者C进程不能从“空”的缓冲区中取产品，设置信号量full（初值为0）单缓冲区的互斥问题P、C进程不能同时使用缓冲区6Semaphoreempty=n,full=0；(单缓冲区)生产者─消费者问题Proceducer

：while(true){

生产一个产品;

P(empty);

送产品到缓冲区;

V(full);};Consumer：while(true){P(full);从缓冲区取产品;

V(empty);消费产品;};7多个缓冲区情况生产者和消费者共享n个缓冲区，利用互斥信号量Mutex(Mutualexclusion，缩写Mutex)实现进程对缓冲池的互斥使用。信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。8....PC生产者消费者n-1n个Buffer

同步当缓冲池已放满产品时，生产者进程必须等待当缓冲池已空时，消费者进程应等待互斥：所有进程应互斥使用缓冲池这一临界资源。91.用记录型信号量解决

Semaphoreempty=n,full=0；empty表示空缓冲个数，初值为n；full表示满缓冲个数，初值为0。互斥使用临界区的信号量mutex，初值为1。101.用记录型信号量解决

Semaphoreempty=n,full=0,mutex;item=buffer[n];intin=0,out=0;Main(){cobeginproducer();consumer();

coend}11生产者producer(){do{

produceaniteminnextp;┋wait(empty);/*申请空缓冲区*/wait(mutex);/*实现对缓冲池的互斥使用*/

buffer[in]=nextp;in=(in+1)%n;signal(mutex);signal(full);/*满缓冲区的个数加1*/}while(TRUE)}重点掌握！12消费者consumer(){

do{wait(full);/*申请满缓冲区*/wait(mutex);

/*实现互斥*/nextc=buffer[out];out=(out+1)modn;signal(mutex);signal(empty);/*空缓冲区的个数加1*/consumetheiteminnextc;┋}while(TRUE);}重点掌握！132.

用AND信号量解决对于生产者—消费者问题，也可利用AND信号量来解决，即用：

Swait(empty，mutex)→wait(empty)和wait(mutex)

Ssignal(mutex，full)→signal(mutex)和signal(full)

Swait(full，mutex)→

wait(full)和wait(mutex)

Ssignal(mutex，empty)→Signal(mutex)和Signal(empty)

14Producer(){repeat┋produceaniteminnextp;┋

Swait(empty,mutex);buffer[in]=nextp;in=[in+1]%n;

Ssignal(mutex,full);untilfalse;}Consumer(){repeatSwait(mutex,full);nextc=buffer[out];out=(out+1)%n;Ssignal(mutex,empty);consumetheiteminnextc;┋untilfalse;}152.5.2哲学家进餐问题5个哲学家围坐在圆桌旁，每人面前有一只空盘子，每2人之间放一只筷子:放在桌子上的筷子是临界资源，可用一个信号量表示一只筷子，五个信号量构成信号量数组。Semaphorechopstick[5]={1,1,1,1,1}；为了就餐，每个哲学家必须拿到两只筷子，并且只能直接从自己的左边或右边去取筷子。

[ˈsɛməˌfɔr]16

1.

利用记录型信号量解决第i位哲学家的活动可描述为：Semaphorechopstick[5]={1,1,1,1,1}；repeatwait(chopstick[i]);//取左边筷子wait(chopstick[(i+1)%5]);

//取右边筷子┋eat;┋signal(chopstick[i]);signal(chopstick[(i+1)%5]);┋

think;untilfalse;

会死锁否？17

哲学家进餐问题哲学家饥饿时，总是先去拿左边的筷子(wait(chopstick[i]))；成功后，再去拿他右边的筷子(wait(chopstick[(i+1)mod5]))；又成功后便可进餐。进餐完毕，则先放下左边的筷子，然后再放右边的筷子。上述解法可保证不会有两个相邻的哲学家同时进餐，但有可能引起死锁。

18假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。几种解决方法

:死锁的情况19至多允许4个哲学家进餐能保证至少有一位哲学家能够进餐，并在进餐完毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。规定哲学家拿起筷子的次序给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之。1、2号哲学家竞争1号筷子，则3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。202.

用AND信号量解决varchopstick:array[0..4]ofsemaphore:=(1,1,1,1,1);

repeatthink;swait(chopstick[(i+1)%5],chopstick[i]);eat;signal(chopstick[(i+1)%5],chopstick[i]);

untilfalse;在哲学家进餐问题中，每个哲学家先获得2临界资源(筷子)方能进餐，用AND信号量机制可获得最简洁的解法212.5.3

“读者—写者”问题“读者一写者(Reader—WriterProblem)问题”:保证一个Writer进程必须与其他进程互斥地访问共享对象。Example:222.5.3

“读者—写者”解决方案读者一写者的同步要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作1.用记录型信号量解决2.用信号量集机制解决Writer在不能同时231.用记录型信号量解决

读者--写者问题有两种类型：读者优先当写者提出写的要求后，允许新的读者继续进入写者优先当写者提出写的要求后，不允许新的读者进入24读者--写者问题的信号量设置：为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。设置一个整型变量Readcount表示正在读的进程数目，也应该为它设置一个互斥信号量rmutex。当Readcount=0，表示无读者进程在读，读者进程需要执行Wait(Wmutex)操作。若成功，读者进程便可去读，相应地，做Readcount+1操作。仅当读者进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让写者进程写。25用记录型信号量解决

读者reader:

beginrepeatwait(rmutex);if(readcount=0)then

wait(wmutex);readcount=readcount+1;signal(rmutex);┋performreadoption;读操作┋wait(rmutex);readcount=readcount-1;ifreadcount=0thensignal(wmutex);signal(rmutex);

untilfalse;end

semaphorermutex=1,wmutex=1;intReadcount=0;

wmutex:读写互斥rmutex:互斥访问readcountReadcount:读进程数重点掌握！26写者writer:

beginrepeat

wait(wmutex);performwriteoption;写操作

signal(wmutex);┋untilfalse;end272.

用信号量集机制解决引入一个信号量L，并赋予其初值为RN，通过执行wait(L，1，1)操作来控制读者的数目wait(S，d，t)操作来:S为信号量，总资源数量d为需求值，运转所需量t为下线,s>t时方能启动P66282.

用信号量集机制解决与前面的略有不同，增加一个限制，即最多只允许RN个读者同时读。引入一个信号量L，并赋予其初值为RN，通过执行wait(L，1，1)操作来控制读者的数目当有一个读者进入，执行wait(L，1，1)操作，使L的值减1。当有RN个读者进入读后，L便减为0，第RN+1个读者要进入读时，必然会因wait(L，1，1)操作失败而阻塞。L=0时表示不允许读者进入L=RN时表示写者可以进入29varRN:integer;L,mx:semaphore:=RN,1;reader:

beginrepeat

swait(L,1,1);

swait(mx,1,0);┋performreadoption;┋

ssignal(L,1);untilfalse;end

writer:beginrepeat

swait(mx,1,1;L,RN,0);┋performwriteoption;┋

ssignal(mx,1);┋untilfalse;end30Now,theproblemsare:信号量机制

进程必须自备同步操作wait(s)和signal(s)

wait(s)和signal(s)分布在进程中

同步操作使用不当，造成死锁同步操作使用问题

wait(s)和signal(s)颠倒

多个进程同时进入临界区

signal(s)误写成wait(s)

其它不能进入临界区

遗漏

wait(s)

几个进程同时进入临界区

signal(s)

其它进程无法进入临界区烦，晕,谁来帮帮我?31I’m

themonitor，coming!

(管程,

similarto“城管”：谁在掐架？）Comeon!Itcan‘tgowrongeverytime...33

管程机制

1.管程的定义2.

管程的语法描述3.

条件变量解决方法：把对临界资源的同步操作集中起来，由一个进程统一管理

341.“管程”长啥样的？

系统资源抽象数据结构

（软件硬件）（表示信息操作）

电传机：状态(忙、闲)、请求/释放操作、等待队列

FIFO队列：队首、队尾、队长、队列操作

缓冲池：大小、指针(空满)、放入/获取操作351.“管程”长啥样的？一组表征资源的共享数据结构

对共享数据结构操作的一组过程管程

管程被请求和释放资源的进程所调用共同数据一组操作过程初始化代码……进入队列362.7

线程线程的基本概念线程间的同步和通信内核支持线程和用户级线程线程控制20世纪60年代提出进程后，OS中都是以进程作为拥有资源和独立运行的基本单位。80年代中期，提出比进程更小的能独立运行的基本单位----线程(Threads);好处：减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。37Compariedwith进程协同完成一个任务具体工作人员，多人共享相同空间（资源）进程线程381.

线程的引入现代操作系统中，进程只作为资源拥有者，而调度和运行的属性赋予新的实体——线程。引入线程，为减少程序并发执行时所付出的时空开销，使OS具有更好的并发性。进程的两个基本属性:①进程是一个可拥有资源的独立单位；②进程同时又是一个可独立调度和分派的基本单位P7539如何能使多个程序更好地并发执行同时又尽量减少系统的开销?是追求的重要目标。解决方法：搬房子累，搬人！好处:(1)对于作为调度和分派的基本单位，不拥有资源，可“轻装上阵”；(2)对拥有资源的基本单位，又不对其进行频繁的切换。40在这个想法下，诞生了“线程”

先把“房子+人”区分开：将进程的两个属性分开，由操作系统分开处理。41进程线程调度独立调度、分派的基本单位线程为调度分派的基本单位进程为拥有资源的基本单位并发性仅进程间可以并发执行进程和线程都可以并发执行拥有资源拥有资源的独立单位不拥有系统资源，但可以访问其隶属进程的资源系统开销创建或撤消进程时开销较大切换代价高线程创建或撤消时开销很小切换代价低支持多处理机若进程只有一个线程，则只能运行在一个处理机上若进程拥有多个线程，则可分散到多个处理机上运行2.7.2.

线程和进程的比较P76重点掌握！421.轻型实体基本上不拥有系统资源，只有一点必不可少的、能保证独立运行的资源2.独立调度和分派的基本单位线程是能独立运行的基本单位，因而也是独立调度和分派的基本单位。线程很“轻”，线程的切换非常迅速/开销小。3.可并发执行

一个进程中的多个线程间可并发执行；不同进程中的线程也能并发执行。4.共享进程资源

同一进程中的各个线程，可以共享该进程所拥有的资源（有相同的地址空间；访问进程所拥有文件、定时器、信号量机构等）。

线程的特点43用户栈系统栈PCB数据程序单线程进程寄存器PCB数据程序多线程进程用户栈系统栈

TCB寄存器用户栈系统栈

TCB寄存器用户栈系统栈

TCB寄存器线程1线程2线程3进程进程44多线程和进程模型

多线程是指操作系统支持在一个进程中执行多个线程的能力。每个进程中只有一个线程在执行，称作单线程方法（MS-DOS）;WINDOWS2000/XP、SOLARIS、LINUX等支持多线程的多进程。在多线程的环境中，进程被定义成资源分配的实体和保护的实体。45状态参数每个线程都可以用线程标识符和一组状态参数进行描述。①寄存器状态②堆栈③运行状态

④优先级⑤专有存储器⑥信号屏蔽线程运行状态线程间也存在着共享资源和相互合作的制约关系，在运行时也具有间断性。三种基本状态：执行状态、就绪状态、阻塞状态线程的创建和终止应用程序启动时，通常仅有一个线程在执行，该线程被称为“初始化线程”。它可根据需要再去创建若干个线程。2.7.3.

线程的状态和TCB461.线程标识符每个线程有唯一标示符2.一组寄存器保存程序计数器PC。3.线程运行状态三种基本状态4.优先级、线程专用存储区、信号屏蔽、堆栈指针。。。

2.线程控制块TCBP7847在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但进程不再作为一个执行的实体。多线程OS中的进程有以下属性：拥有系统分配的资源单位用户地址空间、进程间和线程间同步和通信的机制、打开的文件和已申请到的I/O设备、地址映射表等。可包括多个线程

可含有多个相对独立的线程，但至少要有一个线程；进程为线程提供资源及运行环境，使线程可并发执行。

进程不是一个可执行的实体

进程仍有与执行相关的状态。进程“执行”状态实际上是指该进程中的某线程正在执行。进程挂起时，该进程中的所有线程也都将被挂起；进程激活时，属于该进程的所有线程也都将被激活。3．多线程OS中的进程48线程的实现多线程若想有条不紊地运行，系统必提供用于实现线程同步和通信的机制。为支持不同频率的交互操作、不同程度的并行性，常需提供多种同步机制，如互斥锁、条件变量、信号量以及多读、单写锁等1．互斥锁(mutex)2．条件变量3．信号量机制（私用信号量、公用信号量）491．互斥锁(mutex)

互斥锁是一种用于实现线程间对资源互斥访问的机制。操作互斥锁时空开销低，因而较适合于高频度使用的关键共享数据和程序段。互斥锁可以有两种状态，即开锁(unlock)和关锁(lock)状态。相应地，可用两条命令(函数)对互斥锁进行操作。其中的关锁lock操作用于将mutex关上，开锁操作unlock则用于打开mutex。50

内核支持线程和用户级线程线程在各系统的实现方式不完全相同。一些数据库管理系统（如infomix），实现的是用户级线程如Macintosh、Windows和0S/2操作系统实现的是内核支持线程；Solaris操作系统（UNIX操作系统的衍生版本之一）同时实现了这两种类型的线程。KernelSupportedThreadsUserLeverThreadsP79重点掌握！51内核支持线程和用户级线程Simlarto:国家统一分配。“政府给钱；快，多生孩子！孩子越多，咱家钱的总数越多。”Similarto:已分发到单位（进程），再由单位分配给个人（线程）。“咱家就那么点有限的钱，多生娃，难养活”线程越多，速度越快线程越多，速度不变52依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数:内核维护进程和线程的上下文信息；线程切换由内核完成；一个线程阻塞，不会影响其他线程的运行。时间片分配给线程，所以多线程的进程获得更多CPU时间。1.

内核支持线程(KernelSupportedThreads)53KST线程实现的4优点:在多处理器系统中，内核能够同时调度