现代制造工程2006年第5期专题研究———生产调度系统
基于I LO G S OL VER 的Job 2Shop 调度算法实现
杨达玲,杨建军,白宏斌
(北京航空航天大学机械工程及自动化学院,北京100083)
摘要 通过使用约束规划方法对Job 2Shop 调度问题进行描述和建模,设计用于求解Job 2Shop 调度问题的禁忌搜索算法,在此基础上基于先进的约束规划系统I L OG 对算法进行实现。实践证明基于约束规划将I L OG 优化组件应用于对Job 2
Shop 调度问题的求解中,不仅可以大大提高编程效率而且最后结果也有显著提高。
关键词:Job 2Shop 约束规划 CSP I L OG S OLVER
中图分类号:TP391 文献标识码:A 文章编号:1671—3133(2006)05—0022—03
0 引言
根据车间内工件的工艺路线的不同,车间调度问题可分为所有工件工艺路线相同的Fl ow 2Shop 型和工件工艺路线不同的Job 2Shop 型,而Job 2Shop 调度问题是产品制造业中共存的问题,它是实际生产调度问题的高度抽象。理论上,Job 2Shop 调度问题属于NP 问题,为了解决这一难题,产生了数学规划、系统仿
真等一系列方法,取得了很大成绩[1]
,但是仍然存在求解规模小,时间长等缺点,而随着约束理论和约束规划系统的发展,约束规划技术已经应用于很多商用系统。
基于约束的规划方法是一个相对较新的领域,通常称为Constraint Logic Pr ogra mm ing 或Constraint Pr o 2gra mm ing (CP ),相应的软件工具被称为约束规划系统,其中最具代表性也是应用最为广泛的就是I L OG 优化组件。约束规划起源于上世纪80年代中期,但直到近期才作为一种解决优化问题的方法被人们所认识,它尤其适合于运筹学领域的组合搜索和具有多种约束的问题。约束规划将描述问题和解决问题分离,用户只需描述问题,
剩余的工作全部由计算机来完图1 CSP 求解过程
成。约束规划中变量值域是有限的一类CP 问题称为约束满足问题(CSP )。实际生产中95%的工业应用都属于CSP [2]
,其中包括Job 2Shop 问题。图1所示是CSP 问题求解的一般过程。
本文基于Job 2Shop 约束规划模型,设计了对其求解的禁忌搜索算法,最后使用I L OG 优化组件进行实现和求解,并通过标准FT10310问题验证其有效性。
1 Job 2Shop 问题约束规划模型
为使用约束规划系统I L OG 对Job 2Shop 问题进行表达和求解,对Job 2Shop 问题的约束规划模型加以描述。
111 符号及变量定义
为了便于描述,定义符号及变量如下。k:工件序号,O 为所有工件的集合,k ∈O;i:某工件的工序序号,不同工件k 包括的i 总数不同;j :加工机器序号,RES 为所有机器的集合j ∈RES ;O ki:工件k 的第i 个工序;
rkij :各工序的加工机器,工件k 的第i 个工序在机器R j
上加工,R k j ∈RES ;stkj :各工序的开始时间,工件k 的第j 个作业的开始时间;etki:各个工序的结束时间,工件k 的第i 个作业的结束时间;duki:加工时间,工件k 的第i 个作业的加工时间;S j :机器j 上的加工工序的一种有序集合,S 为Job 2Shop 问题解集;n:求得近优解搜索时所需的回溯次数。112 约束
1)顺序约束。即同一工件内不同工序之间的工
艺顺序约束,即O ki 先于O kj 加工:
stki +dukj <=stkj
2)分离能力约束。即不同工件的作业之间不能
同时占用同一台机床的约束:
(Πp Πd,R k 1ip ≠R k 2jq )∪(stk 1i +duk 1i )≤stk 2j ∪(stk 2j +duk 2j )≥stk 1i
3)累积能力约束。任何时刻对资源的总需求和
消耗不超过可用量限制:
∑rk ij ≤rj (设备维修能力)
2
2
专题研究———生产调度系统现代制造工程2006年第5期
113 目标函数
CSP 的求解目标是在尽可能小的回溯次数下,以
尽可能快的时间,在满足所有约束的条件下以最小化制造周期(Makes pan )为性能指标,即在可行解的解空间中找到一个可行解,该解的所有工件的最大结束时间与其他所有解相比为最小:
m in (m ax (etk i ))∩m in (n )
2 基于I LO G 的禁忌搜索算法
211 禁忌搜索算法
禁忌搜索算法是一种在组合优化问题中找近似最优解的一种启发式方法,这种方法最早由Gl over 提出并确切设计[4,5]
,算法主要流程为:从一个初始可行解(初始解)开始,通过变换得解的邻域函数,按照某种选择策略从邻域中选取一个解(邻域策略),从初始解移动到新解,再以此解为出发点继续下一轮搜索,如此往复直到满足某个条件(停机准则)。参考经典禁忌搜索算法,本文设计算法流程如图2所示
。
图2 算法流程图
212 基于I L OG 的算法实现
在对于以上禁忌搜索算法进行实现过程中,难点
在于不仅要求能够将资源、任务等基本对象自身以及相互之间的各种约束完全表示出来,而且还要求具有能够在大量迭代过程中,能够以高效运行的数据结构来表达可行解、邻域等复杂对象。而I L OG 优化组件中的S OLVER 模块则通过自身强大的预定义约束库,以及具有强大行为函数的基本对象很好地解决了以上两个问题,下面就算法的实现作详细介绍。
在I L OG S OLVER 组件中,约束是一个对象,也可以把约束认为是一个布尔表达式。表达式的值依赖于约束的可满足性:如果不违反约束,则表达式的值为
真;如果约束不被满足,则表达式的值为假。当一个约
束通过函数向搜索引擎公布时,该约束立刻被用来减少它所包含变量的论域,在满足所有约束的条件下给每个变量赋值,如果最终每个变量都至少被赋了1个值,则说明这个问题可解;否则,说明该问题不可解。
S OLVER 通过这种机制,以处理各种复杂的约束关系为核心,提供了强大的核心搜索引擎以及解集、邻域等基本对象和数据结构,方便了算法的实现和优化。
各基本对象在禁忌搜索算法求解Job 2Shop 问题中的作用关系图如图3所示
。
图3 各基类作用关系图
在图3中,Il oSolver 作为核心搜索引擎使用以下
约束传播算法对问题求解:维持一个变量队列,称为约束传播队列。当改变一个约束变量时,如果该变量没在队列中,则把它放入队列的尾部。只要队列中有变量,算法就从队列中取第一个变量,并称这个被取的变量是在过程中。当一个变量在过程中时,则先将它从传播队列中去掉,与这个变量相关的每个约束都被检查。对于每一个被检查的约束,这个约束包含的所有变量都被检查,它们的论域被减小以满足这个约束,如果在这个动作中有一些变量的论域被减小,则这些变量也被放入队列中。如果所有论域中的值都满足约
束,或者有一个论域为空,则算法停止[6]
。
Il o Model 用于描述模型,包括约束、变量、论域等
基本对象,并使用一致性技术从中将所需要的信息提取并送到搜索引擎。它提供了一个足够的预定义约束库来满足广泛的应用。可以用逻辑操作or,and,not 将各种约束结合起来,为特殊问题建立更复杂的约束,很少需要自己定义新的约束类。当然,在逻辑操作不能满足特定应用所需的约束时,也可以定义自己的约束类。
Il oSchedulerEnv 存储了模型对象的环境参数,其包括了设备能力约束、任务转换时间约束、工序前、后约束等对调度结果产生整体影响的因素,并可以根据问题的需要,从“无作用”到“强作用”,从弱至强的6
3
2
现代制造工程2006年第5期专题研究———生产调度系统
个等级来灵活地设定各种环境约束的影响能力。在本
文第1章所叙述Job2Shop问题约束规划模型基础上,
将设备能力约束和工序前、后约束的约束能力设置为
强(Il oH ight),不允许调度结果中出现超出设备能力和
工序前、后混乱的现象。
Il oGoal作为搜索目标的基类,存储在一个目标栈
里。简单地说,当第一个子目标弹出运行时,其他的子
目标被保存为未运行状态,当第一个子目标运行完毕
后返回运行结果,若运行失败还需保存Solver状态并
将下一个未被运行的子目标弹出。实际上约束类是目
标类的子类,所以约束也是目标,也可以被压入目标
栈。在此,仍然基于约束规划模型以最小制造周期
(makes pan)为目标。
Il o MetaHeuristic提供了局部搜索中用于描述启发
规则的一系列方法,包括测试当前条件下该启发规则
是否合法,在该规则条件下是否接受当前邻域选择
(move)以及检测规划是否完成等,从而在当前启发式
规则条件下在领域中高效地作出最优选择。程序基于
这个基类表示了禁忌表及其变化情况,实现了禁忌搜
索这一启发规则。
Il oNHood基于使用由邻域选择(move)引起的解
集变化(deltas)来描述可行解的核心思想,提供了从初
始化、运算测试到最后设置标志位等一系列局部搜索
中,用于描述领域结构及其变化的方法。由此,程序实
现了对邻域的表达和高效搜索。
而Il oSchedulerSoluti on作为可行解容器,不仅表
示了最后的调度结果,而且在整个搜索过程中作为中
间数据结构,纪录着每一次局部搜索的结果及其变化。
3 实例计算与分析
本文以标准的FT10310问题为算例。输入数据
见表1。
表1 算例输入数据
工 序12345678910
工 件机
器
时
间
机
器
时
间
机
器
时
间
机
器
时
间
机
器
时
间
机
器
时
间
机
器
时
间
机
器
时
间
机
器
时
间
机
器
时
间
1129278394365496117628569441021 21433905751011469228746646872930 32911854393749906108127891045533 4281395171599799528854981022643 5314162226614265699218491072753 638422652495948107214776556825 72461374613137326211032989830555 83311862466745327889191048836479 91762694766513851011740889526974 10285113361779641076647452590845 历史上该问题所得到的最优解为930[7],在Penti2 u m I V214G硬件条件下采用本文算法每次都能在2s 左右稳定地取得最优结果1030。图4所示为本文算例甘特图
。
图4 算例甘特图
4 结语
本文基于约束规划技术,使用I L OG优化组件这一有力工具对Job2Shop问题进行建模和求解,可以充分表达问题的各种约束条件,并以约束为核心,使用I L OG提供类以及数据结构对模型进行有效地求解。
参考文献:
[1] 徐俊刚,戴国忠,王宏安.产调度理论和方法研究综
述[J].计算机研究与发展,2004(2).
[2] 王宏安,等.基于约束满足的Job2Shop调度算法研究
[J].计算机工程与应用,2003(3).
[3] 贺仁杰.成像侦察卫星调度问题研究[D].合肥:国
防科技大学,2004(4).
[4] Gl over F.Tabu Search2Part1.I N F OR MS Journal on
Computing,1989,1.
[5] Gl over F.Tabu Search2Part2.I N F OR MS Journal on
Computing,1990,2.
[6] 姜英新,孙吉贵.约束满足问题求解及I L OG S OLV2
ER系统简介[J].吉林大学学报(理学版),2002
(1).
[7] 王凌.车间调度及其遗传算法[M].北京:清华大学
出版社,2003.
作者简介:杨达玲,硕士研究生,主要研究车间调度、制造执行系统等。
收稿日期:2006202223
42
课程设计报告 设计名称：模拟实现一种处理机调度算法 学生姓名： xxx 专业：计算机科学与技术 班别： xxxxxxxx 学号： xxxxxx 指导老师： xxxxx 日期： 2014 年 6 月 20 日
初始条件： 1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。 2．实践准备：掌握一种计算机高级语言的使用。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1．模拟进程调度，能够处理以下的情形： ⑴能够选择不同的调度算法（要求中给出的调度算法）； ⑵能够输入进程的基本信息，如进程名、优先级、到达 时间和运行时间等； ⑶根据选择的调度算法显示进程调度队列； ⑷根据选择的调度算法计算平均周转时间和平均带权周 转时间。 2．设计报告内容应说明： ⑴需求分析； ⑵功能设计（数据结构及模块说明）； ⑶开发平台及源程序的主要部分； ⑷测试用例，运行结果与运行情况分析； ⑸自我评价与总结： i）你认为你完成的设计哪些地方做得比较好或比较出 色； ii）什么地方做得不太好，以后如何改正；
iii）从本设计得到的收获（在编写，调试，执行过程中 的经验和教训）； iv）完成本题是否有其他方法（如果有，简要说明该方 法）； 进程调度模拟设计——先来先服务、优先级法1、背景： 当计算机系统是多道程序设计系统时，通常会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个CPU可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法成为调度算法。 进程调度的核心问题是采用什么样的算法把处理机分配给进程，好的算法将提高资源利用率，减少处理机的空闲时间，避免有些作业长期得不到相应的情况发生等，从而设计出受欢迎的操作系统。较常见的几种进程调度算法有：先来先服务调度算法；短作业优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先算法和多级反馈队列调度算法等。 2.1设计目的 无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机
福建农林大学计算机与信息学院 课程设计报告 课程名称：操作系统 实习题目：进程调度算法模拟 姓名： 系：计算机科学与技术系 专业：计算机科学与技术 年级：2012 学号： 指导教师： 职称：副教授 年月日
福建农林大学计算机与信息学院计算机类 课程设计结果评定
目录 1.本选题课程设计的目的 (4) 2.本选题课程设计的要求 (4) 3.本选题课程设计报告内容 (4) 3．1前言 (4) 3．2进程调度算法模拟的环境 (4) 3．3系统技术分析 (4) 3．4系统流程图及各模块 (5) 3．5程序调试情况 (8) 4．总结 (11) 参考文献 (11) 程序代码 (12)
1.设计目的 课程设计将课本上的理论知识和实际有机的结合起来，锻炼学生的分析系统，解决实际问题的能力。提高学生分析系统、实践编程的能力。 2.设计要求 利用学到的操作系统和编程知识，完成具有一定难度的系统分析研究或系统设计题目。其中：专题系统理论研究应包括研究目的、目标，论点和论据以及证明推导等；分析、设计系统应包括编写、调试程序以及最后写出设计报告或系统说明文档文件，系统说明文档包括系统界面、变量说明、系统功能说明、编程算法或思路、流程图和完整程序。具体要求如下： 1、对系统进行功能模块分析、控制模块分析正确； 2、系统设计要实用； 3、编程简练，可用，功能全面； 4、说明书、流程图要清楚。 3.设计方案 3.1前言 本程序包括三种算法，用C或C++语言实现，执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数，（运行时间，优先数由随机函数产生），执行，显示结果。 3.2本选题设计的环境 WindowsXP下的Microsoft Visual C++ 6.0 3.3系统技术分析 （1）编程实现对N个进程采用某种进程调度算法（如动态优先权调度算法、先来先服务算法、短进程优先算法、时间片轮转调度算法）调度执行的模拟。（2）每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段：进程标识数ID。 进程优先数PRIORITY，并规定优先数越大的进程，其优先权越高。
实验报告 学院（系）名称：计算机与通信工程学院 姓名学号专业计算机科学与技术班级2009级3班实验项目实验一：处理机调度算法的实现 课程名称操作系统课程代码0668036 实验时间2011 年11月17日第3、4节 2011 年11月21日第7、8节 2011 年11月24日第3、4节 实验地点软件实验室7-216 批改意见成绩 教师签字： 实验内容： 1．设定系统中有五个进程，每一个进程用一个进程控制块表示。 2．输入每个进程的“优先数”和“要求运行时间”。 3．为了调度方便，将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程，用指针指出队列的连接情况。 4．处理机调度总是选队首进程运行。采用动态优先数算法，进程每运行一次优先数就减“1”，同时将运行时间减“1”。 5．若某进程运行时间为零，则将其状态置为“结束”,且退出队列。 6．运行所设计程序，显示或打印逐次被选中进程的进程名，以及进程控制块的动态变化过程。 实验要求： 1．详细描述实验设计思想、程序结构及各模块设计思路； 2．详细描述程序所用数据结构及算法； 3．明确给出测试用例和实验结果； 4．为增加程序可读性，在程序中进行适当注释说明； 5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等； 6．实验报告撰写要求结构清晰、描述准确逻辑性强； 7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。
【实验过程记录（源程序、测试用例、测试结果及心得体会等）】 程序运行代码如下： #include
实验一模拟实现进程调度算法(4学时) ①、实验目的 a、进程调度是处理机管理的核心内容。观察、体会操作系统的进程调度方法，并通过一个简单的进程调度模拟程序的实现，加深对进程控制块、进程队列、进程调度算法，进程切换的理解，并体会和了解各种调度算法的具体实施办法。 b、提高实际动手编程能力，为日后从事软件开发工作打下坚实基础。 ②、实验内容 a、设计进程控制块PCB表结构，模拟实现进程调度算法：FIFO，静态优先级调度，时间片轮转调度，短进程优先调度算法，多级反馈队列调度。（实现静态优先级调度算法、短进程优先调度算法）。 b、编写一个进程调度程序模拟程序。模拟程序只对PCB进行相应的调度模拟操作，不需要实际程序。 c、由用户输入（可通过文件输入）进程名、进程状态、进程运行时间和进程优先级等数据。 ③、实验要求 a、使用模块化设计思想来设计。 b、给出主函数和各个算法函数的流程图。 c、学生可按照自身条件，随意选择采用的算法，（例如：采用冒泡法编写程序，实现短进程优先调度的算法）。 d、进程调度程序模拟程序只对PCB进行相应的调度模拟操作，不需要实际程序。 ④、运行结果 a、给出进程的调度模拟操作排序结果。 ⑤、提示 a、每个进程可有三个状态，并假设初始状态为就绪状态。 b、为了便于处理，程序中的进程运行时间以纳秒为单位计算。 C、各进程的优先级或轮转时间数以及进程需运行的纳秒数的初始值均由用户给定。 d、在优先级算法中，采用静态优先级。在时间片轮转算法中，采用可变时间片，由用户给定。 e、对于遇到优先级一致的情况，采用FIFO策略解决。
f、输入：进程流文件（文本文件），其中存储的是一系列要执行的进程，每个进程包括四个数据项：进程名进程状态(1就绪2等待3运行) 所需时间优先级(0级最高)。 g、输出：进程执行流等待时间平均等待时间。 ⑥、分析与讨论 a、各种进程调度算法的异同？ b、如何理解“算法+数据结构=程序设计”？ c、如何理解“数据结构始终是为实现功能服务的”？ ⑦、参考代码 参看：附录A1 考核方法： 1、实验报告占50%，程序设计30%，出勤占20%； 3、每次实验100分，2次实验的平均分为最终实验成绩。 注：无出勤只交实验报告者，以实验报告成绩×50%为最后成绩。 打游戏者发现一次本次实验扣10分。 早退者本次实验扣10分。 点名时未到者，后来补签到按照迟到时间长短扣分，点名后即来扣5分，1节课过后才来扣10分。
一、先来先服务算法 1．程序简介 先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。 2．分析 1．先定义一个数组代表各作业运行的时间，再定义一个数组代表各作业到达系统的时间，注意到达系统的时间以第一个作业为0基础（注意：若各程序都同时到达系统，则到达系统时间都为0）。 2．输入作业数。 3．然后运用循环结构累积作业周转时间和带权周转时间。 4．最后，作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。 3．详细设计 源程序如下： #include
华北科技学院计算机系综合性实验 实验报告 课程名称操作系统C 实验学期2012至2013学年第2学期学生所在系部计算机系 年级专业班级 学生姓名学号 任课教师杜杏菁 实验成绩 计算机系制
《操作系统C》课程综合性实验报告 开课实验室：基础六机房2013年6月3日 实验题目进程调度算法模拟 一、实验目的 通过对进程调度算法的模拟，进一步理解进程的基本概念，加深对进程运行状态和进程调度过程、调度算法的理解。 二、设备与环境 1.硬件设备：PC机一台 2.软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C \C++\Java等编程语言环境。 三、实验内容 （1）用C语言（或其它语言，如Java）实现对N个进程采用某种进程调度算法（如动态优先权调度）的调度。 （2）每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段： ?进程标识数ID。 ?进程优先数PRIORITY，并规定优先数越大的进程，其优先权越高。 ?进程已占用CPU时间CPUTIME。 ?进程还需占用的CPU时间ALLTIME。当进程运行完毕时，ALLTIME变为0。 ?进程的阻塞时间STARTBLOCK，表示当进程再运行STARTBLOCK个时间片后，进程将进 入阻塞状态。 ?进程被阻塞的时间BLOCKTIME，表示已阻塞的进程再等待BLOCKTIME个时间片后，将 转换成就绪状态。 ?进程状态STATE。 ?队列指针NEXT，用来将PCB排成队列。 （3）优先数改变的原则： ?进程在就绪队列中呆一个时间片，优先数增加1。 ?进程每运行一个时间片，优先数减3。 （4）为了清楚地观察每个进程的调度过程，程序应将每个时间片内的进程的情况显示出来，包括正在运行的进程，处于就绪队列中的进程和处于阻塞队列中的进程。
操作系统课程设计报告题目：进程调度算法的模拟实现_ 专业计算机科学与技术 学生姓名 班级 学号 指导教师 发放日期2015.1.30 信息工程学院
目录 1 概述 (1) 2 设计原理 (1) 2.1先来先服务算法 (1) 3 详细设计与编码 (2) 3.1 模块设计 (2) 3.2 系统流程图 (2) 3.3 系统详细设计 (2) 4 结果与分析 (6) 4.1 测试方案 (6) 4.2 测试结果 (6) 4.3 测试结果分析 (9) 5 设计小结 (10) 6 参考文献 (10) 附录程序代码 (12)
进程调度算法的模拟实现 进程调度算法的模拟实现 1 概述 选择一个调度算法，实现处理机调度，进程调度算法包括：先来先服务算法，短进程优先算法，时间片轮转算法，动态优先级算法。可选择进程数量，本程序包括四种算法，用C或C++语言实现，执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数，（运行时间，优先数由随机函数产生），执行，显示结果。 2 设计原理 2.1先来先服务(FCFS)算法 每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列 2.2 时间片轮转法(RR)算法 系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。 2.3短作业优先(SJF)算法 短作业优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。 2.4最高优先权优先(HRRN)算法 优先权调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入最高优先权优先调度算法。动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。
第四章处理机调度 4.3 习题 4.3.1 选择最合适的答案 1．某系统采用了银行家算法，则下列叙述正确的是（）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。 A.Max[i,j]=Allocation[i,j]+Need[i,j] B.Need[i,j]= Allocation[i,j]+ Max[i,j] C.Max[i,j]= Available[i,j]+Need[i,j] D.Need[i,j]= Available[i,j]+ Max[i,j] 3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4．在下列选项中，属于预防死锁的方法是（）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5．在下列选项中，属于检测死锁的方法是（）。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6．在下列选项中，属于解除死锁的方法是（）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 7．为了照顾紧迫型作业，应采用（）。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则
一．课程概述 1.1.设计构想 程序能够完成以下操作：创建进程：先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。 1.2.需求分析 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多个进程能够并发地执行，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统必（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。本次实验在VC++6.0环境下实现先来先服务调度算法，短作业优先调度算法，高优先权调度算法，时间片轮转调度算法和多级反馈队列调度算法。 1.3.理论依据 为了描述和管制进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB(Process Control Block),PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息，系统总是通过PCB对进程进行控制，亦即，系统是根据进程的PCB 而不是任何别的什么而感知进程的存在的，PCB是进程存在的惟一标志。本次课程设计用结构体Process代替PCB的功能。 1.4.课程任务 一、用C语言（或C++）编程实现操作模拟操作系统进程调度子系统的基本功能；运用多 种算法实现对进程的模拟调度。 二、通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转、短作业优先、多 级反馈队列调度算法，使学生进一步掌握进程调度的概念和算法，加深对处理机分配的理解。 三、实现用户界面的开发
处理器调度习题
处理器调度 选择题 ?当CPU执行操作系统代码时，则处理机处于( )。 ?A．执行态 B．目态 C．管态 D．就绪态 ?( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 ?A．系统调用 B．操作系统 C．内核 D．特权指令 ?操作系统提供给程序员的接口是( )。 ?A．进程 B．系统调用 C．库函数 D．B和C ?用户程序向系统提出使用外设的请求方式是( )。 ?A．作业申请 B．原语 C．系统调用 D．I／O指令 ?当作业正常完成进入完成状态时，操作系统( )。 ?A．将输出该作业的结果并删除内存中的作业 ?B．将收回该作业的所占资源并输出结果 ?C．将收回该作业的所占资源及输出结果，并删除该作业 ?D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 ?下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 ?A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 ?B．作业是比进程低一级的概念。 ?C．一个作业至少由一个进程组成。 ?D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 ?作业从后备作业到被调度程序选中的时间称为( )。 ?周转时间B．响应时间C．等待调度时间D．运行时间 ?设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 ?A．T1+T2+T3 B．1／3(T1+T2+T3) ?C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 ?从作业提交给系统到作业完成的时间间隔称为作业的( )。 ?A．中断时间 B．等待时间 C．周转时间 D．响应时间 ?设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 ?A．1 h B．5 h C．2．5 h D．8 h ?FCFS调度算法有利于( )。 ?A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 ?C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 ?下列哪种说法不是SJ(P)F调度算法的缺点( )。 ?A．对于长作业(进程)不利 ?B．未考虑作业(进程)的紧迫程度 ?C．不能有效降低作业(进程)的平均等待时间 ?D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 ?选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 ?A．先来先服务调度算法B．短进程优先调度算法 ?C．优先权调度算法D．高响应比优先调度算法 ?在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 ?A．先来先服务调度算法B．短进程优先调度算法
: 操作系统 课程设计报告 @ 学校：广州大学 学院：计算机科学与教育软件学院 班级：计算机127班 课题：处理机调度程序 任课老师：陶文正、陈文彬 姓名：黄俊鹏 { 学号：11
班内序号：27 成绩： 日期：2015年1月6日 一、设计目的 在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。 二、设计要求 1）进程调度算法包括：时间片轮转法，短作业优先算法，动态优先级算法。2）可选择进程数量 3）本程序包括三种算法，用C语言实现，执行时在主界面选择算法（可用函数实现）（进程数，运行时间，优先数由随机函数产生）执行，显示结果。 三、设计思路及算法思想 1.· 2.界面菜单选项 一级菜单提供2个选项： ①自动生成进程数量 ②手动输入所需进程数量 一级菜单选择完毕后进入二级菜单： ①重新生成进程 ②时间片轮转法 《 ③短作业优先算法 ④动态优先级算法 ⑤退出程序 3.调度算法
程序所用PCB结构体 ! 需要用到的进程结构体如上图所示 1)时间片轮转法 主要是设置一个当前时间变量，curTime和时间片roundTime。 遍历进程组的时候，每运行一个进程，就把curTime += roundTime。进程已运行时间加roundTime 2)短作业优先算法 遍历进程组，找到未运行完成并且运行时间最短的进程，让它一次运行完成，如此往复，直到所有进程都运行完成为止。 3)— 4)动态优先级算法 做法跟短作业优先算法类似，此处主要是比较进程的优先数，优先级高者，先执行。直到全部执行完毕。当一个进程运行完毕后，适当增减其余进程的优先数，以达到动态调成优先级的效果。 4.程序流程图
（1）用C语言（或其它语言，如Java）实现对N个进程采用某种进程调度算法（如动态优先权调度）的调度。 （2）每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段：?进程标识数ID。 ?进程优先数PRIORITY，并规定优先数越大的进程，其优先权越高。 ?进程已占用CPU时间CPUTIME。 ?进程还需占用的CPU时间ALLTIME。当进程运行完毕时，ALLTIME变为0。 ?进程的阻塞时间STARTBLOCK，表示当进程再运行STARTBLOCK个时间 片后，进程将进入阻塞状态。 ?进程被阻塞的时间BLOCKTIME，表示已阻塞的进程再等待BLOCKTIME 个时间片后，将转换成就绪状态。 ?进程状态STATE。 ?队列指针NEXT，用来将PCB排成队列。 （3）优先数改变的原则： ?进程在就绪队列中呆一个时间片，优先数增加1。 ?进程每运行一个时间片，优先数减3。 （4）为了清楚地观察每个进程的调度过程，程序应将每个时间片内的进程的情况显示出来，包括正在运行的进程，处于就绪队列中的进程和处于阻塞队列中的进程。 （5）分析程序运行的结果，谈一下自己的认识。 实验代码 #include "iostream.h" #include "windows.h" //#define N 3 typedef struct{ int ID; int PRIORITY; int CPUTIME;
int ALLTIME; int STARTBLOCK; int BLOCKTIME; int STATE;//0-运行1-阻塞2-就绪3-结束4-未到达 int REACH; int TIME; }PROCESS; void textcolor (int color) { SetConsoleTextAttribute (GetStdHandle (STD_OUTPUT_HANDLE), color ); } void main(){ int i,time,max,l,l1,time1,flag=0,total=0,N,server[10],sum=0; PROCESS pro[10]; textcolor(13); cout<<"注意：本程序中状态代表如下"<
#include
PCB *cur,*p; p=head; cur=p->next; p->next =cur->next; cur->Level--; cur->Time--; cout<<"此次执行的进程信息（执行后）:进程名"; cout< 实验二处理机调度算法 （1）处理机调度的目的是什么？ 为提高内存利用率和系统吞吐量。 将那些暂时不能运行的进程调至外存，当内存不紧张时，将那些具备运行条件的就绪进程重新调入内存。 合理快速的处理计算机软件硬件资源，分配处理机，用以提高处理机的利用率及改善系统性能（吞吐量，响应时间）。 （2）处理机调度的算法有哪些，各自的优缺点是什么？ ①先来先服务算法：有利于长作业（进程），不利于短作业（进程）； ②短作业优先调度算法：有利于短作业（短进程），不利于长作业（长进程）； ③高优先权调度算法：静态缺点：可能导致低优先权进程长期得不到调度甚至饿死； 动态：优先权随进程等待时间增加或执行而变 ④高响应比优先调度算法 ⑤基于时间片轮转调度算法：时间片太小，会频繁发生中断，系统开销增大 时间片太大，响应进程慢。 ⑥多级反馈队列调度算法：具有较好的性能，能很好满足各类型用户的需求。 1．内存中作业运行的序列：A、B、D、C 2．A进入内存的时刻1，结束的时刻5 B进入内存的时刻5，结束的时刻8 D进入内存的时刻8，结束的时刻10 C进入内存的时刻10，结束的时刻15 3．平均周转时间：6 1．内存中作业运行的序列：B、C、A、D 2．B进入内存的时刻3，结束的时刻6 C进入内存的时刻6，结束的时刻11 A进入内存的时刻11，结束的时刻15 D进入内存的时刻15，结束的时刻17 3．平均周转时间：8.75 （4）画出处理机调度算法的程序流程图； （5）补全参考程序； void process(int currentTmp, int nextTmp) { int j; int s=nextTmp-currentTmp; while(memoryNum>0 && s>=memory[0].needtime){ totalTime=totalTime+memory[0].needtime; s=s-memory[0].needtime; printf("线程%c的开始时间是:%d,结束时间 是:%f\n",memory[0].id,memory[0].cputime,totalTime+1); allTime+=totalTime+1; memoryNum--; for(j = 1; j<=memoryNum; j++) memory[j-1] = memory[j]; if(waitNum>0 && s>0){ memory[memoryNum] = wait[0]; memoryNum++; waitNum--; for(j = 1; j<=waitNum; j++) wait[j-1] = wait[j]; sort(memory,memoryNum, 'P'); } } if(memoryNum>0 && s 操作系统 ——项目文档报告 进程调度算法 专业： 班级： 指导教师： 姓名： 学号： 一、核心算法思想 1.先来先服务调度算法 先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。 2.短作业（进程）优先调度算法 短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。该算法对长作业不利，完全未考虑作业的紧迫程度。 3.高响应比优先调度算法 在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足之处是长作业的运行得不到保证。如果我们能为每个作业引人动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为: 优先权=（等待时间+要求服务时间）/要求服务时间 即优先权=响应时间/要求服务时间 如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因而该算法有利于短作业。 当要球服务的时间相同时，作业的优先权决定于其等待时间，等待时间越长，优先权越高，因而它实现的是先来先服务 对于长作业，作业的优先级可以随着等待时间的增加而提高，当其等待时间足够长时，其优先级便可以升到很高，从而也可获得处理机。 4.时间片轮转算法 在时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。 二、核心算法流程图 中南大学 实验名称：处理机调度 课程名称：计算机操作系统 学生姓名盛希玲 学号 05 学院信息科学与工程学院 专业班级电子信息工程0602 完成时间 2008年10月12日 目录 一实验内容........................... 错误!未定义书签。二实验目的........................... 错误!未定义书签。三实验题目........................... 错误!未定义书签。四基本思想........................... 错误!未定义书签。五算法分析........................... 错误!未定义书签。六流程图............................. 错误!未定义书签。七算法描述........................... 错误!未定义书签。八运行输出结果....................... 错误!未定义书签。 一实验内容 选择一个调度算法，实现处理机调度。 二实验目的 多道系统中，当就绪进程数大于处理机数时，须按照某种策略决定哪些进程优先占用处理机。本实验模拟实现处理机调度，以加深了解处理机调度的工作。 三实验题目 设计一个按优先权调度和时间片轮转算法实现处理机调度的程序。 四基本思想 先选择时间片的个数和每个时间片需要的时间，正在运行的进程每运行一秒其优先权数目加一，即其优先权减小。每个时间片运行结束后，选择进入时间片进程优先权数目最小的进程，开始下一个时间片的运行。如果有进程运行结束，则离开，再在就绪队列中选择优先权数目最小的进程进入。在运行期间，如果有新的进程来到，按优先权大小放入就绪队列中。 五算法分析 定义一个结构体，此包含了PCB的信息： struct PCB { char PID[5]; /*进程名*/ int needtime; /*要求运行的时间*/ int cputime; /*已运行时间*/ int priority; /*优先权(越小越高)*/ int starttime; /*进入就绪队列的时间*/ int overtime; /*运行完成的时间*/ int state; /*状态:1就绪2运行3完成*/ struct PCB *next; }; 子函数struct PCB *create(int num,int n)用来建立一个按优先级大小排列的就绪进程链表和一个按时间先后循序排列的将进入就绪进程的链表。 第四章处理机调度 一. 选择最合适的答案 1．某系统采用了银行家算法，则下列叙述正确的是（）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。 **[i,j]=Allocation[i,j]+Need[i,j] **[i,j]= Allocation[i,j]+ Max[i,j] **[i,j]= Available[i,j]+Need[i,j] **[i,j]= Available[i,j]+ Max[i,j] 3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4．在下列选项中，属于预防死锁的方法是（）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5．在下列选项中，属于检测死锁的方法是（）。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6．在下列选项中，属于解除死锁的方法是（）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 7．为了照顾紧迫型作业，应采用（）。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（）相同。 A.先来先服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.长作业优先调度算法 《处理机调度算法的实现》源代码 #include "stdio.h" #include printf("到达时间：%d\n",p[i].reach); p[i].service=rand()%10+1; printf("服务时间：%f\n",p[i].service); if(c=='c'){ p[i].prior=rand()%10+1; printf("优先权:%d\n",p[i].prior); }else p[i].prior=0; p[i].finish=0; p[i].turnover=p[i].service; p[i].cum_turnover=p[i].prior; sort[i]=i; alltime=alltime+p[i].service; } for(i=1;i处理机调度算法实验报告
操作系统模拟进程调度算法
计算机操作系统-处理机调度实验报告
操作系统原理-第四章处理机调度习题
计算机操作系统课程设计源代码《处理机调度算法的实现源代码》
相关主题
文本预览