聊城大学计算机学院计算机操作系统课件 第3章（1）.ppt

1 作业和作业步 3 作业运行的三个阶段和三种状态 分派程序取出进程； 进行进程切换； 转到用户态； 执行被选中进程。 3 进程调度时机 （1）当进程从执行态转换为阻塞态； （2）分时系统中时间片到； （3）当有一个优先级更高的进程就绪； （4）一个进程运行完毕，或由于错误而终止。 举例：SPF ----非抢占式 到达顺序: 进程名 到达时间 服务时间 A 0 1 B 1 100 D 2 100 C 3 1 该调度过程如图所示: 举例：SPF ----抢占式 到达顺序: 进程名 到达时间 服务时间 A 0 1 B 1 100 D 2 100 C 3 1 该调度过程如图所示: 进程 到达时间 服务时间 P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 “饥饿”定义： 在预计时间内，某个或某些进程永远得不到完成工作的机会，因为他们所需的资源总是被别的进程占有或抢占。这种状况称作“饥饿” （Starvation）。 “饥饿”和“死锁”的比较： 相同点：均为资源分配与协调出现问题而引起。 主要区别：见下表。 三、 Dead Lock vs. Starvation §3.8 死锁的检测和解除Deadlock Detection and Relieving Dead Lock Starvation 死锁进程必定处于阻塞状态 饥饿进程可以在就绪状态 死锁进程等待永远不会被释放的资源， 饥饿进程等待会被释放的资源但却自己得不到。没有时间上界的等待，等待时间超过极限(Deadline)则饿死； 死锁一定有环路等待，因此，化简资源分配图可检测是否存在死锁， 饥饿不一定存在环路等待，化简资源分配图，不能检测饥饿进程 死锁一定涉及多个进程 饥饿进程可能只有一个 死锁可能会最终使整个系统陷入死锁并崩溃。 饥饿情形下，系统至少一个进程能正常运行。 CPU Utilization及Throughput会大幅低。 CPU Utilization及Throughput不见得会大幅降低。 易发生在在Non-Preemptive的环境 易发生在不公平、Preemptive的环境 解決：有三大处理方式 解決：先来先服务的资源分配策略 * 虽然有的分时系统没有配置高级调度程序，但一个作业进入内存时，需要决定1、是否接受一个终端用户的连接；2、一个交互作业是否被计算机系统接纳并构成进程，通常系统将接纳所有授权用户，直到系统饱和为止；3、一个新建态的进程能否立即加入就绪队列。 * 实际上是内存管理中的对换功能。 * * 高优先权算法应用于实时系统或要求较高的批处理系统和分时系统中。 非抢占方式主要用于批处理或要求不高的实时系统中。 * 基本优先数UNIX中一般为19～－20 该P-cpu计算的效果为：1）如果一个进程占用处理机时间较长，则P-cpu值增大，优先数也增大，则优先级降低。 2)若一个进程长时间未被调度，或虽频繁调度，每次执行时间较短，200ms，则P-cpu较小甚至为0，则优先数也较小，优先级增大。 * 对基本轮转法的策略可以略加修改，例如，对不同的进程给以不同时间片，时间片长短可以动态修改等，这些做法目的为了提高效率。 * EDF是动态实时调度算法。其思想为：每当一个进程需要占用CPU时，它要表明自己的存在和截止时间等信息。调度程序把所有可以运行的进程按照其截止时间先后顺序放在一个表格中。执行调度时，就学则该表中的第一个进程－－他的截止时间最近。每当一个新进程就绪，系统就查看它的截至时间是否在当前运行进程之前，若是，新进程抢占。 * Linux系统提供了三种进程调度策略：SCHED_FIFO、SCHED_RR以及SCHED_OTHER。 SCHED_FIFO适合于实时进程，它们对时间性要求比较强，而每次运行所需要的时间比较短。一旦这种进程被调度开始运行后，就要一直运行直到自愿让出CPU或者被优先权更高的进程抢占其执行权为止，没有时间片概念。 SCHED_RR对应“时间片轮转法”，适合于每次运行需要较长时间的实时进程。 SCHED_OTHER适合于交互式的分时进程。这类非实时进程的优先权取决于两个因素：进程剩余时间配额和进程的优先数nice（优先数越小，其优先级越高）。nice的取值范围是19~-20。