【操作系统】 Operation System 第十章:信号量和管程
以下内容全部是B站 的陈老师视频的课程总结,https://www.bilibili.com/video/av6538245?p=73,感谢UP主感谢陈老师,由于第十章是最难的部分之一,我从这一章开始来对计算机专业核心课程之一的《操作系统》进行知识点总结,顺序和内容全部根据B站视频来。一方面是加深自己的印象,另一方面贡献给大家减少大家的工作量。
内容上增加了对课程上代码的解读,同时手打记录了课件上出现的全部文字。下一次更新会更新第九章内容。
10.1 信号量和管程
10.1.1 为什么需要信号量
回顾一下lock能解决并发问题中竞争条件(竞态条件)对资源的争夺;
但是lock不能解决同步问题,需要更高级的方式实现同步(包括多线程共享公共数据的协调执行;互斥与条件同步的实现(互斥是指同一时间只能有一个线程可以执行临界区));
同步的实现需要高层次的编程抽象(例如锁)的实现和底层硬件支持。
10.2 信号量
信号量是一种抽象的数据类型,包括:
->一个整形sem,两个原子操作;
->P():sem-1,如果sem<0,等待,否则继续
->V():sem+1,如果sem<=0,唤醒一个等待的P
信号量有点像铁路的信号灯
信号量是Dijkstra在20世纪60年代提出,V:Verhoog,P:Prolaag,分别是荷兰语的增加和减少。
10.3 信号量的使用
10.3.1 信号量的性质
信号量必须是整数,初始值一般是大于0;
信号量是一种被保护的变量(初始化后,唯一改变一个信号量值的方法只能是P()和V();操作只能是原子操作);
P()能阻塞,V()不会阻塞;
信号量假定是公平的(FIFO;如果一直有V()操作,则不会有进程被P()所阻塞);
信号量包括两种类型:
->二进制信号量:0或1;
->计数信号量:任何非负整数;
->可以用上面这两种类型任意一个表示另一个。
信号量可以用在2个方面:
->互斥
->条件同步(采用调度约束实现一个线程等待另一个线程的事情发生)
10.3.2 用二进制信号量实现lock功能,也就是互斥
信号量初始值设置为1,一个线程开头信号量减一锁上,完事后加一解锁;想一想,如果别的线程也想执行,当他执行P操作的时候,信号量为负数了,此时其它的线程就不得不等待,等到当前线程执行完后V操作了,另一个线程才能执行。
10.3.3 用二进制信号量实现线程同步(调度约束)
信号量初始值为0,线程A执行到P()时,信号量为负数挂起,只有到线程B执行到V()时,线程A才可能继续。这确保了同步。
10.3.4 同步问题出现的场景
一个线程等待另一个线程处理事情,例如生产者-消费者模型,此时互斥(锁机制)是不够的;
例如生产者-消费者模型就需要一个有界缓冲区,
->一个或多个生产者产生数据并将数据放在缓冲区中;
->单个消费者每次从缓冲区取出数据;
->在任何一个时间只有一个生产者或消费者可以访问缓冲区,如下图。
10.3.5 生产者-消费者模型的正确性要求
->在任何一个时间只能有一个线程操作缓冲区(互斥);
->当缓冲区为空时,消费者必须等待(调度/同步约束);
->当缓冲区满了时,生产者必须等待(调度/同步约束);
10.3.6 生产者-消费者模型实现策略
->利用一个二进制信号量实现互斥,也就是锁的功能;
->用一个计数信号量fullbuffers来约束生产者;
->用一个计数信号量emptybuffers来约束消费者;
Deposit():
往缓冲区增加东西。所以说fullBuffer加1,emptybuffer减1.
Remove():
和上一个相反。
可以发现,这个锁是紧跟着对缓冲区的操作的。
10.4 信号量的实现
注意,sem>0,说明计算机能满足所有需求,不需要把线程弄到等待队列里。
P():
标记减一,如果标记小于0了,说明资源不够,需要把线程加入队列;
V():
标记加一,如果标记小于等于0,说明等待队列中有元素,唤醒一个队列中的元素并执行;
信号量的用途:互斥和条件同步(注意等待的条件是独立的互斥);
信号量的缺点:读/开发代码困难;容易出错(使用的信号量被另一个线程占用,完了释放信号量);不能够处理死锁;
10.5 管程monitor
管程的目的:分离互斥和对条件同步的关注。
管程的定义:一个锁(临界区)加上0个或若干个条件变量(等待/通知信号量用于管理并发访问的共享数据)。
管程实现的一般方法:收集在对象/模块中的相关共享数据;定义方法来访问共享数据。
一开始,所有进程在右上角的排队队列中,排队完后进行wait()操作,等到signal()操作唤醒后,执行这个进程的代码。
10.5.1 管程的组层
(1)Lock():
Lock::Acquire()如果锁可用,就抢占锁(上锁)
Lock::Release()释放锁,如果这个时候有等待者,就唤醒
Lock操作保证互斥。
(2)Contion Variable:
如果条件不能满足就wait(),一旦条件满足了,signal()会唤醒那些在队列中的线程并继续执行。
10.5.2 管程的实现
需要维持每个条件队列;线程等待的条件是等待一个signal()操作。
(1)wait():
numWaiting就是计数器,统计有多少个线程处于等待队列中;
release()因为当前线程在睡眠,就必须把锁打开一下,以便就绪状态的线程去执行,如果不release可能会造成死锁;
schedule()的意思是,当前线程在wait()了,在队列里睡眠了,此时就需要选择一个就绪态的线程去执行;
就绪态的线程执行完毕后就可以再上锁。
(2)signal():
如果等待队列中有元素,那么就把队列的头元素取出来(并删掉)并唤醒wakeup,此时这个线程就是就绪状态了,它的下一步操作就是wait()里的schedule(),执行这个线程。
注意,signal仅在等待队列中有元素的时候才对numberWaiting执行(减法操作),而信号量不一样,在P()和V()一定会有对信号量的加减操作的。
(1)Deposit():
(这里比较高能,我也是看了好几遍才明白的。)
根据管程定义,只有一个线程能进入管程,所以一开始就上锁,在最后才解锁(紫红色字);这里和信号量是不一样的,信号量的互斥是紧紧靠着信号量的,而管程的互斥是在头和尾。注意,这个lock是管程的lock。
如果buffer没有满,就可以先不看红字,Deposit是要往buffer里加商品,加的时候需要上锁保证对buffer操作的互斥(紫色,一次只运行一个线程操作);直到buffer的计数器为n,装满了;
但是需要提前判断一种情况,就是容器是不是满的(红字部分),如果是满的,就把加入商品这个操作使用条件变量notFull,给notFull传入的参数就是那个管程的lock。此时重点来了,还记得管程条件变量定义里的wait()操作吗?那里面有一个release操作,释放的就是紫红色标记的lock->acquire();只有释放了这个lock,现在处于就绪状态(就是在notFull.signal()操作中被唤醒)的线程才能执行(就是wai()里面的schedule()操作),否则就会死锁;等到就绪状态的线程执行完了,再上锁,恢复原样!
现在再看看notEmpty.release()是不是就好理解了?因为我每进行一次deposit操作,buffer里面就会多一个商品,那么就多一个东西被消费者使用,此时就可以唤醒一个取商品操作的线程,这个就是靠notEmpty.release()实现,此时就有一个取商品线程处于就绪态,他会在remove()操作里的notEmpty.Wait()操作中被执行!!
(2)Remove():
和上面就一样啦,我就不解释了。
10.5.3 两个巨老的方法
上图的黄色标记是等待的线程,蓝色标记是正在执行的线程,它进行了唤醒操作。
注意,在上面的生产者消费者代码执行过程中,一次执行signal操作可能会涉及到2个线程在同一个管程中的操作(是让被唤醒的老黄色线程马上schedule执行呢,还是先让当前新蓝色线程没擦完的屁股擦擦呢?),哪一个先执行??关于这种情况的具体解决,有两种方式:
Hoare:如上图右图。一旦执行了signal操作,先让等待的黄色线程完事了,新蓝色线程再把剩下的屁股擦了;
Hansen(采用):如上图左图。一旦执行了signal操作,新蓝色线程先执行完,然后老黄色线程再执行。
根据两个巨老的方案,修改deposit如上。Hansen实际上和之前一样。之所以用while,是因为上图黄色线程必须等蓝色的完成后才会释放,所以说在队列的线程可能不是一个,都在抢线程;而Hoare方法,他是每signal一次,只有一个等待线程,于是用if。
10.5.4 本节总结
基本的硬件操作(禁用中断/原子指令/原子操作)是高层抽象(信号量/锁/条件变量)的基础,采取不同的高层抽象的算法策略,可以实现临界区和管程等不同的并发编程策略。
10.6 读者写者问题
目的:
->共享数据的访问;
使用者类型:
->读者(不需要修改数据);
->写者(读取和修改数据)。
问题的约束:
->允许同一时间有多个读者,但是任何时间只能有一饿写者;
->当没有写者时,读者才可以访问数据;
->当没有读者和其他写者时,写者才能访问数据;
->在任何时候只能有一个线程可以操作共享变量。
共享数据包括:
->数据集;
->信号量CountMutex(初始值为1,约束读者);
->信号量WriteMutex(初始值为1,约束写者);
->读者数量Rcount(整数,初始值为1)。
10.6.1 基于信号量的读者优先
(1)写者:
sem_wait(WriteMutex)相当于P()操作;
write;
sem_post(WriteMutex)相当于V()操作;这俩其实就是锁。我们知道,二进制的P/V操作就是锁。
确保一个时间只有一个写者在挥洒笔墨。
(2)读者:
在read的再之前,因为要实现对Rcount的保护,所以首先给读者上锁;如果当前没有读者,此时给写者上锁(P()操作)不许写者进来,然后我就可以读了;因为进来了一个读者,所以Rcount++;给读者解锁;
在read的再之后,读完了,因为要实现对Rcount的保护,所以首先给读者上锁;读者走一个,所以Rcount–;如果最后一个读者也读完了,把写者的锁释放;给读者解锁。
10.6.2 基于管程的写者优先
->基于读者优先的方法,只要有一个读者处于活动状态,后来的读者都会被接纳。如果读者源源不断的出现,那么写者会饥饿。
->基于写者优先的方法,一旦写者就绪,那么写者会尽可能快的执行写操作。如果写者源源不断的出现,那么读者就始终处于阻塞状态。
注意,有两类写者,一种是正在创作的写者,另一种是在等待队列中的写者。只要有一种写者存在,读者都要等待。
Database::Read():
要等待以上2种读者;之后才能read;唤醒在等待队列中的写者;
Database::Write():
只需要等待正在读或者正在写的人;没有人正在操作就可以write;唤醒其他人。
管程的数据:
AR/AW活着的读者和写者个数;WR/WW等待着的读者和写者的个数;
条件变量:okToRead可以去读了;okToWrite可以去写了。
(1)读者的操作
StartRead():
(确保即没有等待着写者也没有正在写的写者)
因为是管程,所以两端上锁;
如果等待着写者和正在写的写者数量和大于1,那么等待的读者加1,等着,注意,等完之后WR要减1,AR要加1。
DoneRead():
(读完了,唤醒其他写者)
因为读完了,AR减1;
如果没有人在读且有写者在等着,马上唤醒一个写者。
(2)写者的操作
StartWrite():
只要有人在操作共享变量,我就等着;等完了,我就变成active了。
DoneWrite():
写完了,AW减1;先唤醒写者,再唤醒读者。
10.6 哲学家就餐问题
思路1,哲学家的角度看怎么解决这个问题?
要么不拿,要么就拿两个叉子。
思路2,计算机程序怎么解决这个问题?
不能浪费CPU时间,而且线程之间要相互通信。
思路3,如何实现编程?
->必须有一个描述每个哲学家当前状态的数据结构;
->该结构是一个临界资源,各个哲学家对它的访问应该互斥的进行(线程间互斥);
->一个哲学家吃饱后,需要唤醒左领右舍,所以存在同步关系(线程同步)。
注意,我们考虑的对象,也就是共享资源,是哲学家的状态,而不是叉子的状态。
一个哲学家所有操作的实现:
S2-S4拿叉子的实现:
注意,因为涉及到对共享状态量的访问,所以需要上锁。
其中,看看能不能拿两把叉子的操作:
注意,这里的V操作和之前的P操作对应上了。
S6-S7放下叉子的实现:
注意,因为涉及到对共享状态量的访问,所以需要上锁。