1205复习#

SRTN最短剩余时间优先算法（Shortest Remaining Time Next）#

是抢占版的短作业优先

1. 算法思想： 追求：

   • 最小平均等待时间
   • 最小平均周转时间

2. 算法规则：==剩余时间==最短的优先

3. 是否可抢占：可抢占式

4. 优缺点：

   • 优点：

     • “最小化”平均等待时间

     • “最小化”平均周转时间

     • 高效利用CPU

       • 倾向于优先执行剩余时间短的作业，更好的利用CPU

   • 缺点：

     • 预测性差

5. 是否会产生饥饿：可能产生饥饿

   • 如果一直有短作业进来，长作业还是会长时间得不到服务

• 当一个进程被放入就绪队列时，调度器会计算该进程的预计执行时间，并将其插入到就绪队列中

  • 然后从就绪队列中选一个剩余执行时间最短的进程来执行
  • 如果新进程的剩余执行时间比当前进程更短，则当前进程被抢占，然后把这个进程插入到就绪队列的合适位置

• 每当有进程加入 就绪队列改变时，需要调度

  • 如果，新到达的进程 剩余时间 比当前运行的进程剩余时间 更短，新进程就==抢占==处理机，当前进程回到==就绪队列==

HRRN高响应比优先（Highest Response Ratio Next）#

1. 算法思想：==综合==考虑 进程的 ==等待时间==和==要求服务时间==

2. 算法规则：

   • 每次调度时，先计算各进程的响应比
     • 响应比=（等待时间+要求服务时间）/要求服务时间
   • 然后选响应比最高的进程为其服务

3. 是否可抢占：非抢占式算法

   • 因此 只有当前运行的进程 主动放弃处理机时，才需要调度，才需要计算响应比

4. 优缺点

   • 优点：

     • 综合考虑了 ==等待时间==和==运行时间==（要求服务时间）
     • 等待时间相同时，要求服务时间短的优先（SJF的优点）
     • 要求服务时间相同时，等待时间长的优先（FCFS的优点）
     • 对长作业来说，等待时间越久，响应比越大，从而避免长作业饥饿问题

   • 缺点：

     • 响应比计算开销
       • 每次调度时都需要计算各进程的响应比，会增加系统的计算开销
       • 不适用于实时系统
         • HRRN要根据==等待时间==和==服务时间==来确定优先级
         • 而实时系统的任务 必须在规定时间内完成，并且按预期时间 响应外部事件

5. 是否会导致饥饿：

   • 不会

优先级调度算法（Priority Scheduling）#

1. 算法思想：只考虑任务的紧急程度

2. 算法规则：选择优先级最高的进程为其服务

3. 是否可抢占：两个都有

   • 非抢占式：进程 主动放弃处理机时 进行调度

   • 抢占式：不止进程主动放弃处理机时进行调度，还要在来新进程时进行调度，检查是否会发生抢占

4. 优缺点：

   • 优点：

     • 用优先级区分==紧急程度==、==重要程度==，适用于==实时操作系统==
     • 可灵活的调整对各进程的==偏好程度==

   • 缺点：如果一直有高优先级进程来，可能会导致饥饿

5. 是否会导致饥饿：会

• 就绪队列未必只有一个，可以按照不同优先级来组织

• 另外，也可以把优先级高的进程排在更靠近队头的位置

• 根据优先级是否可以动态改变，可以将优先级分为：

  • 静态优先级：创建进程时确定，之后一直不变
  • 动态优先级：创建进程时有一个==初始值==，之后根据情况动态调整优先级

• 优先级设定：

  • 系统进程 优先级 高于 用户进程

  • 前台进程 优先级 高于 后台进程

  • 操作系统更偏好 I/O密集型进程

    • I/O设备和CPU可以并行工作（I/O进行操作时，CPU去处理别的工作）
      • 如果优先让I/O密集型任务先工作，更有可能让I/O设备尽早投入工作，提高资源利用率和系统吞吐量
      • I/O密集型对应计算密集型

  • 采用动态优先级，什么时候应该调整？

    （可以从追求公平、提升资源利用率等角度考虑）

    • 如果某进程在就绪队列中等待了很长时间，可以适当提升优先级
    • 如果某进程占用处理机运行了很长时间，可以适当的降低优先级
    • 如果某进程频繁的进行I/O操作，可以适当的提高优先级

RR时间片轮转（Round-Robin）#

1. 算法思想：
   • 公平、轮流的为各进程服务，让每个进程在一定时间间隔内都可以得到响应
2. 算法规则：
   • 按进程到达就绪队列的顺序，所有进程各执行一个时间片
   • 如果进程在一个时间片内没执行完，则==剥夺处理机==，将进程放到就绪队列末尾重新排队
3. 是否抢占：抢占式算法
   • 不是==主动释放==处理机而是到时间后==被剥夺==处理机，所以是==抢占式==
4. 优缺点：
   • 优点：
     • 公平
     • 响应快
     • 适用于==分时操作系统==
   • 缺点：
     • ==高频率==的进程切换，有一定的==开销==
     • 不区分任务的==紧急程度==
5. 是否会导致饥饿：不会

• 短作业效应：

  • 对短作业，时间片轮转可以提供快速响应

  • 对长作业，会花费更多时间在上下文切换上