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