武汉大学 操作系统期末考试复习笔记 - 图文(4)

硬件指令方法 用TS实现互斥：

boolean TS(boolean *1ock) {

boolean old； old=*lock； *lock=true； return old；

}

┆

while TS(&lock)；

//lock=1的话，陷入while；lock=0的话，将lock置1，进入临界区 临界区代码 Critical Section ； lock=false ；

其他代码 remainder section； ┆

用swap指令实现进程互斥： //swap(a,b)交换两值 ┆ key=true；

while(key！=false)Swap(&lock，&key)；

//如果lock=true，不停的swap，直到lock=false，进入临界区 临界区代码 Critical Section ； lock=false ；

其他代码 remainder section； ┆

用锁机制实现互斥（自旋锁） lock（w） {

while（w==1）； w = 1； }

unlock（w） {

w = 0； }

进程P1 进程P2 ┆ ┆

lock(w)； lock(w)； 临界区； 临界区； unlock(w)； unlock(w)； ┆ ┆

这一页的方法都不能实现让权等待，即存在忙等待

信号量：信号量S是个整型变量，除了初始化外，它只能通过两个标准原子操作wait()和signal()来访问。

wait (S) signal (S): { while S 0 do no-op; { S++; S--; }

Wait是原来的P操作 Signal是原来的V操作

当进程需要使用资源时则对信号量执行wait，当释放资源时执行signal

互斥信号量的实现

信号量由两个成员（s，q）组成，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。又称信号灯。 除信号量的初值外，信号量的值仅能由P操作（又称为wait操作）和V操作（又称为signal操作）改变。 wait (semaphore *s) { s->value--;

if (s->value < 0)

{ add this process to s->list;

//如果所有资源都被占用，加入等待队列，if里的value是被减过的。如果等于0，那么value被减过之前是1，有资源，就不用等待了 block(); } }

signal (semaphre *s) { s->value++;

if (s->value <= 0)

//如果有进程在等待，就把第一个进程移除。注意if里的value是被加过的，如果value=0，那么就没有进程在等待

{ remove a process P from s->list; wakeup(P); } }

信号量中的整型变量S表示系统中某类资源的数目。 当其值大于0时，表示系统中当前可用资源的数目；

当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。 P，V操作类似 P，V操作是原语

利用信号量实现互斥

设S为两个进程P1、P2实现互斥的信号量，S的初值应为1（即可用资源数目为1）。只需把临界区置于P（S）和V（S）之间，即可实现两进程的互斥。

死锁：两个或多个进程无限等待一个事件的发生，而该事件正是由其中一个的等待进程引起的。

饥饿：无限期的阻塞。进程可能永远都无法从它等待的信号量队列中移去

经典同步问题：

有限缓冲问题 生产者—消费者问题

它描述了一组生产者进程向一组消费者进程提供产品，它们共享一个有界缓冲池。缓冲池中的每个缓冲区可以存放一个产品，生产者进程不断生产产品并将产品放入缓冲池中，消费者进程不断从缓冲池内取出产品并消费。 设置两个同步信号量empty、full，其初值分别为n、0。

//empty代表缓冲区空的区域个数，full代表缓冲区被填充的区域个数 mutex是确保对缓冲区的访问互斥的信号量，初值为1

无论在生产者进程还是在消费者进程中，P操作的次序都不能颠倒，否则将可能造成死锁。

读者-写者问题

第一读者-写者问题：要求没有读者需要保持等待除非有一个写者已经获得允许使用共享数据

第二读者-写者问题：一旦写者就绪，不会有新读者开始读操作

用信号量解决读者-写者问题：

目标：允许多个读进程同时读此数据对象， 但是一个写进程不能与其他进程（不管是写进程还是读进程）同时访问此数据对象

互斥信号量mutex,初值1, 共享变量readcount 记录当前读进程数，初值0，写互斥信号量writer，用于实现写进程与写进程和读进程的互斥，初值为1

读者：

p(mutex)；

if (readcount==0) p(writer)；

//如果没有读者访问，则等待写者的完成。如果有读者，则直接访问临界区 readcount=readcount+1； v(mutex)； 读数据集； p(mutex) ；

readcount=readcount-1 ；

if (readcount==0) v(writer)；//所有人读完才能写 v(mutex)；

Mutex用于保护readcount的互斥访问

哲学家进餐问题：

第i个哲学家活动算法描述： p(stick[i])；

p(stick[(i+1) % 5])； 进餐； v(stick[i])； v(stick[(i+1) % 5])； 思考； 可能会死锁

解决方法：至多允许四个哲学家同时进餐。

仅当左、右两支筷子均可用时，才允许拿起筷子进餐。 奇数号哲学家先拿左筷子再拿右筷子，偶数号哲学家相反。

睡眠的理发师问题 …… 此处隐藏：10字，全部文档内容请下载后查看。喜欢就下载吧 ……