1、13级操作系统课程设计指导书操作系统课程设计指导书李海霞 编信息工程学院基础教学部二0一五年七月目 录实验一 Windows中线程与线程同步 3实验二 进程调度 6实验三 银行家算法 8实验四 请求页式存储管理中常用页面置换算法模拟 14实验一 Windows中线程与线程同步一、实验目的1、掌握Windows中线程的操作；2、熟悉线程不同步时的现象及环境因素；3、掌握一种同步对象的使用。二、实验环境PC机，Window操作系统，Vc+6.0。三、实验理论基础及教材对应关系1、线程和线程不同步的认识；2、线程间的同步和通信。四、实验内容与步骤1、定义全局变量 int i， 初始值置为 0。2、创
2、建两个线程，一个对 i 执行加 1 操作，另一个对 i 执行减 1 操作。两个线程执行相同的次数。#include #include #define MaxCount 9000000 / 循环次数要很大，可多次尝试一些值int i;CRITICAL_SECTION cs;DWORD _stdcall fun1( LPVOID p1) for( int j =0 ;j MaxCount;j+) i+; return 0;DWORD _stdcall fun2( LPVOID p1) for( int j =0 ;j MaxCount;j+) i-; return 0;显然，正常情况下，i 的仍然
3、保持为 0。但是观察两个线程执行后的情况，可以发觉最后 i 的值不一定是 0， 有时是很大的正数，有时是很大的负数，这就是多个线程在操作同一个变量 i时，未同步时带来的严重问题。3、在多个线程操作共享的变量时，才需要考虑同步问题。给上述这两个线程加上同步代码（步骤2的函数稍微改动即可），再来观察对 i 值的影响：#include #include #define MaxCount 9000000 / 循环次数要很大，可多次尝试一些值int i;CRITICAL_SECTION cs;DWORD _stdcall fun1( LPVOID p1) for( int j =0 ;j MaxCoun
4、t;j+) :EnterCriticalSection(&cs); i+; :LeaveCriticalSection(&cs); return 0;DWORD _stdcall fun2( LPVOID p1) for( int j =0 ;j MaxCount;j+) :EnterCriticalSection(&cs); i-; :LeaveCriticalSection(&cs); return 0;加入同步代码的两个线程，无论如何执行，i 的值总是 0 ，结果是正确的。4、主函数的写法int main() DWORD id1,id2; HANDLE hThread2; :Initia
5、lizeCriticalSection(&cs); hThread0 = :CreateThread(0,0,fun1,0,0,&id1); hThread1 = :CreateThread(0,0,fun2,0,0,&id2); :WaitForMultipleObjects(2,hThread,1,INFINITE); printf(i = %dn,i); :DeleteCriticalSection(&cs); getchar(); return 0;五、实验材料的提交与成绩评定实验源程序一份，并附上心得体会和运行结果的word文档（电子版），提交至天空教室。实验二 进程调度一、实验目的
6、用高级语言编写和调试一个有 N个进程并行的进程调度程序，以加深对进程的概念及进程调度算法的理解。二、实验设备PC机、windows2000 操作系统、Turbo C 2.0 / VC+6.0三、实验要求本实验要求4学时完成。实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告，按时上交。四、预备知识设计一个有N个进程并行的进程调度程序。进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。具体描述如下：每个进程有一个进程控制块（ PCB）
7、表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 分析：进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。 每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。 就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。 如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继
8、续运行，此时应将进程的优先数减1（即降低一级），然后按照优先数的大小把它插入就绪队列等待CPU。 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。 重复以上过程，直到所要进程都完成为止。调度算法的参考流程图如下：五、实验步骤1编写一个有N个进程并发的进程调度程序。2在上机环境中输入程序，调试，编译。3设计输入数据，写出程序的执行结果。4根据具体实验要求，填写好实验报告。实验三 银行家算法一、 实验目的1、理解死锁避免相关内容； 2、掌握银行家算法主要流程； 3、掌握安全性检查流程。操作系统中的死锁避免部分的理论进行实验。要求实验者设计一个程序，该程序可对每
9、一次资源申请采用银行家算法进行分配。二、实验环境PC机、windows2000 操作系统、VC+6.0。三、 实验要求1、设计多个资源（3）； 2、设计多个进程（3）； 3、设计银行家算法相关的数据结构； 4、动态进行资源申请、分配、安全性检测并给出分配结果。5、撰写实验报告，并在实验报告中画出银行家和安全性检查函数流程图；四、 实验相关知识死锁避免定义：在系统运行过程中，对进程发出的每一个资源申请进行动态检查，并根据检查结果决定是否分配资源：若分配后系统可能发生死锁，则不予分配，否则予以分配。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性
10、。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。1、系统安全状态（1）安全状态所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列 P1 ，P2 Pn就是安全序列。如果存在这样一个安全序列，则系统是安全的。并非所有的不安全状态都会转为死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。所以避免死锁的实质：系统在进行资源分配时，如何使系统不进入不安全状态。（2）安全状态之例假设系统有三个进程，共有12台磁带机。各进程的最
11、大需求和T0时刻已分配情况如下表：进程最大需求已分配可用P1P2P310495223问：T0时刻是否安全？答：T0时刻是安全的，因为存在安全序列：P2 P1 P3不安全序列：P1 P3 P2P3P1 （3）由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼
12、此都在等待对方释放资源，即陷入僵局，结果导致死锁。 2、 利用银行家算法避免死锁（1）银行家算法中的数据结构 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。 最大需求矩阵Max。最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。 分配矩阵Allocation这也是一个nm的矩阵
13、，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。 需求矩阵Need这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j（2）银行家算法设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已
14、超过它所宣布的最大值。 如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 银行家算法的参考流程图如下：
15、3、安全性算法（1）设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available； Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。 （2）从进程集合中找到一个能满足下述条件的进程： Finishi=false； Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 （3） 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work
16、j= Worki+Allocationi,j; Finishi= true; go to step （2）； （4） 如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 安全性算法的参考流程图如下：五、实验步骤1、设计并编写银行家算法模拟程序。2、在上机环境中输入程序，调试，编译。3、设计输入数据，写出程序的执行结果。4、根据具体实验要求，填写好实验报告。实验四 请求页式存储管理中常用页面置换算法模拟一、实验目的1、了解内存分页管理策略2、掌握调页策略3、掌握一般常用的调度算法4、学会各种存储分配算法的实现方法。5、了解页面大小和内存实际容量对命
17、中率的影响。二、实验环境PC机、windows2000 操作系统、VC+6.0。三、实验要求1、 采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；2、 实现OPT 算法 (最优置换算法)、LRU 算法 (Least Recently)、 FIFO 算法 (First IN First Out)的模拟；（三选一）3、 会使用某种编程语言。实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告，按时上交。四、相关知识请
18、求分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面。并把一部分页面装入内存，启动运行。在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。1、最佳置换算法OPT(Optimal)它是由
19、Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用此算法来评价其它算法。 2、先进先出(FIFO)页面置换算法 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。3、最近
20、最久未使用置换算法 （1）LRU(Least Recently Used)置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 （2）LRU置换
21、算法的硬件支持 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持： 1 寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如下图示出了
22、某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为18。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。五、实验步骤1、编写程序，实现请求页式存储管理中常用页面置换算法的模拟。要求屏幕显示各算法的性能分析表、缺页中断次数以及缺页率。2、在上机环境中输入程序，调试，编译。3、设计输入数据，写出程序的执行结果。4、根据具体实验要求，填写好实验报告。
