OS第五次理论作业
有五个进程 P1、P2、P3、P4、P5，它们同时依次进入就绪队列，它们的优先数和需要的处理器时间如下表
进程 处理器时间 优先级（数小优先级高） P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2 忽略进行调度等所花费的时间，回答下列问题:
写出采用 “先来先服务”、“短作业（进程）优先”、“非抢占式的优先数” 和 “轮转法” 等调度算法，进程执行的次序。（其中轮转法的时间片为 2）
- 先来先服务: P1,P2,P3,P4,P5
- 短作业优先: P2,P4,P3,P5,P1
- 非抢占式的优先数: P2,P5,P1,P3,P4
- 轮转法: P1,P2,P3,P4,P5,P1,P5,P1,P5,P1
分别计算上述算法中各进程的周转时间和等待时间，以及平均周转时间
先来先服务
进程 周转时间 等待时间 执行时间 P1 10 0 10 P2 11 10 1 P3 13 11 2 P4 14 13 1 P5 19 14 5 - 平均周转时间：$(10+11+13+14+19)/5=13.4$
短作业优先
进程 周转时间 等待时间 执行时间 P2 1 0 1 P4 2 1 1 P3 4 2 2 P5 9 4 5 P1 19 9 10 - 平均周转时间：$(1+2+4+9+19)/5=7$
非抢占式的优先数
进程 周转时间 等待时间 执行时间 P2 1 0 1 P5 6 1 5 P1 16 6 10 P3 18 16 2 P4 19 18 1 - 平均周转时间：$(1+6+16+18+19)/5=12$
时间片轮转
进程 周转时间 等待时间 执行时间 P1 19 9 10 P2 3 2 1 P3 5 3 2 P4 6 5 1 P5 15 10 5 - 平均周转时间：$(19+3+5+6+15)/5=9.6$
死锁产生的四个必要条件是什么？
- 互斥条件：指进程对所分配到的资源进行排他性使用，即在一段时间内某资源只能有一个进程占有
- 保持和请求条件：已经获得资源的线程可以请求新的资源
- 不剥夺条件：指进程已获得的资源，在未使用完之前不能被强制剥夺，只能在使用完时由自己释放
- 环路等待条件：指在发生死锁时，必然存在两个或多个进程组成的环形链，每个进程都在等待环形链中下一个节点占用的资源
某系统中有n个进程和m台打印机，系统约定：打印机只能一台一台地申请、一台一台地释 放，每个进程需要同时使用的打印机台数不超过m。如果n个进程同时需要使用打印机的总 数小于m+n，试讨论，该系统可能发生死锁吗?并简述理由。
- 该系统不可能发生死锁
- 设n个进程中每个进程同时需要使用x个打印机,$1<=x<=m,nx<m+n$
- 若发生死锁，需要n个进程各取得x-1个打印机时，同时再需要最后一个打印机时没有打印机了，即$m < n(x-1)$，即$m+n<nx$矛盾
- 故不可能发生死锁
线程的基本概念是什么？引入线程的好处是什么？
- 线程是进程中的一个实体，是CPU调度的基本单位，是可执行单元，只包含少量资源
- 将资源与计算分离，提高并发效率
假设具有5个进程的进程集合$P={P0,P1,P2,P3,P4}$，系统中有三类资源A,B,C，假设在某时刻有如下状态
Allocation Max Available A B C A B C A B C P0 0 0 3 0 0 4 1 4 0 P1 1 0 0 1 7 5 P2 1 3 5 2 3 5 P3 0 0 2 0 6 4 P4 0 0 1 0 6 5 根据上表，当前系统是否处于安全状态
使用安全性算法进行判断(工作向量Work)，补充work和need列
进程 work need allocation work + allocation finish A B C A B C A B C A B C P2 1 4 0 1 0 0 1 3 5 2 7 5 true P0 2 7 5 0 0 1 0 0 3 2 7 8 true P1 2 7 8 0 7 5 1 0 0 3 7 8 true P3 3 7 8 0 6 2 0 0 2 3 7 10 true P4 3 7 10 0 6 4 0 0 1 3 6 11 true 故当前系统处于安全状态
若系统中的可利用资源Available为(0,6,2)，系统是否安全？若系统共处在安全状态，请给出安全序列；若处在非安全状态，简要说明原因。
进程 work need allocation work + allocation finish A B C A B C A B C A B C P3 0 6 2 0 6 4 0 0 2 0 6 4 true P4 0 6 4 0 6 5 0 0 1 0 6 5 true P0 0 6 5 0 0 1 0 0 3 0 6 8 true 0 6 8 不能给出安全序列，故系统不安全