操作系统实验指导书

1、 操作系统原理实验讲义适用专业： 计算机科学与技术 网络工程 太原科技大学计算机科学与技术学院 2010年 6 月前 言操作系统是计算机的核心和灵魂。操作系统软件的设计对整个计算机的功能和性能起着至关重要的作用，所以此门课也是必不可少的，是面向计算机科学与技术、网络工程、软件工程等大多数计算机专业本科生开设的一门计算机专业课程。操作系统是计算机系统的核心，操作系统课程是计算机科学与技术专业的重要必修课。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。操作系统实验是操作系统课程的重要组成部分，属于学科基础实验范

2、畴。作为与相关教学内容配合的实践性教学环节，应在操作系统理论课教学过程中开设。操作系统是计算机科学与技术专业必修的专业基础课程，操作系统实验的作用是：理解操作系统的设计和实现思路，掌握典型算法。基本要求是：理解进程的概念，理解死锁，掌握银行家算法；掌握请求页式存储管理的实现原理及页面置换算法。学生应具有高级语言编程能力、具有数据结构等基础知识。说明：本实验指导书所提供的源程序均已在VC.下调试运行过目 录实验一 P、V 原语的模拟实现1实验二 银行家算法模拟10实验三 请求页式存储管理中常用页面置换算法模拟13实验一 P、V 原语的模拟实现实验学时：2实验类型：验证实验要求：必修一、实验目的本

3、课题实习的目的是，加深对进程概念及进程管理各部分内容的理解；熟悉进程管理中主要数据结构的设计及进程调度算法，进程控制机构、同步结构、通迅机构的实施。要求设计一个允许n个进程并发运行的进程管理模拟糸统。该糸统包括有简单的进程控制、同步及通迅机构，其进程调度算法可任意选择。每个进程用一个PCB表示，其内容可根据具体情况设置。各进程之间应有一定的同步关糸。糸统在运行过程中应能显示或打印各进程的状态及有关参数的变化情况，以便观察诸进程的运行过程及糸统的管理过程。1) 理解信号量相关理论；2) 掌握记录型信号量结构；3) 掌握 P、V 原语实现机制。二、实验要求1) 输入给定代码；2) 进行功能测试并得

4、出正确结果。3) 分析P和V函数功能模块；4) 在实验报告中画出P和V函数流程图；5) 撰写实验报告。三、实验内容本实验针对操作系统中信号量相关理论进行实验，要求实验者输入实验指导书提供的代码并进行测试。代码主要模拟信号量的 P 操作和 V 操作。1) 信号量信号量也称为信号锁，主要应用于进程间的同步和互斥，在用于互斥时，通常作为资源锁。信号量通常通过两个原子操作P和 V来访问。P操作使信号量的值+1，V操作使信号量的值-1。2) 记录型信号量记录型信号量采用了“让权等待”的策略，存在多个进程等待访问同一临界资源的情况，所以记录型信号量需要一个等待链表来存放等待该信号量的进程控制块或进程号。在

5、本实验中，使用记录型信号量。四、范例1.例: 支持多个进程并发运行的简单进程管理模拟糸统。本糸统的同步机构采用的信号量上的P、V操作的机制；控制机构包括阻塞和唤醒操作；时间片中断处理程序处理模拟的时间片中断；进程调度程序负责为各进程分配处理机。糸统中设计了1个并发进程。它们之间有如下同步关糸：1个进程需要互斥使用临界资源S2，进程1和进程2又需要互斥使用临界资源S1.本糸统在运行过程中随机打印出各进程的状态变换过程，糸统的调度过程及公共变量的变化情况。2算法糸统为过程设置了4种运行状态：e-执行态；r-高就绪态；t-低就绪态（执行进程因时间片到限而转入）；w-等待态；c-完成态。各进程的初始态

6、均设置为r.糸统分时执行各进程，并规定1个进程的执行概率均为11%。通过产生随机数x模拟时间片。当进程process1访问随机数x时，若x.>=0.11；当进程process2访问x时，若x<0.11或x>=0.66;当进程process1访问x时。若x<0.66,则分别认为各进程的执行时间片到限，产生“时间片中断”而转入低就绪态t.进程调度算法采用剥夺式最高优先数法。各进程的优先数通过键盘输入予以静态设置。调度程序每次总是选择优先数量小（优先权最高）的就绪态进程投入执行。先从r状态进程中选择，再从t状态进程中选择。当现行进程唤醒某个等待进程，而被唤醒进程的优先数小于现

7、行进程时，则剥夺现行进程的执行权。各进程在使用临界资源S1和S2时，通过调用信号量sem1和sem2上的P、V操作来实现同步。阻塞和唤醒操作和负责完成从进程的执行态到等待态以及从等待态到就绪态的转换。糸统启动后，在完成必要的糸统初始化后便执行进程调度程序。当执行进程因“时间片中断”，或被排斥使用临界资源，或唤醒某个等待进程时，立即进行进程调度。当1个进程都处于完成状态后，糸统退出运行。图1和图2分别示出了糸统主控程序和进程调度程序的大致流程。 Main初始化Secheduler 有执行进程（exe=NTL）进程2进程1进程3END1、数据结构（1）每个进程有一个进程控制块PCB，内容包括：Id

8、 进程标识数，id=0,1,2;Status 进程状态，可为e,r,t,w,c;Priority 进程优先数；Nextwr 等待链指针，指示在同一信号量上等待的下一个进程的标识数。（2）信号量semaphore,对应于临界资源s1和s2分别有sem1和sem2,均为互斥信号量，内容包括： Value 信号量值，初值为1； Firstwr 等待链首指针，指示该信号量上第一个等待进程的标识数。（1）现场保留区，用数组savearea13表示。即每个进程都有一个大小为3个单元的保留区，用来保存被“中断”时的现场信息，如通用寄存器的内容和断点地址等。此外，糸统中还用到下列主要全程变量： Exe 执行进

9、程指针，其值为进程标识数； I 用来模拟一个通用寄存器；五、程序源代码#include<stdio.h>#define TRUE 1#define FALSE 0#define MAXPRI 100#define NIL -1struct int id;char status;int nextwr;int priority;pcb1;struct int value;int firstwr; sem2;char savearea13,addr;int i,s1,s2,seed,exe=NIL;init( ) int j; for (j=0;j<1;j+)pcbj.id=j;p

10、cbj.status='r'pcbj.nextwr=NIL;printf("n process%d priority?",j+1);scanf ("%d",&i);pcbj.priority=i;sem0.value=1;sem0.firstwr=NIL;sem1.value=1;sem1.firstwr=NIL;for (i=1;i<1;i+)for (j=0;j<3;j+)saveareaij='0'float random ( )int m; if (seed<0) m=-seed;else

11、 m=seed;seed=(24151*seed+11839)%64416;return(m/12565.0);timeint(char addr)float x;x=random();if (x<0.11)&&(exe=0)return(FALSE);if (x<0.66)&&(exe=1)return(FALSE);if (x<1.0)&&(exe=2)return(FALSE);saveareaexe0=i;saveareaexe1=addr;pcbexe.status='t'printf("Ti

12、mes silce interrupt'nprocess%d enter into ready.n", exe+1);exe=NIL;return (TRUE);find()int j,pd=NIL, w=MAXPRI;for (j=0;j<1;j+)if (pcbj.status='r')if (pcbj.priority<w)w=pcbj.priority; pd=j; if (pd=NIL)for (j=0; j<1;j+)if (pcbj.status='t')if (pcbj.priority<w) w=pcb

13、j.priority; pd=j; return(pd) ;scheduler() int pd; if(pd=find()=NIL&& exe=NIL)return(NIL); if (pd!=NIL) if(exe=NIL)pcbpd.status='e'exe=pd;printf("process%d is executing.n", exe+1);else if (pcbpd.priority<pcbexe.priority) pcbexe.status='r'printf("process%d ent

14、er into readyn", exe+1);pcbpd.status='e'exe=pd;printf ("process%d enter into readyn", exe+1);i=saveareaexe0;addr=saveareaexe1;return (exe);block(int se)int w;printf("process%d is blockedn", exe+1);pcbexe.status='w' pcbexe.nextwr=NIL;if (w=semse.firstwr)=NIL)s

15、emse.firstwr=exe;else while(pcbw.nextwr!=NIL)w=pcbw.nextwr;pcbw.nextwr=exe;p(int se,char ad)if (-semse.value>=0) return(FALSE);block(se);saveareaexe0=i;saveareaexe1=ad;exe=NIL;return(TRUE);wakeup(int se)int w;w=semse.firstwr;if(w!=NIL) semse.firstwr=pcbw.nextwr; pcbw.status='r' printf(&qu

16、ot;process%d is waken upn",w+1);v(int se,char ad)if(+semse.value>0) return(FALSE);wakeup(se);saveareaexe1=ad;saveareaexe0=i;return(TRUE);eexit(int n)pcbn.status='c'printf("process%d is completed!n", n+1); exe=NIL;processl() if(addr='a')goto a1; if(addr='b')g

17、oto b1; if(addr='c')goto c1; if(addr='d')goto d1; if(addr='e')goto e1; if(addr='f')goto f1;for(i=1;i<6;i+) printf("process1 calls P on the semaphore1n"); if(p(0,'a')break; a1:printf("process1 is executing in the cretical section 1n"); if

18、(timeint('b') break; b1:printf("s1=%dn",+s1); printf("process1 calls V on semaphorel and quit cretical section1n"); if(v(0,'c')break; c1:printf("process1 calls P on esemaphorel 2n"); if(p(1,'d')break; d1:printf("process1 is execting cretical

19、 section 2n"); if(timeint('e')break; e1:printf("s2=%dn",+s2); printf("process1 calls V on semaphore2 and quit cretical section2n");if(v(1,'f')break; f1:printf("process1 cycle count=%dn",i); if(i<6) return; eexit(0);process2()if(addr='a')g

20、oto a2;if(addr='b')goto b2;if(addr='c')goto c2;if(addr='d')goto d2;if(addr='e')goto e2;if(addr='f')goto f2;for(i=1;i<6;+i)printf("process2 calls P on the semaphore2n");if(p(1,'a')break;a2:printf("process2 is executing in the cretical

21、section2n");if(timeint('b')break;b2:printf("s2=%dn",+s2);printf("process2 calls V on semaphore2 and quit cretical section2.n");if(v(1,'c')break;c2:printf("process2 calls P on esemaphore1.n");if(p(0,'d')break;d2:printf("process2 is exect

22、ing cretical section1.n");if(timeint('e')break;e2:printf("s1=%dn",+s1);printf("process2 calls V on semaphore1 and quit cretical section1.n");if(v(0,'f')break;f2:printf("process2 cycle count=%dn",i); if(i<6) return;eexit(1);process1()if (addr='

23、;a') goto a1;if (addr='b') goto b1;if (addr='c') goto c1;for (i=1;i<6; +i)printf("process1,calls P on semaphore2n");if(p(1,'a') break; / * process 1 is biocked * /a1: printf("process 1 is execcuting on its cretical sectionn");if(timeint('b')

24、 break;b1: printf ("s2=%dn", +s2); printf ("process1 calls V on semapore2 and quit cretical sectionn");if(v(1,'c') break; / * wake up a biocked process * /c1: printf("process1 cycien count=%dn",i); if(i<6) return;eexit(2); main ( )int k;printf ("* * * *

25、process management * * * * nn");init();printf("s1=%d, s2=%dn", s1, s2);printf("process1, process2, process1 are all in ready ! n");for ( ; ;)if (k=scheduler()!=NIL)switch(k) case 0: process1(); break; case 1: process2(); break; case 2: process1(); break; default: printf(&quo

26、t;process identifer errorn"); break;else break;printf ("s1=%d, s2=%dn", s1, s2);printf ("n * * * * END * * * * n"); 六、思考1) 如何修改 P 操作，使之能一次申请多个信号量？2）在某个时刻，一个进程最多可以等待多少个信号量？ 实验二 银行家算法模拟实验学时：2实验类型：设计实验要求：必修一、实验目的（1）进一步理解利用银行家算法避免死锁的问题；（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏

27、幕上，再检测和笔算的一致性。（3）理解和掌握安全序列、安全性算法二、实验内容（1）了解和理解死锁；（2）理解利用银行家算法避免死锁的原理；（3）会使用某种编程语言。三、实验原理 (一)安全状态指系统能按照某种顺序如<P1,P2,Pn>(称为<P1,P2,Pn>序列为安全序列)，为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。 (二)银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requestij=k。系统按下述步骤进行安全检查：（1）如果RequestiNeedi则继续以下检查，否则显示需求申请超出最大需求值的错误。（2）如果Req

28、uestiAvailable则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。（三）安全性算法（1）设置两个向量： 工作向量Work: 它表示

29、系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Ø Workj=Worki+Allocationi,j;Ø

30、 Finishi=true;Ø go to step 2; （4）如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。四、实验算法（1）参考图1-1所示流程图编写安全性算法。Y所有finish都为true？输出安全序列NYN存在Finishi =false&&Needij< Availablej初始化Work和FinishFinishi=true，Workj=Workj+ Allocationj所有进程都找完了？Y开始 图1-1 安全性算法流程图（2）编写统一的输出格式。每次提出申请之后输出申请成功与否的结果。如果成

31、功还需要输出变化前后的各种数据，并且输出安全序列。（3）参考图1-2所示流程图编写银行家算法。（4）编写主函数来循环调用银行家算法。结束 否是申请失败。以上分配作废，恢复原来的分配状态：Availablej = Availablej + RequestijAllocationij= AllocationijRequestijNeedij = Needij+RequestijNYNYRequestij> Needij出错返回：return(error)Requestij> Availablej出错返回：(进程阻塞)return(error)Availablej = Available

32、j RequestijAllocationij= Allocationij + RequestijNeedij = Needij Requestij假定分配：输入初始参数（资源分配及请求情况）开始 假定分配之后，系统安全吗？申请成功。输出各种数据的变化图1-2银行家算法流程图五、思考题 （1）在编程中遇到了哪些问题？你是如何解决的？（2）在安全性算法中，为什么不用变量Available，而又定义一个临时变量work？实验三 请求页式存储管理中常用页面置换算法模拟实验学时：4实验类型：设计实验要求：必修一、实验目的（1）了解内存分页管理策略（2）掌握调页策略（3）掌握一般常用的调度算法（4）学会

33、各种存储分配算法的实现方法。（5）了解页面大小和内存实际容量对命中率的影响。二、实验内容（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；（2）实现OPT 算法 (最优置换算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模拟；（3）会使用某种编程语言。三、实验原理分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程

34、能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。1、最佳置换算法OPT(Optimal)它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 2、先进先出(FIFO)页面置换算法 这是最早出现的置换算法。该算法总