《操作系统》第2章 进程管理2.ppt

操作系统原理Principles of Operating System 12.4 进程的同步机构2.4.1 进程与资源n n资源是计算机系统的基本结构元素。资源是计算机系统的基本结构元素。n n资源可以分为软件资源和硬件资源，程序和数据资源可以分为软件资源和硬件资源，程序和数据属于软件资源；属于软件资源；CPU、内存、外设则属于硬件资内存、外设则属于硬件资源。源。n n在操作系统中一般把资源分为临界资源和共享资在操作系统中一般把资源分为临界资源和共享资源，源，n n所谓的临界资源是指在一段时间内仅允许一个进所谓的临界资源是指在一段时间内仅允许一个进程使用资源。如打印机、输入机、磁带机、信号程使用资源。如打印机、输入机、磁带机、信号量和指针等，临界资源可以互斥共享；量和指针等，临界资源可以互斥共享；n n所谓的共享资源是指允许多个进程同时访问的资所谓的共享资源是指允许多个进程同时访问的资源。如处理机、内存和硬盘等。源。如处理机、内存和硬盘等。2进程制约关系n n间接相互制约。这种制约主要源于资源共享，间接相互制约。这种制约主要源于资源共享，这是不相关的进程由于共享同一资源而引起的，这是不相关的进程由于共享同一资源而引起的，即共享某类资源的进程之间由操作系统协调与控即共享某类资源的进程之间由操作系统协调与控制使用该资源的次序而产生相互制约。这种制约制使用该资源的次序而产生相互制约。这种制约是进程是进程资源资源进程之间存在的约束，故称为间进程之间存在的约束，故称为间接制约。例如，有两个进程接制约。例如，有两个进程A和和B，如果在进程如果在进程A提出打印请求时，系统已将打印机分配给进程提出打印请求时，系统已将打印机分配给进程B，此时进程此时进程A阻塞。当进程阻塞。当进程B将打印机释放，进将打印机释放，进程程A被唤醒，获得打印机，由阻塞状态转为就绪被唤醒，获得打印机，由阻塞状态转为就绪状态。状态。3n n直接相互制约。这是相关进程之间为完成同一任务，进程某些操作之间在次序上存在制约关系。如果协作进程的某个操作没有完成，那么进程就会在工作到某些点上等待这个动作的完成，之后才能继续执行下去。我们称这些并发执行的进程间存在着制约关系。这种制约是进程进程之间因共同目的而存在的直接约束，故称为直接制约。例如，输入进程A通过单缓冲向计算进程B提供数据。当缓冲区空时，计算进程B因不能获得所需数据而阻塞，当进程A把数据送入缓冲时，便唤醒进程B；反之，当缓冲区满时，进程A因不能再向缓冲中投放数据而阻塞，当进程B将缓冲内数据取走时，便唤醒进程A。4进程与资源的关系n n从这样一个简单系统的管理中我们得出一个结论：操作系统的任务是控制与管理进程和资源，必须提供一些机制来协调进程与进程之间、进程与资源之间的复杂关系。54.临界区设计原则n n我们对每个进程访问临界资源的那段程序从概念我们对每个进程访问临界资源的那段程序从概念上分离出来，称之为临界区。上分离出来，称之为临界区。n n临界区设计原则如下：临界区设计原则如下：n n进入区进入区(entry section)。申请临界资源，为申请临界资源，为了进入临界区使用临界资源，在进入区要检查可了进入临界区使用临界资源，在进入区要检查可否进入临界区，如果可以进入临界区，通常设置否进入临界区，如果可以进入临界区，通常设置相应的相应的“正在访问临界区正在访问临界区”标志，以阻止其他进标志，以阻止其他进程同时进入临界区。程同时进入临界区。n n访问区访问区(critical section)。进程中访问临界进程中访问临界资源的一段代码。资源的一段代码。n n退出区（退出区（exit section）。）。将将“正在访问临界正在访问临界区区”的标志清除，释放临界资源。的标志清除，释放临界资源。62.4.2 进程同步机构进程同步与互斥的概念n n在系统中有一些需要相互合作、协同工作的进程，这些进程的某些操作存在某种次序上的制约关系，这种制约关系称为进程的同步。n n多个相关进程在访问临界资源在操作时间上相互排斥。这种相互排斥关系叫做进程的互斥。n n各个进程互斥使用临界资源，互斥的实质是互斥共享临界资源，也可以认为互斥是同步的一种特殊形式。72.同步机构应遵循的准则 n n空闲让进n n忙则等待n n有限等待n n让权等待8上锁原语与开锁原语n n实现的方法：设置锁变量实现的方法：设置锁变量w w，w=1w=1表示上锁，表示上锁，w=0w=0表示开锁。表示开锁。n n上锁原语上锁原语n nvoid lock(w)void lock(w)n nwhile(w=1)no-operate;while(w=1)no-operate;n nw=1;w=1;n n n n开锁原语开锁原语n nvoid unlock(w)void unlock(w)n nw=0;w=0;n n n n请读者思考上锁原语与开锁原语是否符合同步机请读者思考上锁原语与开锁原语是否符合同步机构应遵循的准则？构应遵循的准则？9信号量与P、V操作n n信号量的值仅能由信号量的值仅能由信号量的值仅能由信号量的值仅能由P P操作、操作、操作、操作、V V操作改变的结构体变量。操作改变的结构体变量。操作改变的结构体变量。操作改变的结构体变量。信号量的值大于等于零时信号量的值大于等于零时信号量的值大于等于零时信号量的值大于等于零时代表一类可用资源个数，代表一类可用资源个数，代表一类可用资源个数，代表一类可用资源个数，其值小于零时其绝对值代其值小于零时其绝对值代其值小于零时其绝对值代其值小于零时其绝对值代表被阻塞进程的个数。表被阻塞进程的个数。表被阻塞进程的个数。表被阻塞进程的个数。n n信号量的描述如下：信号量的描述如下：信号量的描述如下：信号量的描述如下：n nstructstruct semaphore semaphoren n intint value;value;n nqueue *queue *WQrWQr;n n;10n nwaitwait操作描述和定义如下：操作描述和定义如下：操作描述和定义如下：操作描述和定义如下：n nsemaphore s semaphore s n nvoid wait(s)void wait(s)n n s.value-;s.value-;n nif (s.value0)if (s.value0)block(sblock(s.WQr);/*.WQr);/*阻塞该进程阻塞该进程阻塞该进程阻塞该进程*/n n n nV V操作描述和定义如下：操作描述和定义如下：操作描述和定义如下：操作描述和定义如下：n nsemaphore ssemaphore sn nvoid signal(s)void signal(s)n n s.value+;s.value+;n nif (s.value=0)if (s.value=0)wakeup(swakeup(s.WQr);/*.WQr);/*唤醒阻塞唤醒阻塞唤醒阻塞唤醒阻塞队列的对首进程队列的对首进程队列的对首进程队列的对首进程*/n n 112.5 经典进程同步问题2.5.1进程互斥n n利用利用利用利用waitwait操作、操作、操作、操作、signalsignal操作设计出三个进程共享一台打印操作设计出三个进程共享一台打印操作设计出三个进程共享一台打印操作设计出三个进程共享一台打印机的并发程序描述如下机的并发程序描述如下机的并发程序描述如下机的并发程序描述如下:n nsemaphore semaphore mutexmutex=1;=1;n nvoid main()void main()n nparbegin(P1()parbegin(P1()，P2()P2()，P3();P3();n n n nvoid Pi()/*i=1void Pi()/*i=1，2 2，3*/3*/；n n n nn nwait(mutexwait(mutex););n n使用打印机使用打印机使用打印机使用打印机;n nsignal(mutexsignal(mutex););n nn n 122.5.2生产者与消费者问题n n设置信号量和变量如下：full：满缓冲区资源信号量，初值为0；empty：空缓冲区资源信号量，初值为n；in：生产者指针，初值均为0；out：消费者指针，初值均为0；mutex：缓冲区操作的互斥信号量，初值为1；13生产者与消费者问题描述如下：n nsemaphore empty=n;n nsemaphore full=0;n nsemaphore mutex=1;n nmessage buffern;n nint in=0;n nint out=0;n nvoid main()n nparbegin(proceducer()，consumer();n n14n nvoid proceducer()n ndo n n produce a new message;n n wait(empty);n n wait(mutex);n n send a new message to bufferin;n n in=(in+1)%n;n n signal(mutex);n n signal(full);n n while(true);n n15n nvoid consumer()n ndon n wait(full);n n wait(mutex);n n get a message from bufferout;n n out=(out+1)%n;n n signal(mutex);n n signal(empty);n n consume a message;n n while(true);n n162.5.3哲学家进餐的问题n n分析分析:每个哲学家的行为是：每个哲学家的行为是：思考，感到饥饿，拿到两只筷思考，感到饥饿，拿到两只筷子，进餐，餐毕，放下两只筷子，进餐，餐毕，放下两只筷子又继续思考。为了进餐，每子又继续思考。为了进餐，每个哲学家必须拿到两只筷子，个哲学家必须拿到两只筷子，并且每个人只能直接从自己的并且每个人只能直接从自己的左边或右边去取筷子。但他可左边或右边去取筷子。但他可能一支都拿不到。只有在他拿能一支都拿不到。只有在他拿到两支筷子时方能进餐。到两支筷子时方能进餐。n n设置信号量如下：哲学家进餐设置信号量如下：哲学家进餐信号量信号量smsm，初值为初值为4 4；筷子信；筷子信号量号量chopstickichopsticki，初值为初值为1 1；哲学家进餐问题描述如下哲学家进餐问题描述如下:17n nsemaphore semaphore smsm=4=4；n nsemaphore chopstick5=1semaphore chopstick5=1，1 1，1 1，1 1，1;1;n nvoid main()void main()n nparbegin(philosopher0()parbegin(philosopher0()，philosopher1()philosopher1()，philosopher2()philosopher2()，philosopher3philosopher3()()，philosopher4();philosopher4();n n n nvoid void philosopheriphilosopheri();/*i=0();/*i=0，1 1，2 2，3 3，4*/4*/n nwhile(true)while(true)n n Thinking;Thinking;n n wait(smwait(sm););n n wait(chopsticki);wait(chopsticki);n n wait(chopstick(i+1)%5);wait(chopstick(i+1)%5);n n Eating;Eating;n n signal(chopstick(i+1)%5);signal(chopstick(i+1)%5);n n signal(chopsticki);signal(chopsticki);n n signal(smsignal(sm););n n n n 18n n哲学家进餐的问题主要研究如果解决死锁与饥饿。在多进程并发系统中，多个进程共享资源的程度可以分成以下三个层次：互斥、死锁和饥饿。互斥互斥是指多个相关进程中只允许一个进程访问临界资源，这是正确使用资源的最基本要求；某进程申请的资源被其他等待进程占有，如果该等待进程永远无法改变其阻塞状态，这种情况我们称为死锁死锁；如果该等待进程长期无法改变其阻塞状态，这种情况我们称为饥饿。饥饿。192.6 进程通信n n我们可把进程间通信分成低级通信和高级通信：n n低级通信。进程间只能传递状态和整数值(控制信息)，包括进程互斥和同步所采用的信号量机制。它的优点是速度快，缺点是传送信息量小，通信效率低，编程复杂。由于每次通信传递的信息量固定，因此若传递信息较多则需要进行多次通信。用户直接实现通信的细节，编程复杂，容易出错。n n高级通信。进程间可传送大量的数据，通信效率高，减轻编程的复杂度。包括共享存储器通信、管道通信和消息传递通信等通信机制。20进程通信分为直接通信和间接通信：n n直接通信。是指发送方把信息直接传递直接通信。是指发送方把信息直接传递给接收方。给接收方。n n间接通信。是指通信过程要借助收发双间接通信。是指通信过程要借助收发双方进程之外的共享数据结构作为通信中转，方进程之外的共享数据结构作为通信中转，如信箱。如信箱。n n进程的高级通信有三种方式：进程的高级通信有三种方式：n n共享存储器通信方式。共享存储器通信方式。n n共享文件通信方式。共享文件通信方式。n n消息传递通信方式。消息传递通信方式。212.6.2共享存储器通信方式n n基于共享存储区通信方式n n基于共享数据结构的通信方式222.6.3共享文件通信方式n n管道通信方式就是利用共享文件实现进程间的通信。这种通信方式也叫管道通信。如图所示，所谓管道，是指用于连接一个读进程和一个写进程的文件，称pipe文件。向管道输入数据的进程称为写进程，而接受管道数据的进程称为读进程。该方式首创于UNIX，它能传送大量数据，被广泛采用。232.6.4消息传递通信方式n n消息传递通信方式不仅适合计算机内部通信，也支持计算机网络通信，消息传递通信方式得到广泛应用。消息传递通信一般分为消息缓冲通信、信箱通信和基于消息传递通信等三种。n n消息缓冲通信的实现n n发送原语和接收原语一般应用格式如下：n nsend(receiver，message)；n nreceive(sender，message)或receive(message)；2425信箱通信的实现n n信箱通信方式中也使用原语操作，如发送原语与接收原语等。此外，许多时候都存在着多个发送进程和多个接收进程共享信箱的情况。信箱发送原语和接收原语一般应用格式如下：n nsend(mailbox，message)；n nreceive(mailbox，message)；262.7基于消息传递的网络通信n n消息队列中间件是一种特定的中间件，它利用高效可靠的消息传递机制进行与平台无关的数据交换，并基于数据通信来进行分布式系统的集成。消息中间件可以跨平台操作。n n采用消息队列技术带来的好处是：由于是异步通信，无论是发送方还是接收方都不用等待对方返回成功消息，就可以执行余下的代码，因而大大地提高了事物处理的能力；当信息传送过程中，信息发送机制具有一定功能的故障恢复能力；消息传递机制使得消息通信的双方具有不同的物理平台成为可能。272.7.1基于消息传递的通信n n基于消息传递的通信方式，不仅适合计算机内部通信，也支持计算机网络通信，消息传递通信方式在现代操作系统中得到了广泛的应用。如图所示，在Internet上客户机/服务器的关系并不是一成不变的。当提供服务时，该节点是服务器。当从其他节点获得服务时，该节点就是客户机。28n n具体通信原语一般应用格式如下：n n客户端：send(server-socket，&m1)n n receive(client-port，&m2)n n服务器端：receive(server-port，&m1)n n send(m1.source，&m2)n n其中：n n&m1、&m2为消息的发送区和接受区的地址；n nserver-socket：服务器的套接字；n nserver-port:服务器的端口；n nclient-port：客户的的端口；n nm1.source客户请求包的源地址。292.7.2 端口n n端口（端口（端口（端口（portport）就是运输层服务访问点就是运输层服务访问点就是运输层服务访问点就是运输层服务访问点TSAPTSAP。从这个意从这个意从这个意从这个意义上讲，端口是用来标识应用层的进程。当客户机进程义上讲，端口是用来标识应用层的进程。当客户机进程义上讲，端口是用来标识应用层的进程。当客户机进程义上讲，端口是用来标识应用层的进程。当客户机进程发出连接请求时，它被主机赋予一个端口。发出连接请求时，它被主机赋予一个端口。发出连接请求时，它被主机赋予一个端口。发出连接请求时，它被主机赋予一个端口。n n在运输层与应用层的接口上所设置端口是一个在运输层与应用层的接口上所设置端口是一个在运输层与应用层的接口上所设置端口是一个在运输层与应用层的接口上所设置端口是一个1616bitbit的的的的地址，并用端口号进行标识。端口就是一个抽象的定位地址，并用端口号进行标识。端口就是一个抽象的定位地址，并用端口号进行标识。端口就是一个抽象的定位地址，并用端口号进行标识。端口就是一个抽象的定位符，可以理解为一种邮箱。端口就是源进程将消息发送符，可以理解为一种邮箱。端口就是源进程将消息发送符，可以理解为一种邮箱。端口就是源进程将消息发送符，可以理解为一种邮箱。端口就是源进程将消息发送给运输层的某个端口，目的进程从端口接收消息。端口给运输层的某个端口，目的进程从端口接收消息。端口给运输层的某个端口，目的进程从端口接收消息。端口给运输层的某个端口，目的进程从端口接收消息。端口只是为了标识本计算机应用层中的各进程，不同计算机只是为了标识本计算机应用层中的各进程，不同计算机只是为了标识本计算机应用层中的各进程，不同计算机只是为了标识本计算机应用层中的各进程，不同计算机中的相同端口号是没有联系的，端口只具有本地意义。中的相同端口号是没有联系的，端口只具有本地意义。中的相同端口号是没有联系的，端口只具有本地意义。中的相同端口号是没有联系的，端口只具有本地意义。1616bitbit的端口可允许有的端口可允许有的端口可允许有的端口可允许有6464K K个端口，这个数目对一个计个端口，这个数目对一个计个端口，这个数目对一个计个端口，这个数目对一个计算机来说是足够用的。算机来说是足够用的。算机来说是足够用的。算机来说是足够用的。n n端口可分为两类。一类是熟知端口，其数值一般为端口可分为两类。一类是熟知端口，其数值一般为端口可分为两类。一类是熟知端口，其数值一般为端口可分为两类。一类是熟知端口，其数值一般为0102301023。n n另一类则是一般端口，用来随时分配给请求通信的客户另一类则是一般端口，用来随时分配给请求通信的客户另一类则是一般端口，用来随时分配给请求通信的客户另一类则是一般端口，用来随时分配给请求通信的客户进程。该端口是大于进程。该端口是大于进程。该端口是大于进程。该端口是大于10241024的某个任意数。的某个任意数。的某个任意数。的某个任意数。302.7.3套接字n n套接字套接字(socket)socket)可定义为通信的端点。一对通过网络通可定义为通信的端点。一对通过网络通信的进程需要使用一对套接字。套接字由信的进程需要使用一对套接字。套接字由IPIP地址和端口地址和端口号连接组成。号连接组成。n n主机主机A A某进程某进程1 1可能被赋予端口可能被赋予端口15001500。该连接有一对套。该连接有一对套接字组成：主机接字组成：主机A A上的套接字上的套接字(131.6.23.13:1500)(131.6.23.13:1500)，网，网络服务器上的套接字络服务器上的套接字(161.25.19.8:80)(161.25.19.8:80)；n n同样主机同样主机A A某进程某进程2 2可能被赋予端口可能被赋予端口15011501。该连接有一。该连接有一对套接字组成：主机对套接字组成：主机A A上的套接字上的套接字(131.6.23.13:1501)(131.6.23.13:1501)，网络服务器上的套接字，网络服务器上的套接字(161.25.19.8:80)(161.25.19.8:80)。根据目的。根据目的端口号，在主机间传输的数据包可分送给合适的进程。端口号，在主机间传输的数据包可分送给合适的进程。31