操作系统-体验Nachos下的并发程序设计

1、精选优质文档-倾情为你奉上实验二 体验Nachos下的并发程序设计一、实验人员： 二、实验目的：实现Nachos的同步机制：锁和条件变量，并利用这些同步机制实现一些工具类。三、实验内容：1.实现锁机制和条件变量2.实现一个线程安全的表结构3.实现一个大小受限的缓冲区四、实验步骤：1.实现锁机制和条件变量1.1用Thread:Sleep实现锁机制和条件变量相关代码：Synch-sleep.h#include copyright.h #include thread.h #include list.h #include system.h class Lockpublic: Lock(char* de

2、bugName); /initialize lock be FREE Lock(); char* getName() return name; /debugging assist void Acquire(); /wait until the lock is FREE, then set it to BUSY void Release(); /set lock to be FREE, waking up a thread waiting /in Acquire if necessary bool isHeldByCurrentThread(); / true if the current th

3、read / holds this lock. Useful for checking in Release, and in / Condition variable ops below private: char* name; Thread *LockedThread; bool LockValue; List *queue; class Condition public: Condition(char* debugName); /initialize condition to no one waiting Condition();/析构函数 char* getName() return n

4、ame; void Wait(Lock *conditionLock); /release the lock, relinquish the CPU until signaled,then re-acquire the lock void Signal(Lock *conditionLock); /wake up a thread, if there are any waiting on the condition void Broadcast(Lock *conditionLock); /wake up all threads waiting on the condition private

5、: char* name; List *queue; Synch-sleep.cc#include copyright.h#include system.h#include thread.h#include list.h#include synch-sleep.hLock:Lock(char* debugName) /initialize lock be FREE name = debugName; queue = new List; LockedThread = new Thread(LockedThread); LockValue = 0; Lock:Lock() /析构函数 delete

6、 queue; delete LockedThread; void Lock:Acquire() /wait until the lock is FREE, then set it to BUSY IntStatus oldLevel = interrupt-SetLevel(IntOff); while ( LockValue ) queue-Append(void *)currentThread); /put currentThread at the end of the list currentThread-Sleep(); LockedThread = currentThread; L

7、ockValue = 1; (void) interrupt-SetLevel(oldLevel); void Lock:Release() /set lock to be FREE, waking up a thread waiting in Acquire if necessary Thread *thread; ASSERT( isHeldByCurrentThread() ); IntStatus oldLevel = interrupt-SetLevel(IntOff); LockedThread = NULL; thread = (Thread *)queue-Remove();

8、if ( thread != NULL ) scheduler-ReadyToRun(thread);LockValue=false; (void) interrupt-SetLevel(oldLevel); bool Lock:isHeldByCurrentThread() / true if the current thread holds this lock. Useful for checking in Release, /and in Condition variable ops below if ( LockedThread = currentThread & LockValue

9、) return true; else return false; Condition:Condition(char* debugName) /initialize condition to no one waiting name = debugName; queue = new List; Condition:Condition() /析构函数 delete queue; void Condition:Wait(Lock *conditionLock) /release the lock, relinquish the CPU until signaled,then re-acquire t

10、he lock ASSERT(conditionLock-isHeldByCurrentThread(); IntStatus oldLevel = interrupt-SetLevel(IntOff); queue-Append(void *)currentThread); conditionLock-Release(); currentThread-Sleep(); conditionLock-Acquire(); (void) interrupt-SetLevel(oldLevel); void Condition:Signal(Lock *conditionLock) /wake up

11、 a thread, if there are any waiting on the condition Thread *thread; ASSERT( conditionLock-isHeldByCurrentThread() ); IntStatus oldLevel = interrupt-SetLevel(IntOff); thread = (Thread *)queue-Remove(); if ( thread != NULL ) scheduler-ReadyToRun(thread); (void) interrupt-SetLevel(oldLevel); void Cond

12、ition:Broadcast(Lock* conditionLock) /wake up all threads waiting on the condition Thread *thread; ASSERT( conditionLock-isHeldByCurrentThread(); IntStatus oldLevel = interrupt-SetLevel(IntOff); thread = (Thread *)queue-Remove(); while ( thread != NULL ) scheduler-ReadyToRun(thread); thread = (Threa

13、d *)queue-Remove(); (void) interrupt-SetLevel(oldLevel); 1.2用Semaphore实现锁机制和条件变量相关代码：Synch-sem.h#ifndef SYNCH_SEM_H#define SYNCH_SEM_H#include copyright.h #include thread.h #include list.h class Semaphore public: Semaphore(char* debugName, int initialValue); /设置信号量初值 Semaphore(); /析构函数 char* getName

14、() return name; /debugging assist void P(); /waits until value 0, then decrement void V(); /increment, waking up a thread waiting in P() if necessary /均为原子操作 private: char *name; /useful for debugging int value; /信号量的值，均为非负的 List *queue; /threads waiting in P() for the value to be 0 ; class Lock pub

15、lic: Lock(char* debugName); /initialize lock to be FREE Lock(); /析构函数 char* getName() return name; /debugging assist void Acquire(); /wait until the lock is FREE, then set it to BUSY void Release(); /set lock to be FREE, waking up a thread waiting /均为原子操作 bool isHeldByCurrentThread(); / true if the

16、current thread / holds this lock. Useful for checking in Release, and in / Condition variable ops below. private: char* name; /for debugging Thread *LockedThread; bool LockValue; Semaphore *semaphore; int threadnum; ; class Condition public: Condition(char* debugName); /初始化条件变量为no one waiting Condit

17、ion(); /析构函数 char* getName() return name; /debugging assist void Wait(Lock *conditionLock); /release the lock, relinquish the CPU until signaled, /then re-acquire the lock /为原子操作 void Signal(Lock *conditionLock); /wake up a thread, /if there are any waiting on the condition void Broadcast(Lock *cond

18、itionLock); /wake up all threads waiting on the condition private: char* name; Semaphore *semaphore; int threadnum; ; #endifSynch-sem.cc#include copyright.h #include synch-sem.h #include system.h Semaphore:Semaphore(char* debugName, int initialValue) name = debugName; value = initialValue; queue = n

19、ew List; Semaphore:Semaphore() delete queue; void Semaphore:P() IntStatus oldLevel = interrupt-SetLevel(IntOff);/禁用中断 while (value = 0) / semaphore not available queue-Append(void *)currentThread);/ so go to sleep currentThread-Sleep(); value-; / semaphore available, / consume its value (void) inter

20、rupt-SetLevel(oldLevel);/恢复中断 void Semaphore:V() Thread *thread; IntStatus oldLevel = interrupt-SetLevel(IntOff);/禁用中断 thread = (Thread *)queue-Remove(); if (thread != NULL) / make thread ready, consuming the V immediately scheduler-ReadyToRun(thread); value+; (void) interrupt-SetLevel(oldLevel);/恢复

21、中断 Lock:Lock(char* debugName) /initialize lock to be FREE name = debugName; LockedThread = new Thread(LockedThread); LockValue = 0; threadnum = 0; semaphore = new Semaphore(locksem,0); Lock:Lock() /析构函数 delete LockedThread; delete semaphore; void Lock:Acquire() /wait until the lock is FREE, then set

22、 it to BUSY ASSERT(!isHeldByCurrentThread() ); /check the lock if FREE while ( LockValue ) semaphore-P(); LockedThread = currentThread; LockValue = 1; void Lock:Release() /set lock to be FREE, waking up a thread waiting ASSERT( isHeldByCurrentThread(); /check the lock if BUSY LockedThread = NULL; Lo

23、ckValue = 0; semaphore-V(); bool Lock:isHeldByCurrentThread()if(LockedThread=currentThread)&LockValue)return true;elsereturn false; Condition:Condition(char* debugName) /initialize condition to no one waiting name = debugName; semaphore = new Semaphore(Conditionsem,0); Condition:Condition() delete s

24、emaphore; void Condition:Wait(Lock* conditionLock) /release the lock, relinquish the CPU until signaled,then re-acquire the lock ASSERT( conditionLock-isHeldByCurrentThread(); /check the lock if held conditionLock-Release(); semaphore-P(); threadnum+; conditionLock-Acquire(); void Condition:Signal(L

25、ock *conditionLock) /wake up a thread,if there are any waiting on the condition ASSERT( conditionLock-isHeldByCurrentThread(); if ( threadnum 0 ) semaphore-V(); threadnum-; void Condition:Broadcast(Lock *conditionLock) /wake up all threads waiting on the condition ASSERT( conditionLock-isHeldByCurre

26、ntThread(); while ( threadnum 0 ) semaphore-V(); threadnum-; 1.4用锁机制和条件变量修改双向有序链表修改了dllist.h , dllist.cc，加入了锁和条件锁，为了方便测试，在threadtest.cc里加入一个变量flag，flag=0时不使用锁，flag=1时使用锁。修改部分主要为dllist.cc的Remove和SortedInsert函数void *DLList:Remove(int *keyPtr) / remove from head of listDLLElement *element;if(flag)lock-

27、Acquire();if (IsEmpty()if(flag) lock-Release();return NULL;void *retitem;element=first;*keyPtr=first-key;if (err_type=1)currentThread-Yield();retitem=element-item;if (first=last)first=NULL;last=NULL;elseif (err_type=1)currentThread-Yield();first=element-next;first-prev=NULL;delete element;if(flag)lo

28、ck-Release();return retitem;void DLList:SortedInsert(void *item, int sortKey) / routines to put/get items on/off list in order (sorted by key)DLLElement *insertItem=new DLLElement(item,sortKey);DLLElement *ptr=first;if(flag)lock-Acquire();if (IsEmpty()first=insertItem;if (err_type=2)currentThread-Yi

29、eld();last=insertItem;elsefor (;ptr!=NULL; ptr=ptr-next)if (ptr-keysortKey) break;if (err_type=3)currentThread-Yield();if (ptr=NULL)insertItem-prev=last;last-next=insertItem;last=insertItem;last-next=NULL;elseif (ptr=first)insertItem-next=first; first-prev=insertItem;first=insertItem;first-prev=NULL

30、;elseptr-prev-next=insertItem;insertItem-prev=ptr-prev;if (err_type=4)currentThread-Yield();insertItem-next=ptr;ptr-prev=insertItem;if(flag)lock-Release();2.实现一个线程安全的表结构相关代码：Table.h#include synch-sem.hclass Table public: / create a table to hold at most size entries. Table(int size); Table(); / allo

31、cate a table slot for object. / return the table index for the slot or -1 on error. int Alloc(int *object); / return the object from table index index or NULL on error. / (assert index is in range). Leave the table entry allocated / and the pointer in place. void *Get(int index); / free a table slot

32、 void Release(int index,int t); private: / Your code here. Lock *tablelock; int *table; int *value; int tablesize;/the size of the table;Table.cc#include Table.h #include thread.h#include system.hextern int flag;Table:Table(int size) / create a table to hold at most size entries. tablesize = size; t

33、ablelock = new Lock(Tablelock); table =new int*size;value =new intsize;for(int i=0;iAcquire(); for ( i=0; iYield(); tablei=object; valuei=1;if(flag) tablelock-Release();return i; if(flag) tablelock-Release(); return -1; void *Table:Get(int index) if ( index0 & indexAcquire(); if ( index=0 & indexRel

34、ease(); 3.实现一个大小受限的缓冲区相关代码:BoudedBuffer.hclass BoundedBuffer public:BoundedBuffer();BoundedBuffer(); / create a bounded buffer with a limit of maxsize bytes void Read(char *data, int size,int t); / write size bytes from data into the bounded buffer. / (size may be greater than maxsize) void Write(ch

35、ar *data, int size,int t); private:int buffersize;Lock *bufferlock;Condition *bufferEmpty;Condition *bufferFull;char *buffer;int readout;int writein;int num;BoundedBuffer.cc#include copyright.h#include synch-sleep.h#include BoundedBuffer.h#include system.hextern int flag;BoundedBuffer:BoundedBuffer(

36、) bufferlock=new Lock(bufferlock); bufferEmpty=new Condition(readlist); bufferFull=new Condition(writelist);buffersize=10;buffer=new charbuffersize;readout=0;writein=0;num=0;BoundedBuffer:BoundedBuffer() delete bufferlock; delete bufferEmpty; delete bufferFull;delete buffer;void BoundedBuffer:Read(c

37、har *data,int size,int t)if(flag)bufferlock-Acquire();for(int i=0;iWait(bufferlock);i=0;elseprintf(the buffer is empty,cant read!n);return;elsedatai=bufferreadout;printf(n read buffer%d by thread %d,readout,t);num-;readout=(readout+1)%buffersize;if(flag)bufferFull-Broadcast(bufferlock);if(flag)buffe

38、rlock-Release();void BoundedBuffer:Write(char *data,int size,int t)if(flag)bufferlock-Acquire();for(int i=0;iWait(bufferlock);i=0;elseprintf(nbuffer is full cant write!);return;elsebufferwritein=datai;printf(n write buffer%d by thread %d,writein,t);writein=(writein+1)%buffersize;num+;if(flag)bufferE

39、mpty-Broadcast(bufferlock);if(flag)bufferlock-Release();4.修改threadtest.cc#include copyright.h#include system.h#include math.h#include thread.h#include stdio.h#include dllist.h#include Table.h#include BoundedBuffer.hint testnum = 1,threadnum=1,n,err_type=0,flag=0;DLList *dllist; Table *table;BoundedB

40、uffer *buffer;extern void Insert(int ,int ,DLList*);extern void Remove(int ,int ,DLList*);voidSimpleThread(int which) int num; for (num = 0; num Yield(); voidDLListThread(int t)Insert(t,n,dllist);Remove(t,n,dllist);void BufferThread(int t)char str10;char *p=str;char *q=str;if(t%2)=0)buffer-Write(p,10,t);elsebuffer-Read(q,10,t);printf(n);void TableThread(int t)int *p510; int i