前言

lab7涉及到的是进程间的通信,如何做好同步互斥,这里主要用到两个方法,一个是信号量,一个是管程,然后管程也是基于信号量来实现的,接下来我们来看下具体的实现吧(个人感觉lab7还是比较难的,需要清晰地弄清楚同步互斥的各种概念).

正文

Part0

需要改的文件包括:

  • default_pmm.c
  • default_sched.c
  • kdebug.c
  • pmm.c
  • proc.c
  • swap_fifo.c
  • trap.c
  • vmm.c

其中trap.c需要修改一下

因为在lab7中我们引入了进程sleep,所以需要引入计时器timer,调度器每次更新time相关信息,如果过期,那么就唤醒进程.

练习1: 理解内核级信号量的实现和基于内核级信号量的哲学家就餐问题(不需要编码)

我们首先来分析下利用信号量实现的哲学家问题,我们先看下信号量的结构.

信号量中包含value用于计数,和一个等待队列wait_queue用来维护挂在这个信号量上的进程,然后我们稍微看下等待队列

就是一个简单的双向链表结构,然后里面会有一些相应的操作,这里我准备放在后面分析.(其中底层实现还有计时器和一个硬件支持的中断屏蔽都暂且放在后面)

然后看下信号量中的几个操作

初始化信号量的值和等待队列.

然后是up,先是local_intr_save和local_intr_restore两个硬件支持的屏蔽中断和使能中断来操作寄存器的eflag位,来保证我们的操作是原子的,如果等待队列中不存在进程的话,直接value+1就行了,否则拿到等待队列中的进程后assert一下原来是不是wait_state状态,然后唤醒等待队列中的第一个队列,最后取消屏蔽

然后看下down,首先判断信号量value是不是大于0,直接--然后返回就行了,否则的话需要将当前进程加入等待队列中,然后调用schedule,选择另一个进程继续执行,当这个进程被唤醒后然后从等待队列中删除(注意屏蔽中断)

到这里准备工作差不多了,我们来看下具体流程,同样是从init.c中追踪,proc_init()函数,init_main()函数,然后这里有修改的地方

调用check_sync函数,有两部分分别是用信号量和管程实现的哲学家问题.

看一下先初始化一个mutex锁(同样是用信号量实现的),然后s是一个用于存放哲学家的信号量数组,我们循环5个哲学家线程出来,然后我们跟进下philosopher_using_condvar函数.

来分析下哲学家的具体操作,首先是睡一下作为思考,然后phi_take_forks_sema()来获取叉子,do_sleep一段时间表示吃饭,然后phi_put_forks_sema放下叉子

跟进下,mutex信号量实现的锁,down,up来维护一个临界区,然后自己转为饥饿状态HUNGRY,然后phi_test_sema()具体视图获取叉子,离开临界区后我们需要down一下自己,如果没拿到叉子就会阻塞自己,否则就减下信号量的值

来看下phi_test_sema这个函数,如果自己是饥饿的并且,左手和右手都不在吃,那么自己转换吃EATING状态,然后up一下自己这个信号量.

再看下phi_put_forks_sema,临界区保护下后,装换为思考状态,然后test左右哲学家

总结下哲学家就是在五个线程里面不断的从思考-饥饿-进餐三个状态不断转换,然后进行状态转换是需要用mutex加锁来保护变量,然后注意在哲学家进餐的时候需要利用信号量加锁防止重入,注意每个down,up操作都是一一对应的.

Part2 完成内核级条件变量和基于内核级条件变量的哲学家就餐问题(需要编码)

同样先看下管程的结构

monitor管程,mutex信号量实现的锁,next和next_count是用做唤醒休眠时勇的,然后cv是一个条件变量,来看下这个数据结构

有个信号量来维护,count来记录挂载这个条件变量的数目,然后owner表明这个条件变量属于哪个管程.然后我们来看下对条件变量的几个操作

先是管程的初始化,包括几个变量的赋初值,给条件变量malloc空间等

然后看下唤醒操作,假设现在的进程是B,如果count<=0说明没有睡在这个条件变量上的进程,否则就应该唤醒一个睡在sem这个信号量上的进程A,然后因为管程中只允许存在一个进程,所以当前进程B需要睡眠,所以next_count++,然后唤醒进程A,然后把自己睡在next上面,然后当其他进程返回后需要next_count--掉

再看下cond_wait函数,进程A因为条件变量不满足导致让自己睡过去,首先count++,然后需要分两个情况,

第一种情况当,next_count>0的时候,说明存在进程执行了cond_signal导致睡在next上,形成了一个进程链,那么就up唤醒其中的一个进程,然后把自己睡在sem信号量上,直到从别的进程中返回到这里再执行count--

第二种情况是next_count不存在,说明没有因为执行cond_signal而睡的进程,那么我们就需要唤醒因为互斥而无法进入的进程,然后当前进程睡在sem上,如果之后睡醒后,同样count--

最后我们实现一下check_sync.c中的两个函数

首先是phi_take_forks_condvar,看一下显示把自己置为饥饿状态,然后尝试获取叉子phi_test_condvar(i)

我们看下phi_test_condvar(i),如果自己是饥饿并且左右没有在吃,那么把自己置换为EATING状态,然后这里利用条件变量尝试唤醒挂在当前sem的进程

接着上面的如果没有拿到叉子,说明条件没有满足,需要把自己wait掉让出管程,注意在最后我们都需要唤醒next或者mutex阻塞的进程.

然后看下phi_put_forks_condvar放叉子这个函数,将自己置为思考,然后去test左右的哲学家,此时可能就会唤醒因为没有得到条件变量而阻塞的哲学家,这个时候就会因为count>0的情况后,将next_count++然后up唤醒沉睡的进程,然后再把自己down在next形成一个进程队列,先等待那个被唤醒的进程完成工作返回后再继续执行.

流程总结

这里拿两个哲学家的一次交互进行总结下,其实就是一个哲学家A拿到叉子后,down一下mutex这个信号量锁

,导致后来的哲学家B因为不满足条件变量,count++后,up mutex来做之后让出管程,同时这里把自己睡在sem上,当就餐完毕的哲学家A更改自己状态为THINKING后,test(假设是LEFT)尝试刚刚被阻塞的哲学家B,此时B所需要的条件变量满足了,然后进入cond_signal的函数,因为count>0,所以先把next_count++,然后up把B的sem信号量准备好,然后down把A睡在管程的next进程等待队列上,(注意,直到down函数调用schedule为止此时都一直是A进程在执行),当schedule调度完成后,返回到down的位置,恢复A进程的phi_put_forks_condvar[LEFT]中调用的cond_signal中的next_count--,然后回到phi_put_forks_condvar函数,最后需要有一个

最后这个是保证因为cond_signal而睡眠的进程一定会被唤醒,比如其他进程进入管程最后都会在退出管程的时候确保next等待队列的进程都会被唤醒,所以每一个信号量的up和down都会有了一一对应的关系.

因此更多的哲学家都会类似上面的分析,只不过可能会多了几重的嵌套关系,不过在最后其都会被up down组合完成

底层支持

计时器

lab7需要do_sleep来实现定时器的作用,所以我们需要一个timer定时器的逻辑来完成,所以有了时间中断,

一个 timer_t 在系统中的存活周期可以被描述如下:

  1. timer_t 在某个位置被创建和初始化,并通过 add_timer加入系统管理列表中
  2. 系统时间被不断累加,直到 run_timer_list 发现该 timer_t到期。
  3. run_timer_list更改对应的进程状态,并从系统管理列表中移除该timer_t。

主要是run_timer_list用来遍历timer链表来适时地唤醒相应的进程,大概看了下逻辑,没有什么特别难的地方,不过可以关注下add timer那里的操作比较精巧.

屏蔽与使能中断

主要就是cli和sti两个x86的指令,最终实现了关(屏蔽)中断和开(使能)中断,即设置了eflags寄存器中与中断相关的位。通过关闭中断,可以防止对当前执行的控制流被其他中断事件处理所打断。但是注意这里ucore只实现了的是单处理机下的情况,对于多处理机仅仅依靠屏蔽一个cpu的中断是不行的.

等待队列

当需要等待事件的进程在转入休眠状态后插入到等待队列中。当事件发生之后,内核遍历相应等待队列,唤醒休眠的用户进程或内核线程,并设置其状态为就绪状态(PROC_RUNNABLE),并将该进程从等待队列中清除。

以及一系列操作等待队列的函数这里就不再展开了.

总结

感觉这里同步互斥学的还不是特别好,之后感觉需要再返工学习下,尤其是管程这里比较难理解对于具体的代码,还需要细细地品,加油还有最后一个实验就做完了.