2011操作系统实验指导书1

1《操作系统原理》实验讲义适用专业：计算机科学与技术网络工程太原科技大学计算机科学与技术学院2010年6月2前言操作系统是计算机的核心和灵魂。操作系统软件的设计对整个计算机的功能和性能起着至关重要的作用，所以此门课也是必不可少的，是面向计算机科学与技术、网络工程、软件工程等大多数计算机专业本科生开设的一门计算机专业课程。操作系统是计算机系统的核心，《操作系统》课程是计算机科学与技术专业的重要必修课。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。操作系统实验是操作系统课程的重要组成部分，属于学科基础实验范畴。作为与相关教学内容配合的实践性教学环节，应在操作系统理论课教学过程中开设。操作系统是计算机科学与技术专业必修的专业基础课程，操作系统实验的作用是：理解操作系统的设计和实现思路，掌握典型算法。基本要求是：理解进程的概念，理解死锁，掌握银行家算法；掌握请求页式存储管理的实现原理及页面置换算法。学生应具有高级语言编程能力、具有数据结构等基础知识。说明：本实验指导书所提供的源程序均已在VC６.０下调试运行过．3目录实验一P、V原语的模拟实现..............................................................................1实验二银行家算法模拟.......................................................................................10实验三请求页式存储管理中常用页面置换算法模拟.......................................131实验一P、V原语的模拟实现实验学时：2实验类型：验证实验要求：必修一、实验目的本课题实习的目的是，加深对进程概念及进程管理各部分内容的理解；熟悉进程管理中主要数据结构的设计及进程调度算法，进程控制机构、同步结构、通迅机构的实施。要求设计一个允许n个进程并发运行的进程管理模拟糸统。该糸统包括有简单的进程控制、同步及通迅机构，其进程调度算法可任意选择。每个进程用一个PCB表示，其内容可根据具体情况设置。各进程之间应有一定的同步关糸。糸统在运行过程中应能显示或打印各进程的状态及有关参数的变化情况，以便观察诸进程的运行过程及糸统的管理过程。1)理解信号量相关理论；2)掌握记录型信号量结构；3)掌握P、V原语实现机制。二、实验要求1)输入给定代码；2)进行功能测试并得出正确结果。3)分析P和V函数功能模块；4)在实验报告中画出P和V函数流程图；5)撰写实验报告。三、实验内容本实验针对操作系统中信号量相关理论进行实验，要求实验者输入实验指导书提供的代码并进行测试。代码主要模拟信号量的P操作和V操作。1)信号量信号量也称为信号锁，主要应用于进程间的同步和互斥，在用于互斥时，通常作为资源锁。信号量通常通过两个原子操作P和V来访问。P操作使信号量的值+1，V操作使信号量的值-1。2)记录型信号量记录型信号量采用了“让权等待”的策略，存在多个进程等待访问同一临界资源的情况，所以记录型信号量需要一个等待链表来存放等待该信号量的进程控制块或进程号。在本实验中，使用记录型信号量。四、范例1.例:支持多个进程并发运行的简单进程管理模拟糸统。本糸统的同步机构采用的信号量上的P、V操作的机制；控制机构包括阻塞和唤醒操作；时间片中断处理程序处理模拟的时间片中断；进程调度程序负责为各进程分配处理机。糸统中设计了1个并发进程。它们之间有如下同步关糸：1个进程需要互斥使用临界资源S2，进2程1和进程2又需要互斥使用临界资源S1.本糸统在运行过程中随机打印出各进程的状态变换过程，糸统的调度过程及公共变量的变化情况。2．算法糸统为过程设置了4种运行状态：e------执行态；r-----高就绪态；t------低就绪态（执行进程因时间片到限而转入）；w------等待态；c------完成态。各进程的初始态均设置为r.糸统分时执行各进程，并规定1个进程的执行概率均为11%。通过产生随机数x模拟时间片。当进程process1访问随机数x时，若x.=0.11；当进程process2访问x时，若x0.11或x=0.66;当进程process1访问x时。若x0.66,则分别认为各进程的执行时间片到限，产生“时间片中断”而转入低就绪态t.进程调度算法采用剥夺式最高优先数法。各进程的优先数通过键盘输入予以静态设置。调度程序每次总是选择优先数量小（优先权最高）的就绪态进程投入执行。先从r状态进程中选择，再从t状态进程中选择。当现行进程唤醒某个等待进程，而被唤醒进程的优先数小于现行进程时，则剥夺现行进程的执行权。各进程在使用临界资源S1和S2时，通过调用信号量sem1和sem2上的P、V操作来实现同步。阻塞和唤醒操作和负责完成从进程的执行态到等待态以及从等待态到就绪态的转换。糸统启动后，在完成必要的糸统初始化后便执行进程调度程序。当执行进程因“时间片中断”，或被排斥使用临界资源，或唤醒某个等待进程时，立即进行进程调度。当1个进程都处于完成状态后，糸统退出运行。图1和图2分别示出了糸统主控程序和进程调度程序的大致流程。Main初始化Secheduler有执行进程（exe=NTL）进程2进程1进程3END31、数据结构（1）每个进程有一个进程控制块PCB，内容包括：Id进程标识数，id=0,1,2;Status进程状态，可为e,r,t,w,c;Priority进程优先数；Nextwr等待链指针，指示在同一信号量上等待的下一个进程的标识数。（2）信号量semaphore,对应于临界资源s1和s2分别有sem1和sem2,均为互斥信号量，内容包括：Value信号量值，初值为1；Firstwr等待链首指针，指示该信号量上第一个等待进程的标识数。（1）现场保留区，用数组savearea[1]［3］表示。即每个进程都有一个大小为3个单元的保留区，用来保存被“中断”时的现场信息，如通用寄存器的内容和断点地址等。此外，糸统中还用到下列主要全程变量：Exe执行进程指针，其值为进程标识数；I用来模拟一个通用寄存器；五、程序源代码#includestdio.h#defineTRUE1#defineFALSE0#defineMAXPRI100#defineNIL-1struct{intid;charstatus;intnextwr;intpriority;}pcb[1];struct{intvalue;intfirstwr;}sem[2];charsavearea[1][3],addr;inti,s1,s2,seed,exe=NIL;init(){intj;for(j=0;j1;j++){4pcb[j].id=j;pcb[j].status='r';pcb[j].nextwr=NIL;printf(\nprocess%dpriority?,j+1);scanf(%d,&i);pcb[j].priority=i;}sem[0].value=1;sem[0].firstwr=NIL;sem[1].value=1;sem[1].firstwr=NIL;for(i=1;i1;i++)for(j=0;j3;j++)savearea[i][j]='0';}floatrandom(){intm;if(seed0)m=-seed;elsem=seed;seed=(24151*seed+11839)%64416;return(m/12565.0);}timeint(charaddr){floatx;x=random();if((x0.11)&&(exe==0))return(FALSE);if((x0.66)&&(exe==1))return(FALSE);if((x1.0)&&(exe==2))return(FALSE);savearea[exe][0]=i;savearea[exe][1]=addr;pcb[exe].status='t';printf(Timessilceinterrupt'\nprocess%denterintoready.\n,exe+1);exe=NIL;return(TRUE);}find(){intj,pd=NIL,w=MAXPRI;for(j=0;j1;j++)if(pcb[j].status=='r')if(pcb[j].priorityw){5w=pcb[j].priority;pd=j;}if(pd==NIL)for(j=0;j1;j++)if(pcb[j].status=='t')if(pcb[j].priorityw){w=pcb[j].priority;pd=j;}return(pd);}scheduler(){intpd;if((pd=find())==NIL&&exe==NIL)return(NIL);if(pd!=NIL){if(exe==NIL){pcb[pd].status='e';exe=pd;printf(process%disexecuting.\n,exe+1);}elseif(pcb[pd].prioritypcb[exe].priority){pcb[exe].status='r';printf(process%denterintoready\n,exe+1);pcb[pd].status='e';exe=pd;printf(process%denterintoready\n,exe+1);}}i=savearea[exe][0];addr=savearea[exe][1];return(exe);}block(intse){intw;printf(process%disblocked\n,exe+1);pcb[exe].status='w';pcb[exe].nextwr=NIL;6if((w=sem[se].firstwr)==NIL)sem[se].firstwr=exe;else{while(pcb[w].nextwr!=NIL)w=pcb[w].nextwr;pcb[w].nextwr=exe;}}p(intse,charad){if(--sem[se].value=0)return(FALSE);block(se);savearea[exe][0]=i;savearea[exe][1]=ad;exe=NIL;return(TRUE);}wakeup(intse){intw;w=sem[se].firstwr;if(w!=NIL){sem[se].firstwr=pcb[w].nextwr;pcb[w].status='r';printf(process%diswakenup\n,w+1);}}v(intse,charad){if(++sem[se].value0)return(FALSE);wakeup(se);savearea[exe][1]=ad;savearea[exe][0]=i;return(TRUE);}eexit(intn){pcb[n].status='c';printf(process%discompleted!\n,n+1);exe=NIL;7}processl(){if(addr=='a')gotoa1;if(addr=='b')gotob1;if(addr=='c')gotoc1;if(addr=='d')gotod1;if(addr=='e')gotoe1;if(addr=='f')gotof1;for(i=1;i6;i++){printf(process1callsPonthesemaphore1\n);if(p(0,'a'))break;a1:printf(process1isexecutinginthecreticalsection1\n);if(timeint('b'