恶补《操作系统》2_3——王道学习笔记

2.3_1 进程同步、进程互斥

1、进程同步

指为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

2、进程互斥

把一个时间段内只允许一个进程使用的资源称为临界资源。

对临界资源的互斥访问，可以在逻辑上分为四个部分：

do{entry section;  //进入区  对访问的资源检查或进行上锁critical section; //临界区(段) 访问临界资源的那部分代码exit section;   //退出区  负责解锁remainder section; //剩余区  其它处理} while(true)

需要遵循的原则：

（1）空闲让进。空的可以直接进去

（2）忙则等待。繁忙不能进去

（3）有限等待。不能让进程等待无限长时间

（4）让权等待。不能进去，不要堵着

2.3_2 进程互斥的软件实现方法（重点）

1、单标志法

两个进程在访问完临界区后会把使用临界区的权限教给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

int turn =0;//p0进程while(turn!=0);critical section;turn = 1;remainder section;//p1进程while(turn!=1);critical section;turn = 0;remainder section;

可以实现互斥

存在的问题：p1要访问的话，必须p0先访问，违背：空闲让进原则

2、双标志先检查

算法思想:设置一个bool数组flag[]来标记自己是否想要进入临界区的意愿，先检查后上锁。

bool flag[2]={false,false};//p1进程while(flag[1]);flag[0]=true;critical section;flag[0]=false;remainder section;//p2进程while(flag[0]);flag[0]=true;critical section;flag[1]=false;remainder section;

主要问题：由于进程是并发进行的，可能会违背忙则等待的原则；“检查”和“上锁”并不能一气呵成。

3、双标志后检查

算法思想:设置一个bool数组flag[]来标记自己是否想要进入临界区的意愿,不过是先上锁后检查。

bool flag[2]={false,false};//p1进程flag[0]=true;while(flag[1]);critical section;flag[0]=false;remainder section;//p2进程flag[0]=true;while(flag[0]);critical section;flag[1]=false;remainder section;

主要问题：由于进程是并发进行的，可能会两个同时上锁，都进不去，违反空闲让进和有限等待原则，从而会饥饿。

4、Peterson 算法

主动让对方先使用处理器（孔融让梨）

bool flag[2]={false,false};int turn=0;//p1进程flag[0]=true;turn=1;while(flag[1]&&turn==1);critical section;flag[0]=false;remainder section;//p2进程flag[1]=true;turn=0;while(flag[0]&&turn==0);critical section;flag[1]=false;remainder section;

遵循空闲让进、忙则等待、有限等待三个原则，但是未遵循让权等待（卡在while循环）的原则。

2.3_3 进程互斥的硬件实现方法

1、中断屏蔽方法

关中断（不允许进程中断）

临界区

开中断

简单、高校

多处理机，可能会同时访问临界资源

使用OS内核进程

2、TestAndSet（TSL指令）

TSL是用硬件实现的，上锁、检查一气呵成

不满足让权等待，会盲等

C语言描述逻辑：

//true表示已经上锁bool TestAndSet(bool *lock){bool old;old=*lock;*lock=true;return old;}//以下是使用TSL指令实现互斥的算法逻辑while(TestAndSet (&lock));//上锁并检查临界区代码段lock=false; //解锁

3、Swap指令

别称：Exchange指令、XCHG指令

Swap指令是用硬件实现的

//true表示已经上锁void Swap(bool *a,bool *b){bool temp;temp=*a;*a=*b;*b=temp;}//以下是使用Swap指令实现互斥的算法逻辑bool old=true;while(old=true)Swap(&lock,&old);临界区代码段lock=false; //解锁//剩余代码段

简单；适用多处理机；不能让权等待

2.3_4 信号量机制

信号量：信号量是一种变量，表示系统中某种资源的数量；

一对原语：wait（S）原语和signal（S）原语，分别简称P（S）、V（S），这一对原语可以对信号量进行操作。

1、整形信号量

用一个整数表示系统资源的变量，用来表示系统中某种资源的数量

int S=1;void wait(int S){ //wait原语，相当于：“进入区”（检查和上锁一气呵成）while(S<=0); //如果资源数不够，就意志循环等待S=S-1;    //如果资源数够，则占用一个资源}
void signal(int S){//signal原语，相当于“退出区”S=S+1;    //使用完资源后，在退出区释放资源}

可能会出现盲等

2、记录型信号量（重点）

记录型数据结构表示的信号量

//记录型信号量的定义typedef struct{int value;struct process *L;} semaphore;//某进程需要使用资源时，通过wait原语申请void wait (semaphore S){S.value--;if(S.value<0){block (S.L);//将该进程加入到消息队列中}}//进程使用完资源后，通过signal原语释放void signal (semaphore S){S.value++;if(S.valie<=0){wakeup(S.L);}}

除非特别说明，否则默认S为记录型信号量