2022年《操作系统》课程设计报告 .pdf

《2022年《操作系统》课程设计报告 .pdf》由会员分享，可在线阅读，更多相关《2022年《操作系统》课程设计报告 .pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 /写者#defin

3、e END -1 #define R READER #define W WRITER typedef struct _Person HANDLE 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,

4、2, W, 16, 5, 3, R, 5, 2, 4, W, 6, 5, 5, R, 4, 3, 6, R, 17,7, 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 19 页 - - - - - - - - - END, ; int g_NumOfReading = 0; int g_NumOfWriteRequest = 0;/ 申请写进程的个数HANDLE g_hReadSemaphore;/ 读者信号HANDLE g_hWriteSemaphore;/ 写者信号

5、bool finished = false; / 所有的读完成/bool wfinished = false; / 所有的写完成void CreatePersonList(int *pPersonList); bool CreateReader(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 m

6、ain() g_hReadSemaphore = CreateSemaphore(NULL,1,100,NULL); /创建信号灯， 当前可用的资源数为 1，最大为100 g_hWriteSemaphore = CreateSemaphore(NULL,1,100,NULL); /创建信号灯，当前可用的资源数为 1，最大为100 CreatePersonList(g_PersonLists); / Create All the reader and writers printf(Created all the reader and writern 创建 n); g_CurrentTime =

7、0; while(true) g_CurrentTime+; Sleep(300); / 300 ms printf(CurrentTime = %dn,g_CurrentTime); if(finished) return 0; / return 0; void CreatePersonList(int *pPersonLists) int i=0; int *pList = pPersonLists; bool Ret; while(pList0 != END) switch(pList1) case R: Ret = CreateReader(pList2,pList3,pList0);

8、/351,w452,523,654 break; case W: Ret = CreateWriter(pList2,pList3,pList0); break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 19 页 - - - - - - - - - if(!Ret) printf(Create Person %d is wrongn,pList0); pList += 4; / move to next person list DWORD WINAPI Reade

9、rProc(LPVOID lpParam)/读过程 Person *pPerson = (Person*)lpParam; / wait for the start time while(g_CurrentTime != pPerson-m_nStartTime) printf(Reader %d is Requesting 等待 n,pPerson-m_nID); printf(nn*n); / wait for the write request WaitForSingleObject(g_hReadSemaphore,INFINITE); if(g_NumOfReading =0) Wa

10、itForSingleObject(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_nWorkTime) printf(Reader %d is

11、 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); return 0; D

12、WORD WINAPI WriterProc(LPVOID lpParam) Person *pPerson = (Person*)lpParam; / wait for the start time while(g_CurrentTime != pPerson-m_nStartTime) printf(Writer %d is Requesting 请求进行写操作n,pPerson-m_nID); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 19 页 - - - -

13、 - - - - - printf(nn*n); WaitForSingleObject(g_hWriteSemaphore,INFINITE); / modify the writers real start time pPerson-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退出

14、n,pPerson-m_nID); printf(nn*n); /g_NumOfWriteRequest-; ReleaseSemaphore(g_hWriteSemaphore,1,NULL); if(pPerson-m_nID = 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

15、= &g_Personsg_NumPerson; pPerson-m_nID = ID; pPerson-m_nStartTime = StartTime; pPerson-m_nWorkTime = WorkTime; pPerson-m_nType = READER; g_NumPerson+; / Create an New Thread pPerson-m_hThread= CreateThread(NULL,0,ReaderProc,(LPVOID)pPerson,0,&dwThreadID); if(pPerson-m_hThread = NULL) return false; r

16、eturn true; bool CreateWriter(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_nType = WRITER; g_NumPerson+; / Creat

17、e an New Thread 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 19 页 - - - - - - - - - pPerson-m_hThread= CreateThread(NULL,0,WriterProc,(LPVOID)pPerson,0,&dwThreadID); if(pPerson-m_hThread = NULL) return false; return true; 二、进程间通信与子进程使用管道进行父子进程间通信，程序首先判断参数是否合法

18、，因为输入的字符将从父进程通过发送到子进程中。然后调用pipe 函数创建父子进程用于通信的管道。使用fork 函数创建子进程时， 子进程会获得与父进程相同的资源，其中包括文件描述符信息。因此，调用fork 函数须在 pipe 函数调用前。 当父子进程通过管道进行通信时，files1 为用于数据写入的文件描述符 .因此 ,在子进程中 ,要读取管道中的数据可以调用read函数，而读取得文件描述符为 files0 。对于父进程而言，写入数据需要调用write 函数，要写入的文件描述为files1 。程序代码：#include #include int main(int argc,char* argv

19、) 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)=-1) perror(chil

20、d process cannot read data from pipe); return 1; else printf(in child process, receive message: %sn,msg); _exit(0); else close(f_des0); if(write(f_des1,argv1,strlen(argv1)=-1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 19 页 - - - - - - - - - perror(parent p

21、rocess cannot write data to pipe); return 1; else printf(in parent process, send message: %sn,argv1); wait(NULL); _exit(0); return 0; 三、进程多级调度模拟1.设置多个就绪队列，并给队列赋予不同的优先级数，第一个最高，依次递减。2.赋予各个队列中进程执行时间片的大小，优先级越高的队列，时间片越小。3.当一个新进程进入内存后，首先将其放入一个对列末尾，如果在一个时间片结束时尚未完成，将其转入第二队列末尾。4.当一个进程从一个对列移至第n 个队列后，便在第n 个队列中

22、采用时间片轮转执行完。5.仅当时间片空闲时，才调度第二个队列中的进程。(1i-1) 空闲时，才调度i，如果处理机正在第i 队列中运行，又有新进程进入优先权较高队列，则新进程抢占处理机，将正在运行的进程放入第i 队列队尾，将处理机分给新进程。程序代码：#include #include #include typedef struct node /* 进程节点信息*/ char name20; /* 进程的名字 */ int prio; /*进程的优先级*/ int round; /*分配 CPU 的时间片 */ int cputime; /*CPU 执行时间 */ int needtime; /

23、*进程执行所需要的时间*/ char state; /*进程的状态，W 就绪态， R 执行态， F 完成态 */ int count; /* 记录执行的次数*/ struct node *next; /*链表指针 */ PCB; typedef struct Queue /* 多级就绪队列节点信息*/ PCB *LinkPCB; /*就绪队列中的进程队列指针*/ int prio; /*本就绪队列的优先级*/ int round; /*本就绪队列所分配的时间片*/ struct Queue *next; /* 指向下一个就绪队列的链表指针*/ ReadyQueue; PCB *run=NULL

24、,*finish=NULL; /*定义三个队列，就绪队列，执行队列和完成队列*/ ReadyQueue *Head = NULL; /* 定义第一个就绪队列*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 19 页 - - - - - - - - - int num; /*进程个数 */ int ReadyNum; /*就绪队列个数 */ void Output(); /*进程信息输出函数*/ void InsertFinish(PCB *in); /* 将进程插入到

25、完成队列尾部*/ void InsertPrio(ReadyQueue *in); /* 创建就绪队列，规定优先数越小，优先级越低*/ void PrioCreate(); /* 创建就绪队列输入函数*/ void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程*/ void InsertLast(PCB *in,ReadyQueue *queue); /*将进程插入到就绪队列尾部*/ void ProcessCreate(); /*进程创建函数*/ void RoundRun(ReadyQueue *timechip); /* 时间片轮转调度算法

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

27、e(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-cputime,p-needtime,p-state,p-co

28、unt); p = p-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 19 页 - - - - - - - - - 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) /*将进程插入到完成队列尾部*/ P

29、CB *fst; fst = finish; if(finish = NULL) in-next = finish; finish = in; else 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 = He

30、ad; Head = in; else /*查到合适的位置进行插入*/ if(in -prio = fst -prio) /*比第一个还要大，则插入到队头*/ in-next = Head; Head = in; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 19 页 - - - - - - - - - else while(fst-next != NULL) /* 移动指针查找第一个别它小的元素的位置进行插入*/ nxt = fst; fst = fst-next;

31、if(fst -next = NULL) /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即可*/ in -next = fst -next; fst -next = in; else /*插入到队列中 */ nxt = in; in -next = fst; void PrioCreate() /* 创建就绪队列输入函数*/ ReadyQueue *tmp; int i; printf( 输入就绪队列的个数：n); scanf(%d,&ReadyNum); printf( 输入每个就绪队列的CPU 时间片： n); for(i = 0;i round); /* 输入此就绪队列中给每个进程

32、所分配的CPU 时间片 */ tmp -prio = 50 - tmp-round; /*设置其优先级，时间片越高，其优先级越低*/ tmp -LinkPCB = NULL; /* 初始化其连接的进程队列为空*/ tmp -next = NULL; InsertPrio(tmp); /* 按照优先级从高到低，建立多个就绪队列*/ void GetFirst(ReadyQueue *queue) /*取得某一个就绪队列中的队头进程*/ run = queue -LinkPCB; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师

33、精心整理 - - - - - - - 第 9 页，共 19 页 - - - - - - - - - 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-L

34、inkPCB = 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); 名师资料总结 - - -精品资料欢迎下载 - - -

35、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 19 页 - - - - - - - - - tmp -cputime = 0; tmp -state =W; tmp -prio = 50 - tmp-needtime; /* 设置其优先级，需要的时间越多，优先级越低*/ tmp -round = Head -round; tmp -count = 0; InsertLast(tmp,Head); /*按照优先级从高到低，插入到就绪队列*/ void RoundRun(ReadyQueue *timechip) /* 时

36、间片轮转调度算法*/ int flag = 1; GetFirst(timechip); while(run != NULL) while(flag) run-count+; run-cputime+; run-needtime-; if(run-needtime = 0) /*进程执行完毕*/ run -state = F; InsertFinish(run); flag = 0; else if(run-count = timechip -round)/*时间片用完 */ run-state = W; run-count = 0; /*计数器清零，为下次做准备*/ InsertLast(r

37、un,timechip); flag = 0; flag = 1; GetFirst(timechip); void MultiDispatch() /*多级调度算法，每次执行一个时间片*/ int flag = 1; int k = 0; ReadyQueue *point; point = Head; GetFirst(point); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 19 页 - - - - - - - - - while(run != NULL)

38、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; run-count = 0; /*计数器清零，为下次做准备*/ if(point -next!=NULL) run -round =

39、 point-next -round;/*设置其时间片是下一个就绪队列的时间片*/ InsertLast(run,point-next); /* 将进程插入到下一个就绪队列中*/ flag = 0; else RoundRun(point); /* 如果为最后一个就绪队列就调用时间片轮转算法*/ break; +k; if(k = 3) ProcessCreate(); flag = 1; if(point -LinkPCB = NULL)/*就绪队列指针下移*/ point =point-next; if(point -next =NULL) RoundRun(point); 名师资料总结

40、- - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 19 页 - - - - - - - - - break; GetFirst(point); 四、 “银行家”避免死锁模拟实验相关数据结构：1) 可利用资源向量Available ，它是一个含有m 个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Availablej=k ，标是系统中现有j 类资源 k 个。2) 最大需求矩阵Max，这是

41、一个nm 的矩阵，它定义了系统中n 个进程中的每一个进程对 m 类资源的最大需求。如果Maxij=k，表示进程i 需要 j 类资源的最大数目为k。3) 分配矩阵Allocation ，这是一个nm 的矩阵，它定义了系统中的每类资源当前分配到每一个进程的资源数。如果Allocationij=k，表示进程i 当前已经分到j 类资源的数目为k个。 Allocationi 表示进程i 的分配向量。4) 需求矩阵Need，这是一个 nm 的矩阵， 用以表示每个进程还需要的各类资源的数目。如果 Needij=k ，表示进程i 还需要 j 类资源 k 个，才能完成其任务。Needi 表示进程i 的需求向量。

42、上述三个矩阵间存在关系：Needij=Maxij-Allocationij 程序代码：#include void main() int maxneed53=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

43、A B Cn 10 5 7n); printf(Available Sources:n A B Cn 3 3 2n); printf(Every process 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

44、,k+1); if(count=5) printf(nIt is safe!n); else printf(nIt is dangerous.n); work0=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);

45、if(req0=work0&req1=work1&req2=work2) work0=work0-req0; work1=work1-req1; work2=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+)

46、resultk=-1; for(l=0;l5;l+) for(k=0;k5;k+) if(resultk=-1&needk0=work0&needk1=work1&needk2,k+1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 19 页 - - - - - - - - - if(c=5) printf(nIt is safe!n); else printf(nIt is dangerous.n); 五、内在分配模拟实验动态分区是指系统不预先划分固定分区，而是在

47、装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。另一种也是最常用的就是空闲链表，由于对分区的操作是动态的， 所以很难估计数据结构所占用的空间，而且空闲区表会占用宝贵的系统空间，所以提出了空闲链表的概念。其特点是用于管理分区的信息动态生成并和该分区在物理地址上相邻。 这样由于可以简单用两个空闲块之间的距离定位已分配空间，不仅节约了系统空间， 而且不必维持已分配空间的信息。本实

48、验是要做一个模拟程序，来模拟动态分区算法的分配和回收过程，并不是真正的去分配和回收内存。基本的模拟方法有两种：（1）先从内存中申请一块存储区，对这块存储区进行模拟的分配和回收活动。（2）不申请存储区，自己定义一块虚拟的存储区，对这块存储区进行模拟的分配和回收活动，分配和回收仅仅是对数据结构的修改而已。程序代码：#include using namespace std; int FreePartition100;/ 空闲分区块数组int FirstPartition100;/ 首次适应算法数组int CycleFirstPartition100;/循环首次适应算法数组int BestPartit

49、ion100;/ 最佳适应算法数组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) continue; else 名师资料总结 - -

50、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 19 页 - - - - - - - - - FirstPartitionj-=ProcessNeedi;/找到后把分区大小减去作业的大小? ? ? ? ? ? ? ?str=A+i; cout 作业 str 在第 j+1 块分区中 endl; break; coutendl; cout 分配之后剩余情况：endl; ? ?for(i=0;iPartitionNum;i+) coutFirstPartitioni ; coutendlendl;