21计5郭培鑫 第三次作业
思考题：
- 进程最基本的状态有哪些？哪些事件可能引起不同状态间的转换？
- 什么是进程上下文？试述其主要内容。
- 在时间片轮转调度算法中，可根据哪些因素确定时间片的长度？
答案：
- 进程最基本的状态：就绪态、运行态、阻塞态。时间片、I/O操作、信号处理、显示请求等事件可能引起不同状态间的转换。
- 进程上下文是一个保存了进程执行所需的所有关键信息的数据结构。当操作系统需要切换到另一个进程时，它会保存当前进程的上下文，然后加载新进程的上下文，以实现进程切换。这个过程确保了多个进程可以在共享的CPU上有效地运行，并且在切换之后能够正确地继续执行。
- 时间片大小的确定因素：
- 系统对响应时间的要求。
- 就绪队列中进程的数目。
- 系统的处理能力。
应用题：
1.假定执行作业 Job1，~Job5,作业号的数字为其到达顺序，即依次按照序号 1、2、3、4、5进入单处理器系统，各作业的执行时间和优先数如下表所示。①分别给出采用先来先服务调度算法、时间片轮转调度算法(时间片长度为 1ms)、最短作业优先调度算法及非抢占式优先数调度算法(优先数越小则优先级越高)时各作业的执行次序;② 计算每种情况下作业的平均周转时间。
|
作业号 |
执行时间/ms |
优先数 |
|
Job1 |
10 |
3 |
|
Job2 |
1 |
1 |
|
Job3 |
2 |
3 |
|
Job4 |
1 |
4 |
|
Job5 |
5 |
2 |
答案：
对于①问：分析执行次序
- 先来先服务调度算法：Job1-->Job2-->Job3-->Job4-->Job5
>根据题目可知作业先后顺序执行次序。
- 时间片轮转调度算法：
>根据先来先排队原则和时间片限制，可得出以下表格的每个作业执行顺序
|
时间/ms |
当前 执行的作业 |
队列中的作业 |
|
1 |
Job1 |
Job1 |
|
2 |
Job2 |
Job2、Job1 |
|
3 |
Job1 |
Job1、Job3 |
|
4 |
Job3 |
Job3、Job4、Job1 |
|
5 |
Job4 |
Job4、Job1、Job5、Job3 |
|
6 |
Job1 |
Job1、Job5、Job3 |
|
7 |
Job5 |
Job5、Job3、Job1 |
|
8 |
Job3 |
Job3、Job1、Job5 |
|
9 |
Job1 |
Job1、Job5 |
|
10 |
Job5 |
Job5、Job1 |
|
11 |
Job1 |
Job1、Job5 |
|
12 |
Job5 |
Job5、Job1 |
|
13 |
Job1 |
Job1、Job5 |
|
14 |
Job5 |
Job5、Job1 |
|
15 |
Job1 |
Job1、Job5 |
|
16 |
Job5 |
Job5、Job1 |
|
17-19 |
Job1 |
Job1 |
- 最短作业优先调度算法：根据最短作业优先原则顺序执行作业。如下图表格所示执行次序
>
|
时间/ms |
当前作业 |
队列中的作业 |
|
0 |
0 |
0 |
|
1 |
Job1 |
Job1 |
|
2 |
Job2 |
Job2、Job1 |
|
3 |
Job1 |
Job1、Job3 |
|
4 |
Job1 |
Job1、Job3、Job4 |
|
5，6，7，8，9 |
Job5 |
Job5、Job1、Job3、Job4 |
|
10，11，12，13，14，15，16 |
Job1 |
Job1、Job3、Job4 |
|
17，18 |
Job3 |
Job3、Job4 |
|
19 |
Job4 |
Job4 |
- 非抢占式优先数调度算法：Job1-->Job2-->Job5-->Job3-->Job4
>前10毫秒只有Job1在执行，因为非抢占式原则，故在这10毫秒内，虽然作业全都顺序加入，但是只有Job1执行完，其他作业才有机会获得资源，在第十毫秒后，根据优先级高者获得先执行，因为Job2优先级高于其他，所以接下来执行Job2，以此类推。
对于②问：计算平均周转时间
周转时间=作业完成时刻—作业到达时刻；
平均周转时间=作业周转总时间/作业个数；10 1 2 3 5
- 先来先服务调度算法：（（11-1）+（12-2）+（14-3）+（17-4）+（22-5））/5=12.2 ms
- 时间片轮转调度算法：((20-1)+(3-2)+(9-3)+(6-4)+(17-5))/5 = 8 ms
- 最短作业优先调度算法：((17-1）+（3-2）+（19-3）+（20-4）+（10-5）/5 =10.8 ms
- 非抢占式优先数调度算法：((11-1)+(12-2)+(15-4)+(17-3)+(22-5))/5=12.4 ms
2. 在一个只支持三道程序同时运行的多道程序系统中，作业调度采用最短作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列中，优先数即为进程优先数，优先数越小则优先级越高。
|
作业名 |
到达时刻 |
估计运行时间/min |
优先数 |
|
A |
10:00 |
40 |
5 |
|
B |
10:20 |
30 |
3 |
|
C |
10:30 |
60 |
4 |
|
D |
10:50 |
20 |
6 |
|
E |
11:00 |
20 |
4 |
|
F |
11:10 |
10 |
4 |
试填充下表：
|
作业名 |
进入内存时刻 |
运行结束时间 |
作业周转时间/min |
|
A |
10:00 |
12：40 |
160 |
|
B |
10:20 |
10：50 |
30 |
|
C |
10:30 |
11：50 |
80 |
|
D |
10：50 |
13：00 |
130 |
|
E |
11：50 |
12:10 |
70 |
|
F |
12:10 |
12:20 |
70 |
|
平均作业周转时间T= |
90分钟 |
||
具体思路：
10：00 作业A到达，由于就绪队列为空，作业调度进系统，进程调度执行。
10：20 作业B到达，就绪队列未满，作业调度进系统。
由于B的优先级高于A，所以进程调度A进入就绪态，调度B执行。
作业A已经运行20分钟，还剩20分钟。
10：30 作业C到达，就绪队列未满，作业调度进系统。
由于作业B的优先级高于C，所以进程调度C进入就绪态。
作业B继续运行，已经运行10分钟，还剩20分钟。
作业A还剩20分钟。
10：50 作业D到达，作业B执行完成，作业调度D进系统。
作业C的优先级最高，所以进程调度C执行。
作业A剩余20分钟。
作业C剩余60分钟。
作业D剩余20分钟。
11：00 作业E到达，作业E优先数4，等待作业调度进入系统。
作业C已经运行10分钟，还剩50分钟。
作业A剩余20分钟。
作业D剩余20分钟。
11：10 作业F到达，作业F优先数4，等待作业调度进入系统。
11：50 作业C执行完成，作业E和F的优先数相同，由于作业E先于作业F 等待作业调度，所以作业调度E进入系统；
由于作业E的优先级最高，进程调度E执行，调度A和D为就绪态。
作业A剩余20分钟。
作业D剩余20分钟。
12：10 作业E执行完成，作业调度F进入系统。
由于作业F优先级最高，进程调度F执行，调度A和D为就绪态。
12：20 作业F执行完成。
由于A运行时间最短，进程调度A执行。
作业A剩余20分钟。
作业D剩余20分钟。
12：40 作业A执行完成。
进程调度D执行。
作业D剩余20分钟。
13：00 作业D执行完成。
3.在一个只支持4道程序同时运行的多道程序系统中，若在一段时间内先后到达6个作业，其提交时刻和估计运行时间由下表给出。
|
作业 |
提交时刻 |
估计运行时间/min |
|
1 |
8:00 |
60 |
|
2 |
8:20 |
35 |
|
3 |
8:25 |
20 |
|
4 |
8:30 |
25 |
|
5 |
8:35 |
5 |
|
6 |
8:40 |
10 |
系统采用SRTF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短的作业所抢占。①分别给出6个作业的开始执行时间、作业完成时间、作业周转时间。②计算平均作业周转时间。
答案：
考察最短剩余时间优先算法:最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度。
具体思路分析：
8：00 作业1到达提交时刻，作业调度1进入系统，作业1执行。
8：20 作业2到达提交时刻，作业调度2进入系统。
作业1已运行20分钟，还剩余40分钟。
作业2剩余35分钟。
故作业2执行，作业1进入就绪态。
8：25 作业3到达提交时刻，作业3进入系统。
作业2已运行5分钟，还剩余30分钟。
作业1剩余40分钟。
作业3剩余20分钟。
故作业3执行，作业2进入就绪态。
8：30 作业4到达提交时刻，作业4进入系统。
作业3已运行5分钟，还剩余15分钟。
作业1剩余40分钟。
作业2剩余30分钟。
作业4剩余25分钟。
故作业3执行，作业4进入就绪态。
8：35 作业5到达提交时刻，等待作业调度进入系统。
作业3还剩余10分钟。
作业3继续执行。
8：40 作业6到达提交时刻，等待作业调度进入系统。
作业3还剩余5分钟。
作业3继续执行。
8：45 作业3执行完成。根据作业5先到原则，进程调度5进入系统。
作业1剩余40分钟。
作业2剩余30分钟。
作业4剩余25分钟。
作业5剩余5分钟。
故作业5执行。无需进入就绪态。
8：50 作业5执行完成。进程调度6进入系统。
作业6剩余10分钟。
故作业6执行。无需进入就绪态。
9：00 作业6执行完成。
作业1剩余40分钟。
作业2剩余30分钟。
作业4剩余25分钟。
故作业4执行。
9：25 作业4执行完成。
9：55 作业2执行完成。
10：35 作业1执行完成。
第①问答案：
|
作业 |
开始执行时间 |
作业完成时间 |
作业周转时间 |
|
1 |
8:00 |
10:35 |
155 |
|
2 |
8:20 |
9:55 |
95 |
|
3 |
8:25 |
8:45 |
20 |
|
4 |
9:00 |
9:25 |
25 |
|
5 |
8:45 |
8:50 |
5 |
|
6 |
8:50 |
9:00 |
10 |
第②问答案：
平均作业周转时间：(155+95+20+25+5+10)/6=51.67 分钟。
4.在一个单处理器多道分时系统中有三道作业依次提交，其提交时刻、运行时间、I/O时间、CPU时间分别如下表所示。
|
作业 |
作业提交时刻 |
运行时间/h |
其中 |
|
|
I/O时间/h |
CPU时间/h |
|||
|
Job1 |
8 |
0.36 |
0.18 |
0.18 |
|
Job2 |
8.2 |
0.32 |
0.16 |
0.16 |
|
Job3 |
8.4 |
0.36 |
0.18 |
0.18 |
如果已知下列情况：①每道作业的I/O等待时间占各自总运行时间的一半；②分时运行两道作业，CPU将有20%的时间空闲；③除了CPU，系统有充足的资源供作业使用。试计算各作业的运行完成时刻。
答案：
8.0~8.2时间内: 只有Job1,没有发生进程调度,因此不会浪费时间, 在这0.2h内, 由于①每道作业的I/O时间占总运行时间的一半,所以有0.1h的时间用于I/O,剩余0.1用于CPU,因此 在8.2时刻, Job1还剩余0.36-0.2 = 0.16h的时间需要运行。
8.2~8.4时间内, Job2也开始运行, 同时也会运行Job1, 由于CPU同一时刻只能处理一个作业, 因此会发生进程切换, 在这0.2h内, 会浪费0.2×20%=0.04h的时间, 那么实际可运行的时间就只有0.2-0.04=0.16h, 在前0.08h中,可以让Job1运行I/O 0.08h,同时, Job2可以运行 CPU 0.08h。
在后0.08h中,Job1运行CPU 0.08h, Job2运行I/O 0.08h, 这时,也就是8.4时刻, Job1运行完毕。Job2还剩下0.16的运行时间, 其中各占一半。
8.4时刻, 此时Job3也开始运行, 同样会发生调度, 那么在8.4~8.6这0.2h内, 可用运行时间同样为0.16h, 前0.08h: Job2 CPU, Job3 I/O 后0.08h: Job3CPU, Job2 I/O, 然后8.6时刻, Job2也就运行完毕。
8.6时刻, 只有Job3, 不需要调度, 还剩下CPU和I/O各0.1, 也就是8.6+0.1+0.1=8.8, Job3运行完毕。
故Job1完成时间: 8.4, Job2: 8.6, Job3: 8.8
拓展：
周转时间=作业完成时刻—作业到达时刻；
带权周转时间=周转时间/服务时间；
平均周转时间=作业周转总时间/作业个数；
平均带权周转时间=带权周转总时间/作业个数；