《互斥与同步的解决方法.pdf》由会员分享，可在线阅读，更多相关《互斥与同步的解决方法.pdf（5页珍藏版）》请在三一文库上搜索。
1、互斥与同步的解决方法互斥与同步的解决方法 =硬件方法 -采用软件方法实现进程互斥使用临界资源是很困难的，他们通常能 实现两个进程的互斥，很难控制多个进程的互斥。 -算法设计需要非常小心，否则可能出现死锁，或互斥失败等严重问 题。 -软件方法始终不能解决忙等现象，降低系统效率， -硬件发放包括屏蔽中断和专用机器指令。 +屏蔽中断 -由于进程切换需要依赖中断来实现，如果屏蔽中断则不会出现进程 切换。 -因此，为了实现对临界资源的互斥使用，可以在进程进入临界区之 前，屏蔽中断，当进程退出临界区时，打开系统中断。 -中断被屏蔽以后，系统时钟中断也被屏蔽。处理机将不会被切换到 其它进程。 -于是， 一旦
2、屏蔽中断， 进程就可以检查和修改共享内存区中的数据， 而不必担心其他进程介入，其伪代码如下： Repeat 屏蔽中断； 临界区； 打开中断； 其余部分； Forever。 -这种方法约束条件太强，付出的代价太大。 -因为中断被屏蔽以后，系统将无法响应任何外部请求，也不会响应 当前执行进程的任何异常及系统故障，严重的降低了处理机性能。 -这种方法仅对单处理机系统有效，如果系统有两个或多个共享内存 的处理机，屏蔽中断仅仅对执行本指令的处理机有效，其他处理机仍 将继续运行，并可以访问共享内存空间。 =专用机器指令 -利用一些专用机器指令也能实现互斥，机器指令在一个指令周期内 执行，不会受到其他指令的
3、干扰，也不会被中断。 -Test and Set指令就是较长用的一种机器指令，其定义如下： testset 指令 Function testset(var i:integer):Boolean; Begin If i =0 then Begin i:=1; testset:=true; end else testest:=false; end. Program mutualexclusion; Constn n=;/*进程数*/ Var bolt:integer; Procedure P(i:integer); Begin Repeat Repeat nothinguntil testset(
4、bolt); 临界区； Bolt:=0; 其余部分 Forever End; Begin/*主程序*/ Bolt:=0; parbegain P(1); P(2); P(n) Parend End. exchange 指令 Procedure exchange（var r:register;var m:memory）; Var temp; Begin Temp:=m m:=r; r:=temp; end. Program mutualexclusion; Constn n=;/*进程数*/ Var bolt:integer; Procedure P(i:integer); Var key:in
5、teger; Begin Repeat Key:=1 Repeat exchange(key,bolt)until key=0; 临界区； exchange(key,bolt); 其余部分 Forever End; Begin/*主程序*/ Bolt:=0; parbegain P(1); P(2); P(n) Parend End. +机器指令优点 -非常简单，易于证明； -同时适用于单处理机系统和共享内存的多处理机系统中多个进程互 斥； -可以分别为临界区设置属于他自己的变量，以实现对多个临界区的 互斥访问。 +机器指令缺点 -忙等现象仍然存在，进程都需要循环检测，等待时机进入临界区。 但
6、是， 由于采用了机器指令， 这种忙等消耗的机器时间比软件方法小， 属于“可接受的忙等” 。 -可能出现饥饿现象。当临界区空闲时，执行循环检测的若干个等待 进程能进入临界区的几率是相等的，有的进程可能运气非常不好，很 难有机会进入临界区，而饥饿。 -还有可能导致死锁 -例如，进程 P1 的优先级低于 P2 的优先级，若 P1 通过执行专用机 器指令，进入临界区，且在临界区内被中断，P2 被调度执行，若 P2 也需要进入该临界区，由于临界区被 P1 占用，P2 忙等。由于 P1 的优 先级低于 P2,调度程序不可能强行剥夺P2 的执行而调度 P1。 这样， P1 将一直占用临界区被中断，P2 一直
7、忙等，如果没有外力的作用，这种 僵持状态将一直保持下去，即系统出现死锁。 =信号量方法 -软件方法和硬件方法都存在忙等问题，浪费了处理机时间。 -信号量方法能够实现进程的互斥与同步，而不必忙等。 +信号量实现互斥的基本原理 -两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个 位置暂时停止执行（阻塞等待） ，直到它收到一个可以“向前推进”的 信号（被唤醒“。 -相应地，将实现信号等作用的变量称为信号量，常定义为记录型变 量 s，其中一个域为整形，另一个域为队列，其元素为等待该信号量 的阻塞进程（FIFO） 。 +信号量定义 Type semaphore=record Count:int
8、eger; Queue:list of process End; Var s:semaphore; +定义信号量的两个原子操作 -wait（s）和 signal（s） -早起这两个原语被称作 P（s）和 V（s） wait(s) s.count:=s.count-1； if s.count0 then begin 进程阻塞； 进入进程 s.queue 队列； End; signal（s） s.count:=s.count+1; if s.count0 then begin 唤醒队首进程； 将进程从 s.queue 阻塞队列中移出； End; +wait、signal 的应用 -进程进入临界区之
9、前，首先执行 wait(s)原语，若 s.count0，则进 程调用阻塞原语，将自己阻塞，并插入到s.queue 队列排队。 -注意，阻塞进程不会占用处理机时间，不是忙等，直到某个从临界 区退出的进程执行 signal（s）原语，唤醒它。 -一旦其他某个进程执行了 signal（s）原语中的 s.count+1 操作后，发 现 s.count0，即阻塞队列中还有被阻塞的进程，则调用唤醒原语， 把 s.queue 中第一个进程修改为就绪状态，送就绪队列，准备执行临 界区代码。 利用信号量实现互斥的通用模式 Program mutualexclusion; Const n=;/*进程数*/ Var
10、 s:semaphore(:=1);/*定义信号量 s,s.count 初始化为 1*/ ProcedureP（i:integer）; Begin Repeat Wait(s); 临界区； Signal（s）; 其余部分 Forever End; Begin/*主程序*/ Parbegin P(1);P(2);P(n) Parend End. +信号量的类型 -信号量分为：互斥信号量和资源信号量。 -互斥信号量用于申请获释放资源的使用权，常初始化为1. -资源信号量用于申请或归还资源，可以初始化为大于1 的正整数， 表示系统中某类资源的可用个数。 -wait 操作用于申请资源（或使用权） ，进
11、程执行 wait 原语时，可能 会阻塞自己； -signal 操作用于释放资源（或归还资源使用权） ，进程执行 signal 原 语时，有责任唤醒一个阻塞进程。 +信号量的物理意义 -s.count0 表示还可以执行 wait(s)而不会阻塞的进程数（可用资源 数） 。没执行一次 wait(s)操作，就意味着请求分配一个单位的资源。 -当 s.count0 时，表示已无资源可用，因此请求该资源的进程被阻 塞。此时，s.count 的绝对值等于该信号量阻塞队列中的等待进程数。 执行一次 signal(s)操作就意味着释放一个单位的资源。当s.count0， 表示 s.queue 队列中还有被阻塞的进程，需要唤醒该队列中的第一个 进程，到就绪队列中。 +s.count 的取值范围 -当仅有两个并发进程共享临界资源时，互斥信号量只能取值0、1、 -1.其中， s.count=1，表示无进程进入临界区 s.count=0，表示已有一个进程进入临界区 s.count=-1 表示已有一个进程正在等待进入临界区 -当用 s 来实现 n 个进程互斥时，s.count 的取值范围为 1-(n-1) -操作系统内核以系统调用形式提供wait 和 signal 原语，应用程序通 过该系统调用实现进程间的互斥。 -工程实践证明，利用信号量方法实现进程互斥时高效的，一直被广 泛采用。