本文共 6336 字,大约阅读时间需要 21 分钟。
Basic Concepts: Maximum CPU utilization obtained with multiprogramming
A CPU-bound process might have a few very long CPU bursts.
An I/O-bound process typically has many short CPU bursts
The CPU scheduler selects a process from the ready queue, and allocates the CPU to it.
Non-preemptive scheduling: scheduling occurs when a process voluntarily enters the wait state (case 1) or terminates (case 4). Simple, but very inefficient
Preemptive scheduling: scheduling occurs in all possible cases. Mutual exclusion may be violated. Mutual exclusion may be violated.
实时OS一定要实现可抢占调度
Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:
◆switching context
◆switching to user mode
◆jumping to the proper location in the user program to restart that program
Dispatch latency – time it takes for the dispatcher to stop one process and start another running.上下文切换的时间,与硬件有关
◆CPU utilization : Normally 40% is lightly loaded and 90% or higher is heavily loaded
◆Throughput :The number of processes completed per time unit ,Higher throughput means more jobs get done.对同样的进程集较为客观
◆Turnaround time :The time period between job submission to completion ,From a user’s point of view, turnaround time is more important than CPU utilization and throughput
◆Waiting time : the sum of the periods that a process spends waiting in the ready queue
◆Response time: The time from the submission of a request (in an interactive system) to the first response is called response time
判断process的类型是观察CPU burst的长度,Long CPU burst 是有较长的CPU时间,有很多Short CPU burst 的进行频繁的IO,IO burst的长度取决于设备,并不是因为是IO bound burst而变得很长
Jitter 抖动, 抖动越小可预测性越大
◆First-Come, First-Served (FCFS)
◆Shortest-Job-First (SJF)
◆Priority
◆Round-Robin
◆Multilevel Queue
◆Multilevel Feedback Queue
The process that requests the CPU first is allocated the CPU first.
Using a queue.
FCFS is not preemptive
Convoy effect :short process behind long process, CPU utilization may be low. 护航效应
When a process must be selected from the ready queue, the process with the smallest next CPU burst is selected. Thus, the processes in the ready queue are sorted in CPU burst length.
SJF can be non-preemptive or preemptive!!!
◆nonpreemptive
◆preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF).
SJF is provably optimal(最优的) – gives minimum average waiting time for a given set of processes
Without a good answer to this question, SJF cannot be used for CPU scheduling.
We try to predict the next CPU burst by using the length of previous CPU bursts, using exponential averaging.
how to do:
some long jobs may not have a chance to run at all. This is starvation.
Priority may be determined internally or externally:
◆internal priority:
determined by time limits,memory requirement, # of files, and so on. (内部性质决定的)
◆external priority:
not controlled by the OS (e.g., importance of the process) (人为设定的)
The scheduler always picks the process (in ready queue) with the highest priority to run
Indefinite block (or starvation) may occur: a low priority process may never have a chance to run–>solution: Aging
Aging: gradually increases the priority of processes that wait in the system for a long time.
All processes in the ready queue is a FIFO list. When the CPU is free, the scheduler picks the first and lets it run for one time quantum.
Each process is assigned permanently to one queue based on some properties of the process .
Each queue has its own scheduling algorithm,
Time slice: each queue gets a certain amount of CPU time which it can schedule amongst its processes( i.e., 80% to foreground in RR, 20% to background in FCFS )
Multilevel queue with feedback scheduling is similar to multilevel queue; however, it allows processes to move between queues,aging can be implemented this way
If a process uses more (resp., less) CPU time, it is moved to a queue of lower (resp., higher) priority.
That is to say : ,I/O-bound (resp., CPU-bound) processes will be in higher (resp., lower) priority queues.
更确切的,Multilevel Feedback Queue 可以说是一种调度的框架
CPU scheduling more complex when multiple CPUs are available.不做深入讨论
Classic Test:
**Consider a multi-level feedback queue in a single-CPU system. The first level (queue 0) is given a quantum of 8 ms, the second one a quantum of 16 ms, the third is scheduled FCFS. Assume jobs arrive all at time zero with the following job times (in ms): 4, 7, 12, 20, 25 and 30, respectively. Assume the context switch overhead is zero unless otherwise stated. **
•Show the Gantt chart for this system.
•Compute the average waiting and turnaround time.
•Suppose the context switch overhead is 1 ms. Compute the average turnaround time
字丑勿喷,哈哈
转载地址:http://llgwi.baihongyu.com/