OS ucore lab 7
练习零： 填写已有实验：
<pre mdtype="fences" cid="n88" lang="c" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">复制以下文件 其中 trap.c 需要进行修正
vmm.c trap.c default_pmm.c pmm.c proc.c swap_fifo.c
trap.c:
static void trap_dispatch(struct trapframe tf) {
++ticks;
/* 注销掉下面这一句
因为这一句被包含在了 run_timer_list()
run_timer_list() 在之前的基础上 加入了对 timer 的支持
***/
// sched_class_proc_tick(current);
run_timer_list();
}</pre>
练习一：理解内核级信号量的实现和基于内核级信号量的哲学家就餐问题（不需要编码）
完成练习0后，建议大家比较一下（可用kdiff3等文件比较软件）个人完成的lab6和练习0完成后的刚修改的lab7之间的区别，分析了解lab7采用信号量的执行过程。执行make grade，大部分测试用例应该通过。
请在实验报告中
- Q1： 给出内核级信号量的设计描述，并说其大致执行流流程。
- Q2：请在实验报告中给出给用户态进程/线程提供信号量机制的设计方案，并比较说明给内核级提供信号量机制的异同。
- Q1:
<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="c" cid="n76" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">// 先是定义了一个信号量的数据结构
typedef struct {
int value; // 计数值 用于 PV操作
wait_queue_t wait_queue; // 进程等待队列
} semaphore_t;
// 用于等待队列 存放了当前等待的线程PCB和唤醒原因 等待队列 用于还原结构体的等待队列标志
typedef struct {
struct proc_struct proc;
uint32_t wakeup_flags;
wait_queue_t wait_queue;
list_entry_t wait_link;
} wait_t;
// 初始化信号量中的计数值和等待队列
void sem_init(semaphore_t sem, int value) {
sem->value = value;
wait_queue_init(&(sem->wait_queue));
}
/P操作：
要关闭中断并保存 eflag 寄存器的值 避免共享变量被多个线程同时修改
判断计数值是否大于0，若大于0说明此时没有其他线程访问临界区则直接将计数值减1并返回
若计数值小于0则已经有其他线程访问临界区了，就将当前线程放入等待队列中并调用调度函数
等到进程被唤醒再将当前进程从等待队列中，取出并删去，最后判断等待的线程是因为什么原因被唤醒。
**/
static __noinline uint32_t __down(semaphore_t sem, uint32_t wait_state) {
bool intr_flag;
local_intr_save(intr_flag);
if (sem->value > 0) {
sem->value --;
local_intr_restore(intr_flag);
return 0;
}
wait_t __wait, wait = &__wait;
wait_current_set(&(sem->wait_queue), wait, wait_state);
local_intr_restore(intr_flag);
schedule();
local_intr_save(intr_flag);
wait_current_del(&(sem->wait_queue), wait);
local_intr_restore(intr_flag);
if (wait->wakeup_flags != wait_state) {
return wait->wakeup_flags;
}
return 0;
}
/V操作：
也要关闭中断并保存eflag寄存器的值，防止共享变量同时被多个线程访问或修改
先判断等待队列是否为空。若为空，则将计数值加1并返回
若不为空，说明还有线程在等待，此时取出等待队列的第一个线程并将其唤醒，唤醒的过程中
将其从等待队列中删除
***/
static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
bool intr_flag;
local_intr_save(intr_flag);
{
wait_t *wait;
if ((wait = wait_queue_first(&(sem->wait_queue))) == NULL) {
sem->value ++;
}
else {
assert(wait->proc->wait_state == wait_state);
wakeup_wait(&(sem->wait_queue), wait, wait_state, 1);
}
}
local_intr_restore(intr_flag);
}</pre>
<pre mdtype="fences" cid="n257" lang="" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">将内核信号量机制迁移到用户态的最大麻烦在于，用于保证操作原子性的禁用中断机制、以及CPU提供的Test and Set指令机制都只能在用户态下运行，而使用软件方法的同步互斥又相当复杂，这就使得没法在用户态下直接实现信号量机制；于是，为了方便起见，可以将信号量机制的实现放在OS中来提供，然后使用系统调用的方法统一提供出若干个管理信号量的系统调用：
申请创建一个信号量的系统调用，可以指定初始值，返回一个信号量描述符(类似文件描述符)；
将指定信号量执行P操作；
将指定信号量执行V操作；
将指定信号量释放掉；
</pre>
-
Q2：
<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="" cid="n139" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit;">相同点：
提供信号量机制的代码实现逻辑是相同的；
不同点：
由于实现原子操作的中断禁用、Test and Set指令等均需要在内核态下运行，因此提供给用户态进程的信号量机制是通过系统调用来实现的，而内核级线程只需要直接调用相应的函数；</pre>
练习二: 完成内核级条件变量和基于内核级条件变量的哲学家就餐问题（需要编码）
首先掌握管程机制，然后基于信号量实现完成条件变量实现，然后用管程机制实现哲学家就餐问题的解决方案（基于条件变量）。
<pre mdtype="fences" cid="n156" lang="c#" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">// 管程数据结构
typedef struct monitor{
semaphore_t mutex; // 二值信号量 用来互斥访问管程
semaphore_t next; // 用于 条件同步 用于发出signal操作的进程等条件为真之前进入睡眠
int next_count; // 记录睡在 signal 操作的进程数
condvar_t cv; // 条件变量
} monitor_t;
// 条件变量数据结构
typedef struct condvar{
semaphore_t sem; // 用于条件同步 用于发出wait操作的进程等待条件为真之前进入睡眠
int count; // 记录睡在 wait 操作的进程数(等待条件变量成真)
monitor_t * owner; // 所属管程
} condvar_t;
// 初始化管程
void monitor_init (monitor_t * mtp, size_t num_cv) {
int i;
assert(num_cv>0);
mtp->next_count = 0; // 睡在signal进程数 初始化为0
mtp->cv = NULL;
sem_init(&(mtp->mutex), 1); // 二值信号量 保护管程 使进程访问管程操作为互斥的
sem_init(&(mtp->next), 0); // 条件同步信号量
mtp->cv =(condvar_t ) kmalloc(sizeof(condvar_t)num_cv); // 获取一块内核空间 放置条件变量
assert(mtp->cv!=NULL);
for(i=0; i<num_cv; i++){
mtp->cv[i].count=0;
sem_init(&(mtp->cv[i].sem),0);
mtp->cv[i].owner=mtp;
}
}
// 管程wait操作
/
先将 因为条件不成立而睡眠的进程计数加1
分支1. 当 管程的 next_count 大于 0 说明 有进程睡在了 signal 操作上 我们将其唤醒
分支2. 当 管程的 next_count 小于 0 说明 当前没有进程睡在 signal操作数 只需要释放互斥体
然后 再将 自身阻塞 等待 条件变量的条件为真 被唤醒后 将条件不成立而睡眠的进程计数减1 因为现在成立了
*/
void cond_wait (condvar_t cvp) {
cprintf("cond_wait begin: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
cvp->count++;
if (cvp->owner->next_count > 0) {
up(&(cvp->owner->next));
} else {
up(&(cvp->owner->mutex));
}
down(&(cvp->sem)); // 阻塞自己 等待条件成真
cvp->count--;
cprintf("cond_wait end: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}
// 管程signal操作
/
分支1. 因为条件不成立而睡眠的进程计数小于等于0 时 说明 没有进程需要唤醒 则直接返回
分支2. 因为条件不成立而睡眠的进程计数大于0 说明有进程需要唤醒 就将其唤醒
同时设置 条件变量所属管程的 next_count 加1 以用来告诉 wait操作 有进程睡在了 signal操作上
然后自己将自己阻塞 等待条件同步 被唤醒 被唤醒后 睡在 signal 操作上的进程应该减少 故 next_count 应减 1
*/
void cond_signal (condvar_t *cvp) {
cprintf("cond_signal begin: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
if (cvp->count > 0) { // 若存在因为当前条件变量而等待的进程的话
up(&(cvp->sem));
cvp->owner->next_count++; // 所属管程的 next 计数 加 1 表示当前进程会被等待者堵塞
down(&(cvp->owner->next)); // 阻塞自己 等待条件同步
cvp->owner->next_count--;
}
cprintf("cond_signal end: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}</pre>
<pre mdtype="fences" cid="n157" lang="c" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">check_sync.c:
// 测试编号为i的哲学家是否能获得刀叉 如果能获得 则将状态改为正在吃 并且 尝试唤醒 因为wait操作睡眠的进程
// cond_signal 还会阻塞自己 等被唤醒的进程唤醒自己
void phi_test_condvar (i) {
if(state_condvar[i]==HUNGRY&&state_condvar[LEFT]!=EATING
&&state_condvar[RIGHT]!=EATING) {
cprintf("phi_test_condvar: state_condvar[%d] will eating\n",i);
state_condvar[i] = EATING ;
cprintf("phi_test_condvar: signal self_cv[%d] \n",i);
cond_signal(&mtp->cv[i]) ;
}
}
// 拿刀叉
void phi_take_forks_condvar(int i) {
down(&(mtp->mutex)); // P操作进入临界区
state_condvar[i] = HUNGRY; // 饥饿状态 准备进食
phi_test_condvar(i); // 测试当前是否能获得刀叉
while (state_condvar[i] != EATING) {
cond_wait(&mtp->cv[i]); // 若不能拿 则阻塞自己 等其它进程唤醒
}
if(mtp->next_count>0)
up(&(mtp->next));
else
up(&(mtp->mutex));
}
// 放刀叉
void phi_put_forks_condvar(int i) {
down(&(mtp->mutex)); // P操作进入临界区
state_condvar[i] = THINKING; // 思考状态
phi_test_condvar(LEFT); // 试试左右两边能否获得刀叉
phi_test_condvar(RIGHT);
if(mtp->next_count>0) // 有哲学家睡在 signal操作 则将其唤醒
up(&(mtp->next));
else
up(&(mtp->mutex)); // 离开临界区
}</pre>
<pre mdtype="fences" cid="n159" lang="" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">相同点：基本的实现逻辑相同；
不同点：最终在用户态下实现管程和条件变量机制，需要使用到操作系统使用系统调用提供一定的支持; 而在内核态下实现条件变量是不需要的；</pre>
实验结果：
京公网安备 11010502036488号