操作系统课程设计

1、操作系统课程设计报告2009-12-25文件组织：以上代码位于code文件夹输出位于output文件夹。目录一、内核线程调度策略设计 .3设计目标： .3设计背景： .31.1为Nachos添加按动态优先数调度策略 .3设计算法说明： .4设计内容和步骤： .4新的设计的实验内容和步骤： .7以上设计实验输出结果的分析： .8二、Hoare条件变量的设计与实现 .8设计目标： .8设计背景： .81.1实现Hoare样式的管程 .10设计算法说明： .10设计内容和步骤： .10新的设计的实验内容和步骤： .18以上设计实验输出结果的分析： .18三、实现系统调用与内存管理 .18设计目标：

2、.18设计背景： .181.1 实现fork，exec，exit与join系统调用 .19设计算法说明： .19设计内容和步骤： .201.2 实现内存管理 .24设计算法说明： .24设计内容和步骤： .25以上设计实验输出结果的分析： .38四、文件系统 .40设计目标： .40设计背景： .401.1实现二级索引 .40设计算法说明： .40设计内容和步骤： .40新的设计的实验内容和步骤： .42以上设计实验输出结果的分析： .42本设计的创新点： .43本设计存在的问题和没达到的功能： .43设计的体会、收获和总结 .43一、内核线程调度策略设计设计目标：在Nachos系统中实现按优

3、先数调度线程研究各种调度策略算法的实现，分析各种调度算法的性能。设计背景：从Nachos系统的基本内核./threads/scheduler.cc文件中可以看出Nachos系统的基本内核实现了先进先出的调度策略。调度类Scheduler管理着一个就绪队列list。它的成员函数ReadyToRun (current Thread)将当前线程挂入该队列的队尾：Scheduler:ReadyToRun (Thread *thread)DEBUG('t', "Putting thread %s on ready list.n", thread->getName

4、();thread->setStatus(READY);readyList->Append(void *)thread);它的另一成员函数FindNextToRun()则从list队首摘出一个就绪线程准备运行： Thread *Scheduler:FindNextToRun ()return (Thread *)readyList->Remove();这从基本内核执行的输出中可以得到验证：* thread 0 looped 0 times* thread 1 looped 0 times* thread 0 looped 1 times* thread 1 looped 1

5、times* thread 0 looped 2 times* thread 1 looped 2 times* thread 0 looped 3 times* thread 1 looped 4 times1.1为Nachos添加按动态优先数调度策略设计算法说明：采用静态优先数先给定一个线程的基本优先级，该优先数可以在创建一个线程的时候指定，范围在0到100之间，数值越小优先级越低。 动态优先数计算方法为：初始值 = 静态优先数执行线程每Tick + 10就绪线程每Tick - 1唤醒线程 - 5当执行线程动态优先数为0时重新计算就绪队列动态优先数： 按降序调整就绪队列优先级，从就绪队列首

6、选择新的执行线程。 设计内容和步骤：1、2、 将thread目录下的所有文件拷贝到lab2中，并修改其Makefile.local文件。 INCPATH += -I./lab2 -I./machine 在Thread类中增加一个变量用于记录优先级并增加相应的构造函数与访问函数。void setPriority(int p)this->priority = p;void increPriority(int in)if(this->priority + in < Max && this->priority + in > Min)elseint getP

7、riority()return priority;private:int priority;Thread:Thread(char* threadName,int p)name = threadName;stackTop = NULL;stack = NULL;status = JUST_CREATED;priority = 0;priority = p; if(in > 0) else this->priority = Min; this->priority = Max; this->priority += in;#ifdef USER_PROGRAMspace = N

8、ULL;#endif3、 在Scheduler类中增加一个方法用于为整个就绪队列中的所有线程改变优先级void ThreadLowPri(_int arg) Thread *t = (Thread *)arg; t->increPriority(-1);Scheduler:AddAll()readyList->Mapcar(VoidFunctionPtr) ThreadLowPri);4、 在interrupt:OneTick中改变优先级scheduler->AddAll();currentThread->increPriority(10);if(currentThre

9、ad->getPriority() = Max)yieldOnReturn = TRUE;5、 更改相应的加入就绪队列与从就绪队列中取一个线程运行的方法svoidScheduler:ReadyToRun (Thread *thread)DEBUG('t', "Putting thread %s on ready list.n", thread->getName();thread->setStatus(READY);readyList->SortedInsert(void *)thread,thread->getPriority(

10、);/-/ Scheduler:FindNextToRun/ Return the next thread to be scheduled onto the CPU. If there are no ready threads, return NULL. Thread is removed from the ready list. / Side effect:/-Thread *Scheduler:FindNextToRun ()Thread* thread = (Thread *)readyList->Remove();if(thread) thread->increPriori

11、ty(-5);return thread;6、 修改Thread:Yield()方法，使得在选取下一个线程运行的时候包括当前线程voidThread:Yield ()Thread *nextThread;IntStatus oldLevel = interrupt->SetLevel(IntOff);ASSERT(this = currentThread);DEBUG('t', "Yielding thread "%s"n", getName();scheduler->ReadyToRun(this);nextThread =

12、 scheduler->FindNextToRun();if (nextThread != NULL) scheduler->Run(nextThread);(void) interrupt->SetLevel(oldLevel);7、 修改测试类voidSimpleThread(_int which)int num;for (num = 0; num < 5; num+) interrupt->SetLevel(IntOff);printf("* thread %d looped %d timesn", (int) which, num);i

13、nterrupt->SetLevel(IntOn);printf("thread %d exit-n",(int) which);/-/ ThreadTest/ Set up a ping-pong between two threads, by forking a thread/ to call SimpleThread, and then calling SimpleThread ourselves./-voidThreadTest()DEBUG('t', "Entering SimpleTest");Thread *t1 =

14、new Thread("forked thread1",10);Thread *t2 = new Thread("forked thread2",20);Thread *t3 = new Thread("forked thread3",30);Thread *t4 = new Thread("forked thread4",40);Thread *t5 = new Thread("forked thread5",50);t1->Fork(SimpleThread, 1);t2->Fo

15、rk(SimpleThread, 2);t3->Fork(SimpleThread, 3);t4->Fork(SimpleThread, 4);t5->Fork(SimpleThread, 5);新的设计的实验内容和步骤：重新执行./lab2中的make然后运行，运行结果如下：* thread 1 looped 0 times* thread 1 looped 1 times* thread 1 looped 2 times* thread 2 looped 0 times* thread 2 looped 1 times* thread 2 looped 2 times*

16、thread 2 looped 3 times* thread 2 looped 4 timesthread 2 exit- * thread 3 looped 0 times* thread 3 looped 1 times* thread 3 looped 2 times* thread 4 looped 0 times* thread 4 looped 1 times* thread 4 looped 2 times* thread 4 looped 3 times* thread 4 looped 4 timesthread 4 exit- * thread 1 looped 3 ti

17、mes* thread 1 looped 4 timesthread 1 exit- * thread 3 looped 3 times* thread 3 looped 4 timesthread 3 exit-* thread 5 looped 0 times* thread 5 looped 1 times* thread 5 looped 2 times* thread 5 looped 3 times* thread 5 looped 4 timesthread 5 exit-No threads ready or runnable, and no pending interrupt

18、s.Assuming the program completed.Machine halting!Ticks: total 400, idle 10, system 390, user 0Disk I/O: reads 0, writes 0Console I/O: reads 0, writes 0Paging: faults 0Network I/O: packets received 0, sent 0Cleaning up.以上设计实验输出结果的分析：主线程首先执行后放弃CPU，T1优先级最低排在队首先被选中。主线程由于优先级最高被排在队列尾。T1线程放弃CPU，当前T2在队首先被选中

19、。这样依次进行，直到所有的线程招待结束。二、Hoare条件变量的设计与实现设计目标：在nachos中实现Hoare样式的条件变量使用Hoare样式的条件变量，实现生产者、消费者问题使用Hoare样式的条件变量，实现哲学家就餐问题，要求避免死锁与饥饿 设计背景：在nachos，已经实现了Mesa样式的管程，其类声明如下：class Condition public:Condition(char* debugName);Condition(); / initialize condition to / "no one waiting" / deallocate the condi

20、tionchar* getName() return (name); void Wait(Lock *conditionLock);/ these are the 3 operations on / condition variables; releasing the / lock and going to sleep are / *atomic* in Wait()void Signal(Lock *conditionLock); / conditionLock must be held by void Broadcast(Lock *conditionLock);/ the current

21、Thread for all ofprivate:char* name;List* queue; / threads waiting on the conditionLock* lock; / debugging aid: used to check correctness of / arguments to Wait, Signal and Broacast; / these operations其中最主要两个方法是wait与signal，其代码如下：void Condition:Wait(Lock* conditionLock)IntStatus oldLevel = interrupt-

22、>SetLevel(IntOff);ASSERT(conditionLock->isHeldByCurrentThread(); / check pre-condition if(queue->IsEmpty() ASSERT(lock = conditionLock); / another pre-conditionqueue->Append(currentThread); / add this thread to the waiting list conditionLock->Release(); / release the lockcurrentThread

23、->Sleep(); / goto sleepconditionLock->Acquire(); / awaken: re-acquire the lock(void) interrupt->SetLevel(oldLevel);void Condition:Signal(Lock* conditionLock)Thread *nextThread;IntStatus oldLevel = interrupt->SetLevel(IntOff);ASSERT(conditionLock->isHeldByCurrentThread();if(!queue->

24、IsEmpty() (void) interrupt->SetLevel(oldLevel); ASSERT(lock = conditionLock); nextThread = (Thread *)queue->Remove(); scheduler->ReadyToRun(nextThread); / wake up the thread lock = conditionLock; / helps to enforce pre-condition从其中可以看出，在signal中，一个队列把另一个队列唤醒，只是把被唤醒的队列放在了就绪队列中，而从wait中也可以看出，一个

25、线程被唤醒之后，轮到它运行时，它还得去获得锁，而唤醒它的线程在离开管程之前，并没有释放锁，因此只有当唤醒线程运行完之后，被唤醒的线程才能去运行。但是，当一个线程被唤醒之后，这时候它运行的条件是一定满足的，而随着唤醒线程的运行，并且在重新获得锁的过程中，被唤醒线程运行的条件可能就已经失去了。因此，最好可以在一个线程被唤醒之后，就立刻让它运行，而让唤醒线程去等待。这就是Hoare样式的管程。1.1实现Hoare样式的管程设计算法说明：首先，要增加一个队列，用于唤醒进程去等待。当线程1把线程2唤醒之后 ，线程1立刻去等待。其次，在设计的过程中，把原来用于互斥进入管程的锁换成了信号量。这是因为当线程1

26、去唤醒线程2时，此时一定是线程1在运行，如果要让线程2去运行，就必须要让线程2获得锁。但是，锁必须由获得它的线程进行释放，因此线程1必须释放锁，但此时线程2会与别的线程进行竞争，最后不一定是线程2能获得锁。而使用信号量，可以让线程1去等待的时候并不去执行V操作，而是直接让线程2运行，此时别的进程或阻塞在条件变量中，或在唤醒等待队列中，或在管程外，最后运行的一定是线程2。可以由线程2与唤醒等待队列中最后退出管程的那个线程负责执行V操作。使用一个信号量next来实现唤醒等待队列，当一个线程在一个条件变量上wait时或当其退出管程时，优先去唤醒唤醒等待队列的线程，如果没有的话，就让一个等待在管程外的

27、线程运行。对于生产者消费者问题，采用两个条件变量full与empty来实现。对于哲学家就餐问题，采用的策略是让每次进入的哲学家数量比筷子数量少1，并且只有两边的筷子能同时拿起来的时候才可以去就餐，这样就可以避免死锁与饥饿。设计内容和步骤：修改threads/synch.h与threads/synch.cc，增加Hoare样式的条件变量的声明与定义。class HCondition public:HCondition(char* debugName);/ initialize condition to / "no one waiting"/ deallocate the co

28、nditionHCondition(); char* getName() return (name); void Wait(Semaphore *conditionLock,Semaphore* nextSema,int& count);void Signal(Semaphore *conditionLock,Semaphore* nextSema,int& count);private:char* name;List* queue; / threads waiting on the conditionSemaphore* lock; / debugging aid: used

29、 to check correctness of/ arguments to Wait, Signal and BroacastSemaphore* next;void HCondition:Wait(Semaphore* conditionLock,Semaphore* nextSema,int& nextCount) IntStatus oldLevel = interrupt->SetLevel(IntOff);ASSERT(nextCount >= 0);printf("%s waiting!n",currentThread->getNam

30、e();if(queue->IsEmpty() ASSERT(lock = conditionLock); / another pre-conditionASSERT(next = nextSema);queue->Append(currentThread); / add this thread to the waiting listprintf("now now now next count = %dn",nextCount);if(nextCount > 0) else (void) interrupt->SetLevel(oldLevel);v

31、oid HCondition:Signal(Semaphore* conditionLock,Semaphore* nextSema,int& nextCount)Thread *nextThread;IntStatus oldLevel = interrupt->SetLevel(IntOff);ASSERT(nextCount >= 0);if(!queue->IsEmpty() ASSERT(lock = conditionLock); ASSERT(next = nextSema); nextThread = (Thread *)queue->Remov

32、e(); printf("%s was wakedn",nextThread->getName(); scheduler->ReadyToRun(nextThread); / wake up the thread nextCount+; next->P(); conditionLock->V(); currentThread->Sleep(); / goto sleep next->V(); currentThread->Sleep(); / goto sleep lock = conditionLock; / helps to e

33、nforce pre-condition next = nextSema; nextCount-;(void) interrupt->SetLevel(oldLevel);2、在lab3中，增加生产者消费者问题的管程的实现，代码位于lab3/Ring.cc3、在lab3中，增加生产者消费者问题的测试类，代码位于lab3/myprocon.cc 4、 增加哲学家就餐问题的管程与测试的实现。其主要代码如下：/ ring.cc/实现了一个生产者消费者的管程extern "C" #include <stdio.h>#include "ring.h&quo

34、t;slot:slot(int id, int number)Ring:Ring(int sz)Ring:Ring() / Initialize the data members of the ring object. size = sz; cs = 0; nextCount = 0; in = 0; out = 0; buffer = new slotsize; /allocate an array of slots. conditionLock = new Semaphore("Condition Lock",1); next = new Semaphore("

35、;Next semaphore",0); full = new HCondition("full"); empty = new HCondition("empty"); if (sz < 1) fprintf(stderr, "Error: Ring: size %d too smalln", sz); exit(1); thread_id = id; value = number; extern int exit(int st);delete buffer; delete conditionLock; delete

36、next; delete full; delete empty;voidRing:Put(slot *message,_int which)conditionLock->P(); while(Full() printf(" >>>>>>>>>>>>>>>>>>>>>>>>>>>>>.inner Prodcuer %i is going to put a slot printf("full!n&qu

37、ot;); full->Wait(conditionLock,next,nextCount); whose number is %in",which,message->value);voidRing:Get(slot *message,_int which)conditionLock->P(); while(Empty() printf("inner Consumer %i is going to get a slotn",which); message->thread_id = bufferout.thread_id; message-&

38、gt;value = bufferout.value; out = (out + 1) % size; cs-; printf("empty!n"); empty->Wait(conditionLock,next,nextCount); bufferin.thread_id = message->thread_id; bufferin.value = message->value; in = (in + 1) % size; cs+; empty->Signal(conditionLock,next,nextCount); if(nextCount

39、> 0) else conditionLock->V(); printf("nextCOunt = %d",nextCount); next->V();printf("<<<<<<<<M<<<<<<<<<<<<<<<<<<<<<<. inner Consumer %i get a slot %in",which,message->value);int R

40、ing:Empty() int Ring:Full() #include <stdio.h>#include "copyright.h"#include "system.h"#include "ring.h"#define MAX_LENGTH 1#define PRO_COUNT 3#define CON_COUNT 3#define TIME 20Ring* myRing = new Ring(MAX_LENGTH);int slotId = 0,0,0,0,0;void producer(_int which)for

41、(int i = 0;i < TIME;i+) slot* s = new slot(which,slotIdwhich+); printf("Prodcuer %i is going to put a slot whose number printf("test for full in = %i,out = %i,currentSize = %in",in,out,cs); return (cs >= size); printf(" test for empty in = %i,out = %i,currentSize = %in"

42、;,in,out,cs); return (cs = 0); full->Signal(conditionLock,next,nextCount); if(nextCount> 0) else conditionLock->V(); printf("nextCOunt = %d",nextCount); next->V();is %in",which,s->value);myRing->Put(s,which); printf("Prodcuer %i put a slot whose number is %inn&q

43、uot;,which,s->value); printf("Prodcuer %i exit-",which);void consumer(_int which)void procon()#ifndef DP_H_#define DP_H_#include "synch.h"class DPpublic:DP(int _number); DP(); void pickup(int i); void putdown(int i); printf("All createn"); t = new Thread("consum

44、er1"); t->Fork(consumer, 1); t = new Thread("consumer2"); t->Fork(consumer, 2); DEBUG('t', "producer and consumer problem start!"); printf("producer and consumer problem start!n"); Thread *t = new Thread("producer1"); t->Fork(producer, 1)

45、; t = new Thread("producer2"); t->Fork(producer, 2); for(int i = 0;i < TIME;i+) printf("Consumer %i slot* s = new slot(0,0); printf("Consumer %i is going to get a slotn",which); myRing->Get(s,which); printf("Consumer %i get a slot whose number is %inn",whi

46、ch,s->value); exit-",which);void test(int i); void eat(int i); typedef enum stateeating,waiting,hungry,thinking State; State* state; HCondition* condition; int number; Semaphore* lock; Semaphore* next; int nextCount; private:#endif /* DP_H_ */#include "dp.h"DP:DP(int _number):numbe

47、r(_number),nextCount(0)DP:DP()void DP:pickup(int i)ASSERT(i >= 0 && i < number); statei = hungry; lock->P(); test(i); while(statei != eating) printf(">>>>>>>>>>>>>>>phi %i has pickup the forksn",i); conditioni->Wait(lock,next,nextCount); test(i); for(int i = 0;i < number;i+) delete condition; delete lock; delete next; delete conditioni; state = new Statenumber; condition = new HCondition*number; for(int i = 0;i < number;+i) lock = new Semaphore("lock",number - 1); next = ne