操作系统课程设计指导书

《操作余统》课程设计

指导书

信息技术系

10—0年六月

课程设计任务（一）：进程调度

一、目的与规定

1、目的

进程是操作系统最重要口勺概念之一，进程调度乂是操作系统关键的重要内容。本任务规

定学生独立地用C语言（或其他程序设计语言）编写和调试一种简朴的进程调度程序。调

度算法（如，简朴轮转法和优先数法等）可任意选择或自行设计。以加深对进程调度用多种

调度算法11勺理解。

2、规定

（1）设计一种有n个进程并行的进程调度程序。每个进程由一种进程控制块（PCB）表

达。进程控制块一般应包括下述信息：进程名、进程优先数、进程需要运行的时间、

占用CPU口勺时间以及进程的状态等，且可按调度算法的不一样而增删。

（2）调度程序可包括4〜5种不一样的调度算法，运行时可任意选一种，以利于多种算法

H勺分析比较。完毕1种调度算法得基本分即60分，每增长1种加10分，满分100

分。

（3）系统应能显示各正程状态和参数口勺变化状况，便于观测诸进程的调度过程

二、示例

1、题目

本程序可选用优先数法或简朴轮转法对五个进程进夕亍调度。每个进程处在运行R（run）.

就绪W（wait）和完毕Finish）三种状态之一，并假设起始状态都是就绪状态W。为了便于处

理，程序进程的运行时间以时间片为单位计算。各进程的优先数或轮转时间片数、以及进程

需要运行H勺时间片数，均由伪随机数发生器产生。

进程控制块构造如下：

PCB

进程标识数

链指针

优先数能转时间片数

占用CPU时间片数一

进程所需时间片数

进程状态

进程控制块链构造如下:

其中：RUN一目前运行进程指针；

HEAD一进程就绪链链首指针；

TAID一进程就绪链链尾指针。

2、算法与框图

(1)优先数法。进程就绪链按优先数大小从高到低排列，链首进程首先投入运行。每过一种

时间片，运行进程所需运行的时间片数减1,阐明它已运行了一种时间片，优先数也减

3,理由是该进程假如在一种时间片中完毕不了，优先级应当减少一级。接着比较现行

进程和就绪链链首进程H勺优先数，假如仍是现行进程高或者相似，就让现行进程继续进

行，否则，调度就绪链链首进程投入运行。原运行进程再按其优先数大小插入就绪链，

且变化它们对应的进程状态，直至所有进程都运行完各自的时间片数。

3、程序运行成果格式

（1）程序运行成果格式

TYPETHEALGORITHM:PRIORITY

OUTPUTOFPRIORITY

RUNNINGPROC.WAITINGQUEUE

3415

ID12345

PRIORITY93830290

CPUTIME00000

ALLTIME33634

STATEWRWWW

NEXT53410

SYSTEMFINISHED

(2)阐明：

程序后动后，屏幕上显示“TYPETHEALGORITHM”，规定顾客打入使用何种调度算

法。本程序只编制了优先数法("priority”)和简朴轮转法("RoundRobin")两种。打入某

一算法后，系统自动形成与进程控制块，实行该算法的进程调度算法，并打印各进程在调度

过程中II勺状态和参数的变化。

4、小结

本任务用较简朴的I二种措施模拟进程调度，在进程运行时间和进程状态变化方面也做了

简化，但已经可以反应进程调度的实质。本任务能加深对进程调度的理解和熟悉它的实行措

施。

三、设计题

自行设计一种进程调度程序，在计算机上调试和运行该程序，其功能应当不亚于示例。

直观地评测多种调度算法的性能。

提醒1:可编写一种反馈排队法(FB措施)的进程调度程序。该算法的基本思想是设

置几种进程就绪队列，如队列I……队列i,同一队列中的进程优先级相似，可采用先进先

出措施调度。各队列的进程，其优先级逐队减少。即队列1的进程优先数最高，队列i的最

低。而时间片，即以此占用CPU的时间恰好相反，队列1的最短，队列i则最长。谎.度措

施是开始进入的进程都在队列1中参与调度，假如在•和时间片内该进程完不成，应排入队

列2,即优先级要减少，但下一次运行日勺时间可加长(即时间片加长了)。以此类推，直至

排到队列i。调度时目前队列1中找，待队列1中已无法程时，再调度队列2时进程，一旦

队列I中有了进程，乂应返回来调度队列IH勺进程。这种措施最佳设计成运行过程中能发明

一定数量H勺进程，而不是一开始就生成所有进程。

提醒2：可综合多种算法的）优先，考虑在多种不一样状况下H勺实行措施，如上述FB算

法。也可选用有关资料中报导H勺某些措施，加以分析、简化和实现。

四、思索题

（1）示例中的程序，没有使用指针型（pointer）数据构造，怎样用指针型构造改写本实

例，使更能体现C语言H勺特性。

（2）怎样在程序中真实地模拟进程运行H勺时间片？

（3）假如增长进程的“等待”状态，即进程因祈求输入输出等问题而挂起的状态，怎样

在程序中实现？

课程设计任务（二）：祈求页式存储管理

一、目的与规定

1、目的

近年来，由于大规模集成电路（LSI）和超大规模集成电路（VLSI）技术H勺发展，

使存储器的容量不停扩大，价格大幅度下降。但从使用角度看，存储器的容量和成本总

是受到一定的限制。因此，提高存储器的运用效率一直是操作系统研究的重要课题之一。

其中虚拟存储技术是.用来扩大内存容量U勺一种重要措施。学生应独立地用C语言（或

其他程序设计语言）编写几种常用的存储分派算法，并设计•种存储管理的模拟程序，

对多种算法进行分析比较，评测其性能优劣，从而加深对这些算法的理解。

2、规定

为了比较真实地模拟存储管理，可预先生成一种大体符合实际状况的指令地址流。

然后模拟这样一种指令序列H勺执行来计算和分析多种算法的访问命中率。

二、示例

1、题目

本示例采用页式分派存储管理方案，并通过度析计算不一样页面淘汰算法状况下的

访问命中率来比较多种算法的优劣。此外也考虑到变化页面大小和实际存储器容量对计

算成果的影响，从而可为选择好的算法、合适H勺页面尺寸和实存容量提供根据。

本程序是按卜述原则生成指令序列H勺：

（1）50%的指令是次序执行的。

（2）25%『、J指令均匀散布在前地址部分。

（3）25%的指令均匀散布在后地址部分。

示例中选用最佳淘汰算法（OPT）和近来至少使用页面淘汰算法（LRU）计算页面

命中率。公式为

命中率7_页面失效次数

页地址流长度

假定虚存容量为32K,页面尺寸从1K至8K,实存容量从4页至32页。

2、算法与框图

（1）最佳淘汰算法（OPT）。

这是一种理想日勺算法，可用来作为衡量其他算法优劣的J根据，在实际系统中是难以

实现的，由于它必须先懂得指令的所有地址流。由于本示例中已预先生成了所有的指令

地址流，故可计算出最佳命中率。

该算法的准则是淘汰-满页表中不再访问或是最迟访问H勺的页。这就规定将页表中

的页逐一与后继指令访问的所有页比较，如后继指令不在访问该页，则把此页淘汰，否

则得找出后继指令中最迟访问的页面淘汰。可见最佳淘汰算法要花费较长的运算时间。

（2）近来至少使用页淘汰算法（LRU）。

这是一种常常使用口勺措施，有多种不一样【向实行方案，本例采用不停调整页表链的

措施，即总是淘汰页表链链首页，而把新访问的页插入链尾。假如目前调用页已在页表

内，则把它再次调整到链尾。这样就能保证近来使月的页，总是处在靠近链尾部分，而

不常使用的页则移到琏首，逐•被淘汰，在页表较大时，调整页表链日勺代价也是不小的。

（3）程序框图如下图2所示。

图2计算页面命中率框图

3、程序运行成果格式

(I)程序运行成果格式

THEVIRTUALADDRESSSTREAMASFOLLOWS:

a[0]=16895a(H=16896a⑵=16897a[3]=16302

a[4]=25403a[5]=1394Ia[61=13942a[7]=8767

A[252]=23583a[253]=20265a[254]=20266a[255]=20267

Thealgorithmis:opl

PAGENUMBERWITHSIZEIkFOREACHADDRESSIS:

pageno[0]=17pageno[l]=17pageno[2]=17pageno[3]=16

pagcno[4]=25pagcno[5]=14pagcno[6]=14pagcno[7]=9

pageno[252]=24pagenol253]=20pageno|254]=20pageno[255]=20

vmsize=32kpagesize=1k

pageassignedpages_in/totalreferences

47.0000E-1

67.0(X)0E-l

88.0000E-1

108.0000E-1

128.0000E-1

149.0000E-1

169.0000E-1

189.0000E-1

209.0000E-1

229.0000E-1

249.0000E-1

269.0000E-1

289.0CX)0E-l

309.0000E-1

329.0(X)0E-l

PAGENUMBERWITHSIZE2kEACHADDRESSIS:

PAGENUMBERWITHSIZE4kEACHADDRESSIS:

PAGENUMBERWITHSIZE8kEACHADDRESSIS:

Endtheresultforopt

*********************今**************************

thealgorithmisIru

……同上

EndtheresultforIru

*********************************************

（2）示例中使用的有关数据构造、常量和变量阐明如下：

length被调试的指令地址流长度，可作为一种常量设定。

called目前祈求的I页面号。

pagefault页面失效标志,如目前祈求页called已在页表内，则置pagefault二false,否则

为true。

table页表。tab电i]=j,表达虚存II勺第j页在实存II勺第i页中。

used目前被占用的I实存页面数，可用来判断目前实存中与否有空闲页。

（3）本程序启动后,屏幕上显示“thealgorithmis：",顾客可选择最佳淘汰算法（打

入“OPT”）或者近来至少使用淘汰算法（打入“LRU”）计算页面命中率。当然还可以

加入多种其他的算法。

4、小结

（1）编制评测多种算法性能的J模拟程序是研制系统程序，尤其是操作系统所必须的。模

拟的环境愈是真实，其成果愈是可靠，也就更有助于选择合适的方案。本任务虽然

简朴，但可作为一种尝试。

（2）注意正整数的范围只能从0……32767,限制程序中的虚存尺寸为32K,实际如采用

更大的虚存'实存，更能阐明问题。

三、设计题

（1）编制和调试示例给出日勺祈求页式存储管理程序，并运行之。2种算法均完毕得

70分。

（2）增长2种己学过的淘汰算法，计算它们的丈面访问命中率。试对多种算法的命

中率加以比较分析。每增长1种加15分，满分100分。

提醒：可选用FIFO措施，即先访问H勺页先淘汰，也可选用LRU措施中H勺其他方

案。如在页表中设置标志位，按标志位值得变化来淘汰。也可用LFU措施，为页表中

各页面设置访问计数器，淘汰访问频率最低的页（注意：目前访问的页不能淘汰）等等。

四、思索题

（1）设计一种界地址存储管理的模拟系统，模拟界地址方式下存储区的分派和回收过

程。

提醒1：必须设置一种内存分派表，按照分派表中有关信息实行存储区的分派，并

不停根据存储区的分派和回收修改该表。算法有初次匹配法，循环初次匹配法和最佳匹

配法等。可用多种措施日勺比较来充实实习内容。可使用碎片搜集和复盖等技术。

（2）自行设计或选用一种较为完善的内存管理措施，并加以实现。

提醒2：设计一种段页式管理的模拟程序或通过一种实际系统的消化和分析，编制

一种程序来模拟该系统。

课程设计任务（三）：文献操作与管理

一、目的与规定

1、目的

伴随社会信息量H勺不停增长，规定计算机处理H勺信息与日俱增，波及到社会生活的各个

方面。因此，文献管理是操作系统II勺一种极为重要的构成部分。学生应独立地用C语言（或

其他程序设计语言）编写和调试一种简朴H勺文献系统，模拟文献管理的工作过程。从而对多

种文献操作命令的实质内容和执行过程有比较深入11勺理解，掌握它们的实行措施，加深理解

课堂上讲授过的知识。

2、规定

（1）设计一种有n个顾客的文献系统，每个顾客最多可保留m个文献。

（2）限制顾客在一次运行中只能打开I个文献。

（3）系统应能检查输入命令的对的性，出错要显示出错原因。

（4）对文献必须设置保护措施，如只能执行，容许读、容许写等。在每次打开文献

时，根据本次打开的规定，再次设置保护级别，即可有二级保护。

（5）对文献的操作至少应有下述几条命令：

creat建立文献。

delete删除文献。

open打开文献。

close关闭文献。

read读文献。

write写文献。

二、示例

1.题目

（1）本任务设计一种10个顾客的文献系统，每个顾客最多可保留10个文献，

一次运行中顾客可打开5个文献。

（2）程序采月二级文献目录，即设置主文献目录（MFD）和顾客文献目录

（UFD）。前者应包括文献主（即顾客）及他们U勺目录区指针；后者应给出

每个文献主占有H勺文献目录，即文献名，保护码，文献长度以及他们寄存

的位置等。此外为打开文献设置运行文献目录（AFD）,在文献打开时应填

入打开文献号，本次打开保护码和读写指针等。

（3）为了便于实现，简化对文献的读写操作，在执行读写命令时，只修改读写

指针，并不进行实际文献口勺读写操作。

2.算法与框图

（1）因系统小，文献目录的检索使用了简朴的线性搜索，而没有采用Hash等有

效算法。

（2）文献保护简朴实用了三位保护码，对应于容许读、容许写和运行执行，如

下所示：

111

容许写容许读容许执行

如对应位为0,则不容许。

(3)程序中使用H勺重要数据构造如下:

主文献目录和顾客文献目录

打开文献口录

(4)程序框图如图3所示。

图3文献系统框图

3.程序运行成果格式

(1)程序运行成果格式

RUN

YOURNAME?YOUIJIN

YOURNAMEISNOTNTHEUSERNAMETABLEJRYAGAIN.

YOURNAME?YOUJIN

YOURFILEDIRECTORY

FILENAMEPROTECTIONCODELENGTH

XUMAINIII9999

FlIII0

YOUJINYUIII100

******0000

******0000

木木***木0000

******0000

******0000

******0000

COMMANDNAME?GREATER

COMMANDNAMEGIVENISWRONG!

ITSHOULDBEONEOFFOLLOWING:CREATE,DELETE,OPEN,CLOSE,

READ,WRITE.BYE.TRYAGAIN

COMMANDNAME7CREATE

THENEWFILESNAME(LESSTHAN9CHARS)?F2

THENEWFILE'SPROTECTIONCODE?101

THENEWHLEISCREATED.

ENTERTHEOPENMODE?101

THISFILEISOPENED,ITSOPENNUMBERIS1

COMMANDNAME?READ

OPENFILENUMBER?

ERRORMESSAGE:ITISNOTALLOWEDTOREADTHISFILE!!!

COMMANDNAME7WRITE

OPENFILENUMBER?1

HOWMANYCHARACTERSTOBEWRITTENINTOTHATFILE?190

COMMANDNAME?OPEN

FILENAMETOBEOPENED?Fl

ENTERTHEOPENMODE?Ill

THISFILEISOPENED,ITSOPENNUMBERIS2

COMMANDNAME?WRITE

OPENFILENUMBER?2

COMMANDNAME?CLOSE

THEOPENEDFILENUMBERTOBECLOSED?2

THISFILEISCLOSED.

COMMANDNAME?BYE

NOWYOURFILEDIRECTORYISFOLLOWING:

XUMANIll9999

FIIII1900

YOUJINYU111100

F2101190

*****00D0

*****00D0

木木木**00D0

*****0000

GOODBXE.

(2)本程序用交互方式工作。

后动程序后，系统查询：YOURNAME?输入顾客名，登入主目录后，系统立即响

应。

注意，木程序中前一种登录顾客名的程序，顾客需实目前主目录中登入顾客名。系

统响应后会给出顾客文献目录，然后显示：

COMMANDNAME?打入对应命令后就可建立、删除、读、写、打开和关闭文献，如

命令输错，系统会指出并给顾客提醒。操作完毕后应关闭文献，然后输入“BYE”命令

退出文献系统。退出前系统再次打印目前文献目录。

4.小结

文献系统欧J管理有多种各样的方案和算法。由于时间和条件欧J限制，本示例只是简朴的

模拟了文献口勺几种操作命令，学生可从其他途径深入深入学习和探讨。

三、设计题

（1）编制和调试示例给出的文献操作与管理程序，并运行之。2种算法均完毕得70分。

（2）增长3个文献操作命令，并加以实现。每增长1种加10分，满分100分。

提醒：可以增长移动读写指针命令，如把指针移至某一起始位置或文献头；变化文献属

性的命令，如更改文献名，变化文献保护级别等。

四、思索题

（1）编制一种通过屏幕选择命令H勺文献管理系统，每幅屏幕要为顾客提供足够的选择

信息，不需要输入冗长的命令。

提醒1：为了便于顾客操作，微机大多采用按照屏幕H勺提醒选择命令，这里可以使用高

级语言编制通过屏幕显示选择文献操作命令的文献管理模拟程序。

（2）设计一种树形目录构造的文献系统，其根目录为rool,各分支可以是目录，也可

以是文献，最终的叶子都是文献。

提醒2：可以参照Linux操作系统的文献构造和管理措施。采用多级保护，即把顾客提

成文献主，伙伴和一般顾客三类，分别予以使用权。为了缩短搜索文献的途径，可设置工作

FI录，能在目前使用的目录下查找文献，不必每次都从艰FI录开始查找。

（3）根据学校的各皱机构，编制一种文献系统，规定上级机构能查阅和修改下级机构

的文献，而下级机构只有在授权状况下才能杳阅上级H勺文献，但不能修改，同•级的文献可

以共享。

提醒3：学校机构可.由如卜图4构成：

教科校一十

图4学校机构图

课程设计任务（四）：死锁观测与防止

一、目的与规定

1、目的

死锁会引起进程僵死，严重的话会导致整个系统瘫痪。因此，死锁现象是操作系统尤其

是大型系统中必须设法防止口勺。学生应独立II勺使用C语言（或其他程序设计语言）编写和

调试一种系统动态分派资源口勺简朴模拟程序，观测死锁产生的条件，并采用合适的算法，有

效的防止死锁U勺发生。从而更直观地理解死锁的起因，初步掌握防止死锁的简朴措施，加深

理解课堂上讲授过的知识。

2、规定

（1）设计一种由n个并发进程共享m个系统资源的系统。系统中进程可动态地申请资

源和释放资源。系统按各进程H勺申请动态地分派各资源。

（2）系统应能显示各进程申请和释放资源以及系统动态分派资源的过程，便于顾客观

测和分析。

（3）系统应能选择与否采用防止死锁算法或选用何种防止算法（如有多种算法）。在不

采用防止算法时观测死锁现象口勺发生过程。在使用防止死锁算法时，理解在同样申请条件下,

防止死锁的过程。

二、示例

1、题目

本示例采用银行家算法防止死锁的发生。假设有三人并发进程共享十个系统。在三个进

程申请口勺系统资源之和不超过10时，当然不也许发生死锁，由于各个进程申请口勺资源都能

满足。在有一种进程申请的系统资源数超过10时，必然会发生死锁。应当排除这二种状况。

程序采用人工输入各进程为申请资源序列。假如随机给各进程分派资源，就也许发生死锁,

这就是不采用防止死锁算法的状况。假如，按照一定的规则，为各进程分派资源，就可以防

止死锁时发生。示例中采用了银行算法。

2、算法与框图

程序框图如图5,6,7所示：

图5防止死锁程序框图

00000D00

0D0000DD

A00D040D

ADVANCE=true

0

▼

DD0000D0

0D0D0D0D

000Q50D

ADVANCE=true

图6死锁处理程序框图

（开始）

置未完成进程的T标志为1

已完成进程的T标志为0

用局部变量PROGRESS为“true”（即

是否有进程标志位T从I变。）

判定是否还存在不能完成的进程，是

若不存在，置SAFE为•true,否则"

为-false,置PROGRESS为“false”

否

是

▼

现行进程能够完成，把其所占资源

加到别余资源中去，5W标志

T（表示该进程能完成。），置

PROGRESS为‘irue'

图7safe函数框图

3、程序运行成果格式

（1）程序运行成果格式

INPUT:

OPTION=0

CLAIMOFPROCESS1IS:123-1-10

CLAIMOFPROCESS2IS:2311-20

CLAIMOFPROCESS3IS:125-20

MAXCLAIMOFPROCESS1IS:6

MAXCLAIMOFPROCESS2IS:7

MAXCLAIMOFPROCESS3IS:8

THESYSTEMALLOCTIONPROCESSISASFOLLOWS:

PROCESSCLAIMALLOCATIONREMAINDER

①1119

RESOURCEISALLOCATEDTOPROCESS1

②2227

RESOURCEISALLOCATEDTOPROCESS2

③3116

RESOURCEISALLOCATEDTOPROCESS3

④1234

RESOURCEISALLOCATEDTOPROCESS1

⑤2324

IFALLOCATED,DEADLOCKMAYOCCUR

⑥1234

THEREMAINDERISLESSTHANPROCESS2CLAIMS

©30010

PROCESS3HASFINISHED,RETURNITSRESOURSE

THEWHOLEWORKISCOMPLETED

(2)程序中使用口勺数据构造和变审名阐明如下：

OPTION选择标志

=0选用“防止死馈”算法

=1不用“防止死颈”算法

AP(I,J)资源祈求矢量

—{n>0第I进程第J次申请n个资源。

n<0第I进程第J次释放n个资源。

n=0第I进程在第J次种植。

VPMAXCLAIM(I)第I进程对资源11勺最大需求量

VALLOCATION(I)第I进程已分派到资源数

VPSTATUS(I)第I进程完毕祈求标志，为1时表达已完毕各次祈求。

VCOUNT(I)第I进程祈求次数计数器。具值表达该进程第几次祈求。

TOTAL已分派的系统资源总数。

REMAINDER剩余H勺系统资源数。

INQUIRY目前运行进程号

（3）程序中定义的过程和函数阐明如下：

①FRONT过程：初始化过程，装入所有初始数据，为各有关变量置初值，检

查每个进程祈求U勺资源总数与否超过系统所能提供的资源数。

②PRINT过程：输出一次分派成果。

③RETRIEVE过程：当测得资源不够分派或分派后也许产生死锁，回收已假

定分派了口勺资源。

©TERMINATION过程：检查每个进程时候都己完毕或者发生死锁。假如进

程所有完毕或发生死锁，则将全局变量ADVANCE置成（rue,否则置成false。

⑤R2过程：为检查进程的分派资源数与否超过了它的最大申请量，或是释放

H勺资源数与否超过占有数，这里是检查例外状况。

⑥上过程：为各进程设置能执行完标志T,对于还不能完毕的进程将它的标志

T置1,能完毕的进程标志T置0.

⑦SAFE函数：测试在目前分派状态下，会不会产生死锁，若不会，死锁函数

值返回true,否则返回falseo

⑧ALLOCATE过程：按申请想目前进程分派或收回资源。

⑨RETURN过程：收回目前进程的所有资源，井将此进程的）VPSTATUS置