操作系统——进程管理算法和例题

1、概述

1.1 进程调度

当进程的数量往往多于处理机的个数，出现进程争用处理机的现象，处理机调度是对处理机进行分配，就是从就绪队列中，按照一定的算法（公平、髙效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

处理机调度是多道程序操作系统的基础，它是操作系统设计的核心问题。

1.2 调度算法

（1）先来先服务（FCFS）

（2）最短作业优先

（3）最短剩余时间优先

（4）轮转调度

（5）优先级调度

（6）多级队列

1.3 各项指标计算

• CPU利用率

• 周转时间

?

?

?

2 实例

2.1 时间相关

case 1：

?答：画出时间线：

?（1）在100ms-150ms时CPU空闲等待，利用率是（300-50）/300

（2）无

（3）有，0-50,180到200?

case 2：

答：要考虑优先级，即优先级低的进程要把资源给优先级高的?

P1：T1=80（等待时间+运行时间->作业完成时间-作业提交时间）

P2：T2=10+80（等待时间+运行时间->作业完成时间-作业提交时间）

P3：T3=40+50（等待时间+运行时间->作业完成时间-作业提交时间）

CPU利用率：（10+10+20+30）/90

D1利用率：（30+20+20）/90

D2利用率：（30+40）/90

case 3:

?答：由图可知：

（1）B

（2）A

（3）（20+10+20+40+30+40+20）/210=85.7%

case 4：

?答：

（1）FCFS：1,2,3,4,5

	执行时间	周转时间
1	10	10（10）
2	1	10+1（11）
3	2	10+1+2（13）
4	1	10+1+2+1（14）
5	5	10+1+2+1+5（19）

平均周转时间：（10+11+13+14+19）/5

带权平均周转时间：（10/10+11/1+13/2+14/1+19/5）/5

（2）SJF：2,4,3,5,1【因为作业是时刻0同时到达，因此，选执行最短时间作业】

	执行时间	周转时间
2	1	1（1）
4	1	1+1（2）
3	2	1+1+2（4）
5	5	1+1+2+5（9）
1	10	1+1+2+5+10（19）

平均周转时间：（1+2+4+9+19）/5

带权平均周转时间：（1/1+2/1+4/2+9/5+19/10）/5

（3）非剥夺式优先级调度：2,5,1,3,4

	执行时间	周转时间
2	1	1(1)
5	5	1+5（6）
1	10	1+5+10（16）
3	2	1+5+10+2（18）
4	1	1+5+10+2+1（19）

平均周转时间：（1+6+16+18+19）/5

带权平均周转时间：（1/1+6/5+16/10+18/2+19/1）/5

（4）RR：1,2,3,4,5

	执行时间	周转时间
1	10	19
2	1	2
3	2	7
4	1	4
5	5	14

平均周转时间：（19+2+7+4+14）/5

带权平均周转时间：（19/10+2/1+7/2+4/1+14/5）/5

case 5

周转时间：完成时间-到达时间：

FCFS

1->2->3->4->5

作业编号	到达时间	执行时间	完成时间	周转时间
1	0	5	5	5
2	1	7	12	11
3	2	3	15	13
4	3	10	25	22
5	4	4	29	25

平均周转时间：（5+11+13+22+25）/5=15.2

SJF

最早提交的那个作业是第一个处理的（和执行时间的长短无关) 作业1处理完的时间是5，那么在这个时候作业2、作业3、作业4、作业5已经提交了，这个时候处理那一个就根据作业执行时间的长短来确定

1->3->5->2>4

作业编号	到达时间	执行时间	完成时间	周转时间
1	0	5	5	5
3	2	3	8	6
5	4	4	12	8
2	1	7	19	18
4	3	10	29	26

平均周转时间：（5+6+8+18+16）/5=12.6

2.2 进程同步和互斥例题

case1：

?分析：

进程：仓库存放A产品，仓库存放B产品

设置信号量：mutex（每次只能放一种产品），Sa表示A-B的数量差，Sa表示B-A的数量差

Semaphore mutex=1;  //互斥的信号量
Semaphore Sa=M-1,Sb=N-1   //同步信号量

process_A(){

    while(1){
         
        P(Sa);     
        P(mutex); // 占用仓库
        A入库
        V(mutex); // 释放仓库
        V(Sb);

    }
}

process_B(){

    while(1){
        
        P(Sa);
        P(mutex); // 占用仓库
        B入库
        V(mutex); // 释放仓库
        V(Sb);

    }
}