操作系统概念 CPU调度/CPU Scheduling 第五章笔记

Posted on | In |

2017年10月12日
08:01

写在前面

本笔记仅仅是本人在上课时的一些随手记录，并不完整也不完全正确。

如有错误，请在评论中或直接联系我指正，谢谢！

原始文件下载：(mht)(pdf)

Basic Concepts

Maximum CPU utilization obtained with multiprogramming

CPU-I/O Burst Cycle（突发时间）

Process execution consists of a cycle of CPU execution and I/O wait

  • I/O bound: I/O↑ CPU↓
  • CPU bound：I/O↓ CPU↑

进程调度的关键

在长期调度中协调I/O bound与CPU bound

CPU调度

Selects from among the processes in memory that are ready to execute
Allocates the CPU to one of them

调度
Review

Non-preemptive（非抢占方式）

Scheduling take place when a process:

  • Terminates
  • Switches from running to waiting(I/O requests)
  • Some kind of primitive is executed in process communication or
    synchronization, such as Block primitive（阻塞原语）,Wakeup
    primitives（唤醒原语）

Preemptive（抢占方式）

允许打断正在运行中的进程

Scheduling take place when a process:

  • Running to ready
  • Waiting to ready

Causes

  • Access to Shared data
  • While in kernel mode
  • Interrupts occurring during crucial OS activities

Dispatcher（进程调度程序）

将cpu的控制权分配给process

Tasks:

  • Switching context
  • To user mode
  • Jumping to the proper location in their user program to restart that program

Dispatch latency

  • Stop one process and start another running

Scheduling Criteria

General Criteria

  • CPU utilization

  • Throughput

    Number of Processes that are completed per time unit

  • Turnaround time

    Time spent waiting to

    Get into memory
    Waiting in the ready queue
    Executing on the CPU
    Doing I/O

    Long-term Scheduling

  • Waiting time

Time that a process spends waiting in the ready queue

  • Response time

From the submission of a request until the first response is produced

Interactive system

Optimization Criteria

  • Max CPU utilization
  • Max throughput
  • Min turnaround time（轮转时间）
  • Min waiting time
  • Min response time

Scheduling Algorithms*

FCFS

First-come, first-served
Average waiting time is often quite long.
适合处理长调度，有利于长作业
Convoy effect（护航效应）
  short process behind long process

SJF

Shortest-job-first（SJF）（非抢占）
对于抢占，非抢占

  • 抢占效果更优
  • 抢占：SRTF

Optimal - gives minimum average waiting time for a given set of processes

  • The difficulty is knowing the length of the next CPU request
  • Could ask the user

预测下一个CPU burst time

指数平均

Tn= actual length of nth CPU burst

α->0
  History not count

α->1
  Only the actual last CPU burst counts

算法易于实现，但是效率不高

缺点

  • 忽略作业等待时间
  • 会出现饥饿现象（大作业很难执行）

比较

SJF的平均作业周转时间比FCFS要小，所以它的调度性能比FCFS好

SJF调度算法问题

需要知道作业所需运行时间，否则调度就没有依据，不可能精确计算出运行时间
（即难点为预测下一个作业时间片长度）

Priority Scheduling

数字越小，优先级越高

SJF: Priority is the predicted next CPU burst time

Starvation:
  Low priority processes may never execute

Solution:
动态调整优先级，Aging —- as time progresses increase the priority of the process

静态优先级

动态优先级

高响应比优先调度HRRF
响应比：作业等待时间与运行时间比值
响应比=（等待时间+要求服务时间）/要求服务时间

缺点：

  • 响应比计算增加了系统开销

Round-Robin Scheduling 轮转算法

将cpu时间分为确定的时间片，每个作业不得超过这个固定时间
若单个任务超过这个时间，则按时间片划分，按FIFO处理（ready queue）
时间片不能太长，不然会退化成FCFS
时间片不能太短

  • 负载严重
  • 吞吐量受影响

平衡短作业的性能和长作业的吞吐量

  • 10-100ms
  • 上下文切换：0.1-1ms
  • 1%的负载是上下文切换

Multilevel Queue Scheduling

每个队列有自己的调度算法

Multilevel Feedback Queue

  • 队列之间必须有调度，采用固定优先级抢占调度
  • 进程可以在队列之间移动，借助aging实现

Definition

  • 分为前台foreground process和后台background process
  • 前台交互，后台批处理
  • 80%(time) foreground RR
  • 20% background FCFS

Feedback Queue

  • 根据时间推移，动态改变作业所在的队列
  • Number of queues
  • Scheduling algorithms for each queue
  • Method used to determine when to upgrade/demote a process
  • Method used to determine which queue a process will enter when that process needs service

Algorithm for a particular system

Multiple-Processor Scheduling

SMP / Asymmetric multiprocessing

Load Balancing

  • SMP: keep the workload balances
    one or more processors sit idle, others high workload(bad)

    Pull

    • 空闲cpu从繁忙cpu中获取一个进程

    Push

    • 繁忙cpu队列把一个进程推送到空闲CPU队列中

Real-Time Scheduling

硬实时

硬件实现

  • CPU运算周期按照原先设定的标准（比如Time Slice）
  • 或按照某些硬件优先权分配
软实时
  • 对非实时的操作系统进行某些改动，达到近乎实时的效果
  • 用一个专门的软件部件，达到快速反应
  • 这个进程的优先级相当高

Thread Scheduling

Local Scheduling

How the threads library decides which thread to put onto an available LWP

Global Scheduling

How the kernel decides which kernel thread to run next

PCS&SCS

  • PCS进程竞争范围
  • SCS系统竞争范围
  • 先PCS，再通过LWP放到SCS，再放到CPU

Solaris 2

  • Real time
  • System
  • Interactive & time sharing

Scheduling evaluation

Deterministic modeling

Queuing models

Implementation/simulation