《2023年山东大学计算机学院操作系统实验报告.docx》由会员分享，可在线阅读，更多相关《2023年山东大学计算机学院操作系统实验报告.docx（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、操作系统课程设计报告000000000000学院:计算机科学与技术学院 专业：计算机科学与技术 班级：20* *级*班姓名：* * * * * * 规定线程被唤醒后立即执行它,只是在它等待了指定期间后将它。放入等待队列 中。不要通过产生任何附加的线程来实现wai t Unt i 1函数,你仅需要修改 waitUntil函数和时间中断解决程序。w a it U ntil函数并不仅限于一个线程使用 在任意时间，任意多的线程可以调用它来阻塞自己。3 .方案于Al a r m类有关的是machin e.Tim e r类.它在大约每500个时钟滴 答使调用回调函数(由T i mer.se11 nterr
2、uptHand 1 er函数设立).因此 A 1 arm类的构造函数中一方面要设立该回调函数Ala r m.timerln t errup t ().为了实现w a itUnti 1,需要在Al a r m类中实现一个内部类Waiter,保 存等待的线程及其唤醒时间在调用waitU ntil (x)函数时，一方面得到关于该 线程的信息：(线程：当前线程，唤醒时间：当前时间+ x),然后构造新的 Waite r对象，并调用s leep操作使当前线程挂起.在时钟回调函数中(大约 每5 0 0个时钟间隔调用一次)则依次检查队列中的每个对象。假如唤醒时间 大于当前时间，则将该对象移出队列并执行wa k
3、 e操作将相应线程唤醒。4 .实现代码class Wa i ter(Wai t er( 1 ong wa keTime,KThread threa d)(0thi s.wak e Tim e = wa k eT i me;0 thi s . t hread=thread;)p r i v a te 1 ong wa k eTime;private KTh r ead th r ead;)pub 1 i c void waitUntil(long x)(boolea n intSta t us = Mach i ne.i nter r u pt() . d i sable();4 o ng wa
4、ke T i me = Ma c h i ne.time r ().g etTime() + x;Waiter wa iter = new Waite r (wakeTime,KThread.cu r r entT hread();owa itli s t .a dd(w a iter);System.out.p r in t ln(KTh r ead.cu r ren t Th read() .getName() 。线程休眠，时间为:+ 1/13为沿6上面6().9 t Time() + ”，应当在 。+ wakeT ime+“醒来.”);oKThread. s 1 eep();M a ch
5、ine . inte r r u p t () .r e sto r e(in t Sta tus);)pu bli c vo i d t imerlnterrup t ()Wa i ter wai ter;fo r (in t i = 0;iwaitlist . size () ; i+ +)wa i ter=wai 11 i s t .remov e ();df ( wa i t e r. wakeTime= Ma c hi n e . timer().ge t Time()(System . out.pri n tin(唤醒线程:+w a iter.th r e a d.g e tNam
6、e() + ,时间为:+ M a c h i ne.timer().g etTimeO);。wa ite r . t h r ead. r ead y (); /线程进入就绪状态e Isewai t lis t . add(waiter);)oKT hread. c u rrentTh r ead(). y i eld();)p ri v ate Li n k e dList waitl i st;Ta s kl.4用条件变量，不使用信号量，实现同步发送接受消息，s p ea k , I i sten1.规定使用条件变量来实现一个字长信息的发送和接受同步。使用void spea k(i n t
7、 word)和 i n t list e n()函数来实现通讯(Commun i c ator)类的 通讯操作。speak函数具有原子性，在相同地Communica t or类中档待listen 函数被调用，然后将此字发生给listen函数。一旦传送完毕，两个函数都返回(1 isten函数返回此字I.分析对一个Commun i ca t or类的对象cz线程A先调用c.spea k er(x )发送 一个字后被挂起，直到另一线程B调用c .listen ()收到这个字x后，A和B 同时返回.类似地，线程B先调用c. 1 i st e n (x)后被挂起，直到另一线程B 调用c . s pea
8、ke r (x)发送一个字后，A和B同时返回.同时需要注旨在一 个C omm u nica t or上有多个s pake r和lis t ener的情形.此时的spea k e r和1 is t ene r只能是一对一的，即一个speaker只能将数据发送到一个I i s t ene r,一个listen e r也只能接受来自一个s p ekaer的数据，其余的 speakers和liste n e r s都需要等待.2 .方案每个Communi ca t or有一个锁(保证操作的原子性)和与该锁联系的两 个条件变量用于保证spea k e r I i s t en e r间的同步.在spe
9、a k函数中, 一方面检查若已有一个s pea k er在等待(s peaknum 0)或无lis ten e r 等待，则挂起.否则设立变量，准备数据并唤醒一个listener.在listen函数中, 增长一个listen e r后，一方面唤醒s peaker,然后将自己挂起以等待sp eake r准备好数据再将自己唤醒.这个问题其实是一个缓冲区长度为0的生产者/消费者问题.3 .实现代码p u blic Comm uni cator ()(loc k = n e w Lock();con = new Condition (lock);)publi c void spea k (int wo
10、rd)(loc k.acquireQ;if(spe a k n u m 01| 1 isten num=0)(spea k num + +;oc 0n. s leep ();)if ( 1 istennum0)(。c on.wakeAl 1();d i s ten num = 0;)this.word=wo r d ;Sys t em.o u t.pri n 11 n ( KT h read.curren t T h r ead().g e tN a me()+线程说+this.wo r d);1 o c k.re 1 ease();)p u b 1 i c int li s ten()(lo
11、ck.acquire();while(listennum0| | speaknum =O)(dis t en n um + +;con.sleep ();listen num -;)if(speaknum0)(o c on.wake ();spea knum-;)KTh r ead. c urrentTh r ead ().y i e ld();Sy s tern .o ut.println(KTh r ead.cu r rentTh r ead().g etName()+ ” 线程听到+this.w。r d);list ennum = O;1 ock . re 1 e ase();retu
12、r n this . word ;)p rivat e Lock loc k;private Cond it ion con;pri vate int word;pr i vate static int speaknum;pri vate s tati c int I i sten n um ;T a skl.5完毕P ri。r i t y S cheduler实现优先级调度.规定通过完毕P r io ritySchedu 1 er类在Nacho s中实现优先级调度(pr i or i ty sched uling)o优先级调度是实时系统中的关键构建模块。1 .分析在Nachos中，所有的调度
13、程序都继承抽象类S c heduler.系统已经提供 了一个简朴的轮转调度器Round RobinScheduler,它对所有线程不区分优 先级而采用简朴的FIFO队列进行调度.我们实现的优先级调度类PrioritySched u 1 er 也Z嵌承自 S c heduler. 优先级调度的传统算法如下：每个线程拥有一个优先级(在Nachos中，优先 级是一个0到7之间的整数，默认为1).在线程调度时，调度程序选择一个拥 有最高优先级的处在就绪状态的线程运营.这种算法的问题是也许出现饥 饿现象：设想有一个低优先级的线程处在临界区中运营而高优先级的线程在 临界区外等待.由于前者优先级较低，它也许
14、不会被调度器选中从而高优先级 的线程也不得不浪费时间等待.为解决上述优先级反转问题，需要实现一种让出优先级的机制 (Priority Donation):提高拥有锁的低优先级线程的优先级以使它迅速完 毕临界区，不使其它较高优先级的线程等待太久.提高后的优先级称为有效优 先级，它可以不断变化.实际调度时就是以有效优先级为评判标准的.2 .方案SThread State类中增长两个表即Li n kedLi s t类，存放的对象是P r i orityQu e ue,即优先级队列对象。一个表用来记录该线程所占用资源的优先 队列r esou r cesIHave,另一个表用来记录该线程所想占有的资源的
15、优先队列 resou r ceIWant0 resourc e sIHa ve作为发生优先级反转时，捐献优先级 计算有效优先级的来源依据,res。urc elWant用来为线程声明得到资源做准 备。wait ForAccess()将需要等待获得资源的线程加入一个等待队列等待调度。g e tEffectiveP r iority ()计算有效优先级时,遍历等待队列中所用线程的 有效优先级，找出最大的优先级即可。3 .实现代码p u bli c void wa i t For A cce s s ( Priori t yQueu e w a i tQueue )wa i tQue u e.wait
16、Que ue.ad d (thi s .threa d);if (IwaitQueu e.t r ansferPriority)waitQ u e u e.l o ckHol d er. e f f ectiveP r io r i ty = e x piredEff ect i vePrio r i ty ;)publi c void acq u i re (Prio r i tyQueu e waitQ ueue)(waitQueue.waitQueue. r emove (t his . t h read);wai t Queue . Ioc kHo 1 der = this;wa i
17、t Queue.lo c kHolder. effec t ivePriority = exp i redE f f ectiveP r iori t y ;wa i tQu e u e . 1 oc k Holder.wa iters = wa i t Queu e;)pu b 1 ic in t g et E f f e ct i vePr i o r i t y()(if (ef f ecti v ePri o r ity != expiredEffectivePriority)。 return effe c tivePrio r i t y;e f feet i v e P ri o
18、r ity = p riority;if (wa i te r s = = null)retu r n effe ctivePrio r ity;fo r (It e rato r i = waiters.wa i tQ u eue.ite r a t o r (); i. h a s N ext();)(Threa d S t ate ts = g e tThre a dState (KT h re a d ) i.next ();i f (ts.pr iorityeffective Prior ity)(effec t i veP r ior i t y = t s.pr i ority;
19、)r e turn ef f ect i v e Prio r ity;)protec tedinteffecti vePriority = expired E f f ect i veP r io r i t y；p r otected static f i na 1 int e x piredE f f ec t ive Prior ity =- 1；目录实验平台4一 Projectl线程系统4Taskl.l 实现 KThread.join()41 . 要求42 .分析43 .方案44 .实现代码4Taskl.2利用中断提供原子性，直接实现条件变量61 . 要求62 .分析63 .方案74
20、 .实现代码7Taskl.3 实现 waitUntil91 . 要求92 .分析93 . 方案104 .实现代码10Taskl.4用条件变量，不使用信号量，实现同步发送接收消息，speak , listen121 . 要求122 .分析133 . 方案134 .实现代码14Taskl.5完成Priorityscheduler实现优先级调度161 . 要求162 .分析163 . 方案174 .实现代码17323232三Project2多道程序设计protected P riori t yQu eue wait e r s = null;1.实1.2.求析案现 .322.3.4.isk：3233
21、代码36411.2.实2.3.(求析案现 .41423.4.42代码43isk；511.2.3.实一求折案现5151514.代码S3publ i c KThrea d n extT h re a d ()(L i b.a s sert Tru e (Ma c hine.in t er r upt ( ) .disabled();oif (pi c kNextTh r ea d() = n u II)。 return null;oKThread t hre a d = p i ckNextTh r ead ().t h re a d ;getThreadS t ate(thre a d) . a
22、cqui r e(this);ret urn t hread;)pro t ec t ed Threads t ate pickNextThrea d()(i f (wai t Queue.i s Empt y () return n ull;0T h r ead Sta t e to P ick = g etThread S t a t e(KTh re a d)wai t Q ueue.getF i rst ();for (Ite r at or i = wa i tQueue.iter a to r (); i.has N e xt ();)T h rea d S ta t e t s
23、= g e tThr e a d State (K T hr e a d ) i . nex t()；if (ts . g e t Eff e cti v e P ri o ri t y() to P ick . ge t E f f ectivePr i orityO)toP i ck = ts;)r etu r n t oPic k ;)L inke d L i s t wa i t Qu eu e = new LinkedL i st();ThreadSta te lockHo 1 de r = null ;Task 1 . 6.规定用以上实现的线程互斥/同步机制解决一个过河问题。成人和
24、小孩都试图从。a hu出发到moloka i。一只船只可以携带最多 两个小孩或一个成人（但不能是一个小孩和一个成人）。船上可划回瓦胡岛，但 这么做需要一个引航员。安排一个能让所有人到m。1 okai岛的解决方案.分析需要记录的信息：1）。岛上大人/小孩的人数2） M岛上大人/小孩的人数3）船的位置（在0岛还是M岛）4）船的状态（空/半满/全满）（半满指只有一个小孩，全满指有两个小孩或 一个大人）初始状态：1）大人和小孩都在。岛上2）船在。岛3）船为空对于大人比较简朴.若满足以下条件则独自乘船过河（每个大人过且仅过 一次河，线程即告结束）,否则（在。岛）等待：1）。岛上只有一个小孩或没有小孩2）
25、船在。岛3）船为空对于小孩，分以下5种情况讨论1）某小孩在0岛，船在。岛，船为空，0岛上的小孩数大于等于2:该 小孩上船等此外一个小孩上船后，两人一起划船过河到M2）某小孩在。岛，船在。岛，船为空，0岛上没有大人：该小孩上船过 河3）某小孩在。岛，且不属于以上三种情况：等待4）某小孩在M岛，船在0岛：等待5）当所有的大人运完了之后开始运大人，当运过去两个大人后Q岛出现了 两个孩子，这个时候这两个孩子划船过河，即使此时大人还没有完全被运 送完全。返程:只有小孩可以有返程路线，大人返程没故意义。1 .方案使用三个锁变量保证互斥，三个条件变量保证同步。2 .实现代码package nachos .
26、t hreads ;impo r t nach o s .ag .BoatG r ader;pu b 1 ic class Boat（3 t ati c BoatGrade r bg;4 t atic i n t ch i IdrenOnO a h u=0 ;5 t a t ic i nt c hild r enOnMolo kai=0;st a tic int adu 1 t OnOa hu =0;6 t atic int adul t OnMolokai=0;5 ta t ic i nt p i 1 ot = 0;static boolean over;static Lock 1 ock
27、1;st atic Condi t io n childre nWaitOnOahu;static Loc k I o c k2 ;s t a t i c Co nd iti on a dul t W a itOnOahu;static Lock lock3;st a tic Conditi o n childrenReadyOnMolok a i;public st a tic void begin( in t a d ults, int chi 1 d r en, BoatGra der b)obg = b;Joek 1 = new Loc k ();。child r en Wa i tO
28、nOa hu = new Condition(loc k 1);lock 2 = new Lock();。a d u 1 tWa i tOnO a hu = new Condition ( 1 ock2);Jo c k 3 = new Lo c k();children ReadyOn Molo k a i = new Condition(lock3);。 f o r ( i nt i= 0;iadult s; i + +)(“new KTh r ead(newAdult(childrenWaitOnOa hu,adu 1 tWaitOnO a h u,children Rea dyOnMol
29、o k a i).se t Name( adult) .fork ();4or(i n t i =0;i 1)(1 ockl.acquire();。chi 1 drenWaitOnOah u .wake ();pilot = 1;bg.Chi 1 dRowToMoloka i ();ac hildre n OnO a hu -。childre nOnM o 1 okai + +;。 oo loc k l.re 1 e a se ();。Iock3.acquire();。 childre n Rea d yO n M o Io k ai.sleepO; o0|ock3 . releas e ()
30、;00 Jelse(。Jock2.a c quireQ;”adu 1 tWa itOnOa h u.wake();oJock2.relea s e ();bg . Ad ul t RideT oMolo kai ();。lockl.acqu i re();chi 1 dre nWa i tOnOahu.s lee p();0000lockl.relea se ();ocontinue;6 )。e Ise(if(a d ultOnOahu! = 0)。 bg.ChildR i d eToMo 1 o k a i();ochild r enOnOahu;。c hildrenOnMolo kai+;
31、。Iock3 .acqu i r e();。0chiIdr e n ReadyO n Molokai.wake();Jo c k3. r el e a se();oooo|ock3.acq u i r e();。30chiI d ren Read yOnMol o k ai.s lee p();。 。1 o c k3.relea se();0)e 1 seooolock3. a c q u i re();000o v e r=true;。 bg.ChildRideToMolokai();o 。 ch i IdrenOnOahu -;。0chi 1 d renO n Molo k a i + +
32、;。hildrenReady OnMo 1 okai.wa keAII();o。1 ock3 . relea s e();oo。if(ov e r= = t ru e) b rea k; )oelse(pilot = 3 ;a bg.ChildRowToOahu();0chiId r enOnOa hu + +;children O n Molo kai-;cont i nue;s tat i c vo i d S a m p lelt i ne r ary ()(-Sys t em . out . printin ( n * *Everyone pi 1 es on the boat and
33、 goes to Molokai * *);bg.Adul t RowToMolo k a i ();obg.Child R ideT o Mol oka i(); b g . Ad u 1 tRideToMolo kai();。bg.ChildRi d eToM o lokai();)p r ivate static cl a s s Child im plement s Run nable(Ch i Id ( Cond i t ion c hi 1 drenWaitOnOahu,Conditi on ad u ItWaitO n Oahu,Condition chil d r enR ea
34、dyO n Moloka i)(。 th i s.loca t i o n_now = I o catio n _now;othis.child r en Wai t O nOa hu=chi 1 drenWaitOnOa hu ;0 thi s .ad u 1 tWa i tOn Oahu=adu 1 tWaitO n O a hu;t his.c h i I d r e nReadyOnM o lokai=childre n Re a d yOnMoloka i；)0pu b 1 i c void run()(oChildl t inerary ();)p riv a te int S t
35、 atu s;p r i vate int Io cation_now;/ 1:0a h u,2:Mo 1 okaiprivat e Co n d i tion chi IdrenWaitOnOah u ;priva t e Cond i tion adu 1 tWaitOnO a hu ;pr i vate C ond i tion c hi 1 d r en ReadyOn Molo k a i;)pr i vate static clas s Adult imp 1 em e n t s Ru nnab 1 e(Adult(Con d ition ch i Id r enWaitOnO
36、a huzCo n ditio n ad u ItWaitO n Oahu,C ondi tion ch i 1 d re n Ready On Molokai) th i s.chi 1 drenWai t OnOahu=ch i IdrenWa i tOnOa hu;。ahis.adultW a itOnO ahu =adultWa i t OnOahu;-this, chi Idre nRead y OnMolokai = childre n ReadyOnM oI o ka i；。p u blic void r u n ()(Adu 11Itinerary ();)p r i v at
37、e Co n d i t ion ch i Id r enWaitO n O a h u ;opriv ate C ond i tion a d ultWaitOnO ahu;opri vateCondition child r en R ead y OnMolokai;)三Project2多道程序设计Task2 . 11 .规定实现六个系统调用 creat, open, read, write, close , u n link.分析系统共提供了七个系统调用:halt （停机，已经提供），ere at （创建并打开 磁盘文献）,。p e n （打开磁盘文献），read （读10,可以是磁盘或
38、屏幕write （写。），dose （关闭10）, unlink （删除磁盘文献）。要保证如下几点：1）稳定性，不能由于一个进程的非法系统调用就使操作系统崩溃，而应当 返回错误代码。2） halt调用只能由第一个进程（roo t process）执行。3）系统调用需要读写内存时，通过readVirtualMemo r y和writ eV i rtualMemory 进行。4）文献名以null结尾，不超过256字符。5）假如系统调用犯错，应返回-1。6）为每个打开的10文献分派一个 文献描述符”，用整数表达.每个 进程最多可以拥有16个。 其中0和1应分派给标准输入和标准输出（即屏幕），这由Sy
39、nch Console类管理。不同进程可以用相同的文 献描述符解决不同的文献。7） Na c ho s已经提供了一个简朴的文献系统Fil e Sys t e m（Ma chi ne 包中），通过T hread ed Kern el. f il e S yst e m 访问。8）系统不需要考虑文献访问的互斥等问题。3.方案1） create系统调用为了实现文献描述符”，为每个进程开一张大小为16的数组（本地描述符表），下标为描述符编号，内容为文献对象（Open File类型, 描述符未使用为null）.止匕外，需要一个全局的Hash t able （全局文献 表），key为文献名，v a lue
40、为该文献名被多少个进程打开。在Creat系统调用中，一般进行如下操作：a）用 r eadVirtualMemoyString 读取文献名b）通过Us e rKerneLfileS y s t em.op e n打开文献（第二个参数为 true表达创建新文献）c）维护本地描述符表（返回一个内容为null的项目的下标作为描 述符，将文献对象填入）d）维护全局文献表（假如全局表中没有此文献名，将（文献名，1） 放入，否则将本来的元组的val u e加1）e）返回文献描述符2） open系统调用在0 p en系统调用中进行如下操作：a）从内存读取文献名b）通过User Kern a I. f ileS
41、ys t em . ope n打开文献（第二个参数 为 f a 1 s e）c）维护本地描述符表d）维护全局文献表e）返回文献描述符3） re ad系统调用Read系统调用的三个参数依次为：文献描述符，写入的内存地址,读取的字节数。在Read系统调用中进行如下操作:a）从本地描述符表中得到文献对象b）通过Op e nFile . rea d读取文献内容c）将文献内容写入内存d）返回写入内存的字节数4） w r ite系统调用Write系统调用的三个参数依次为：文献描述符，读内存的地址，写 入文献的字节数.在Write系统调用中进行如下操作：a）从本地描述符表中得到文献对象b）访问内存，得到要写
42、入文献的内容c）通过 Op e nF i I e .w r it e写文献d）返回写入文献的字节数5） close系统调用Cl o se系统调用的唯个参数为文献描述符.在C 1 ose系统调用中 进行如下操作：a）从本地描述符中得到文献对象b）通过Op e nF i Ie . close关闭文献c）从本地描述符表中移出文献对象d）从全局文献表中移出文献名的引用（若value为L将其中的元组删除，否则将value减1）e）返回06） unlink系统调用一般地，在Un 1 i nk调用中只需读取文献名并执行fileSyst e m.rem ove方法删除文献即可。但是，一个文献也许被多个进程打开
43、而不能立即删 除，必须等所有打开这个文献的进程都关闭该文献后才干删除。因此，在 Unlink调用中还要检查文献名在全局文献表中的情况:若在全局文献表中不 存在,则立即删除。否则，将文献名添加到删除队列中。这样，在C 1。s e系 统调用中还要增长如下内容:若文献关闭后它在全局文献表中已经不存在且 文献名在删除队列中，则此时执行删除文献操作，并将文献从删除文献中移出。7） halt系统调用调用Ma c hine.h a It之前先判断系统中是否尚有进程在执行，若没有 则停机。8)健壮性以上系统调用只是在一般情况下函数的执行流程。为了提高系统的健壮 性，在系统调用中还要进行下列错误检查(-1表达犯错)：a)文献名长度不得超过25 6字符，不得具有非法字符或空。b)打开，创建文献时，局部描述符表不能满，文献名不能在删除队列中.c) f ileSys t em的操作返回值必须对的。d) re a dV i rtualMemo r y 和 wr i teVi r tu alMemory 的返回值必须 对的。4.实现代码private i n t handleCrea t e(String