《操作系统》课程设计报告new

1、操作系统课程设计报告一、读者/写者的问题模拟实现读者/写者问题，是指保证一个 writer 进程必须与其他进程互斥地访问共享对象的同步问题。 读者写者问题可以这样的描述：有一群写者和一群读者，写者在写同一本书，读者也在读这本书，多个读者可以同时读这本书，但是只能有一个写者在写书，并且读者必优先，也就是说，读者和写者同时提出请求时，读者优先。当读者提出请求时，需要有一个互斥操作，另外需要有一个信号量 S 来确定当前是否可操作。 信号量机制是支持多道程序的并发操作系统设计中解决资源共享时进程间的同步与互斥的重要机制，而读者写者则是这一机制的一个经典范例。与记录型信号量解决读者写者问题不同，信号量机

2、制它增加了一个限制，即最多允许 RN 个读者同时读。为此，又引入了一个信号量 L,并赋予初值为 RN，通过执行 wait （L,1,1）操作来控制读者的数目，每当有一个读者进入时，就要执行wait（L,1,1）操作，使 L 的值减 1。当有 RN 个读者进入读后，L 便减为 0，第 RN+1 个读者要进入读 时，必然会因 wait（L,1,1）操作失败而堵塞。程序实例：#include #include #include #include #include #include #define MAX_PERSON 100#define READER 0 /读者#define WRITER 1 /

3、写者#define END -1#define R READER#define W WRITER typedef struct _PersonHANDLE m_hThread;/定义处理线程的句柄int m_nType;/进程类型（读写）int m_nStartTime;/开始时间int m_nWorkTime;/运行时间int m_nID;/进程号Person; Person g_PersonsMAX_PERSON;int g_NumPerson = 0;long g_CurrentTime= 0;/基本时间片数 int g_PersonLists = /进程队列1, W, 3, 5, 2,

4、 W, 16, 5, 3, R, 5, 2,4, W, 6, 5, 5, R, 4, 3, 6, R, 17,7,END,;int g_NumOfReading = 0;int g_NumOfWriteRequest = 0;/申请写进程的个数HANDLE g_hReadSemaphore;/读者信号HANDLE g_hWriteSemaphore;/写者信号bool finished = false; /所有的读完成/bool wfinished = false; /所有的写完成void CreatePersonList(int *pPersonList);bool CreateReader

5、(int StartTime,int WorkTime,int ID);bool CreateWriter(int StartTime,int WorkTime,int ID);DWORD WINAPI ReaderProc(LPVOID lpParam);DWORD WINAPI WriterProc(LPVOID lpParam);int main()g_hReadSemaphore = CreateSemaphore(NULL,1,100,NULL); /创建信号灯，当前可用的资源数为1，最大为100g_hWriteSemaphore = CreateSemaphore(NULL,1,1

6、00,NULL); /创建信号灯，当前可用的资源数为1，最大为100CreatePersonList(g_PersonLists); / Create All the reader and writersprintf(Created all the reader and writern 创建n);g_CurrentTime = 0;while(true)g_CurrentTime+;Sleep(300); / 300 msprintf(CurrentTime = %dn,g_CurrentTime);if(finished) return 0; / return 0;void CreatePe

7、rsonList(int *pPersonLists)int i=0;int *pList = pPersonLists;bool Ret;while(pList0 != END)switch(pList1)case R:Ret = CreateReader(pList2,pList3,pList0);/351,w452,523,654break; case W:Ret = CreateWriter(pList2,pList3,pList0);break;if(!Ret)printf(Create Person %d is wrongn,pList0); pList += 4; / move

8、to next person listDWORD WINAPI ReaderProc(LPVOID lpParam)/读过程Person *pPerson = (Person*)lpParam;/ wait for the start timewhile(g_CurrentTime != pPerson-m_nStartTime) printf(Reader %d is Requesting 等待n,pPerson-m_nID);printf(nn*n);/ wait for the write requestWaitForSingleObject(g_hReadSemaphore,INFIN

9、ITE); if(g_NumOfReading =0)WaitForSingleObject(g_hWriteSemaphore,INFINITE); g_NumOfReading+;ReleaseSemaphore(g_hReadSemaphore,1,NULL);pPerson-m_nStartTime = g_CurrentTime;printf(Reader %d is Reading the Shared Buffer等待n,pPerson-m_nID);printf(nn*n);while(g_CurrentTime m_nStartTime + pPerson-m_nWorkTi

10、me)printf(Reader %d is Exit退出n,pPerson-m_nID);printf(nn*n);WaitForSingleObject(g_hReadSemaphore,INFINITE);g_NumOfReading-;if(g_NumOfReading = 0)ReleaseSemaphore(g_hWriteSemaphore,1,NULL);/此时没有读者，可以写ReleaseSemaphore(g_hReadSemaphore,1,NULL);if(pPerson-m_nID = 4) finished = true; /所有的读写完成ExitThread(0)

11、;return 0;DWORD WINAPI WriterProc(LPVOID lpParam)Person *pPerson = (Person*)lpParam;/ wait for the start timewhile(g_CurrentTime != pPerson-m_nStartTime)printf(Writer %d is Requesting 请求进行写操作n,pPerson-m_nID);printf(nn*n);WaitForSingleObject(g_hWriteSemaphore,INFINITE);/ modify the writers real start

12、 timepPerson-m_nStartTime = g_CurrentTime;printf(Writer %d is Writting the Shared Buffer写内容n,pPerson-m_nID);while(g_CurrentTime m_nStartTime + pPerson-m_nWorkTime)printf(Writer %d is Exit退出n,pPerson-m_nID);printf(nn*n);/g_NumOfWriteRequest-;ReleaseSemaphore(g_hWriteSemaphore,1,NULL);if(pPerson-m_nID

13、 = 4) finished = true;/所有的读写完成ExitThread(0);return 0;bool CreateReader(int StartTime,int WorkTime,int ID)DWORD dwThreadID;if(g_NumPerson = MAX_PERSON)return false;Person *pPerson = &g_Personsg_NumPerson;pPerson-m_nID = ID;pPerson-m_nStartTime = StartTime;pPerson-m_nWorkTime = WorkTime;pPerson-m_nTyp

14、e = READER;g_NumPerson+;/ Create an New ThreadpPerson-m_hThread= CreateThread(NULL,0,ReaderProc,(LPVOID)pPerson,0,&dwThreadID);if(pPerson-m_hThread = NULL)return false;return true;bool CreateWriter(int StartTime,int WorkTime,int ID)DWORD dwThreadID;if(g_NumPerson = MAX_PERSON) return false;Person *p

15、Person = &g_Personsg_NumPerson;pPerson-m_nID = ID;pPerson-m_nStartTime = StartTime;pPerson-m_nWorkTime = WorkTime;pPerson-m_nType = WRITER;g_NumPerson+;/ Create an New ThreadpPerson-m_hThread= CreateThread(NULL,0,WriterProc,(LPVOID)pPerson,0,&dwThreadID);if(pPerson-m_hThread = NULL)return false;retu

16、rn true; 二、进程间通信与子进程使用管道进行父子进程间通信，程序首先判断参数是否合法，因为输入的字符将从父进程通过发送到子进程中。然后调用pipe函数创建父子进程用于通信的管道。使用fork函数创建子进程时，子进程会获得与父进程相同的资源，其中包括文件描述符信息。因此，调用fork函数须在pipe函数调用前。当父子进程通过管道进行通信时，files1为用于数据写入的文件描述符.因此,在子进程中,要读取管道中的数据可以调用read函数，而读取得文件描述符为files0。对于父进程而言，写入数据需要调用write函数，要写入的文件描述为files1。程序代码：#include #inclu

17、de int main(int argc,char* argv)int f_des2;int pid;char msgBUFSIZ;if(argc!=2)printf(Usage: %s messagen,argv0);return 1;if(pipe(f_des)=-1)perror(cannot create the IPC pipe);return 1;pid=fork();if(pid=-1)perror(cannot create new process);return 1;else if(pid=0)close(f_des1);if(read(f_des0,msg,BUFSIZ)=

18、-1)perror(child process cannot read data from pipe);return 1;elseprintf(in child process, receive message: %sn,msg);_exit(0);else close(f_des0);if(write(f_des1,argv1,strlen(argv1)=-1)perror(parent process cannot write data to pipe);return 1;elseprintf(in parent process, send message: %sn,argv1);wait

19、(NULL);_exit(0);return 0;三、进程多级调度模拟1.设置多个就绪队列，并给队列赋予不同的优先级数，第一个最高，依次递减。2.赋予各个队列中进程执行时间片的大小，优先级越高的队列，时间片越小。3.当一个新进程进入内存后，首先将其放入一个对列末尾，如果在一个时间片结束时尚未完成，将其转入第二队列末尾。4.当一个进程从一个对列移至第n个队列后，便在第n个队列中采用时间片轮转执行完。5.仅当时间片空闲时，才调度第二个队列中的进程。(1i-1)空闲时，才调度i，如果处理机正在第i队列中运行，又有新进程进入优先权较高队列，则新进程抢占处理机，将正在运行的进程放入第i队列队尾，将处理机

20、分给新进程。程序代码：#include #include #include typedef struct node /*进程节点信息*/ char name20; /*进程的名字*/ int prio; /*进程的优先级*/ int round; /*分配CPU的时间片*/ int cputime; /*CPU执行时间*/ int needtime; /*进程执行所需要的时间*/ char state; /*进程的状态，W就绪态，R执行态，F完成态*/ int count; /*记录执行的次数*/ struct node *next; /*链表指针*/ PCB; typedef struct

21、Queue /*多级就绪队列节点信息*/ PCB *LinkPCB; /*就绪队列中的进程队列指针*/ int prio; /*本就绪队列的优先级*/ int round; /*本就绪队列所分配的时间片*/ struct Queue *next; /*指向下一个就绪队列的链表指针*/ ReadyQueue; PCB *run=NULL,*finish=NULL; /*定义三个队列，就绪队列，执行队列和完成队列*/ ReadyQueue *Head = NULL; /*定义第一个就绪队列*/ int num; /*进程个数*/ int ReadyNum; /*就绪队列个数*/ void Outp

22、ut(); /*进程信息输出函数*/ void InsertFinish(PCB *in); /*将进程插入到完成队列尾部*/ void InsertPrio(ReadyQueue *in); /*创建就绪队列，规定优先数越小，优先级越低*/ void PrioCreate(); /*创建就绪队列输入函数*/ void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程*/ void InsertLast(PCB *in,ReadyQueue *queue); /*将进程插入到就绪队列尾部*/ void ProcessCreate(); /*进程创建函

23、数*/ void RoundRun(ReadyQueue *timechip); /*时间片轮转调度算法*/ void MultiDispatch(); /*多级调度算法，每次执行一个时间片*/ int main(void) PrioCreate(); /*创建就绪队列*/ ProcessCreate();/*创建就绪进程队列*/ MultiDispatch();/*算法开始*/ Output(); /*输出最终的调度序列*/ return 0; void Output() /*进程信息输出函数*/ ReadyQueue *print = Head; PCB *p; printf(进程名t优先

24、级t轮数tcpu时间t需要时间t进程状态t计数器n); while(print) if(print -LinkPCB != NULL) p=print -LinkPCB; while(p) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,p-count); p = p-next; print = print-next; p = finish; while(p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p

25、-cputime,p-needtime,p-state,p-count); p = p-next; p = run; while(p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,p-count); p = p-next; void InsertFinish(PCB *in) /*将进程插入到完成队列尾部*/ PCB *fst; fst = finish; if(finish = NULL) in-next = finish; finish = in; else

26、while(fst-next != NULL) fst = fst-next; in -next = fst -next; fst -next = in; void InsertPrio(ReadyQueue *in) /*创建就绪队列，规定优先数越小，优先级越低*/ ReadyQueue *fst,*nxt; fst = nxt = Head; if(Head = NULL) /*如果没有队列，则为第一个元素*/ in-next = Head; Head = in; else /*查到合适的位置进行插入*/ if(in -prio = fst -prio) /*比第一个还要大，则插入到队头*

27、/ in-next = Head; Head = in; else while(fst-next != NULL) /*移动指针查找第一个别它小的元素的位置进行插入*/ nxt = fst; fst = fst-next; if(fst -next = NULL) /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即可*/ in -next = fst -next; fst -next = in; else /*插入到队列中*/ nxt = in; in -next = fst; void PrioCreate() /*创建就绪队列输入函数*/ ReadyQueue *tmp; int i;

28、 printf(输入就绪队列的个数：n); scanf(%d,&ReadyNum); printf(输入每个就绪队列的CPU时间片：n); for(i = 0;i round); /*输入此就绪队列中给每个进程所分配的CPU时间片*/ tmp -prio = 50 - tmp-round; /*设置其优先级，时间片越高，其优先级越低*/ tmp -LinkPCB = NULL; /*初始化其连接的进程队列为空*/ tmp -next = NULL; InsertPrio(tmp); /*按照优先级从高到低，建立多个就绪队列*/ void GetFirst(ReadyQueue *queue)

29、/*取得某一个就绪队列中的队头进程*/ run = queue -LinkPCB; if(queue -LinkPCB != NULL) run -state = R; queue -LinkPCB = queue -LinkPCB -next; run -next = NULL; void InsertLast(PCB *in,ReadyQueue *queue) /*将进程插入到就绪队列尾部*/ PCB *fst; fst = queue-LinkPCB; if( queue-LinkPCB = NULL) in-next = queue-LinkPCB; queue-LinkPCB =

30、in; else while(fst-next != NULL) fst = fst-next; in -next = fst -next; fst -next = in; void ProcessCreate() /*进程创建函数*/ PCB *tmp; int i; printf(输入进程的个数：n); scanf(%d,&num); printf(输入进程名字和进程所需时间：n); for(i = 0;i name); getchar(); /*吸收回车符号*/ scanf(%d,&(tmp-needtime); tmp -cputime = 0; tmp -state =W; tmp

31、-prio = 50 - tmp-needtime; /*设置其优先级，需要的时间越多，优先级越低*/ tmp -round = Head -round; tmp -count = 0; InsertLast(tmp,Head); /*按照优先级从高到低，插入到就绪队列*/ void RoundRun(ReadyQueue *timechip) /*时间片轮转调度算法*/ int flag = 1; GetFirst(timechip); while(run != NULL) while(flag) run-count+; run-cputime+; run-needtime-; if(run

32、-needtime = 0) /*进程执行完毕*/ run -state = F; InsertFinish(run); flag = 0; else if(run-count = timechip -round)/*时间片用完*/ run-state = W; run-count = 0; /*计数器清零，为下次做准备*/ InsertLast(run,timechip); flag = 0; flag = 1; GetFirst(timechip); void MultiDispatch() /*多级调度算法，每次执行一个时间片*/ int flag = 1; int k = 0; Rea

33、dyQueue *point; point = Head; GetFirst(point); while(run != NULL) Output(); if(Head -LinkPCB!=NULL) point = Head; while(flag) run-count+; run-cputime+; run-needtime-; if(run-needtime = 0) /*进程执行完毕*/ run -state = F; InsertFinish(run); flag = 0; else if(run-count = run-round)/*时间片用完*/ run-state = W; r

34、un-count = 0; /*计数器清零，为下次做准备*/ if(point -next!=NULL) run -round = point-next -round;/*设置其时间片是下一个就绪队列的时间片*/ InsertLast(run,point-next); /*将进程插入到下一个就绪队列中*/ flag = 0; else RoundRun(point); /*如果为最后一个就绪队列就调用时间片轮转算法*/ break; +k; if(k = 3) ProcessCreate(); flag = 1; if(point -LinkPCB = NULL)/*就绪队列指针下移*/ po

35、int =point-next; if(point -next =NULL) RoundRun(point); break; GetFirst(point); 四、“银行家”避免死锁模拟实验相关数据结构：1) 可利用资源向量Available ，它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Availablej=k，标是系统中现有j类资源k个。 2) 最大需求矩阵Max，这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxij=k，表示进程i

36、需要j类资源的最大数目为k。3) 分配矩阵Allocation，这是一个nm的矩阵，它定义了系统中的每类资源当前分配到每一个进程的资源数。如果Allocationij=k，表示进程i当前已经分到j类资源的数目为k个。Allocationi表示进程i的分配向量。 4) 需求矩阵Need，这是一个nm的矩阵，用以表示每个进程还需要的各类资源的数目。如果Needij=k，表示进程i还需要j类资源k个，才能完成其任务。Needi表示进程i的需求向量。 上述三个矩阵间存在关系：Needij=Maxij-Allocationij程序代码：#include void main() int maxneed53

37、=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3; int allocation53=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2; int req3; int i,j,k,l,c=0,count=0; int need53=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; int result5=-1,-1,-1,-1,-1; int work3=3,3,2; printf(All Sources:n A B Cn 10 5 7n); printf(Available Sources:n A B Cn 3 3 2n); printf(Every proc

38、ess max need sources:n A B Cn); for(i=0;i5;i+) printf(P%d: ,i+1); for(j=0;j3;j+) printf( %d ,maxneedij); needij=maxneedij-allocationij; printf(n); for(l=0;l5;l+) for(k=0;k5;k+) if(resultk=-1&needk0=work0&needk1=work1&needk2,k+1); if(count=5) printf(nIt is safe!n); else printf(nIt is dangerous.n); wo

39、rk0=3; work1=3; work2=2; printf(Please input P1 request sources:n); scanf(%d,%d,%d,&req0,&req1,&req2); if(req0=need00&req1=need01&req2=need02) printf(The request is reasonable.n); else printf(The request is beyond need.n); if(req0=work0&req1=work1&req2=work2) work0=work0-req0; work1=work1-req1; work

40、2=work2-req2; need00=need00-req0; need01=need01-req1; need02=need02-req2; allocation00=allocation00+req0; allocation01=allocation01+req1; allocation02=allocation02+req2; / printf(%d %d %d,work0,work1,work2); for(k=0;k5;k+) resultk=-1; for(l=0;l5;l+) for(k=0;k5;k+) if(resultk=-1&needk0=work0&needk1=w

41、ork1&needk2,k+1); if(c=5) printf(nIt is safe!n); else printf(nIt is dangerous.n); 五、内在分配模拟实验动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。 另一种也是最常用的就是空闲链表，由于对分区的操作是动态的，所以很难估计数据结构所占用的空间，而且空闲

42、区表会占用宝贵的系统空间，所以提出了空闲链表的概念。其特点是用于管理分区的信息动态生成并和该分区在物理地址上相邻。这样由于可以简单用两个空闲块之间的距离定位已分配空间，不仅节约了系统空间，而且不必维持已分配空间的信息。本实验是要做一个模拟程序，来模拟动态分区算法的分配和回收过程，并不是真正的去分配和回收内存。基本的模拟方法有两种：（1）先从内存中申请一块存储区，对这块存储区进行模拟的分配和回收活动。（2）不申请存储区，自己定义一块虚拟的存储区，对这块存储区进行模拟的分配和回收活动，分配和回收仅仅是对数据结构的修改而已。程序代码：#includeusing namespace std;int F

43、reePartition100;/空闲分区块数组int FirstPartition100;/首次适应算法数组int CycleFirstPartition100;/循环首次适应算法数组int BestPartition100;/最佳适应算法数组int WorstPartition100;/最坏适应算法数组int ProcessNeed100;/每个作业的大小int PartitionNum,ProcessNum;/分区块数，作业数/首次适应算法void First()int i,j;char str;for(i=0;iPartitionNum;i+)FirstPartitioni=FreePartitioni;for(i=0;iProcessNum;i+)/找出第一块满足作业的分区for(j=0;jFirstPartitionj)continu