2023年操作系统课程设计任务书级计算机软件网络

2023-2023学年第一学期

「操作系统」课程设计任务书

依照大纲和课程内容实践特点，结合《操作系统》、《LINUX操作系统》和

《嵌入式程序设计》课程重要内容，课设的具体规定及任务如下：

一、设计成果的规定

课程设计应严格按照规定完毕，在系统调试成功后，需要提供「操作系统」

课程设计报告，具体涉及：

（1）设计目的（1）设计内容（3）设计准备（理论、技术）（4）设计

过程（设计思想、代码实现）（5）设计结果并分析（6）系统的结构、原理

框图和模块等的具体说明（7）用户使用说明书和参考资料（8）设计体会。

注：1.（1）-（7）项可以打印，（8）设计体会必须手写。

2.报告的封皮、封底，采用给定的模板；报告的内容，在教师的指导

下，独立完毕，自主排版，不做统一规定。

二、设计任务（每名同学选一题，独立完毕）

题目一：进程与线程一Linux进程与线程通讯

1.设计目的

深刻理解线程和进程的概念，掌握线程与进程在组成成分上的差别以及与其

相适应的通讯方式和应用目的。

Linux系统的fork。保持了UNIX的经典语义，被创建的进程具有独立于父

进程的地址空间，两者之间的通讯通常可采用pipe机制，clone（）是Linux

系统特有的系统调用，可以通过参数拟定父子进程之间是否共享存储空间等资

源。在地址空间等资源共享的情况下，clone实质相称于创建了一个轻进程或线

程，这是clone的通常用法。实际在Linux系统中，fork以及用户级线程pthread

都是基于clone实现的。

2.设计内容

以Linux系统进程和线程机制为背景,掌握fork。和clone()系统调用的

形式和功能以及与其相适应的高级通讯方式。由fork派生的子进程之间通过

pipe通讯，由clone创建的线程之间通过共享内存通讯，对于后者需要考虑互

斥问题。

以生产者-消费者问题为例，通过实验理解fork()和clone()两个系统

调用的区别。程序规定可以创建4个进程或线程，其中涉及两个生产者和两个消

费者，生产者和消费者之间可以传递数据。

题目二：解决机调度一实时调度算法EDF和RMS

1.设计目的

进一步理解解决机调度算法，了解硬实时概念，掌握最早截止期优先调度算

法

EDF(EarliestDeadlineFirst)和速率单调调度算法RMS(RateMonotonic

Scheduling)的可调度条件，并能在可调度情况下给出具体调度结果。

2.设计内容

在Linux环境中采用用户级线程模拟实现EDF和RMS两种实时调度算法。给

定一组实时任务，按照EDF算法和RMS算法分别判断是否可调度。在可调度的情

况下，创建一组用户级线程，分别代表各个实时任务，并按算法所拟定的调度顺

序安排各个线程运营，运营时在终端上画出其Gantt图。为避免图形绘制冲淡算

法，Gantl图可用字符表达。

题目三：存储管理一动态异长存储资源分派算法

1.设计目的

理解动态异长存储分区资源管理，掌握所需数据结构和管理程序，了解各种

存储分派算法的优点和缺陷。

2.设计内容

(1)分析UNIX最先适应(FirstFit,FF)存储分派算法,即map数据结构、

存储分派函数mallocO和存储释放函数mfreeO,找出与算法有关的成分。

(2)修改上述与算法有关的成分，使其分别体现BF(BestFit,最佳适应)

分派原则和WF(WorstFit,最环适应)分派原则。

题目四：文献系统一Hash结构文献

1.设计目的

理解Linux文献系统的内部技术，掌握Linux与文献有关的系统调用命令，

并在此基础上建立面向随机检索的Hash结构文献。

Linux系统保持UNIX文献系统的风格，提供流式文献界面，这种结构具有

简洁灵活的特点，但并不直接支持记录式文献和关键字检索。本设计在Linux

文献系统基础上，设计一组库函数，以提供对随机检索的支持。

2.设计内容

(1)参考教程中Hash文献构造算法，设计一组Hash文献函数，涉及Hash

文献创建、打开、关闭、读、写等。

(2)编写一个测试程序，通过记录保存、查找、删除等操作，检查上述Hash

文献是否实现相关功能。

题目五：设备管理一Linux设备驱动程序安装

1.设计目的

结识Linux设备的种类和设备工作方式，理解设备驱动程序的工作原理，掌

握设备驱动程序的编写规范，能编写并安装简朴的设备驱动程序。

2.设计内容

在Linux系统中，编写一个简朴的字符型设备驱动程序模块，设备具有独

占特性，可执行读和写操作，相关系统调用为open,close,read,write。Open

和close分别相称于请求和释放设备，read和write将内容保存在设备模块内

设备驱动程序是操作系统内核和机器硬件之间的接口。设备驱动程序为应用

程序屏蔽了硬件的细节，故在应用程序看来，硬件设备只是一个设备文献，应用

程序可以像操作普通文献同样对硬件设备进行操作。

本设计规定同学按照标准设备驱动程序的环节编写驱动程序。由于键盘的设

备驱动程序属于字符设备的驱动，因此，应当按照字符设备的规则编写。规定同

学编写键盘设备文献file_operations结构，以及以下几个键盘操作函数：健盘

控制函数Kbd」octl()、关闭键盘设备函数Kbd_Closc()、打开键盘设备函数

Kbd_0pen()、获取键值函数Kbd_Getkey()、键盘服务子程序Kbd」SR()、键盘设

备的硬件初始化函数SetupKbd()、注册键盘设各使用函数KbdTnitO和卸载键

盘设备函数Kbd_Exit()。

题目八：初次适应算法的动态分区分派方式模拟

1.设计目的

了解动态分区分派中使用的数据结构和分派算法，并进一步加深对动态分区

存储管理方式及其实现过程的理解。

2.设计内容

1)用C语言实现采用初次适应算法的动态分区分派过程alloc。和回收过程

free()o其中，空闲分区通过空闲分区链表来管理，在进行内存分派时，系统优

先使用空闲区低端的空间。

2)假设初始状态如下，可用的内存空间为640KB,并有下列的请求序列；

作业1申请130KB

作业2申请60KB

作、比3申请100KB

作业2释放60KB

作业4申请200KB

作业3释放100KB

作业1释放130KB

作业5申请140KB

作业6申请60KB

作业7申请50KB

作业6释放60KB

请采用初次适应算法进行内存块的分派和回收，同时显示内存块分派和回收

后空闲内存分区链的情况。

题目九；循环初次适应算法的动态分区分派方式模拟

工•设计目的

了解动态分区分派中使用的数据结构和分派算法，并进一步加深对动态分区

存储管理方式及其实现过程的理解。

2.设计内容

1）用C语言实现采用循环初次适应算法的动态分区分派过程alloc。和回收过

程free。。其中，空闲分区通过空闲分区链表来管理，在进行内存分派时，系

统优先使用空闲区低端的空间。

2）假设初始状态如下，可用的内存空间为640KB,并有下列的请求序列;

作业1申请130KB

作业2申请60KB

作业3申请100KB

作业2释放60KB

作业4申请200KB

作业3释放100KB

作业1释放130KB

作业5申请140KB

作业6申请60KB

作业7申请50KB

作业6释放60KB

请采用循环初次适应算法进行内存块的分派和回收，同时显示内存块分派和

回收后空闲内存分区链的情况。

题目十：最佳适应算法的动态分区分派方式模拟

1.设计目的

了解动态分区分派中使用的数据结构和分派算法，并进一步加深对动态分区

存储管理方式及其实现过程的理解。

2.设计内容

1）用C语言分别实现采用最佳适应算法的动态分区分派过程alloc。和回收过

程其中，空闲分区通过空闲分区链表来管理，在进行内存分派时，系

统优先使用空闲区低端的空间。

2）假设初始状态如下，可用的内存空间为640KB,并有下列的请求序列；

作业1申请130KB

作业2申请60KB

作业3申请100KB

作业2释放60KB

作业4申请200KB

作业3释放100KB

作业1释放130KB

作业5申请140KB

作业6申请60KB

作业7申请50KB

作业6释放60KB

请采用最佳适应算法进行内存块的分派和回收，同时显示内存块分派和回收

后空闲内存分区链的情况。

题目十一：最坏适应算法的动态分区分派方式模拟

1.设计目的

了解动态分区分派中使用的数据结构和分派算法，并进一步加深对动态分区

存储管理方式及其实现过程的理解。

2.设计内容

1)用C语言分别实现采用最坏适应算法的动态分区分派过程alloc。和回收过

程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分派时，系

统优先使用空闲区低端的空间。

2)假设初始状态如下，可用的内存空间为640KB,并有下列的请求序列；

作业1申请130KB

作业2申请60KB

作业3申请100KB

作业2释放60KB

作业4申请200KB

作业3释放100KB

作业1释放130KB

作业5申请140KB

作业6申请60KB

作业7申请50KB

作业6释放60KB

请采用最坏适应算法进行内存块的分派和回收，同时显示内存块分派和回收

后空闲内存分区链的情况。

题目十二：进程调度模拟算法

1.设计目的

通过算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间

的切换，同时掌握进程调度算法的实现方法和技巧。

2.设计内容

(1)用C语言来实现对N个进程采用动态优先权优先算法的进程调度。

(2)每个用来标记进程的进程控制块PCB用结构来描述，涉及以下字段：

・进程标记数ID；

•进程优先数PRIORITY,并规定优先数越大的进程，其优先权越高;

•进程已占月的CPU时间CPUTIME；

•进程还需占用的CPU时间ALLTIME。当进程运营完毕时,ALLTIME

变为0;

•进程的阻塞时间STARTBLOCK,表达当进程再运营STARTBLOCK

个时间片后，进程将进入阻塞状态；

•进程被阻塞的时间BLOCKTIME,表达已阻塞的进程再等待

BLOCKTIME个时间片后，进程将转换成就绪状态；

•进程状态STATE；

•队列指针NEXT,用来将PCB排成队列。

(3)优先数改变的原则：

•进程在就绪队列中呆一个时间片，优先数增长1；

•进程每运营一个时间片，优先数减3。

(4)假设在调度前，系统中有5个进程，它们的初始状态如卜.：

ID01234

PRIORITY93830290

CPUT1ME00000

ALLTIME33634

STARTBLOCK2-1-1-1-1

BLOCKTIME30000

STATEREADYREADYREADYREADYREADY

(5)为了清楚地观测进程的调度过程，程序应将每个时间片内的进程的情况

显示出来，参照的具体格式如下：

RUNNINGPROG:i

READY_QUEUE:->id1->id2

BLOCK_QUEUE:->id3->id4

ID01234

PRIORITYPOPlP2P3P4

CPUTIMECOClC2C3C4

ALLTIMEAOAlA2A3A4

STARTBLOCKTOT1T2T3T4

BLOCKTIMEBOBlB2B3B4

STATESOSIS2S3S4

题目十三：请求调页存储管理方式的模拟1

1.设计目的

通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统

的原理和实现过程的理解。

2.设计内容

1）假设每个页面中可存放10条指令，分派给作业的内存块数为4。

2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址

空间为32页，目前它的所有页都尚未调入内存。在模拟过程中，假如所访问的

指令已在内存，则显示其物理地址，并转下一条指令。假如所访问的指令尚未装

入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。假如4

个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一

条指令。

在所有320指令执行完毕后，请计算并显示作业运营过程中发生的缺页率c

3）置换算法：采用先进先出（FIFO）置换算法。

提醒：

（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生

成：

①50%的指令是顺序执行的；

②25%的指令是均匀分布在前地址部分；

③25%的指令是均匀分布在后地址部分；

具体的实行方法是：

①在［0,319］的指令地址之间随机选取一起点m；

②顺序执行一条指令，即执行地址为m+1的指令；

③在前地址［0,m+1］中随机选取一条指令并执行，该指令的地址为M;

④顺序执行一条指令，其地址为亦+1的指令；

⑤在后地址Dn'+2,319］中随机选取一条指令并执行；

⑥反复上述环节①〜⑤，直到执行320次指令。

（2）将指令序列变换为页地址流

①设页面大小为1K；

②用户内存容量为4页到32页；

③用户虚存容里为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存

中的存放方式为：

第0条〜第9条指令为第。页（相应虚存地址为［0,9］）；

第10条〜第19条指令为第1页（相应虚存地址为［10,19］）；

第310条〜第319条指令为第31页（相应虚存地址为［310,319］）0

按以上方式，用户指令可组成32页。

（3）计算先进先出（FIFO）算法在不同内存容量下的命中率。

其中，命中率=1-页面失效次数/页地址流长度

题目十四：请求调页存储管理方式的模拟2

1.设计目的

通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统

的原理和实现过程的理解。

2.设计内容

1）假设每个页面中可存放10条指令，分派给作业的内存块数为4。

2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地

址空间为32页，目前它的所有页都尚未调入内存。在模拟过程中，假如所访问

的指令己在内存，则显示其物理地址，并转下一条指令。假如所访问的指令尚未

装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。假如4

个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一

条指令。

在所有320指令执行完毕后，请计算并显示作业运营过程中发生的缺页率°

3）置换算法：最近最久未使用（LRU）算法。

提醒：

（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生

成：

①50%的指令是顺序执行的；

②25%的指令是均匀分布在前地址部分；

③25%的指令是均匀分布在后地址部分；

具体的实行方法是：

①在［0,319］的指令地力卜之间随机选取一起点m：

②顺序执行一条指令，即执行地址为m+1的指令；

③在前地址［0,m+1］中随机选取一条指令并执行，该指令的地址为M；

④顺序执行一条指令，其地址为m'+1的指令；

⑤在后地址+2,319］中随机选取一条指令并执行；

⑥反复上述环节①〜⑤，直到执行320次指令。

（2）将指令序列变换为页地址流

①设页面大小为1K；

②用户内存容量为4页到32页；

③用户虚存容里为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存

中的存放方式为：

第0条〜第9条指令为第。页（相应虚存地址为［0,9］）；

第10条〜第19条指令为第1页（相应虚存地址为［10,19］）；

第310条〜第319条指令为第31页（相应虚存地址为［310,319］）o

按以上方式，用户指令可组成32页。

（3）计算最近最少使用（LRU）算法在不同内存容量下的命中率。

其中，命中率=1-页面失效次数/页地址流长度

题目十五：请求调页存储管理方式的模拟3

1.设计目的

通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统

的原理和实现过程的理解。

2.设计内容

1）假设每个页面中可存放10条指令，分派给作业的内存块数为4。

2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地

址空间为32页，目前它的所有页都尚未调入内存。在模拟过程中，假如所访问

的指令己在内存，则显示其物理地址，并转下一条指令。假如所访问的指令尚未

装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。假如4

个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一

条指令。

在所有320指令执行完毕后，请计算并显示作业运营过程中发生的缺页率°

3）置换算法：最佳置换（OPT）算法。

提醒：

（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生

成：

①50%的指令是顺序执行的；

②25%的指令是均匀分布在前地址部分;

③25%的指令是均匀分布在后地址部分；

具体的实行方法是：

①在［0,319］的指令地址之间随机选取一起点m；

②顺序执行一条指令，即执行地址为m+1的指令；

③在前地址［0,m+1］中随机选取一条指令并执行，该指令的地址为N;

④顺序执行一条指令，其地址为"+1的指令；

⑤在后地址［m'+2,319］中随机选取一条指令并执行；

⑥反复上述环节①〜⑤，直到执行320次指令。

（2）将指令序列变换为页地址流

①设页面大小为1K；

②用户内存容量为4页到32页；

③用户虚存容里为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存

中的存放方式为：

第0条〜第9条指令为第。页（相应虚存地址为［0,9］）;

第10条〜第19条指令为第1页（相应虚存地址为［10,19］）；

第310条〜第319条指令为第31页（相应虚存地址为［310,319］）。

按以上方式，用户指令可组成32页。

（3）计算最佳置换（OPT）算法在不同内存容量下的命中率。

其中，命中率=1-页面失效次数/页地址流长度

题目十六：请求调页存储管理方式的模拟4

1.设计目的

通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统

的原理和实现过程的理解。

2.设计内容

1）假设每个页面中可存放10条指令，分派给作业的内存块数为4。

2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地

址空间为32页，目前它的所有页都尚未调入内存。在模拟过程中，假如所访问

的指令已在内存，则显示其物理地址，并转下一条指令。假如所访问的指令尚未

装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。假如4

个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一

条指令。

在所有320指令执行完毕后，请计算并显示作业运营过程中发生的缺页率c

3）置换算法：最少访问（LFU）算法。

提醒：

（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生

成：

①50%的指令是顺序执行的；

②25%的指令是均匀分布在前地址部分；

③25%的指令是均匀分布在后地址部分；

具体的实行方法是：

①在［0,319］的指令地址之间随机选取一起点叱

②顺序执行一条指令，即执行地址为m+1的指令；

③在前地址［0,口+1］中随机选取一条指令并执行，该指令的地址为d;

④顺序执行一条指令，其地址为+1的指令；

⑤在后地址+2,319］中随机选取一条指令并执行；

⑥反复上述环节①〜⑤，直到执行320次指令。

（2）将指令序列变换为页地址流

①设页面大小为1K；

②用户内存容量为4页到32页；

③用户虚存容里为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存

中的存放方式为：

第0条〜第9条指令为第0页（相应虚存地址为［0,9］）；

第10条〜第19条指令为第1页（相应虚存地址为［10,19］）；

第310条〜第319条指令为第31页（相应虚存地址为［310,319］）0

按以上方式，用户指令可组成32页。

（3）计算最少访问（LFU）算法在不同内存容量下的命中率。

其中，命中率=1-页面失效次数/页地址流长度

题目十七：请求调页存储管理方式的模拟5

1.设计目的

通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统

的原理和实现过程的理解。

2.设计内容

1）假设每个页面中可存放10条指令，分派给作业的内存块数为4。

2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地

址空间为32页，目前它的所有页都尚未调入内存。在模拟过程中，假如所访问

的指令已在内存，则显示其物理地址，并转下一袋指令。假如所访问的指令尚未

装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。假如4

个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一

条指令。

在所有320指令执行完毕后，请计算并显示作业运营过程中发生的缺页率c

3）置换算法：最近最不经常使用（NRU）算法。

提醒：

（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生

成：

①50%的指令是顺序执行的；

②25%的指令是均匀分布在前地址部分；

③25%的指令是均匀分布在后地址部分；

具体的实行方法是：

①在［0,319］的指令地址之间随机选取一起点叱

②顺序执行一条指令，即执行地址为m+1的指令；

③在前地址［0,m+l］中随机选取一条指令并执行，该指令的地址为水；

④顺序执行一条指令，其地址为"+1的指令；

⑤在后地址+2,319］中随机选取一条指令并执行；

⑥反复上述环节①〜⑤，直到执行320次指令。

（2）将指令序列变换为页地址流

①设页面大小为1K；

②用户内存容量为4页到32页；

③用户虚存容里为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存

中的存放方式为：

第0条〜第9条指令为第。页（相应虚存地址为［0,9］）；

第10条〜第19条指令为第1页（相应虚存地址为［10,19］）；

第310条〜第319条指令为第31页（相应虚存地址为［310,319］）0

按以上方式，用户指令可组成32页。

（3）计算最近最不经常使用（NRU）算法在不同内存容量下的命中率。

其中，命中率二1.页面失效次数/页地址流长度

题目十八：P、V操作及进程同步的实现工

1.设计目的

掌握信号量通信方式的一般方法，了解系统实现''阻塞〃和''唤醒〃功能的方法

和技巧。同时掌握进程同步和互斥的概念及实现技术。

2.设计内容

1）用语言编程实现P、V原语并用P、V原语描述如下理发师-顾客问题：

有一个理发师，一把理发椅和n把提供应等候理发的顾客座的椅子。假如

没有顾客，则理发师便在理发椅子上睡觉；当第一个顾客到来时，必须唤醒该理

发师进行理发；假如理发师正在理发时又有顾客到来，则假如有空椅子可坐，他

就坐下来等待，假如没有空椅子，他就离开理发店。

为理发师和顾客各编一段程序描述他们的行为，规定不能带有竞争条件，试

用P、V操作实现。

2）实验规定及说明

①定义信号量并将P、V操作定义为带参数

②以输出字符串的形式表达理发师和顾客的行为。

③设计适当的数据结构和函数描述顾客等待队列和''唤醒〃理发师理发过

程，以及没有顾客时的''阻塞〃理发师过程。

④编程时需考虑理发师和顾客相应的程序是并发操作的。

提醒：可运用随机函数模拟并发操作。

⑤理发师和顾客两个进程各自调用一个函数模拟生产及消费的操作。

题目十九：P、V操作及进程同步的实现2

1.设计目的

掌握信号量通信方式的一般方法，了解系统实现''阻塞〃和''唤醒〃功能的方法

和技巧。同时掌握进程同步和互斥的概念及实现技术。

2.设计内容

用语言编程实现P、V原语并用P、V原语哲学家就餐问题：

为每个哲学家各编一段程序描述他们的行为，试用P、V操作实现。

题目二十：银行家算法

1.设计目的

1）了解多道程序系统中，多个进程并发执行的资源分派。

2）掌握银行家算法，了解资源在进程并发执行中的资源分派情况。

3）掌握防止死锁的方法，系统安全状态的基本概念。

2.设计内容

设计一个n个并发进程共享m个系统资源的程序以实现银行家算法。规定:

1）简朴的选择界面；

2）能显示当前系统资源的占用和剩余情况。

3）为进程分派资源，假如进程规定的资源大丁•系统剩余的资源，不与分派

并且提醒分派天成功；

4)撤消作业，释放资源。

编写和调试一个系统动态分派资源的简朴模拟程序，观测死锁产生的条

件，并采用适当的算法，有效地防止和避免死锁的发生。

银行家算法分派资源的原则是：系统掌握每个进程对资源的最大需求量，

当进程规定申请资源时，系统就测试该进程尚需资源的最大量，假如系统中现存

的资源数大于或等于该进程尚需求资源最大量时＜就满足进程的当前申请。这样

就可以保证至少有一个进程也许得到所有资源而执行到结束，然后归还它所占有

的所有资源供其它进程使用。

银行家算法中的数据结构

(1)可运用资源向量Available(一维数组)

是一个具有m个元素，其中的每一个元素代表一类可运用的资源数目，其

初值是系统中所配置的该类所有可用资源数目。假如AvailableLj］二k,表达系统

中现有Ri类资源k个。

(2)最大需求矩阵Max(二维数组)

m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需

求。假如Max(i,j)=k,表达进程i需要Rj类资源的最大数目为k。

(3)分派矩阵Allocation(二维数组)

m的矩阵，它定义了系统中每一类资源当前己分派给每一进程的资源数。假

如Allocation(i,j)=k,表达进程i当前已分得Rj类资源k个。

(4)需求矩阵Need(二维数组)

是一个具有n*m的矩阵，用以表达每一个进程尚需的各类资源数。假如

Need(iJ)=k,表达进程i还需要Rj类资源k个，方能完毕其任务。

Need(i,j)=Max(ij)-Allocation(i,j)

题目二十一：SPOOLING技术

1.设计目的

设计一个SPOOLING假脱机输出的模拟程序,更好地理解和掌握SPOOLING

技术的实现原理。

2.设计内容

SPOOLING技术广泛地应用于各种计算机的I/O。该技术通过预输出和缓输

出的方法，使用共享设备的一部分来模拟独占设备。

1）设计一个实现SPOOLING技术的进程

设计一个SPOOLING输出服务进程、一个SPOOLING输出进程、两个用户

请求进程。用户进程请求输出一系列信息，调用输出服务进程，由输出服务进程

将该信息送入输出井。等待SPOOLING进程进行输出。SPOOLING输出进程工

作时.，根据请求块记录的各进程要输出的信息将其输出。

2）设计进程调度算法

进程调度采用随机算法，两个请求输出的用户进程的调度概率各为45%,

SPOOLING输出进程为10%,这由随机数发生器产生的随机数来模拟决定。

1）进程状态

2）进程基本状态有可执行、等待、结束三种。可执行状态就是进程正在运

营或等待调度的状态；等待状态又分为等待状态1、等待状态2、等待状

态3。

状态变化的条件为：

①进程执行完毕时，置为“结束”态。

②服务程序在将输出信息送输出井时，如发现输出井已满，将调用进程置为

“等待状态1"。

③SPOOLING进程在进行输出时，若输出井空，则进入“等待状态2"。

④SPOOLING进程输出一个信息块后，应立即释放该信息块所占的输出井空

间，并将正在等待输出的进程置为“可执行状态”。

⑤服务程序在输出信息到输出井并形成输出请求信息块后，若SPOOLING

进程处在等待态，则将其置为“可执行态”。

⑥当用户进程申请请求输出块时，若没有可用请求时，调用进程进入“等待

状态3”。

题目二十二：进程间通信

1.设计目的

Linux系统的进程通信机构（IPC）允许在任意进程间大批量的互换数据。本

实验的目的是了解和熟悉Linux支持的通信机制、共享存储区机制及信号量

机制。

2.设计内容

（1）共享存储区的创建，链接和断开

（2）消息的创建，发送和接受

（3）编写程序1,实现运用共享存储区进行进程通信。使用系统调用

shmget（）,shmat（）,shmdt。及shmctl。编制•长度为1k的消息发送和

接受程序。

（4）编写程序2,实现运用消息队列进行进程通信。使用系统调用shmgct。,

shmat（）,shmdt。及shmctl。编制一长度为1k的消息发送和接受程序。

〈程序设计提醒〉

（1）为了便于操作和观测结果，用一个程序作为“引子”，先后fork（）

两个子进程，SERVER和CLIENT,进行通信。

（2）SERVER端建立个Key为75的共享区，并将笫一个字节置为-1,

作为数据空的标志，等待其他进程发来的消息。当该字节的值发生变

化时，表达收到了消息，进行解决。然后再次把它的值设为-1。假如

碰到的值为0,则视为结束信号，取消该队列，并退出SERVERo

SERVER每接受到一个消息后显示一句“（server）receivedvo

（3）CLIENT端使用Key为75的共享区，当共享取得第一个字节为-1时,

SERVER端空闲，可发送请求。CLIENT随即填入9到0。期间等待

SERVER端再次空闲。进行完这些操作后，CLIENT退出。CLIENT

每发送一条信息后显示一句“（client）sent”。

（4）父进程在SERVER和CLIENT均退出后结束。

题目二十三：进程的管道通信和软中断通信

1.设计目的

加深对进程概念的理解，明确进程和程序的区别。进一步结识并发执行的实

质，并了解Linux系统中进程通信的基本原理。

2.设计内容

（1）编制一段程序，实现进程的管道通信。

使用系统调用pipe（）建立一条管道线，两个子进程P1和P2分别向管道各写一

句话：

Child1issendingamessage!

Child2issendingamessage!

而父进程则从管道中读出来自两个子进程的信息，显示在屏幕上。

规定父进程先接受子进程P1发来的消息，再接受子进程P2发来的消息。

（2）编制一段程序，实现进程的软中断通信。

使用系统调用fork。创建两个子进程，再用系统调用signal。让父进程捕获键

盘上来的中断信号（即按DEL键）；当捕获到中断信号后，父进程用系统调用

Kill。向两个子进程发出信号，子进程捕获到信号后分别输出下列信息后终止：

Child1iskilledbyparent!

Child2iskilledbyparent!

父进程等待两个子进程终止后，输出下列信息后终止。

Parentiskilled!

题目二十四：linux进程与线程通讯

1.设计目的：

深刻理解线程和进程的概念，掌握线程和进程在组成成分上的差别以及与其

相适应的通信方式和应用目的。

2.设计内容：

以Linux系统进程和线程机制为背景，掌握fo「k()和clone。系统调用的

形式和功能以及与其相适应的高级通信方式。由fork派生的子进程之间通过

pipe通信，由clone创建的线程之间通过共享内存通信。

以生产者■消费者为例，通过实验理解fork和clone两个系统调用的区别。程序

规定可以创建4个进程或线程，具中涉及两个生产者和两个消费者，生产者和

消费者之间可以传递数据。

题目二十五：动态不等长存储资源分派算法

1.设计目的：

理解动态异常存储分区资源管理，掌握所需数据结构和管理程序，了解各种存储

分派算法的优缺陷。

2.设计内容：

(1)分析Unix最先适应(firstfit,ff)存储分派算法。即map数据结构、存储

分派函数malloc()和存储释放函数mfree(),找出与算法有关的成分。

(2)修改上述算法有关成分，使其分别体现BF(bestfit,最佳适应)分派原则

WF(worstfit,最坏适应)分派原则。

题目二十六：编程演示三种存储管理方式的地址换算过程

1.设计目的：

理解页式、段式、段页式的逻辑地址向物理地址的转换过程。理解重定位的含义。

规定演示对的、清楚，编程所用工具不限

2.设计内容：

编程实现演示页式、段式、段页式的地址转换过程

1、分页方式的地址换算

2、分段方式的地址换算

3、段页式的地址换算

题目二十七：编程模拟多进程共享临界资源

1.设计目的：理解多进程共享临界资源的原理，并编程实现

2.设计内容：

规定产生3个进程：

（1）两个进程模拟需要进入临界区的用户进程，当需要进入临界区时，显示：

“进程x请求进入临界区…”，同时向管理进程提出申请；申请返回，表达进入了

临界区。在临界区中档待一段随机时间，并显示：“进程x正在临界区…”；当时

间结束，显示：“进程x退出临界区…”，同时向管理进程提出退出申请；当申请

返回，显示：“进程x已退出临界区。”

（2）一个进程作为原语的管理进程，接受其他进程的临界区进入请求：假如允

许进入，则设立相应变量，然后返回；假如不允许进入，则进入循环等待，直到

允许为止；

（3）对临界区的访问应遵循空闲让进、忙则等待、有限等待、让权等待的准则。

（4）进程间通信可以采用信号、消息传递、管道或网络通信方式。

题目二十八：文献系统的设计与实现

1.设计目的：

通过设计一个小型文献系统，进一步掌握文献管理的方法和技术，在实践

中去结识文献系统的实现原理，加深对文献系统存储、数据的安全性和一致性理

解，使学生初步具有研究、设计、编制和调试操作系统模块的能力。

2.设计内容：

实现一个模拟文献系统，可为该文献系统设计相应的数据结构来管理目录、

磁盘空闲空间、己分派空间等。提供文献的创建、删除、移位、改名等功能。、

提供良好的界面，可以显示磁盘文献系统的状态和空间的使用情况。提供虚拟

磁盘转储功能，可将信息存入磁盘，还可从磁盘读入内存。

题目二十九：主存空间的分派与回收

1.设计目的

本设计题目重要让大家熟悉主存的各种分派与回收。所谓分派，就是解决多

道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运营完毕时，

将作业或进程所占用的主存空间归还给系统。主存的分派与回收的实现是与主存

储器的管理方式有关的。通过本次设计，帮助学生理解在不同的存储管理方式下,

如何实现主存空间的分派与回收。使学生初步具有研究、设计、编制和调试操作

系统模块的能力。

2.设计内容

采用可变式分区管理，使用初次或最佳适应算法实现主存的分派与回收。可

以采用分区说明表或空闲区链来进行。设计多个作业或进程动态请求内存资源的

模拟系统，使用初次或最住适应算法实现内存的分派与回收，实现可变式分区管

理；设计相应的内存分派算法，定义相关数据结构，以及输出显示每次请求分派

内存的结果和内存的E分派和未分派的状况。

题目三十：Windows多线程控制台程序

1.设计目的

学习和掌握如何编写Windows多线程控制台程序。通过编写程序，加深对进

程和线程关系的理解，掌握多线程程序的执行和编写技巧。

2.设计内容

写一个单进程多线程的Windows控制台程序，该程序在一个进程内建立N

个线程来执行指定的任务。N由命令行传递给系统。

Win32控制台程序中，主函数的格式如：

Voidmain（intargc,char*argv[]）,可以获取命令行参数。

通过VC++”工程/设立”的C/C++属性页设立应用程序为“MTD”多线程。

运用Win32APICreatcThrcadO来生成线程。

题目二十一：读者与写者问题（进程同步问题）

1.设计目的

了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同

步问题的方法，进而学会运用进程的同步与互斥。

设计规定：编程模拟读者与写者问题，规定显示结果。

2.设计内容

（1）多个进程共享一个文献，其中只读文献的称之为读者，其余只写文献的称

为写者。读者可以同时读，但是写者只能独立写。

（2）对（1）修改，使得它对写者优先，即一旦有写者到，后续的读者都必须等

待，而无论是否有读者在读文献。

题目三十二：模拟文献管理系统

1.设计目的

进一步了解文献管理系统，初步掌握文献管理系统的实现方法。

2.设计内容

编写一程序，模拟一个简朴的文献管理系统。树型结构，目录下可以是目录,

也可以是文献。

在此文献管理系统，可实现的操作有：

改变目录：格式：cd〈目录名》

显示目录：格式：dirk目录名》]

创建目录：格式：md〈目录名）

删除目录：格式："＜目录名）

新建文献：格式：edit〈文献名》

删除文献：格式：del〈文献名）

退出文献系统：exit

实现参考：

（1）文献系统采用二叉树型存储结构，结点结陶如下：

StructFileNode

（

Charfilename[FILENAMELEN];〃文献名/目录名

Intisdir;〃目录、文献的辨认标志

Intijlink;〃文献链接数

Intadr;〃文献的地址

StructFileNode"parent,"child;〃指向父亲的指针和左孩子的指针

StructFi1eNode*siblingprev,*siblingnext;〃指向前一个兄弟的指针和后

一个兄弟的指针。

）

（2）目录名和文献名支持全途径名和相对途径名，途径名各分量间用隔

开

（3）功能具体描述：

改变目录：改变当前工作目录，目录不存在是给出犯错信息

显示目录：显示指定目录下或当前目录下所有文献和一级目录（选做：带/s参

数的dir命令，显示所有子目录）

创建目录：在指定途径或当前程径下创建指定目录。重名时给出犯错信息。

删除目录：删除指定目录下所有文献和子目录。要删目录不空时，要给出提醒是

否要删除。

创建文献：创建指定名字的文献，只要创建表达文献的节点即可，内容及大小不

考虑。

删除文献：删除指定文献，不存在时给出犯错信息。

退出文献系统:exit

（4）总体流程：

初始化文献目录

输出提醒符，等待接受命令，分析键入的命令；

对合法的命令，执行相应的解决程序，否则输犯错误信息，继续等待新命令。直

到键入exit退出为止。

题目三十三：内存的申请与释放

1.设计目的

了解操作系统内存分派的算法。

2.设计内容

（1）定义一个自由存储块链表，按块地址排序，表中记录块的大小。当请求分

派内存时，扫描自由存储块链表，址到找到一个足够大的可供分派的内存块，若

找到的块大小正好等于所请求的大小时，就把这一块从自由链表中取下来，返回

给申请者。若找到的块太大，即对其分割，并从该块的高地址部分往低地址部分

分割，取出大小合适的块返回给申请者，余下的低地址部分留在链表中。若找不

到足够大的块，就从操作系统中请求此外一块足够大的内存区域，并把它链接到

自由块链表中，然后再继续搜索。

释放存储块也要搜索自由链表，目的是找到适当的位置将要释放的块插进去，假

如被释放的块的任何一边与链表中的某一块临接，即对其进行合并操作，直到没

有合并的临接块为止，这样可以防止存储空间变得过于零碎。

（2）空闲区采用分区说明表的方法实现（1）中的功能。规定同上。