第2章分布式操作系统

第二章.进程管理及并发控制和同步第1节进程的定义和特征第2节进程的状态和进程控制块第3节进程控制第4节进程的同步与互斥第5节并发执行的描述方式第6节基于共享变量的同步操作原理第7节基于消息传递的同步操作原语第8节进程调度进程的定义和特征§1.进程的定义§2.进程的特征§3.进程的结构进程的定义进程（process）或任务（task）这一术语是在六十年代初期，首先在麻省理工学院（MIT）的MULTICS系统和IBM公司的CTSS/360系统中引入的，其后有许多人对进程下过各式各样的定义，下面列举几种比较能反映进程实质的定义：进程的定义⑴进程是程序的一次执行，亦即进程是在指定的内存区域中的一组指令序列的执行过程。⑵进程（或任务task）是可以和别的计算并发（concurrent）执行的计算。⑶进程可以定义为一个数据结构和能在其上进行操作的一个程序。⑷进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位⑸进程（process）是一个具有独立功能的程序关于相关的数据集在处理机上的执行过程。进程的特征进程具有顺序性动态性并发性独立性和异步性等特征。进程的最基本的特征是并发性。顺序性一个进程的顺序性是指每个进程在顺序处理机上的执行是严格按次序进行的，即只有当其中的一个操作结束后，才能开始其后续操作.动态性进程的动态性是指它是程序的一次执行过程，表现为它是由“创建（create）”而产生，由调度程序“调度”而运行，因“等待事件”而阻塞，最后，由“撤消（destroy）”而消亡。可见，进程是有一定生命期的，是动态地产生，运行和消亡的。并发性进程的并发性是指多个进程可以同时在一个系统中并发地执行。独立性进程的独立性是指它可以作为系统进行资源分配和调度的独立单位异步性进程的异步性是指系统中的活动的进程总是按照各自独立的、不可预测的速度运行。进程的结构为了描述进程的运动变化过程并使之能独立地运行，应该为每个进程配置一个进程控制块（processcontrolblock简记为PCB）。进程的结构三部分所组成：一个程序段相应的数据段一个进程控制块在UNIX系统中，把这三部分统称为进程映像（image）。而将进程定义为“进程映像的执行。进程的状态⑴就绪状态（Ready）⑵运行状态（Running）⑶阻塞状态（Blocked）进程的状态进程的状态(UNIX)进程控制块⑴进程标识符（Identification）⑵进程的当前状态（Status）⑶处理机状态保护区⑷进程的起始地址⑸资源清单⑹进程优先数⑺队列指针(pointer)或链接字(link)⑻进程族的联系⑼计账信息为了对于进程进行控制，操作系统内必须设置一个机构，它具有上述进程控制及进程通讯和资源管理等功能。这样的机构称为操作系统的内核（Kernel）原语所谓原语（Primitive）是机器指令的延伸，它由若干条指令组成，用以完成特定功能的一段程序。为了保证原语操作的正确性，原语在执行期间是原子的，亦即原语在执行期间是不可分割的。原语⑴创建原语（CreatePrimitive）⑵悬挂原语（SuspendPrimitive）⑶激活原语（ActivatePrimitive）⑷阻塞原语（BlockPrimitive）⑸唤醒原语（WakeupPrimitive）⑹撤消原语（DestroyPrimitive）对进程之间共享资源的控制必须满足下列要求：安全性（safety）活动性（liveness）公正性（fairness）安全性（safety）在任意一个给定时刻只允许至多一个进程使用一个共享资源，不允许两个及两个以上进程同时使用同样的共享资源。否则，进程对共享资源操作的结果往往是破坏性的。活动性（liveness）活动性表现为两个方面，一方面任意一个进程在使用共享资源时，必须在有限时间内释放，不能无限期地占用而导致其它进程永远无法使用；另一方面当某个进程欲使用共享资源时，则应在有限时间内达到目的，而不应该互相阻止导致彼此永远都不能使用。公正性（fairness）对进程使用共享资源的次序不作不公正的规定。当某个进程欲使用共享资源时，只要其它进程不在使用该共享资源，就应该允许该进程使用。并且任意一个要求使用共享资源的进程不能无限期地等待，总应该在某个公正的时间界限内获得该资源。第4节进程的同步与互斥进程之间常常相互作用，并存在某种彼此依赖或互相制约的关系这些关系按其性质可分为同步（synchronization）和互斥（mutualexclusion）关系。进程的同步一进程运行到某点时，要求另一伙伴进程它提供信息，在未得到这一信息时，该进程等待，直至收到这一信息后，才能继续执行。它们彼此都清楚对方的存在及作用，而且每一进程还可能直接依赖于本组进程中其它成员所产生（或所提供）的数据。这是进程间的一种直接交互关系，表现了进程间协同工作的特性，因此称为进程间的同步关系。临界资源并发进程可以共享系统中的各种资源，但系统中的有些资源具有一次仅允许一个进程所使用的属性。我们称这类资源为临界资源（criticalresources）。进程的互斥若一进程在使用临界资源时，则其它欲占用者必须等待，仅当使用者释放后，等待的进程才可使用它。这就导致了若干进程因竞争临界资源而不得互斥地执行的情况。进程间的这种现象就称为进程的互斥。临界区在操作系统中把访问临界资源的那段程序称为临界段或临界区（criticalsection）。临界段问题实质上是一个互斥问题。临界段应遵循下面的原则：⑴当有多个进程都希望进入它们的临界段时，它们不应相互封锁，而应在有限时间内让其中之一进入临界段。⑵每次至多只有一个进程进入临界段中。⑶当某一进程已进入临界段，其它试图进入该临界段的进程必须等待。⑷位于临界段中的进程只能在其中逗留有限的时间一旦它离开临界段，则应允许某个等待进入临界段的进程进入其中。同步机制进程的同步是通过同步机制实现的。同步机制主要有两个作用：第一，它能够推迟一个进程的执行直至给定的条件成立。第二，它可用来保证一个语句序列是一个不可分割的操作。§1.忙等待〔busywaiting）为了唤醒一个条件，进程给一个共享变量置值，为了等待那个条件，进程反复地测试那个共享变量直至获得所需要的值。由于等待条件的进程必须反复地测试那个共享变量，因此称采用这种方式阻塞进程执行的技术为忙等待。计算机硬件配置指令⑴测试与设置(TestandSet简记为TS)functionTest-and-Set(vartarget:boolean):boolean;Test-and-Set:=target;target:=TRUE;end;利用测试与设置的同步lock(mutex)：while(TS(mutex));unlock(mutex)：mutex:=FALSE;计算机硬件配置指令⑵对换（Swap）指令该对换指令对换内存两个单元的内容。procedureSwap(vara,b:boolean);vartemp:boolean;begintemp:=a;a:=b;b:=tempend;利用对换指令的同步lock(mutex):key:=TRUE;repeatSwap(mutex,key)untilkey=FALSE;unlock(mutex):mutex:=FALSE;Dekker的软件解（1968）intturn;booleanflag[2];process(i)inti;{while(TRUE){compute;flag[i]:=TRUE;while(flag[(i+1)mod2]){if(turn=i)continue;flag[i]:=FALSE;Dekker的软件解while(turn≠i);gototry;};critical_section;turn:=(turn+1)mod2;flag[i]:=FALSE;};};turn:=0;flag[0]:=FALSE;flag[1]:=FALSE;Process(0)ANDprocess(1);Peterson的软件解[198l]#includeprototypes.h#defineFALSE0#defineTRUE1#defineN2/*numberofprocess*/intturn;/*whoseturnisit*/intinterested[N];/*allvaluesinitially0(FALSE)*/voldenter-region(intprocess)/*process:whoisentering(0or1)*/{intother;/**/other=1-process;interested[process]=TRUE;turn=process;while(turn==process&&interested[other]==TRUE);/*nullstatement*/}voidleave-region(intprocess)/*process:whoisleaving(0or1)*/{interested[process]=FALSE;/*indicatedeparturefromcriticalregion*/}intturn;booleanflag[2];process(i)inti;{while(TRUE){compute;flag[i]:=TRUE;while((flag[i+1mod2])∧(turn=i+1mod2));critical_section;turn:=(turn+1)mod2;flag[i]:=FALSE;};};turn:=0;flag[0]:=FALSE;flag[1]:=FALSE;Process(0)ANDprocess(1);§2.信号量及其P、V操作信号量（semaphore）[Dijkstra，1963]是一个整型变量，与其相关的两个操作是P、V操作。它是最早提出的同步操作原话，P、V操作的名称源于荷兰字Prolagen（试图降低）和Verhogen（升起)。信号量及其P、V操作定义2.1一个信号量s是一个非负整型变量，它仅仅可以由下列的两个不可分的（即原子的）访问例程之一来测试和修改：P(s)和V(s)操作P(s):whiles≤0do;s:=s-1;V(s):s:=s+1主要缺点是忙等待P(s)操作typesemaphore=recordvalue:integer;L:listofprocess;end;信号量的value初值表示系统中某类资源的数目。因此，这类信号量又称资源信号量。P(s)操作P(semaphoreS){S.value＝S.value－l;IfS.value0then阻塞该进程，并把它置入S.L等待队列中；操作系统重新调度;else该进程继续执行;}V(s)操作V(semaphoreS){S.value=S.value＋l;IfS.value≤0then从S.L等待队列中取出一进程;将其状态改为“就绪”，并且放入就绪队列;else该进程继续执行;}互斥问题为了解决互斥问题，每个临界段前后分别放一个P、V操作，它们都操作在同一信号量上，所有互斥的临界段利用相同的信号量，且该信号量的初值为1。programmutex-example;varmutex:semaphoreinitial(1);processP1;1oopP(mutex);临界段;V(mutex);非临界段;endend;end.processP2;1oopP(mutex);临界段;V(mutex);非临界段;endend;programsynch-example;vars1,s2:semaphoreinitial(0,0);processP1;1oopsend(message);V(s1);P(s2);……;end;……;end;end.processP2;1oopP(s1);receive(message);V(s2);……;end;……;end;有界缓