山东大学操作系统课设nachosWord文档格式.docx
《山东大学操作系统课设nachosWord文档格式.docx》由会员分享，可在线阅读，更多相关《山东大学操作系统课设nachosWord文档格式.docx（85页珍藏版）》请在冰点文库上搜索。
Phase1：
Buildathreadsystemforkernelprocesses
Task1.1ImplementsJoin（）method
一、问题描述
1.Notethatanotherthreaddoesnothavetocalljoin（）,butifitiscalled,itmustbecalledonlyonce.
2.Athreadmustfinishexecutingnormallywhetherornotitisjoined.
二、解决方案
线程B在线程A运行的过程中调用join方法，阻塞线程A的运行获取运行权，此时线程A等待线程B完成运行后重新运行。
实现要求：
1.每个线程拥有自己的waitJoinQueue，里面存放了由于自己的join而被阻塞无法执行的线程。
2.由于我们对每个线程添加了waitJoinQueue切里面存有在等待的线程，故而我们需要修改finish函数，在线程完成运行即将终止时检查其waitJoinQueue，唤醒队列中在等待的线程。
三、实现代码
1.声明KThread.waitJoinQueue:
publicThreadQueuewaitJoinQueue;
2.初始化KThread.waitJoinQueue:
waitJoinQueue=ThreadedKernel.scheduler.newThreadQueue（true）;
注意这段代码在KThread构造器中，无论是否有currentThread都要有这段代码，这段代码应该出现两次
3.Join（）
publicvoidjoin（）{
Lib.debug（dbgThread,"
Joiningtothread:
"
+toString（））;
Lib.assertTrue（this!
=currentThread）;
/**forjoinmethod**/
Lib.assertTrue（joinCounter==0）;
joinCounter++;
booleanintStatus=Machine.interrupt（）.disable（）;
if（this.status!
=statusFinished）{
//System.out.println（this.getName（）+"
injoin"
+currentThread.getName（））;
waitJoinQueue.waitForAccess（currentThread）;
currentThread.sleep（）;
}
Machine.interrupt（）.restore（intStatus）;
}
4.finish（）中添加的部分
/**forjoinmethod**/
KThreadt=currentThread.waitJoinQueue.nextThread（）;
if（t!
=null）{
//System.out.println（"
currentThread:
+currentThread.getName（）+"
nextthread:
+t.getName（））;
t.ready（）;
四、方案总结
1.waitJoinQueue的初始化要求在每个线程中都得到执行。
因为之前没考虑到出现了错误这里特别说一下。
2.Joincounter静态全局变量记录join方法被调用的次数以控制其满足题目要求
3.一定要记得修改finish方法唤醒waitJoinQueue中等待的线程
Task1.2Implementconditionvariablesdirectly
1.Provideatomicitybyusinginterruptenableanddisable.
2.Provideanequivalentimplementationwithoutdirectlyusingsemaphores（youmayofcoursestilluselocks,eventhoughtheyindirectlyusesemaphores）.
3.Yoursecondimplementationofconditionvariablesmustresideinclassnachos.threads.Condition2.
1.LockconditionLock:
利用锁完成实现
2.ThreadQueuewaitQueue:
该条件变量等待的线程构成的队列
3.sleep（）:
其他线程在该条件变量上的等待即进入该条件变量的waitQueue陷入阻塞状态
4.wake（）:
唤醒该条件变量中等待的某个线程
5.wakeAll（）:
即对wake（）方法的循环调用，直到队列中没有线程为止
1.相关变量
privateLockconditionLock;
privateThreadQueuewaitQueue;
他们在构造器中完成初始化
publicCondition2（LockconditionLock）{
this.conditionLock=conditionLock;
waitQueue=ThreadedKernel.scheduler.newThreadQueue（true）;
}
2.sleep（）:
publicvoidsleep（）{
Lib.assertTrue（conditionLock.isHeldByCurrentThread（））;
conditionLock.release（）;
//System.out.println（"
----------"
）;
waitQueue.waitForAccess（KThread.currentThread（））;
KThread.currentThread（）.sleep（）;
++++++++++"
conditionLock.acquire（）;
//executedafterwakenup
3.wake（）
publicvoidwake（）{
KThreadt=waitQueue.nextThread（）;
=null）
4.wakeAll（）
publicvoidwakeAll（）{
while（t!
t=waitQueue.nextThread（）;
1.我们采用ThreadQueue对象来实现等待队列而非简单的利用一个LInkedList，这样保证了这个队列的调度算法与调度器的一致性，也免除了自己在wake方法中到底wake哪个线程的纠结。
2.ThreadQueue.nextThread对于队列中没有线程的情况返回null值，故我们通过检查它的返回值来确定队列里有没有线程。
3.线程陷入阻塞之前放弃锁，恢复就绪状态再获取锁。
Task1.3CompletetheimplementationofAlarmClass
1.ImplementethewaitUntil（longx）method.
2.Thereisnorequirementthatthreadsstartrunningimmediatelyafterwakingup;
justputthemonthereadyqueueinthetimerinterrupthandleraftertheyhavewaitedforatleasttherightamountoftime.
3.DonotforkanyadditionalthreadstoimplementwaitUntil（）.
4.youneedonlymodifywaitUntil（）andthetimerinterrupthandler.waitUntilisnotlimitedtoonethread.
1.threadTime类:
我们要处理的是线程在某个时间点调用waitUntil方法等待一个时间间隔后重新开始执行的问题，在这个问题中，线程与时间紧密结合。
ThreadTime类中将会保存线程信息以及线程应该被唤醒的时刻。
2.LinkedListlist:
alarm中的等待序列，这个序列中保存了所有调用了waitUntil方法进入等待状态的线程的threadTime类。
3.nachos系统每隔大概500个时间间隔会调用一次timerInterrupt（），于是我们在这个函数中检查list中等待的线程是否已经完成了等待，比较标准为当前系统时刻大于等于线程应该被唤醒的时刻
4.waitUntil函数：
在这个函数被线程调用后，调用时刻与函数接收的参数运算后得到线程应该被唤醒的时刻，如果这个时刻还没到达我们就把这个线程和他的唤醒时刻放到threadTime类中进入list中。
1.一些相关变量：
LinkedListlist=newLinkedList（）;
//usedtostorethreadTime
2.threadTime类：
/**added**/
privateclassthreadTime{
KThreadthread=null;
longtime=0;
threadTime（KThreadthread,longtime）{
this.thread=thread;
this.time=time;
KThreadgetThread（）{
returnthread;
longgetTime（）{
returntime;
3.waitUntil函数
publicvoidwaitUntil（longx）{
//fornow,cheatjusttogetsomethingworking（busywaitingisbad）
longwakeTime=Machine.timer（）.getTime（）+x;
threadTimett=newthreadTime（KThread.currentThread（）,wakeTime）;
if（wakeTime>
Machine.timer（）.getTime（））{
if（list.size（）==0）
list.add（tt）;
else{
for（inti=0;
i<
list.size（）;
i++）{
if（（（threadTime）list.get（i））.getTime（）>
wakeTime）
list.add（i,tt）;
elseif（i==list.size（）-1）
list.add（i+1,tt）;
}
}
4.timerInterrupt中检查list中线程是否等待完成的代码
while（list.size（）>
0）{
longcurrentTime=Machine.timer（）.getTime（）;
for（inti=0;
i++）{//smallerindexmeansearlierstepintothisqueue,havingwaitalongertimeinturn
if（currentTime>
=（（threadTime）list.get（i））.getTime（））{
（（threadTime）list.get（i））.getThread（）.ready（）;
list.remove（i）;
i=0;
currentTime=Machine.timer（）.getTime（）;
break;
1.线程进入等待的规律是：
早调用waiUntil方法的线程早进入等待，如果同一时刻有两个线程都满足等待完成条件，由于早调用方法的线程更早进入等待序列，这意味着他等待了更久的时间，那么他会早一步离开等待序列，这满足了题目的要求。
2.要检查调用函数的线程等待时间是不是已经过去了。
Task1.4implementsynchronoussendandreceiveofonewordmessageusingconditionvariables
1.ImplementtheCommunicatorclasswithoperations,voidspeak（intword）andintlisten（）.
2.Neitherthreadmayreturnfromlisten（）orspeak（）untilthewordtransferhasbeenmade.
3.YoursolutionshouldworkeveniftherearemultiplespeakersandlistenersforthesameCommunicator
4.Eachcommunicatorshouldonlyuseexactlyonelock.
按照题目中的线索我们应该利用条件变量完成相关功能。
Communicator对象可以调用speak和listen方法进行通信。
对于speak方法：
首先检查是否有listener，如果没有就进入等待，如果有就唤醒listener把信息传递过去然后退出。
对于listen方法：
首先检查是否有speaker，如果没有就进入等待，如果有就唤醒speaker收听信息。
对于communicator类，我们应该保存speaker和listener的条件变量，以及能说明两者数目的相关数值变量。
1.相关变量：
LinkedListwords;
Condition2speaker;
Condition2listener;
intnum_speaker,num_listener,num_words;
Locklock;
变量在构造器中的初始化
publicCommunicator（）{
words=newLinkedList<
Integer>
（）;
lock=newLock（）;
speaker=newCondition2（lock）;
listener=newCondition2（lock）;
num_words=0;
num_speaker=0;
num_listener=0;
2.speak（）
publicvoidspeak（intword）{
booleanstatus=Machine.interrupt（）.disable（）;
lock.acquire（）;
if（num_listener==0）{
words.add（word）;
speaker.sleep（）;
num_words++;
num_speaker++;
listener.wake（）;
else{
num_listener--;
System.out.println（KThread.currentThread（）.getName（）+"
speaked"
+word）;
lock.release（）;
Machine.interrupt（）.restore（status）;
3.listener（）
publicintlisten（）{
if（num_speaker==0）{
num_listener++;
speaker.wake（）;
listener.sleep（）;
num_speaker--;
listened"
+words.peek（））;
return（int）words.pop（）;
1.可能由于对相关要求认识不够清晰明确，于题目要求的azero-lengthboundedbuffer不同，我们采用了一个链表来保存speaker想要传输的信息
2.利用锁来保持操作的原子性，起到了操作互斥的作用
3.当且仅当一次成功的信息传递完成时线程才可以退出。
4.在我的实现中，要求speakerlistener线程成对存在，与课上某些同学演示的不同。
Task1.5implementpriorityschedulinginnachos
1.Changealineinnachos.confthatspecifiestheschedulerclasstouse.
2.YoumustimplementthemethodsgetPriority（）,getEffectivePriority（）,andsetPriority（）.
3.Inchoosingwhichthreadtodequeue,theschedulershouldalwayschooseathreadofthehighesteffectivepriority.Ifmultiplethreadswiththesamehighestpriorityarewaiting,theschedulershouldchoosetheonethathasbeenwaitinginthequeuethelongest.
4.Apartialfixforthisproblemistohavethewaitingthreaddonateitsprioritytothelowprioritythreadwhileitisholdingthelock.
5.BesuretoimplementScheduler.getEffectivePriority（）,whichreturnsthepriorityofa
升级会员 