牛客192239号

2016-06-08 11:28 已编辑山东大学

关注

程序员面试必考题（十一）：同步与互斥

来自微信公众号：开点工作室（ID：kaidiancs）

在操作系统章中会允许进程共享资源、以并发和并行的方式执行，要使进程正确、协调有效地执行，需要同步机制的支持。在操作系统内核中同步机制的实现有多种不同的方式，本文对同步机制中涉及的概念、实现方式、经典同步问题等内容进行阐述。

1进程同步的基本概念

在支持进程并发和并行的多任务操作系统中，进程同步机制的任务是使具有资源共享关系的进程能以互斥的方式访问临界资源；使具有相互合作关系的进程能协调运行。

临界资源是必须以互斥方式访问的共享资源。进程中访问临界资源的代码称为临界区。

实现进程的同步与互斥可以采用不同的方法，同步机制应遵循下述4条准则：

① 空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许其他进程访问临界资源。

② 忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，其他申请临界资源的进程必须等待，以保证对临界资源的互斥访问。

③ 有限等待。对要求访问临界资源的进程，应保证其在有限时间内能进入自己的临界区，以免进程陷入饥饿状态。

④ 让权等待。当进程不能进入自己的临界区时，应立即释放CPU，以免进程陷入“忙等”状态。

2实现临界区互斥的基本方法

(1)软件实现方法

Peterson算法是一个实现两个进程在临界区和非临界区代码段之间交替执行的软件算法，程序描述如下：

int turn;

boolean flag[2] ；

do{

flag[i] =TRUE;

turn = j;

while ( flag[j] && turn == j );

criticalsection

flag[i] =FALSE;

remaindersection

}while (TRUE);

该算法用turn的值表示哪个进程可以进入临界区。turn==i表示允许进程pi执行临界区代码；数组flag用于表示某个进程是否准备进入临界区，flag[i]==TRUE说明进程pi准备进入临界区。

(2)硬件实现方法

① 关中断

实现互斥最简单的方法之一是关中断，该方法只适用于单处理机系统，进程在执行临界区期间不响应中断，使用方法如下所示。

while (TRUE)

{… …

关中断；

临界区；

开中断；

… …

}

② TestAndSet指令

某些计算机系统会提供特殊的硬件指令来实现互斥，TestAndSet指令的实现可以用如下程序表示：

boolean TestAndSet(boolean *target) {

booleanrv = *target ；

*targe = TRUE ；

return rv ；

}

do{

while (TestAndSetLock(&lock))

； // do nothing

//crictical section

lock= FALSE ；

//remainder section

}while ( TRUE )

③ Swap指令

Swap指令的实现可以用如下程序表示：

void Swap(boolean *a,boolean *b){

boolean temp =*a ；

*a = *b ；

*b=temp ；

}

do{

key= TRUE ；

while ( key == TRUE )

Swap( &lock,&key ) ；

//critical section

lock = FALSE ；

// remainder section

}while ( TRUE ) ；

3 信号量

信号量机制通过定义表示共享资源使用情况的特殊变量，即信号量及对信号量的一对操作wait和signal操作（P-V操作）来实现进程之间的互斥与同步。根据信号量数据类型的不同，信号量可分为整型信号量和记录型信号量。

(1)整型信号量

整型信号量是一个用来表示可用资源数量的整型变量，其值只能被wait和signal操作访问。整型信号量机制的代码描述如下所示。s是信号量，初始值被设置成可访问的资源数量，当整型信号量用于进程互斥时，s被初始化为1，表示临界资源不能被多个进程同时访问。

int s ；

wait( s )

{ while s <= 0 do no-op

s = s-1;

}

signal( s )

{s = s + 1;

}

整型信号量代码描述

(2)记录型信号量

记录型信号量中包含一个存放可使用的资源数量的字段和一个进程阻塞队列。当进程通过wait操作申请的某种资源数量为零时，进程通过执行wait操作中的block过程自我阻塞，其进程控制块被插入s.L队列，在其他进程释放资源后通过signal 操作中的 wakeup过程唤醒被阻塞进程。

记录型信号量的定义如下：

typedef struct{

int value ；

struct process *L ；

}semaphore ；

记录型信号量的wait和signal操作定义如下

wait(s)

{s.value = s.value - 1 ；

if(s.value < 0) then (s.L) ；

}

signal(s)

{s.value = s.value + 1;

if(s.value <= 0) then wakeup(s.L) ； }

4 管程

管程是由与访问共享资源相关的变量以及实现共享资源访问的一组过程共同构成的资源管理模块。由管程的名称、局部于管程内部的变量说明、初始化管程内部变量的程序、实现对共享资源访问的程序几个部分构成。管程的语法描述和应用方式以用管程实现哲学家进餐问题为例予以说明。哲学家进餐问题是多个进程竞争有限资源的同步问题模型。问题描述：5个哲学家围坐于圆形餐桌旁，餐桌上共有5只筷子，每两个哲学家之间放一只筷子，哲学家不断重复思考、饥饿时进餐、进餐完毕继续思考的过程。哲学家进餐问题的同步要求：任一个哲学家只有拿到自己左右两边的筷子时才能进餐，进餐结束后放下左右两边的筷子。解决哲学家进餐问题的管程dp定义如下：

Monitor dp

{

enum{THINGKING ,HUNGRY , EATING}state[5] ；

condition self[5] ；

void pickup( int i) {

state[i] = HUNGRY ；

test( i ) ；

if (state[i] != EATING)

self[i].wait( ) ；

}

void putdown( inti ){

state[i] = THINKING;

test( (i+4)%5 ) ;

test( (i+1)%5) ;

}

void test( int i){

if ((state[(i+4)%5] != EATING) &&

(state[i] == HUNGRY) &&

(state[(i+1)%5] != EATING ) )

{ state[i]=EATING;

self[i].signal( );

}

initializationg_code(){

for (inti=0;i<5;i++)

state[i] = THINGKING;

}

dp中的self[i]是条件变量，被定义为condition类型。管程中的这类条件变量只有wait和signal 操作可以访问。当进程调用管程中的过程申请资源而未能满足时，通过wait操作将进程阻塞在相应条件变量的阻塞队列中。当该资源被释放时，通过对条件变量的signal操作向进程发送信号，如果进程接收到信号时处于阻塞态，此时会被唤醒，否则，通过signal操作发送的信号被忽略。

调用管程 dp的哲学家进程描述如下：

Dining -Philosopher( i )

while( TRUE )

{ dp.pickup( i );

… …

eat

… …

dp.putdown(i)

}

管程具有以下特征：

①管程中的过程可以被所有要访问管程的进程共享。

② 管程内定义的变量只能由该管程的过程访问，不允许进程或其他管程直接访问，一个管程中的过程也不能访问任何非局部于管程的变量。

③ 在任一时刻，只有一个进程能够真正进入管程调用其内部的过程，其他试图通过调用同一管程内的过程访问共享资源的进程必须等待。

④ 管程是需要编程语言支持的一种同步机制。

5 经典同步问题

(1)生产者-消费者问题

生产者-消费者问题是相互合作进程之间的同步问题模型。该问题描述为：系统中有两类进程，即生产者进程和消费者进程，以及大小为n的有界缓冲池。生产者进程生产产品，当缓冲池中有空缓冲区时，将产品放入其中。若缓冲池中没有空缓冲区，生产者进程阻塞。消费者进程在缓冲池中有非空缓冲区时，从中取产品，否则阻塞。缓冲池是临界资源，必须以互斥的方式访问。用记录型信号量机制实现生产者-消费者问题的同步代码如下所示。

Producer

do {

… …

// produce an item in nextp

… …

wait(empty) // 申请空缓冲区

wait(mutex) // 申请互斥访问缓冲池

… …

//add nextp to buffer

… …

signal(mutex)// 释放缓冲池互斥信号量

signal(full) // 释放一个非空缓冲区