—B调算法学习教程.pptx





《—B调算法学习教程.pptx》由会员分享,可在线阅读,更多相关《—B调算法学习教程.pptx(54页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1.1.先来先服务First-Come-First-Served (FCFSFCFS)(作业进程)调度算法 FCFS是一种最简单的调度算法,可用于作业或进程调度。此算法的原则是按照作业到达后备作业队列(或进程进入就绪队列)的先后次序来选择作业(或进程)。FCFS算法属于非抢占方式,一旦一个进程占有处理机,它就一直运行下去,直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。FCFS算法易于实现,表面上很公平。CPU就绪队列就绪队列123后备队列后备队列内存第1页/共54页例题:在单道环境下,某批处理有四道作业,已知他们的进入系统的时刻、估计运算时间如下:作业进入时刻(h)运行时间(h)
2、12348.008.509.009.502.000.500.100.20用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间第2页/共54页8.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004.0016.006.50平均周转时间平均周转时间T平均带权周转时间平均带权周转时间T作业作业进入时刻进入时刻运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间12348.008.509.009.502.000.500.100.20带权周转用用FCFS算法算法:计算作业的运行情况、平均周转时间和平均计算作业的
3、运行情况、平均周转时间和平均带权周转时间带权周转时间完成时间=开始时间+运行时间周转时间=完成时间 进入时间带权周转时间=周转时间/运行时间6.875(h)1.725(h)第3页/共54页FCFS算法调度例2作业名 进入时间 运行时间(分)需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 有用户空间100KB,并规定作业相应程序装入内存连续区域,并不能被移动,作业与进程均采用FCFS算法第4页/共54页有用户空间100KB,并规定作业相应程序装入内存连续区域,并不能被移动,作业与进程均采用FCFS算法
4、作业名进入时间运行时间(分)需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20100K15K60K10K15K第5页/共54页 FCFS FCFS总结:总结:FCFSFCFS根根据据进进程程到到达达就就绪绪队队列列的的时时间间来来分分配配中中央央处处理理机机,一一旦旦一一个个进进程程获获得得了了中中央央处处理理机机,就就一一直直运运行行到到结结束束,先先来先服务是非剥夺调度。来先服务是非剥夺调度。这这种种调调度度从从形形式式上上讲讲是是公公平平的的,但但它它使使短短作作业业要要等等待待长长作作业业的的完
5、完成成,重重要要的的作作业业要要等等待待不不重重要要作作业业的的完完成成。从从这这个意义上讲又是不公平的。个意义上讲又是不公平的。先先进进先先出出调调度度使使响响应应时时间间的的变变化化较较小小,因因此此它它比比其其它它大大多多数数调调度度都都可可预预测测。由由于于这这种种调调度度方方法法不不能能保保证证良良好好的的响响应应时时间间,在在处处理理交交互互式式用用户户时时很很少少用用这这种种方方法法。在在当当今今系系统统中中,先先进进先先出出很很少少作作为为调调度度模模式式,而而是是常常常常嵌嵌套套在在其其它它的的调调度度模模式式中中。例例如如,许许多多调调度度模模式式根根据据优优先先级级将将处
6、处理理机机分分配配给给进进程程,但但具具有有相相同同优优先先级级的的进进程程却却按按先先进进先先出出进进行行分配。分配。第6页/共54页2.2.短作业进程优先(SJF/(SJF/Shortest Process Next)调度算法 这种调度算法主要用于作业调度,它从作业后备队列中挑选所需运行时间(估计值)最短的作业进入主存运行。这一算法有利于短作业,对长作业不利。采用SJF有利于系统减少平均周转时间和平均带权周转时间。第7页/共54页作业作业进入时刻进入时刻(h)运行时间运行时间(h)12348.008.509.009.502.000.500.100.20例题:用用 SJF 算法计算作业的运行
7、情况、平均周转时间和平均算法计算作业的运行情况、平均周转时间和平均带权周转时间带权周转时间第8页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.20平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第9页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进
8、入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.20平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第10页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 3 9.0
9、0 0.10 4 9.50 0.20平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第11页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 3 9.00 0.10 10.00 4 9.50 0.20平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第12页/共54页该算法总是优先
10、调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 3 9.00 0.10 10.00 10.10 4 9.50 0.20平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第13页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周
11、转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 3 9.00 0.10 10.00 10.10 4 9.50 0.20 10.10平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第14页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 3 9.00 0.10 10.00
12、 10.10 4 9.50 0.20 10.10 10.30平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第15页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 10.30 3 9.00 0.10 10.00 10.10 4 9.50 0.20 10.10 10.30平均周转时间平均周转时间 T平均带权周转时间平均带权周
13、转时间T 最短作业优先法(SJFSJF)第16页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 10.30 10.80 3 9.00 0.10 10.00 10.10 4 9.50 0.20 10.10 10.30平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第17页/共54页该算法总是优先调度要求运行时间最短的作业该算
14、法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2 8.50 0.50 10.30 10.80 3 9.00 0.10 10.00 10.10 4 9.50 0.20 10.10 10.30平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第18页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完
15、成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.00 10.00 2.00 2 8.50 0.50 10.30 10.80 2.30 3 9.00 0.10 10.00 10.10 1.10 4 9.50 0.20 10.10 10.30 0.80平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第19页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.0
16、0 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.80 2.30 4.60 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.10 10.30 0.80 4.00 平均周转时间平均周转时间 T平均带权周转时间平均带权周转时间T 最短作业优先法(SJFSJF)第20页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8.
17、00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.80 2.30 4.60 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.10 10.30 0.80 4.00 平均周转时间平均周转时间 T1.55h平均带权周转时间平均带权周转时间T5.15h 最短作业优先法(SJFSJF)第21页/共54页该算法总是优先调度要求运行时间最短的作业该算法总是优先调度要求运行时间最短的作业作业作业 进入时刻进入时刻 运行时间运行时间 开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转 1 8.00 2.00 8
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 学习 教程

限制150内