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

互斥同步...




戳上面的蓝字“开点工作室”关注我们哦！

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

1进程同步的基本概念

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

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

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

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

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

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

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

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

(1)软件实现方法

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

int turn;

boolean flag[2]；

do{

flag =TRUE;

turn = j;

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

criticalsection

flag =FALSE;

remaindersection

}while (TRUE);

该算法用turn的值表示哪个进程可以进入临界区。turn==i表示允许进程pi执行临界区代码；数组flag用于表示某个进程是否准备进入临界区，flag==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