---
tags: 作業系統
---
# 作業系統(五)
## Basic Concepts
- Multiprogramming is to have some process running at all times,to maximize CPU utilization.
- Process execution consists of a cycle of CPU execution and I/O wait.
- The figure shows the durations of CPU bursts.
- Processes generally have a large number of short CPU bursts(I/O預處理) and small number of long CPU bursts.
- An I/O-bound program typically has many short CPU bursts.(做io比較多的short cpu time比較多)
- A CPU-bound program might have a few long CPU bursts(做cpu運算的long cpu time比較多)

## CPU Scheduler
- CPU scheduler (short-term scheduler) select one of the processes in the ready queue to be executed, whenever the CPU becomes idle.
- CPU scheduling decisions may take place when a process:
- 1. Switches from running to waiting state (I/O or wait for child processes).
- 2. Switches from running to ready state (interrupted).(process只能跑固定秒數，但還沒跑完時)
- 3. Switches from waiting to ready (completion of I/O).
- 4. Terminates

- When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme is nonpreemptive(不可中斷的).(當process自願交出cpu使用權的時候)
- Otherwise, it is is preemptive.
- Preemptive scheduling usually has better scheduling performances(throught put比較好，response time比較快). However, it incurs data inconsistency(不一致)
## Scheduling Criteria
- CPU utilization:
- The utilization of CPU.
- Can range from 0 to 100 percent.
- It should range from 40 percent (lightly loaded system) to 90 percent (heavily used system).
- Turnaround time:
- Amount of time to execute a particular process.
- Is the sum of the periods spent waiting in the ready queue, executing on the CPU, doing I/O, …

- Waiting time
- Since a CPU scheduling algorithm only select processes in ready queue for execution, it does not affect the amount of time during which a process executes or does I/O
- (first)Response time:
- This measure is the amount of time it takes from when a request was submitted until the first response is produced
- interactive system

- for interactive system (such as time-sharing systems), it is more important to minimize the variance in the response time than to minimize the average response time.(在系統中，盡量每個行程的response time差不多，也不要某個行程回應特別久，其他回應特別短)
## Scheduling Algorithms
- ### First-Come, First-Served Scheduling(FCFS)
- 
- 
- 因為行程的先後順序，平均的等待時間會有很大的變動
- The FCFS scheduling algorithm is nonpreemptive
- convoy effect
- All the other processes wait for the one big process to get of the CPU.
- Result in lower CPU and device utilization
- 此演算法如果使用cpu時間的行程比較早來的話，會造成後面的行程都在等待前面較長的行程完成，I/O就會idle
- Shortest-Job-First Scheduling(SJF)
- 
- **The SJF scheduling algorithm is optimal**
- we can try our best to predict the length.
- We expect that the next CPU burst will be similar in length to the previous ones.
- And pick the process with the shortest predicted CPU burst.
- 
- The SJF algorithm can be either **preemptive** or **nonpreemptive**
- 
- SJF scheduling is used frequently in long-term scheduling, where users need to specify “process time limit” of the processes

## Priority Scheduling
- The SJF algorithm is a special case of the priority scheduling algorithm(short cpu burst->higher priority)
- 同樣優先權的按照來的順序去排
- 數字越小優先權越高
- Priorities can be defined either internally or externally.
- Internally – use measurable quantity in terms of time limits, memory requirements …
- Externally – set by criteria outside the operating system, such as importance, funds, …often political factors.
- Priority scheduling can be either preemptive or nonpreemptive
- **Starvation**
- 拿不到cpu使用權
- Low-priority processes can be blocked indefinitely.
- Solution: **aging**
- Gradually increase the priority of processes that wait in the system for a long time.
- E.g., by 1 every 15 minutes.
- A process would eventually arrive the highest priority and would be executed.

- 循環排程 (Round-Robin Scheduling,RR)
- 會設立一個10~100msec的時間切片，當此時間用完，會將目前正在執行的process移到等待佇列(wait queue)中，再以FCFS的方式從wait queue中挑下一個process執行
- Is similar to FCFS scheduling, but preemption is added to switch between processes
- 微小的單位時間被定義為 **時間切片(time quantum/time slice)**
- 
- 假設有ｎ個process在ready queue，time quantum是ｑ，每一個Process得到1/n CPU Time
- Each process must wait no longer then (n-1)xq time units unit its next time quantum.(最多一個process只要等(n-1)*q就可以拿到cpu使用權)
- The performance of the RR algorithm depends heavily on the size of the time quantum
- If the time quantum is extremely large, the RR policy is the same as the FCFS policy(如果time quantum太大，其實就會變成只是像FCFS一樣的效果)
- 如果time quantum太小，context switch會太頻繁，context switch的overhead會太大
- each of n processes has its own processors running at 1/n the speed of the real processor(在time quantum極小的情況)
- 
- In general, the average turnaround time can be improved if most processes finish their next CPU burst in a single time quantum(一般來說，turnaround time可以改善，如果大部分的processes都在時間切片內完成它們的任務)
- Moreover, if the cost of context-switch is added in, the average turnaround time increases for a smaller time quantum
- A rule of thumb is that 80 percent of the CPU bursts should be shorter than the time quantum

- ## Multilevel Queue Scheduling
- The scheduling algorithm partitions the ready queue into several separate queues.
- Each queue has its own scheduling algorithm.
- 這種演算法將ready queue分成兩個：Foreground(需要交談的)、Background(可以批次的)。而這兩種queue有各自運用的演算法。而在排程時，這兩種queue之間要先做優先順序的排程、CPU時間的分配。
- The foreground queue might be scheduled by an RR algorithm(Foreground：RR演算法、高優先、80%的CPU時間).
- The background queue is scheduled by an FCFS algorithm(Background：FCFS演算法、低優先、20%的CPU時間)
- 
- ## Multilevel Feedback-Queue Scheduling
- The scheduling algorithm allows a process to move between queues(因為Multilevel queue的順序是固定的，有時還是需要調整一下順序，所以產生Multilevel feedback queue演算法，所以他是一種動態的排程機制。)
- The idea:
- If a process uses too much CPU time, it will be moved to a lower-priority queue.(要用比較長cpu time的process，到比較低優先權的queue，但增加time quantum)
- A process that waits too long in a lower-priority queue may be moved to a higher-priority queue
- 
- A multilevel-feedback-queue scheduler is generally defined by the following part.
- numbers of queue.(有幾個queue)
- Scheduling algorithms for each queue.(每個queue的演算法)
- Method used to determine when to upgrade a process.(什麼時候要把順序往前調)
- Method used to determine when to demote a process.(什麼時候要把順序往後調)
- Method used to determine which queue a process will enter when that process needs service(queue的選擇)

## 多處理器的排程(Multiple-Processor Scheduling)
- ## 非對稱(Asymmetric multiprocessing):
- Has all scheduling decision, I/O processing, and other system activities handled by a single processor – the master server(其中一顆processor是老大，負責指派東西給其他processor)
- ## 對稱(Symmetric multiprocessing,SMP):
- Each processor is self-scheduling.
- All processes may be in a common ready queue, or each processor may have its own private queue of ready processes.(每一個processor都有自己的private queue)
- Scheduling schedules each processor to examine the ready queue and selects a process to execute.
- Virtually all modern operating systems support SMP

- ## **Cache** in storage hierarchy:
- ## If the process migrates to another processor …
- The contents of cache memory must be invalidated for the processor being migrated from.(processor當中的cache之間的搬移)
- The cache for the processor being migrated to must be repopulated
- ## To avoid the cost, most SMP systems try to avoid migration of processes between processors.(盡量避免在兩個process之間做資料搬移)
- This is known as processor affinity, meaning that a process has an affinity for the processor on which it is currently running.
- **Soft affinity**(軟親和力): try to, but not guarantee that it will do so.
- **Hard affinity**(硬親和力): provide system calls for the forbiddance

- ## **Load balancing**:
- 如果某個processor的queue太滿，就嘗試搬到比較涼的processor
- Is often unnecessary on systems with a common ready queue.
- Once a processor becomes idle, it immediately extracts a runnable process from the common ready queue

- ## Two general approaches to load balancing
- **Push** migration:(有人推任務多的processor的任務去別的idle processor)
- A specific task (kernel process) periodically checks the load on each processor.
- Evenly distributes the load by moving (or pushing) processes from overloaded to idle or less-busy processor.
- **Pull** migration(idle processor拉任務過來):
- An idle processor pulls a waiting task from a busy processor.
- ## Push and pull need not be mutually exclusive.

## Real-Time CPU Scheduling
- **Soft** real-time systems – no guarantee as to when critical real-time process will be scheduled
- **Hard** real-time systems – task must be serviced by its deadline
- Two types of latencies affect performance
- 1. Interrupt latency – time from arrival of interrupt to start of routine that services interrupt
- 2. Dispatch latency – time for schedule to take current process off CPU and switch to another
- 
## Priority-based Scheduling
- For real-time scheduling, scheduler must support preemptive, priority-based scheduling
- Processes have new characteristics: periodic ones require CPU at constant intervals
- Has processing time t, deadline d, period p
- 0 ≤ t ≤ d ≤ p
- Rate of periodic task is 1/p
- 
## Rate Montonic Scheduling
- A priority is assigned based on the inverse of its period => **fixed priority**(依據頻率高低決定優先權，週期短(頻率高)有高優先權，週期長(頻率低)較低優先權)
- Shorter periods = higher priority;
- Longer periods = lower priority
- 
- t2改成35
- Properties
- Optimal fixed-priority scheduler for independent processes
- 
- 有成立代表所有process都可以排成，可以滿足deadline
- 沒成立不一定不能排，要手動檢查
## Missed Deadlines with Rate Monotonic Scheduling
- critical instance:
- An instance at which the process is requested simultaneously with requests of all higher priority processes
- 檢查到兩個process的公倍數時間
- 

## Earliest Deadline First Scheduling (EDF)
- Priorities are assigned according to deadlines: the earlier the deadline, the higher the priority; the later the deadline, the lower the priority(依據誰的deadline先到，誰的優先權就他媽越高，deadline越慢到的滾去後面涼快)
## Operating System Examples – Solaris
- Solaris uses priority-based thread scheduling:
- Six classes of scheduling:
- Real time.
- System.
- Fair share.
- Fix Priority
- Time sharing (default class for a process).
- Interactive (e.g., windowing applications).
- Each class includes a set of priorities.
- The scheduler converts the class-specific priorities into global priorities.
- The thread with the highest global priority is selected to run.
- If there are multiple threads with the same priority, the scheduler uses a round-robin queue.(若同時有許多執行緒他媽有一樣的優先權，則使用fucking round-robin來決定順序)
- Thus, the selected thread runs unit it (1) blocks, (2) uses its time slice, or (3) is preempted by a higher-priority thread.

- Threads in the real-time class are given the highest priority
- The scheduling policy for time sharing (and interactive) class dynamically alters priorities of threads using a multilevel feed back queue.
- 

## Operating System Examples – Windows XP
- Windows XP scheduler is a priority-based, preemptive scheduling algorithm.
- When a thread’s time quantum runs out … and it is in the variable-priority class.
- Its priority is lowered.
- To limit the CPU consumption of compute-bound thread.
- When a variable-priority thread is released from a wait operation …
- Its priority is boosted.
- Tend to give good response times to interactive threads.
- Foreground window given 3x priority boost

## Operating System Examples – Linux
- The Linux scheduler is based on scheduling classes, and is a preemptive, priority-based algorithm
- For the normal class:
- Each task is associated with a nice value.
- Nice values range from -20 to +19 (0 as default).
- Generally, a numerically lower nice value indicates a higher relative priority

- 
- CFS(Completely Fair Scheduler) does not use discrete values of time slices!!
- It identifies a targeted latency, which is an interval of time during which every runnable task should run at least once.
- The targeted latency has default and minimum values, and can increase if the number of tasks is growing.

- CFS does not directly assign priorities
- It records how long each task has run using variable **vruntime (virtual run time).**
- The virtual run time is associated with a decay factor based on the priority (nice value) of a task.
- For tasks at normal priority (nice value of 0), vruntime is identical to actual physical run time.
- If a higher-priority task runs for 200 milliseconds, its vruntime will be less than 200 milliseconds
- To decide which task to run next:
- CFS simply selects the task that has the smallest vruntime value!!
- In addition, a higher-priority task that becomes available to run can preempt a lower-priority task

## Algorithm Evaluation – Deterministic Modeling
- The evaluation method takes a particular **predetermined workload** and defines the performance of each algorithm for that workload.
- However, it requires exact numbers for input (predetermined workload), and its answers apply only to those cases.

## Algorithm Evaluation – Queueing Models
- The computer system is described as network of servers
- Queueing-network analysis: knowing arrival rates and service rates, we can computer utilization, average waiting time …
- If the system is in a **fucking steady state** ––– the number of processes leaving the queue must be equal to the number of processes that arrive(她媽的排隊的process跟進來的一樣多叫她媽的穩定狀態):
- 

## Algorithm Evaluation – Simulations
- Simulation involves:
- Programming a model of the computer system.
- The programmed system has a variable representing a clock.(有個變數他媽表示時間?)
- As the variable’s value is increased, the simulator modifies the system state to reflect the activities of the devices, the processes, and the scheduler.(當那個變數的值增加，simulator會去修改系統狀態並影響device processes scheduler的行動吧)
- To acquire more accurate result, we can use trace tapes.