[OS] Chapter3 -- Processes

http://www.csie.ntnu.edu.tw/~swanky/os/chap4.htm
http://www.csie.ntnu.edu.tw/~swanky/os/chap10.htm -> IPC
http://en.wikipedia.org/wiki/Process_(computing)
http://en.wikipedia.org/wiki/Scheduling_(computing)：第一段

Process: the unit of work in most systems
包含：code section, data section, program counter, registers, stack, etc.
Program is a passive entity(是死的); Process is an active entity(是活的)
Processes of the same program: same text section, different data sections
Thread: a basic unit of CPU utilization
Threads of the same process: same code & data section, other resources.
<對照習題4.5, Fig.4.11，fork出child process時是複製data，
而產生新thread時是共享data。>

Process state: new, waiting, ready, running, terminated
Process control block (PCB) -- information representing a process:
1. Process state
2. Program counter
3. CPU registers
4. CPU-scheduling information
5. Memory-management information
6. Accounting information
7. I/O status information

Scheduling queues:
1. Job queue -- containing all processes in the system.
2. Ready queue -- those in memory that are ready to be executed.
3. Device queue -- processes waiting for that device.
<對照Fig.3.6看架構>

Schedulers:
1. Long-term scheduler (Job scheduler, Admission scheduler):
從Job Queue中挑選合適的Jobs，將其載入到Memory中(放進ready Q)準備執行。
a. 執行的頻率不高
b. 可控制degree of Multiprogramming
c. 可調和I/O Bound與CPU Bound Job比例混合
d. 適用於batch system，不適用於time-sharing, real-time systems。
2. Short-term scheduler:
從Ready Queue中挑選priority較高之process，使其獲得CPU的控制權。
a. 執行頻率很高
b. 必須非常快，否則浪費CPU time
c. 適用於所有系統
3. Medium-term scheduler:
當記憶體空間不足，且有高優先權之process需要memory時，
挑選某些process做"swapping"。
a. swap out: remove processes from memory to "reduce the
the degree of multiprogramming"
b. swap in: reintroduce the swapped-out processes
into memory
c. 可調和I/O bound與CPU bound Job比例
d. 適用Time sharing system

Context switch:
Save the state of old process and load the state of new process.

fork() system call: creates a new process
exec() system call: load a binary file into memory and execute
wait() system call: wait for child process to complete
exit() system call: process terminates
abort() system call: terminate execution of child process

Inter-Process Communication
Independent process -- can't affect or be affected by others
Cooperating process -- can affect or be affected by others
Advantages:
1. Information sharing
2. Computation speedup
3. Modularity
4. Convenience
Cooperating processes require an IPC mechanism:
1. Shared memory
2. Message passing
<對照study guide: ch10的補充>

Client-Server Communication
1. Remote procedure calls (RPC)
Client's Stub locates the server and packs parameters
Server's Skeleton unpacks parameters and performs procedures
<對照Fig3.28的流程>
2. Remote method invocation (RMI)
Java mechanism similar to RPC, except:
a. Invoking a method directly without a matchmaker.
b. Ordinary data structures without packaging(marshalling).

[OS] 證明：Shortest Job First [SJF] is the optimal scheduling algorithm

修改自 http://computing.dcu.ie/~humphrys/Notes/OS/processes.html

What is the optimal schedule?

In general, if in-order bursts are x1, x2, ..., xn, then:

For each dispatched process, waiting time = (好像計網概題目XD)
1st: 0
2nd: x1
3rd: x1 + x2
4th: x1 + x2 + x3
...
nth: x1 + x2 + ... + xn-1

=> Total waiting time
= (n-1) x1 + (n-2) x2 + ... + (2) xn-2 + (1) xn-1 + (0) xn

Obviously this sum is minimized if the xi's that are multiplied the most times are the smallest ones, i.e., x1 < x2 < ... < xn-1 < xn.
Thus, in non-preemptive scheduling, "Shortest Job First" (actually Shortest Next CPU burst) is optimal for the purpose of minimizing Average Waiting Time. #

算是個淺顯又不失嚴謹的證明法 希望有幫助囉^^
P.S.王家祥老師說他喜歡考這個。

[OS] Chapter5 -- CPU scheduling

http://www.csie.ntnu.edu.tw/~swanky/os/chap4.htm
http://en.wikipedia.org/wiki/CPU_Scheduling

Process execution consists of a "cycle" of CPU bursts and I/O bursts.
CPU-burst distribution follow a (hyper)exponential pattern.
=> I/O bound programs: many short CPU bursts(左半邊)
CPU bound programs: a few long CPU bursts(右半邊)

Recall process states:
new, waiting, ready, running, terminated

CPU scheduling decisions may take place when a process:
1. running -> waiting [I/O or event wait]
2. running -> ready [interrupt]
3. waiting -> ready [I/O or event completion]
4. running -> terminates
Scheduling under 1 and 4 is nonpreemptive.
Scheduling under 2 and 3 is preemptive.

Dispatcher transfers control of CPU to selected process, involving:
1. Context switching
2. Switching to user mode
3. Jumping to proper location in user program to 'restart' that program

Scheduling performance criteria/objectives:
[max]1. CPU utilization - CPU用在process執行的時間比率
[max]2. Throughput(產能) - 單位時間內完成的工作數量
[min]3. Turn around Time - submission ~ completion
[min]4. ★Waiting Time - total/average waiting time in "ready queue"
[min]5. Response Time - submission ~ 1st response
在time-sharing system及user-interactive system中特別強調
其他目標：
# Fair(排班時儘量要求公平)
# No Starvation(避免飢餓)
# Support "priority" scheduling
# Resource Utilization ↑

Scheduling algorithms: [建議study guide整段全看]
1. First-come, first-served (FCFS):
Long average waiting time
Convoy effect(護衛效應) -- lower CPU and I/O utilization

2. Shortest-job-first (SJF): [證明是optimum]
Actually "shortest next CPU burst"
Difficulty: next CPU burst難以估計 -> used in long-term scheduling
[變種1] Approximate SJF:
Exponentially Weighted Moving Average (EWMA)
τn+1 = (α)tn + (1-α)τn
= (α)tn + (1-α)(α)tn-1 + ... + (1-α)^n(α)t0 + (1-α)^(n+1)*τ0
{α=1/2} = 1/2tn + 1/4tn-1 + ... + 1/2^(n+1)t0 + 1/2^(n+1)τ0

Non-preemptive SJF -- SJF (Shortest Job First)
[變種2] Preemptive SJF -- SRTF (Shortest Remaining Time First)
若其剩餘的CPU burst time大於新到達的process之CPU burst time，
則此process會被迫放棄CPU，交由新process執行。

3. Priority:
也可分為non-preemptive和preemptive
關鍵在於priority value的定義方式: internal vs external
SJF是一種priority scheduling -- Priority is the "next CPU burst"
FCFS是一種priority scheduling -- Priority is the "arrival time"
Problem: Starvation -- Low priority processes may never execute.
(易發生在unfair，甚至加上preemptive的環境)
=> Solution: Aging -- 隨著時間經過逐漸提高該process的priority

4. Round-robin (RR):
Time quantum: q
若未能在q內完成工作，則此process會被preempt掉，排到ready queue的尾端。
Time-sharing system使用RR
q too large => 趨近FCFS
q too small => overhead of context switching
Typically, higher turnaround than SJF, but better response. (fair)
Time quantum愈多 => context switch愈多，但與turnaround time並無明顯相關。

5. Multi-level queue:
將單一ready queue分成許多不同優先權等級的ready queues
每個Queue中可有自己的排班法則，如：foreground:RR, background: FCFS。
不允許process在各個queue中移動(沒有feedback)
Queue與queue之間的scheduling: fixed priority, priority time slice.
Preemptive, possibility of starvation

6. Multi-level feedback scheduling
基本同[5]，但Process可以在queue之間移動。
Still unfair, but prevent starvation
Design issues:
a. # of queues
b. Scheduling algorithms for each queue
c. 新Process進來該插到哪個queue
d. When to upgrade a process. e.g. Aging
e. When to downgrade a process. e.g. 在quantum內無法做完
設計上最為複雜

分類：
# Fair：
1. FCFS
2. RR
# No starvation：
1. FCFS
2. RR
3. Multilevel Feedback Queue
# Non-preemptive：
1. FCFS
2. SJF
3. Non-preemptive priority
# Preemptive:
1. SRTF
2. Preemptive priority
3. RR
4. Multi-level queue
5. Multi-level feedback queue

Multiple-processor scheduling: (assuming homogeneous systems)
1. Asymmetric multiprocessing: 有master-slave processors
2. Symmetric multiprocessing(SMP): self-scheduling
a. common ready queue; b. separate ready queues.
Process affinity -- attempt to keep running on the same processor
Load sharing: push migration -- process觀察後自主換排
pull migration -- idle processor拉waiting process
Symmetric multithreading[SMT] or Intel's hyper-threading[HT] --
One physical processor[PP], multiple logical processors[LP]

Real-time scheduling:
Hard real-time -- within a guaranteed amount of time
=> Resource reservation is needed
Soft real-time -- only receive higher priority

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
Algorithm evaluation methods:
1. Deterministic modeling
Input: a given algorithm, a predetermined workload
Output: Corresponding performance
優：simple and fast
缺：too specific
使用：舉例說明時；同樣程式可以一直跑；觀察趨勢再證明

2. Queuing models -- 排隊理論
Input: distribution of service time, process arrival time, etc.
Output: utilization, average queue, average waiting time, etc.
Little's formula:
n = λ * W
n:queue length; λ:arrival rate; W:waiting time (都是average)
優：compare algorithms
缺：只是理論估計，unrealistic，independent assumptions

3. Simulations -- Programming a model of the system
優：more accurate
缺：跑模擬費時，large storage，coding

4. Implementations -- Construct a read system
優：the most accurate way
缺：too costly, environment may change

OS參考資源 -- Operating System Study Guide

Operating System Study Guide

這裡有Operating Systems Concepts（恐龍本）6/e的詳細筆記

作者是師大資工博士生 蕭宇程 （才大我三歲@@"）

只能說這位大大太神了！這資料根本就可以當OS開課講稿嘛@@"

強力推薦！


之後會貼上我自己整理的Operating Systems Principles/Concepts 7/e筆記，主要參考資料是課堂講義和他的文章。

建議第一次期中考，時間不夠的話倒著讀會比較順，前兩章東西太雜。