13级操作系统课程设计指导书

《操作系统》课程设计指导书

李海霞  编

信息工程学院基础教学部

二〇##年七月


目  录

实验一 Windows中线程与线程同步... 3

实验二 进程调度... 6

实验三 银行家算法... 8

实验四 请求页式存储管理中常用页面置换算法模拟... 14


实验一 Windows中线程与线程同步

一、实验目的

1、掌握Windows中线程的操作;

2、熟悉线程不同步时的现象及环境因素;

3、掌握一种同步对象的使用。

二、实验环境

PC机,Window操作系统,Vc++6.0。

三、实验理论基础及教材对应关系

1、线程和线程不同步的认识;

2、线程间的同步和通信。

四、实验内容与步骤

1、定义全局变量 int i, 初始值置为 0。

2、创建两个线程,一个对 i 执行加 1 操作,另一个对 i 执行减 1 操作。两个线程执行相同的次数。

#include <stdio.h>

#include <windows.h>

#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 的仍然保持为 0。但是观察两个线程执行后的情况,可以发觉最后 i 的值不一定是 0, 有时是很大的正数,有时是很大的负数,这就是多个线程在操作同一个变量 i时,未同步时带来的严重问题。

3、在多个线程操作共享的变量时,才需要考虑同步问题。

给上述这两个线程加上同步代码(步骤2的函数稍微改动即可),再来观察对 i 值的影响:

#include <stdio.h>

#include <windows.h>

#define MaxCount 9000000  // 循环次数要很大,可多次尝试一些值

int i;

CRITICAL_SECTION cs;

DWORD __stdcall fun1( LPVOID p1)

{

    for( int j =0 ;j < MaxCount;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 hThread[2];

    ::InitializeCriticalSection(&cs);

    hThread[0] = ::CreateThread(0,0,fun1,0,0,&id1);

    hThread[1] = ::CreateThread(0,0,fun2,0,0,&id2);

    ::WaitForMultipleObjects(2,hThread,1,INFINITE);

    printf("i = %d\n",i);

    ::DeleteCriticalSection(&cs);

    getchar();

    return 0;

}

五、实验材料的提交与成绩评定

实验源程序一份,并附上心得体会和运行结果的word文档(电子版),提交至天空教室。


实验二 进程调度

一、实验目的

 用高级语言编写和调试一个有 N个进程并行的进程调度程序,以加深对进程的概念及进程调度算法的理解。

二、实验设备

PC机、windows2000 操作系统、Turbo C 2.0 / VC++6.0

三、实验要求

本实验要求4学时完成。

实验前应复习实验中所涉及的理论知识和算法,针对实验要求完成基本代码编写、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告,按时上交。

四、预备知识

设计一个有N个进程并行的进程调度程序。

进程调度算法:采用最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)和先来先服务算法。具体描述如下:

每个进程有一个进程控制块( PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。

分析:进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。进程的到达时间为进程输入的时间。

进程的运行时间以时间片为单位进行计算。

每个进程的状态可以是就绪 W(Wait)、运行R(Run)、或完成F(Finish)三种状态之一。

就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。

如果运行一个时间片后,进程的已占用 CPU时间已达到所需要的运行时间,则撤消该进程,如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间,也就是进程还需要继续运行,此时应将进程的优先数减1(即降低一级),然后按照优先数的大小把它插入就绪队列等待CPU。

每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB,以便进行检查。   

重复以上过程,直到所要进程都完成为止。

调度算法的参考流程图如下:

五、实验步骤

1.编写一个有N个进程并发的进程调度程序。

2.在上机环境中输入程序,调试,编译。

3.设计输入数据,写出程序的执行结果。

4.根据具体实验要求,填写好实验报告。


实验三 银行家算法

一、 实验目的

1、理解死锁避免相关内容;

2、掌握银行家算法主要流程;

3、掌握安全性检查流程。

操作系统中的死锁避免部分的理论进行实验。要求实验者设计一个程序,该程序可对每一次资源申请采用银行家算法进行分配。

二、实验环境

PC机、windows2000 操作系统、VC++6.0。

三、 实验要求

1、设计多个资源(≥3);

2、设计多个进程(≥3);

3、设计银行家算法相关的数据结构;

4、动态进行资源申请、分配、安全性检测并给出分配结果。

5、撰写实验报告,并在实验报告中画出银行家和安全性检查函数流程图;

四、 实验相关知识

死锁避免定义:在系统运行过程中,对进程发出的每一个资源申请进行动态检查,并根据检查结果决定是否分配资源:若分配后系统可能发生死锁,则不予分配,否则予以分配。

由于在避免死锁的策略中,允许进程动态地申请资源。因而,系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程;否则,进程等待。其中最具有代表性的避免死锁算法是银行家算法。

1、系统安全状态

(1)安全状态

所谓系统是安全的,是指系统中的所有进程能够按照某一种次序分配资源,并且依次地运行完毕,这种进程序列{ P1 ,P2 …Pn}就是安全序列。如果存在这样一个安全序列,则系统是安全的。

并非所有的不安全状态都会转为死锁状态,但当系统进入不安全状态后,便有可能进入死锁状态;反之,只要系统处于安全状态,系统便可避免进入死锁状态。所以避免死锁的实质:系统在进行资源分配时,如何使系统不进入不安全状态。

(2)安全状态之例

假设系统有三个进程,共有12台磁带机。各进程的最大需求和T0时刻已分配情况如下表:

问:T0时刻是否安全?

答:T0时刻是安全的,因为存在安全序列:P2 àP1à P3

不安全序列:P1à…

            P3à…

            P2àP3àP1 

(3)由安全状态向不安全状态的转换

如果不按照安全序列分配资源,则系统可能会由安全状态进入不安全状态。例如,在T0时刻以后,P3又请求1台磁带机,若此时系统把剩余3台中的1台分配给P3,则系统便进入不安全状态。 因为,此时也无法再找到一个安全序列, 例如,把其余的2台分配给P2,这样,在P2完成后只能释放出4台,既不能满足P1尚需5台的要求,也不能满足P3尚需6台的要求,致使它们都无法推进到完成,彼此都在等待对方释放资源,即陷入僵局,结果导致死锁。

2、 利用银行家算法避免死锁

(1)银行家算法中的数据结构

① 可利用资源向量Available。

这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。

② 最大需求矩阵Max。

最大需求矩阵Max。这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。

③ 分配矩阵Allocation

这也是一个n×m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。

④ 需求矩阵Need

这也是一个n×m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成其任务。 

Need[i,j]=Max[i,j]-Allocation[i,j]

(2)银行家算法

设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:

① 如果Requesti[j]≤Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

 ② 如果Requesti[j]≤Available[j],便转向步骤(3);否则, 表示尚无足够资源,Pi须等待。

③ 系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:

  Available[j]∶=Available[j]-Requesti[j];

  Allocation[i,j]∶=Allocation[i,j]+Requesti[j];

  Need[i,j]∶=Need[i,j]-Requesti[j];

④ 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则, 将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

银行家算法的参考流程图如下:

 


3、安全性算法

(1)设置两个向量:

① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work∶=Available;

② Finish: 它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]∶=false; 当有足够资源分配给进程时, 再令Finish[i]∶=true。

(2)从进程集合中找到一个能满足下述条件的进程: 

① Finish[i]=false;

② Need[i,j]≤Work[j]; 若找到, 执行步骤(3), 否则,执行步骤(4)。 (3) 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:

 Work[j]∶=Work[i]+Allocation[i,j];

  Finish[i]∶=true;

  go to step (2);

(4) 如果所有进程的Finish[i]=true都满足, 则表示系统处于安全状态;否则,系统处于不安全状态。

安全性算法的参考流程图如下:

五、实验步骤

1、设计并编写银行家算法模拟程序。

2、在上机环境中输入程序,调试,编译。

3、设计输入数据,写出程序的执行结果。

4、根据具体实验要求,填写好实验报告。


实验四 请求页式存储管理中常用页面置换算法模拟

一、实验目的

1、了解内存分页管理策略

2、掌握调页策略

3、掌握一般常用的调度算法

4、学会各种存储分配算法的实现方法。

5、了解页面大小和内存实际容量对命中率的影响。

二、实验环境

PC机、windows2000 操作系统、VC++6.0。

三、实验要求

1、 采用页式分配存储方案,通过分别计算不同算法的命中率来比较算法的优劣,同时也考虑页面大小及内存实际容量对命中率的影响;

2、 实现OPT 算法 (最优置换算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模拟;(三选一)

3、 会使用某种编程语言。

实验前应复习实验中所涉及的理论知识和算法,针对实验要求完成基本代码编写、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告,按时上交。

四、相关知识

请求分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片,称为页面。并把一部分页面装入内存,启动运行。

在进程运行过程中,若其所要访问的页面不在内存而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据,送磁盘的对换区中。但应将哪个页面调出,须根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。

一个好的页面置换算法,应具有较低的页面更换频率。从理论上讲,应将那些以后不再会访问的页面换出,或将那些在较长时间内不会再访问的页面调出。

1、最佳置换算法OPT(Optimal)

它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面,将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但可以利用此算法来评价其它算法。

2、先进先出(FIFO)页面置换算法

这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。

3、最近最久未使用置换算法

(1)LRU(Least Recently Used)置换算法的描述

FIFO置换算法性能之所以较差,是因为它所依据的条件是各个页面调入内存的时间,而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)置换算法,是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t,当须淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。

(2)LRU置换算法的硬件支持

LRU置换算法虽然是一种比较好的算法,但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问,以及如何快速地知道哪一页是最近最久未使用的页面,须有以下两类硬件之一的支持:

①  寄存器

为了记录某个进程在内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存器,可表示为R=Rn-1Rn-2Rn-3……R2R1R0 当进程访问某物理块时,要将相应寄存器的Rn-1位置成1。此时,定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数,那么具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面。如下图示出了某进程在内存中具有8个页面,为每个内存页面配置一个8位寄存器时的LRU访问情况。这里,把8个内存页面的序号分别定为1??8。由图可以看出,第7个内存页面的R值最小,当发生缺页时首先将它置换出去。

② 栈

可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时,便将页面的页面号从栈中移出,将它压入栈顶。因此,栈顶始终是最新被访问页面的编号民,而栈底则是最近最久未使用的页面的页面号。

五、实验步骤

1、编写程序,实现请求页式存储管理中常用页面置换算法的模拟。要求屏幕显示各算法的性能分析表、缺页中断次数以及缺页率。

2、在上机环境中输入程序,调试,编译。

3、设计输入数据,写出程序的执行结果。

4、根据具体实验要求,填写好实验报告。

相关推荐