《第2章分布式操作系统课件》由会员分享，可在线阅读，更多相关《第2章分布式操作系统课件（175页珍藏版）》请在金锄头文库上搜索。
1、第二章. 进程管理及并发控制和同步,第1节 进程的定义和特征 第2节 进程的状态和进程控制块 第3节 进程控制 第4节 进程的同步与互斥 第5节 并发执行的描述方式 第6节 基于共享变量的同步操作原理 第7节 基于消息传递的同步操作原语 第8节 进程调度,进程的定义和特征,1. 进程的定义 2. 进程的特征 3. 进程的结构,进程的定义,进程（process）或任务（task）这 一术语是在六十年代初期，首先在 麻省理工学院（MIT）的MULTICS 系统和IBM公司的CTSS/360系统中 引入的，其后有许多人对进程下过 各式各样的定义，下面列举几种比 较能反映进程实质的定义：,进程的定义,
2、进程是程序的一次执行，亦即进程是在指定的内存区域中的一组指令序列的执行过程。 进程（或任务task）是可以和别的计算并发（concurrent）执行的计算。 进程可以定义为一个数据结构和能在其上进行操作的一个程序。 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位 进程（process）是一个具有独立功能的程序关于相关的数据集在处理机上的执行过程。,进程的特征,进程具有 顺序性 动态性 并发性 独立性和 异步性等特征。 进程的最基本的特征是并发性。,顺序性,一个进程的顺序性是指每个进程 在顺序处理机上的执行是严格按 次序进行的，即只有当其中的一 个操作结束后，才能
3、开始其后续 操作.,动态性,进程的动态性是指它是程序的一 次执行过程，表现为它是由“创 建（ create）”而产生，由调度 程序“调度”而运行，因“等待 事件”而阻塞，最后，由“撤消 （destroy）”而消亡。可见，进 程是有一定生命期的，是动态地 产生，运行和消亡的。,并发性,进程的并发性是指多个进程 可以同时在一个系统中并发 地执行。,独立性,进程的独立性是指它可以作为系 统进行资源分配和调度的独立单 位,异步性,进程的异步性是指系统中的 活动的进程总是按照各自独 立的、不可预测的速度运行。,进程的结构,为了描述进程的运动变化过程 并使之能独立地运行，应该为 每个进程配置一个进程控制块
4、 （process control block简记为 PCB）。,进程的结构,三部分所组成： 一个程序段 相应的数据段 一个进程控制块 在UNIX系统中，把这三部分统 称为进程映像（image）。而将 进程定义为“进程映像的执行。,进程的状态,就绪状态（Ready） 运行状态（Running） 阻塞状态（Blocked）,进程的状态,进程的状态(UNIX),进程控制块,进程标识符（Identification） 进程的当前状态（Status） 处理机状态保护区 进程的起始地址 资源清单 进程优先数 队列指针(pointer)或链接字(link) 进程族的联系 计账信息,为了对于进程进行控制，操
5、作系 统内必须设置一个机构，它具有 上述进程控制及进程通讯和资源 管理等功能。这样的机构称为操 作系统的内核（Kernel）,原语,所谓原语（Primitive）是机器指 令的延伸，它由若干条指令组成， 用以完成特定功能的一段程序。 为了保证原语操作的正确性，原 语在执行期间是原子的，亦即原 语在执行期间是不可分割的。,原语,创建原语（Create Primitive） 悬挂原语（Suspend Primitive） 激活原语（Activate Primitive） 阻塞原语（Block Primitive） 唤醒原语（Wakeup Primitive） 撤消原语（Destroy Primit
6、ive）,对进程之间共享资源的控制必须满足下列要求：,安全性（safety） 活动性（liveness） 公正性（fairness）,安全性（safety）,在任意一个给定时刻只允许至多 一个进程使用一个共享资源，不 允许两个及两个以上进程同时使 用同样的共享资源。否则，进程 对共享资源操作的结果往往是破 坏性的。,活动性（liveness）,活动性表现为两个方面， 一方面任意一个进程在使用共享资源时， 必须在有限时间内释放，不能无限期地 占用而导致其它进程永远无法使用； 另一方面当某个进程欲使用共享资源时， 则应在有限时间内达到目的，而不应该 互相阻止导致彼此永远都不能使用。,公正性（fai
7、rness）,对进程使用共享资源的次序不作不公正的规定。当某个进程欲使用共享资源时，只要其它进程不在使用该共享资源，就应该允许该进程使用。并且任意一个要求使用共享资源的进程不能无限期地等待，总应该在某个公正的时间界限内获得该资源。,第4节 进程的同步与互斥,进程之间常常相互作用，并存在 某种彼此依赖或互相制约的关系 这些关系按其性质可分为 同步（synchronization）和 互斥（mutual exclusion）关系。,进程的同步,一进程运行到某点时，要求另一伙伴进程 它提供信息，在未得到这一信息时，该 进程等待，直至收到这一信息后，才能继 续执行。它们彼此都清楚对方的存在及作 用，而
8、且每一进程还可能直接依赖于本组 进程中其它成员所产生（或所提供）的数 据。这是进程间的一种直接交互关系，表 现了进程间协同工作的特性，因此称为进 程间的同步关系。,临界资源,并发进程可以共享系统中的各种资源，但系统中的有些资源具有一次仅允许一个进程所使用的属性。我们称这类资源为临界资源（critical resources）。,进程的互斥,若一进程在使用临界资源时，则其它欲占用者必须等待，仅当使用者释放后，等待的进程才可使用它。这就导致了若干进程因竞争临界资源而不得互斥地执行的情况。进程间的这种现象就称为进程的互斥。,临界区,在操作系统中把访问临界资源的那段程序称为临界段或临界区（critic
9、al section）。 临界段问题实质上是一个互斥问题。,临界段应遵循下面的原则：,当有多个进程都希望进入它们的临界段时，它们不应相互封锁，而应在有限时间内让其中之一进入临界段。 每次至多只有一个进程进入临界段中。 当某一进程已进入临界段，其它试图进入该临界段的进程必须等待。 位于临界段中的进程只能在其中逗留有限的时间一旦它离开临界段，则应允许某个等待进入临界段的进程进入其中。,同步机制,进程的同步是通过同步机制实现 的。同步机制主要有两个作用： 第一，它能够推迟一个进程的执行直至给定的条件成立。 第二，它可用来保证一个语句序列是一个不可分割的操作。,1. 忙等待busy waiting）,
10、为了唤醒一个条件，进程给一个共 享变量置值，为了等待那个条件， 进程反复地测试那个共享变量直至 获得所需要的值。由于等待条件的 进程必须反复地测试那个共享变量， 因此称采用这种方式阻塞进程执行 的技术为忙等待。,计算机硬件配置指令,测试与设置(Test and Set 简记为TS) function Test-and-Set(var target : boolean) : boolean; Test-and-Set := target; target := TRUE; end;,利用测试与设置的同步,lock(mutex)： while (TS(mutex) ; unlock(mutex)：
11、mutex := FALSE;,计算机硬件配置指令,对换（Swap）指令 该对换指令对换内存两个单元的内容。 procedure Swap(var a, b : boolean); var temp : boolean; begin temp := a; a := b; b := temp end;,利用对换指令的同步,lock(mutex): key := TRUE; repeat Swap(mutex, key) until key = FALSE; unlock(mutex): mutex := FALSE;,Dekker的软件解（1968）,intturn; booleanflag2;
12、 process(i) int i; while (TRUE) compute; flagi := TRUE; while (flag(i+1) mod 2) if (turn = i) continue; flagi := FALSE;,Dekker的软件解,while (turn i) ; goto try; ; critical_section; turn := (turn+1) mod 2; flagi := FALSE; ; ; turn := 0; flag0 := FALSE; flag1 := FALSE; Process(0) AND process(1);,Peterson
13、的软件解 198l,#include prototypes.h #define FALSE0 #define TRUE1 #defineN2/* number of process */ intturn;/* whose turn is it */ intinterestedN; /* all values initially 0 (FALSE) */,vold enter-region(int process) /* process: who is entering (0 or 1) */ intother;/* */ other = 1 - process; interestedproce
14、ss = TRUE; turn = process; while (turn = = process /* null statement */ ,void leave-region(int process) /* process: who is leaving (0 or 1) */ interestedprocess = FALSE; /* indicate departure from critical region */ ,intturn; booleanflag2; process(i) int i; while (TRUE) compute; flagi := TRUE; while
15、 (flagi+1 mod 2)(turn = i+1 mod 2) ; critical_section; turn := (turn+1) mod 2; flagi := FALSE; ; ;,turn := 0; flag0 := FALSE; flag1 := FALSE; Process(0) AND process(1);,2. 信号量及其P、V操作,信号量（semaphore）Dijkstra， 1963是一个整型变量，与其相关 的两个操作是P、V操作。它是最 早提出的同步操作原话，P、V操 作的名称源于荷兰字Prolagen （试图降低）和Verhogen（升起)。,信号量及其
16、P、V操作,定义 2.1 一个信号量s是一个非负 整型变量，它仅仅可以由下列的 两个不可分的（即原子的）访问 例程之一来测试和修改：,P(s)和V(s)操作,P(s): while s 0 do ; s := s -1; V(s): s := s +1 主要缺点是忙等待,P(s)操作,type semaphore = record value : integer; L : list of process; end; 信号量的value初值表示系统中某类资 源的数目。因此，这类 信号量又称资 源信号量。,P(s)操作,P(semaphore S) S.value S.value l; If S.value 0 then阻塞该进程，并把它置入S.L等 待队列中；操作系统重新调度; else该进程继续执行; ,V(s)操作,V(semaphore S) S.value = S.value l; If S.value 0 then 从S.L等待队列中取出一进程; 将其状态改为“就绪”，并且 放入就绪队列; else该进
