nachos系统实验报告：实验三

实验三

一.实验目的

学会运用实验二中实现的工具来实现一些多线程并发问题。

二.实验内容

1) EventBarrier：EventBarrier与某个 事件 相联系。事件有signaled和unsignale两种状

态。线程想通过事件时必须等待 事件 被另外线程 signal。只有当所有进入事件的线程完成动作时 发出signal的线程才将事件状态设为unsignaled

2) AlarmClock：AlarmClock让某个线程停止指定时间单位。当事件到达时重新将线程

放入就绪队列。

3) Bridge：Bridge是一个单行桥且最大允许3量车在桥上行驶。实现应解决注意公平性

与饥饿问题。

4) Elevator：实现Elevator类,并解决3个并发问题

a)一个电梯，电梯容量无限。 b)一个电梯，电梯容量有限。 c)多个电梯。

三.实验结果

1. EventBarrier

类定义：

enum BarrierStatus { unsignaled, signaled } ; class EventBarrier{ public: EventBarrier() ; ~EventBarrier() ; void Wait() ; void Signal() ; void Complete() ; int Waiters() ; private: LockO *lock ; ConditionO *conSignal ; //用于 挂起和唤醒 调用Signal()函数的线程。 ConditionO *conComplete ; //用于 挂起和唤醒 完成response 而处于等待别的事件response的线程 ConditionO *conWait ; //用于 挂起和唤醒 那些当事件处于unsignaled而调用Wait()的线程 BarrierStatus status ; //事件状态 int waiterNum ; };

void EventBarrier::Wait() { lock->Acquire(); waiterNum++ ; if (status == signaled) { //处于 signaled 状态，直接return lock->Release(); return ; } //处于 unsignaled 状态 //等到处于Signaled状态为止。 conWait->Wait(lock); lock->Release(); } void EventBarrier::Complete () { lock->Acquire() ; waiterNum-- ; if (waiterNum == 0) { conSignal->Signal(lock); } conComplete->Wait(lock) ; lock->Release(); } void EventBarrier::Signal (){ lock->Acquire(); status = signaled ; conWait->Broadcast(lock); //通知所有等待Event的事件 while (waiterNum != 0){ conSignal->Wait(lock); //当还有事件没response时挂起 } conComplete->Broadcast(lock); //通知所有等待别的线程response的线程 status = unsignaled ; lock->Release(); } //通知Signal线程全部事件已处理完 //等待其它线程response

主要函数

1）Wait(): 线程挂起待事件被 signal，当事件已经处于signaled状态时直接return

2）Signal(): 线程通知所有等待事件的线程。并且挂起等待 所有调用Wait()的线程 结束操作并调用Complete()通知此线程（包括在挂起过程中调用Wait()的线程）。

3)Complete():当所有Wait()线程都完成操作调用Complete后通知Signal线程,此线程已经完成操作,并且的等地其它线程response。

测试结果：

测试中主线程来释放Signal信号。

另4个线程做为等待线程，名字分别为 Thread 1～4。

Thread 1,2在主线程Signal之前就调用Wait()函数，Thread 3,4在事件被标志Signaled状态时才调用Wait()。最终结果如下图所示，事件在四个线程都response自后才改变状态，四个线程个主线程都运行正确。

Thread 1,2 进入等待

signal事件

Thread 3,4直接过Barrier。完成操作进入complete等待

Thread 1,2 进入complete等待。

通知所有正在等待response的线程所有线程都已经complete

2.AlarmClock

类定义

class Alarm { public: Alarm() ; ~Alarm() ; void Pause (int howLong) ; void ThreadRestart() ; private: LockO *lock ; ConditionP *conLock ; } ;

主要函数： //让线程在 howLong 事件后开始运行 //闹钟结束后重新开始运行线程 //此条件变量里的线程队列是按照优先级排列的 //每次运行优先级最高的线程

void Alarm::ThreadRestart() { conLock->Signal(NULL); } static void TimeUP(int NoUse) { alarmClock->ThreadRestart() ; } void Alarm::Pause(int howLong) { lock->Acquire(); interrupt->Schedule(TimeUP, 0, howLong, AlarmInt); conLock->Wait(lock, stats->totalTicks + howLong); lock->Release(); }

1） Pause(int howLong)：让事件停止 howLong 个时间单位。调用了系统自带的函数 interrupt->Schedule函数，在howLong时间后调用TimeUP（int 0)函数。并将中断的发生时间totalTicks + howLong当做此线程的优先级将其挂起,确保每次alarmClock唤醒的线程是设置闹钟最早的线程。

2） TimeUP （int NoUse): 用于当做中断发生时的调用函数，函数中的alarmClock为全局闹钟变量。参数没有任何作用。

3） ThreadRestart()：一个闹钟中断到来。唤醒对应线程（最早线程），将其加入就绪队列。

测试结果：

共七个线程，每个线程设置的 howLong 为 1～200随即数。已运行多次进行检验。 其中一次结果如下图所示。每个线程在正确的时间结束闹钟进入就绪队列。

每次时钟中断增加事件随机

Thread 0 ,184 alarm end

Thread3 ,201 alarm end

Thread 2, 271 alarm end

Thread 1, 284 alarm end Thread 6, 289 alarm end Thread 4, 325 alarm end

Thread 5, 400 alarm end

Bridge 供Bridge模块使用的静态全局变量

static int traDir ; //此时桥的交通方向 static int carNum ; //桥上的车子数量 static List *dirQueue = new List(); //按先来用于存储等待的车的方向 static LockO *lock = new LockO(NULL); static ConditionO *conLock = new ConditionO(NULL) ;

3.

void ArriveBridge (int dir) { bool is = 1 ; lock->Acquire(); if (carNum == 3) { //Bridge full is = 0 ; dirQueue->Append((void*)dir); conLock->Wait(lock); } else if (carNum != 0) { if (dir != traDir) { //opposite direction is = 0 ; dirQueue->Append((void*)dir); conLock->Wait(lock); } else { if (!dirQueue->IsEmpty()) { // There are cars waiting is = 0 ; dirQueue->Append((void*)dir); conLock->Wait(lock); } } } if (is){ carNum++ ; } traDir = dir ; lock->Release() ; } void ExitBridge (int dir) { int tDir ; lock->Acquire(); if (!dirQueue->IsEmpty()) { if (carNum == 1) { //此时下1~3辆车可能时反向, //唯一一辆车下桥时发信号给下一辆车 for (int i = 1; i <= 3 && (!dirQueue->IsEmpty());i++) { tDir = (int) dirQueue->GetItem(1) ; traDir = tDir ; if (tDir != dir){ dirQueue->Remove() ; conLock->Signal(lock); carNum++ ; } else { break ; } } } else if (carNum == 3) { //若下辆车方向一样则 tDir = (int)dirQueue->GetItem(1) ; if (tDir == traDir){ dirQueue->Remove() ; conLock->Signal(lock); carNum++ ; } } } carNum-- ; lock->Release();

Bridge采用的是先到先进的政策，若方向为1的车进桥，此时桥上只有1辆方向为1的车，但对面有方向为0的车在等待时，此车也进入等待。以此达到公平和防止饿死，因为不会用车辆处于一直等待的状态。 1)ArriveBridge(int dir) :

当桥上由3辆车时：线程直接挂起。

当桥上由1,2辆车时：若线程方向与桥的方向相反，线程挂起 若线程方向与桥的方向相同但对面由车等待，则线程挂起 当桥上没有车时：线程直接通过 2）void ExitBridge (int dir)：

当没有车等待时直接exit。有车等待时：

当桥上有1辆车时：等待的车方向一定相反，按先后顺序唤醒1～3辆方向与此线程方向相反的车。

当桥上有2辆车时：因为此时等待队列下一辆车不可能与其方向相同。所以当桥上车辆为2辆时不用处理。

当桥上有3两车时：若等待队列下一辆车方向相同，车唤醒下一辆车。 测试结果：

创造6两车，每辆车的方向为随机0或1。已检验多次，其中一次截图如下。 结果正确。

//从生成的车

辆可以看出2～6号车将被挂起。

1号车exit

桥，唤醒下面3辆方向与其相反的车辆

2号车出桥并唤醒5号

车

3号车出桥唤醒6号车

除了随机的测试之外还测试了一些具体的情况如： car 1, dir 0 car 2, dir 1 car 3, dir 0 car 4, dir 1 car 1, dir 0 car 2, dir 0 car 3, dir 0 car 4, dir 0 最终结果都显示正确。

car 5, dir 0 car 5, dir 0

car 6, dir 1 car 6, dir 0

一

4.Elevator

Elevator 代码较多，下面按运行顺序进行介绍。首先介绍Elevator的运行规则： 1）当Elevator无人且无人等待此电梯时，电梯自动回到第1层。当电梯在第 无任何需要时，电梯自动进入就绪态，让别的线程运行。 2）当电梯运行的方向上还有人等待进入电梯（不分进入的方向）时，电梯继 续运行，直到电梯运行的方向上没有人要进入（或电梯满人）和退出为止，电 梯改变方向。 3）电梯先出后进，且进来的人必须全都完成RequsetFloor（）之后电梯才能关 门。 4）当有多个电梯时，用GetClosestElevator（）函数来选择一个最近的电梯。 计算远近时，假设此时电梯都按自己的方向运行到底之后才转变方向来确定 电梯到达此楼需跨过多少楼层来当做距离。 函数介绍：

电梯循环运行的Run()函数：

void Elevator::Run() //run函数是elevator线程不断运行的循环函数 { int destFloor ; while (true) { destFloor = FindNextDest() ; //找到电梯下次进入的楼层 if (destFloor == 0) { //此时表示电梯无动作 dir = still ; currentThread->Yield(); continue ; } //确定电梯运行方向 if (currentFloor < destFloor){ dir = up ; } else if (currentFloor > destFloor) { dir = down ; } chooseLock->Acquire(); if (currentFloor != destFloor) { int time = destFloor - currentFloor ; time = time > 0 ? time : -time ; alarmClock->Pause(time * 100); VisitFloor(destFloor); } chooseLock->Release(); OpenDoors(); CloseDoors(); if (dir == still && IsElevatorOccupy()){ //处理电梯处于第一层的特殊情况 dir = up ; } } } void Elevator::OpenDoors() { exitBarrier[currentFloor].Signal(); //先让里面的人出去 //再让外面的人进来 if ( calledDir == up ) { enterBarrierUp[currentFloor].Signal(); } else if ( calledDir == down ) { enterBarrierDown[currentFloor].Signal(); } } void Elevator::CloseDoors() { lock->Acquire(); closingBarrier[currentFloor].Wait(lock); lock->Release(); } //此处的Barrier不是EventBarrier，此处Wait的功能是：只有进入电梯中的人都要求了要去的楼层后电梯才将门关上 bool Elevator::Enter() { lock->Acquire(); //capacity表示电梯容量,0为无穷 if (occupancy == capacity && capacity != 0) { lock->Release(); //电梯人满 if (calledDir == up) { inWaiterUp[currentFloor]-- ; enterBarrierUp[currentFloor].Complete(); } else if (calledDir == down) { inWaiterDown[currentFloor]-- ; enterBarrierDown[currentFloor].Complete(); }//因为rider函数循环会将其再次加入等待的队列 //所以即使没有进入也要更新一次信息,调用complete return false ; } occupancy++ ; lock->Release(); closingBarrier[currentFloor].AddSwitch(); //必须所有运行过AddSwitch的线程都完成 //RequestFloor的动作后，elevator才能CloseDoor if (calledDir == up) { inWaiterUp[currentFloor]-- ; enterBarrierUp[currentFloor].Complete(); } else if (calledDir == down) { inWaiterDown[currentFloor]-- ; enterBarrierDown[currentFloor].Complete();void Elevator::RequestFloor(int floor) { lock->Acquire(); ASSERT ( currentFloor != floor) closingBarrier[currentFloor].SwitchOn() ; //当所有调用AddSwitch函数再调用 //SwitchOn()之后,电梯便能CloseDoor。 outWaiter[floor]++ ; exitBarrier[floor].Wait(lock) ; lock->Release(); } void Elevator::Exit() { occupancy-- ; outWaiter[currentFloor]-- ; exitBarrier[currentFloor].Complete(); }

void Building::CallUp(int fromFloor) { Elevator *e ; if (elevatorNum == 1) { e = elevator ; e->globalLock->Acquire(); e->ReciveCall (fromFloor, up); return ; } }

Elevator* Building::AwaitUp(int fromFloor) { Elevator *e ; if (elevatorNum == 1) { e = elevator ; e->enterBarrierUp[fromFloor].Wait(e->globalLock); e->globalLock->Release(); return e ; } chooseLock->Acquire(); //在选择电梯时,电梯不能移动 e = GetClosestElevator(fromFloor, up) ; e->chooser++ ; chooseLock->Release(); e->globalLock->Acquire(); e->ReciveCall (fromFloor, up); e->enterBarrierUp[fromFloor].Wait(e->globalLock); e->globalLock->Release(); return e ;

测试结果：

1.无容量限制的电梯，building有3层，共7个人测试结果如下每个人的开始层数和目的层数都是随机的。结果正确

2.1个电梯，容量为3，building有10层，共4个人。每个人一开始都在第三层等待。结果截图如下。除此实验外。还运行了多次building有3 层，共10个人的测试程序 （截图太长），结果正确。

四个人都从第3层出发，电梯容量为3

Rider 3因为电梯满人而没进成功

Rider 1,2,4,RequstFloor

Rider3 重新call一次

下次目的地选择第5层。

到达第六层后3个人一起下电梯

最后载Rider 3

电梯不需要了回到第一层。

Elevator结束

3.多个电梯：2个电梯，4个人。两人先选择电梯后，后两人在电梯位置改变后在进入building进行选择电梯。除此之外还运行了3个电梯，每个电梯3容量，共 20人的测试几次。 结果正确

四.实验总结

? EventBarrier是用于某线程在进行某些操作前需要某个事件或条件先得到满足

后再执行的情况下使用。如ELevator实现中某层等待的人要进入电梯中的情况。 ? 因为Nachos的时间只有在线程调用Intrrupt::SetLeve或Thread::Sleep

（Intrrupt::Idle）函数时才会前进。所以Nachos的时钟中断只可能在这调用可这两个函数的时候产生。

? Bridge可以想象成总线传输数据一般，一次只能传输某个方向的数据，且传输的数据大小有限（OneVehicle代表一个单位数据）。 ? Bridge用先进现出的方法很大程度上影响了多线程的运行效率，lock的覆盖的范围也太大同时影响效率。在很多情况下即使对面有车先等着的时候这里也可以过桥， 有很大改进空间。

? Elevator是到现在为止最复杂的多线程并行处理。在处理过程中发生很多错误。 如在拥有lock的情况下还用EventBarrier将其挂起等等。Elevator的实现让我对多线程的同步和互斥由了更深了了解和掌握。 ? Elevator的策略也不好，没有在有容量的情况下解决饥饿问题，电梯的搭乘策略会造成饿死。可以按等待的人按电梯的时间来分配优先级优化电梯的选择搭乘算法。在多电梯情况下更需要电梯选择策略来提高多个电梯的效率，避免个别几个电梯被过多使用，而另几个处于较闲的状态，使整体效率下降。

本文来源：https://www.bwwdw.com/article/urpo.html