课 程 设 计 报 告
课程名称 操作系统 课题名称 进程调度算法的设计
专 业 通信工程 班 级 1101 学 号 201103020135 姓 名 莫 黎 指导教师 颜国风
2014年 6 月 29 日
湖南工程学院 课 程 设 计 任 务 书
课程名称 操作系统 课 题 进程调度算法的设计
专业班级 通信1101 学生姓名 莫 黎 学 号 201103020135 指导老师 颜国风 审 批
任务书下达日期 2014 年 6 月 23 日 任务完成日期 2014 年 6 月 29 日
1设计内容与设计要求
1.1设计内容
1.1.1 进程调度算法的设计 ● 设计要求：
①设计进程控制块PCB表结构，分别适用于优先数调度算法和循环轮转调度算法。
②建立进程就绪队列。对两种不同算法编制入链子程序。 ③编制两种进程调度算法：1）优先数调度；2）循环轮转调度 ● 设计技术参数:
①本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。
②为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。
③在优先数算法中，优先数的值为50与运行时间的差值，即P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。
④对于遇到优先数一致的情况，采用FIFO策略解决。 1.1.2 银行家算法设计 ● 设计要求：
编制银行家算法通用程序，并检测所给状态的系统安全性。设进程I提出请求Request[N]，则银行家算法按如下规则进行判断。
(1)如果Request[N]<=NEED[I，N]，则转(2)；否则，出错。 (2)如果Request[N]<=AVAILABLE，则转(3)；否则，出错。 (3)系统试探分配资源，修改相关数据： AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUEST
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 ● 设计技术参数：
假设有n个进程m类资源，则有如下数据结构：
可利用资源向量Available。这是一个含有m个 元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj 类资源K个。
最大需求矩阵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]。 1.1.3页面置换算法模拟设计 ● 设计要求：
计算并输出下述各种算法在不同内存容量下的命中率。
A. FIFO先进先出的算法 B. LRR最近最少使用算法
C. OPT最佳淘汰算法（先淘汰最不常用的页地址） D. LFR最少访问页面算法 E. NUR最近最不经常使用算法
● 设计技术参数：
（1）命中率=1-页面失效次数/页地址流长度
（2）本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。
（3）随机数产生方法，采用系统提供函数SRAND()和RAND ()来产生
● 实验过程：
(1)．过随机数产生一个指令序列，共320条指令，具体的实施方法是： A. [0，319]的指令地址之间随机选取一起点M; B. 顺序执行一条指令，即执行地址为M+1的指令；
C. 在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’;
D. 顺序执行一条指令，其地址为M’+1；
E. 在后地址[M‘+2，319]中随机选取一条指令并执行； F. 重复A—E，直到执行320次指令。 (2)．指令序列变换成页地址流，设：
① 页面大小为1K；
② 用户内存容量为4页到32页； ③ 用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条—第9条指令为第0页（对应虚存地址为[0，9]）； 第10条—第19条指令为第1页（对应虚存地址为[10，19]）； 。。。。。。。。。。。。。。。。。。。。。
第310条—第319条指令为第31页（对应虚存地址为[310，319]）； 按以上方式，用户指令可组成32页。
(3). 计算并输出下述各种算法在不同内存容量下的命中率。 1.1.4 作业调度模拟 ● 设计要求：
① 加深对作业概念地理解。 ② 掌握短作业优先调度算法。
③ 深入了解批处理系统如何组织作业、管理作业和调度作业。 ④ 了解作业控制块的作用，以及作业控制块的内容和组织方式。 ● 设计技术参数：
① 利用作业控制块将系统中的作业组织起来；
为了将系统中的作业组织起来，需要为每个进入系统的作业建立档案以记录和作业相关的信息，例如作业名、作业所需要的资源、作业执行的时、作业进入系统的时间、作业信息在存储器中的位置、指向下一个作业控制块的指针等信息。这个记录作业相关信息的数据块称为作业控制块（JCB）,并将系统中等待作业调度的作业控制块组织成一个队列，这个队列称为后备队列。当一个作业全部信息进入系统后，就为其建立作业控制块，并挂入后备队列中。当一个作业全部进入系统后，就为其建立作业控制块，并挂入后备队列中。当进行作业调度时，从后备队列中查找选择作业。
② 利用短作业优先算法进行作业调度；