源码获取
https://github.com/icoty/nachos-3.4-Lab
内容一:总体概述
本实习希望通过修改Nachos系统平台的底层源代码,达到“扩展同步机制,实现同步互斥实例”的目标。
内容二:任务完成情况
任务完成列表(Y/N)
Exercise1 | Exercise2 | Exercise3 | Exercise4 | Challenge1 | Challenge2 | Challenge3 | |
---|---|---|---|---|---|---|---|
第一部分 | Y | Y | Y | Y | Y | Y | N |
具体Exercise的完成情况
Exercise1 调研
调研Linux或Windows中采用的进程/线程调度算法。具体内容见课堂要求。
同步是指用于实现控制多个进程按照一定的规则或顺序访问某些系统资源的机制,进程间的同步方式有共享内存,套接字,管道,信号量,消息队列,条件变量;线程间的同步有套接字,消息队列,全局变量,条件变量,信号量。
互斥是指用于实现控制某些系统资源在任意时刻只能允许一个进程访问的机制。互斥是同步机制中的一种特殊情况。进程间的互斥方式有锁,信号量,条件变量;线程间的互斥方式有信号量,锁,条件变量。此外,通过硬件也能实现同步与互斥。
- linux内核中提供的同步机制
Exercise2 源代码阅读
code/threads/synch.h和code/threads/synch.cc:Condition和Lock仅仅声明了未定义;Semaphore既声明又定义了。
Semaphore有一个初值和一个等待队列,提供P、V操作:
- P操作:当value等于0时,将当前运行线程放入线程等待队列,当前进程进入睡眠状态,并切换到其他线程运行;当value大于0时,value–。
- V操作:如果线程等待队列中有等待该信号量的线程,取出其中一个将其设置成就绪态,准备运行,value++。
Lock:Nachos中没有给出锁机制的实现,接口有获得锁(Acquire)和释放锁(Release),他们都是原子操作。
- Acquire:当锁处于BUSY态,进入睡眠状态。当锁处于FREE态,当前进程获得该锁,继续运行。
- Release:释放锁(只能由拥有锁的线程才能释放锁),将锁的状态设置为FREE态,如果有其他线程等待该锁,将其中的一个唤醒,进入就绪态。
Condition:条件变量同信号量、锁机制不一样,条件变量没值。当一个线程需要的某种条件没有得到满足时,可以将自己作为一个等待条件变量的线程插入所有等待该条件变量的队列,只要条件一旦得到满足,该线程就会被唤醒继续运行。条件变量总是和锁机制一起使。主要接口Wait、Signal、BroadCast,这三个操作必须在当前线程获得一个锁的前提下,而且所有对一个条件变量进行的操作必须建立在同一个锁的前提下。
- Wait(Lock *conditionLock):线程等待在条件变量上,把线程放入条件变量的等待队列上。
- Signal(Lock *conditionLock):从条件变量的等待队列中唤醒一个等待该条件变量的线程。
- BroadCast(Lock *conditionLock):唤醒所有等待该条件变量的线程。
code/threads/synchlist.h和code/threads/synchlist.cc:利用锁、条件变量实现的一个消息队列,使多线程达到互斥访问和同步通信的目的,类内有一个Lock和List成员变量。提供了对List的Append(),Remove()和Mapcar()操作。每个操作都要先获得该锁,然后才能对List进行相应的操作。
Exercise3 实现锁和条件变量
可以使用sleep和wakeup两个原语操作(注意屏蔽系统中断),也可以使用Semaphore作为唯一同步原语(不必自己编写开关中断的代码)。
这里选择用1值信号量实现锁功能,Lock添加成员变量lock和owner,请求锁和释放锁都必须关中断,Condition添加一个成员变量queue,用于存放所有等待在该条件变量上的线程。代码如下:
1 | // synch.h Lock声明部分 |
Exercise4 实现同步互斥实例
基于Nachos中的信号量、锁和条件变量,采用两种方式实现同步和互斥机制应用(其中使用条件变量实现同步互斥机制为必选题目)。具体可选择“生产者-消费者问题”、“读者-写者问题”、“哲学家就餐问题”、“睡眠理发师问题”等。(也可选择其他经典的同步互斥问题)。
生产者-消费者问题(Condition实现)
1 | // threadtest.cc |
生产者-消费者问题(Semaphore实现)
1 | // threadtest.cc |
Challenge1 实现barrier(至少选做一个Challenge)
可以使用Nachos 提供的同步互斥机制(如条件变量)来实现barrier,使得当且仅当若干个线程同时到达某一点时方可继续执行。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66// threadtest.cc
// 条件变量实现barrier
Condition* barrCond = new Condition("BarrierCond");
Lock* barrLock = new Lock("BarrierLock");
int barrierCnt = 0;
// 当且仅当barrierThreadNum个线程同时到达时才能往下运行
const int barrierThreadNum = 5;
void barrierFun(int num)
{
/*while(1)*/
{
barrLock->Acquire();
++barrierCnt;
if(barrierCnt == barrierThreadNum){
// 最后一个线程到达后判断,条件满足则发送一个广播信号
// 唤醒等待在该条件变量上的所有线程
printf("threadName:[%s%d],barrierCnt:[%d],needCnt:[%d],Broadcast.\n",\
currentThread->getName(),num,barrierCnt,barrierThreadNum);
barrCond->Broadcast(barrLock);
barrLock->Release();
}else{
// 每一个线程都执行判断,若条件不满足,线程等待在条件变量上
printf("threadName:[%s%d],barrierCnt:[%d],needCnt:[%d],Wait.\n",\
currentThread->getName(),num,barrierCnt,barrierThreadNum);
barrCond->Wait(barrLock);
barrLock->Release();
}
printf("threadName:[%s%d],continue to run.\n", currentThread->getName(),num);
}
}
void barrierThreadTest(){
DEBUG('t', "Entering barrierThreadTest");
for(int i = 0; i < barrierThreadNum; ++i){
Thread* t = new Thread("barrierThread");
t->Fork(barrierFun,i+1);
}
}
// 运行结果,当第五个线程进入后判断条件满足,唤醒所有线程
root@yangyu-ubuntu-32:/mnt/nachos-3.4-Lab/nachos-3.4/threads#
root@yangyu-ubuntu-32:/mnt/nachos-3.4-Lab/nachos-3.4/threads# ./nachos -rs -q 6
threadName:[barrierThread1],barrierCnt:[1],needCnt:[5],Wait.
threadName:[barrierThread2],barrierCnt:[2],needCnt:[5],Wait.
threadName:[barrierThread3],barrierCnt:[3],needCnt:[5],Wait.
threadName:[barrierThread4],barrierCnt:[4],needCnt:[5],Wait.
threadName:[barrierThread5],barrierCnt:[5],needCnt:[5],Broadcast.
threadName:[barrierThread5],continue to run.
threadName:[barrierThread2],continue to run.
threadName:[barrierThread1],continue to run.
threadName:[barrierThread4],continue to run.
threadName:[barrierThread3],continue to run.
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
Ticks: total 814, idle 4, system 810, user 0
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
Cleaning up...
root@yangyu-ubuntu-32:/mnt/nachos-3.4-Lab/nachos-3.4/threads#
Challenge2 实现read/write lock
基于Nachos提供的lock(synch.h和synch.cc),实现read/write lock。使得若干线程可以同时读取某共享数据区内的数据,但是在某一特定的时刻,只有一个线程可以向该共享数据区写入数据。
1 | // threadtest.cc |
内容三:遇到的困难以及解决方法
困难1
刚开始没有加-rs参数,导致永远都只有一个线程在运行,原因是没有中断发生,运行的线程永远在执行循环体,加-rs参数,会在一个固定的时间短内发一个时钟中断,然后调度其他线程运行。
内容四:收获及感想
可以说实际操作后,对信号量,条件变量的应用更加清晰了。
内容五:对课程的意见和建议
暂无。
内容六:参考文献
[1] 内核中各种同步机制