Chapter 4 Process & Thread Management

前一章 | 首頁 | 下一章

Process(處理程序)

Def:A program in execution(執行中的程式)
Process的組成: Note:process與program的不同
process program
Active(帶有PC,指示目前的control of flow) Passive
A program in execution A file store in Disk(storage)

Process Control Block(PCB) contents

Def:OS為執行Process management,所以將process所有相關的資訊集中,建立一個集合(table)表示,稱為PCB

PCB contents包含下列:(p.4-5)

  1. Process Number(Process ID)
  2. Process State
    new, ready, running, waiting, halted...
  3. Program Counter
    the address of the next instruction to be executed for this process
  4. CPU registers
    accumulators, index registers, stack pointers, general purpose registers, condition-code information
    eg. 通用register, stack pointer, PSW等
  5. CPU-scheduling information
    process priority, pointers to scheduling queues, scheduling parameters
    eg. 優先權值, 在ready queue中的PCB指標
  6. Memory-management information
    the value of the base and limit registers, page tables, segment tables
    eg. Base/limit register, page table(if paging記憶體管理)
  7. Accounting information
    the amount of CPU and real time used, time limits, account numbers, job or process numbers...
    eg. 用了多少CPU time, 使用CPU的Max time, Quantum
  8. I/O status information
    the list of I/O devices allocated to this process, a list of open files
    eg. 未完成的I/O request,在I/O queue中的等待編號

又稱task control block

Process STD(State Transition Diagram)

Def:
描述Process之Life cycle
以可能的state及state之間的轉換事件來描述

允許Concurrent Processes Execution之理由(P4-6)

  1. 資源共享
  2. 加速運算
  3. 模組化
  4. 方便性

Process Creation

  1. Def:
    a process(Parent process)可以透過system call(eg. Fork() in UNIX)建立許多new processes(child process),目的是要利用這些child process完成特定的subtasks(or交付的工作)
  2. Issues
    1. Issue 1:Child process所需要的resources由何處取得?
      1. 由parent process:
        由parent process負責分派資源給child process
      2. 由OS:
        缺點:parent可生出過多的child process以致系統負擔太重
        限制child數目,以免系統負擔過重
    2. Issue 2:Parent被Delete, child process會如何?
      1. Delete All
      2. 仍存活
        1. 從OS取得資源
        2. 從祖父級以上process取得資源
    3. Issue 3:child與parent process之互動execution之情況有兩種
      1. Child與Parent counurrent execution
      2. Parent wait for child until child finish its job.
  3. Fork(), execlp(), wait() in UNIX之探討
    1. Fork():system call for process creation
    2. Fork()的傳回值:
    3. execlp()(old version exec())
    4. system call用以載入一個obj.code file(Binary code)到Memory中
    5. wait():system call用以suspend process
    6. Terminate():system call用以中止process

例:試利用Fork()及execlp() in UNIX寫出程式,此程式中parent process會生出一個child process負責執行"/bin/ls"命令,而parent must wait until child完成後,並印出"child complete"字串
程式:

#include<stdio.h>
void main(int argc, char* argr[]){
   int pid;
   pid = fork();
   if(pid < 0) {
      //fork失敗之處理
      fprintf(stderr,"fork failed");
      exit(-1);
   }
   else if(pid == 0) {
      //child process要做的事
      execlp("/bin/ls", ls, NULL);
   }
   else {
      //parent要做的事
      wait(NULL);
      printf("Child complete");
      exit(0);
   }
}

Schedular種類

Long-term scheduler(Job scheduler)

  1. Def:
    從Job Queue中挑選合適的Jobs,將其載入到Memory中準備執行
    selects which processes should be brought into the ready queue.
  2. 特點:
    1. 執行的頻率不高
    2. 可控制Multiprogramming Degree
    3. 可調和I/O Bound與CPU Bound Job比例混合
  3. 適用與不適用

Short-term Scheduler(CPU scheduler或Process scheduler)

  1. Def:
    從Ready Queue中挑選priority較高之process,使其獲得CPU的控制權
    selects which process should be executed next and allocates CPU.
    又稱之process scheduler or CPU scheduler
  2. 特點:執行頻率較高
  3. 適用性:適用於所有系統

Medium-term scheduler

  1. Def:
    Time sharing system常用
    當記憶體空間不足,且有高優先權之process需要memory,此時,此scheduler會挑選某些processes(eg. storage-time Quantum超過,lower priority process)將它們的Memory contents暫時SWAP out(reduce the programming degree of the system)到backing store(eg. Disk)以空出記憶體空間,等到Memory空間足夠時,再由此scheduler將此SWAP IN回記憶體中,繼續執行
  2. 特點:
    1. 可調和I/O bound與CPU bound Job比例
    2. 適用Time sharing system

Context Switching(內文切換)

  1. Def:
    當CPU從一個process切到另一個process執行之前,OS必須保存原有process的執行狀態(eg. pc, CPU register store in PCB),同時載入New Process的執行狀態(eg. Load PC, CPU register值from its PCB)稱之Context switching
    而 Context switching是一系統負擔,其時間長短,幾乎完全取決於Hardware因素
  2. 如何降低context switch之負擔

Dispatcher(分派器)

  1. Def:
    將CPU控制權授予經由short-term scheduler所挑選的process
  2. 工作內容:
    1. Context switching
    2. change mode from monitor mode to user mode
    3. Jump to the execution entry of the user program(process?)
  3. Dispatch Latency(分派延遲)

Scheduling Algorithm探討

  1. 排班效能評估標準(5個)
  2. 排班目標
  3. 各種Algorithm(7個)
  4. 計算題

Scheduling Performance Criteria

有五個:
  1. CPU Utilization(CPU利用度)
  2. Def:CPU化在process執行時間(CPU idle time + CPU用在process執行時間)
  3. Throughput(產能)
  4. Def:單位時間內完成的工作數量
  5. Waiting Time(等待時間)
  6. Def:process待在ready queue中等待獲取CPU的時間總和
  7. Turn around Time(完成時間)
  8. Def:自process進入系統(Memory)到其工作完成的這段時間總和
  9. Response Time(回應時間、反應時間)
  10. Def:自user command交付給系統到系統產生第一個回應的時間
    eg. 在Time-sharing system及user interactive system中特別強調

排班目標(objectives)

Starvation

Def:
當process因長期無法取得完成工作所需要的全部資源,形成自身無限期停滯(infinite blocking)的現象
(eg. 易發生在unfair,甚至加上preemptive的環境)
解決方式:"Aging" technique

作法:
系統每隔一段時間,將待在系統內時間很長,卻又未能完成工作的process,逐漸調高其priority,因此,在有限的時間內,其優先權可以升到最高,進而可取得資源完成工作

Non-preemptive及Preemptive

  1. Def:
    1. Non-preemptive:
      當process取得CPU在執行時,除非該process順利完成or自願釋放CPU(ie. waiting for I/O),其它process才有機會取得CPU,即不能強迫process放棄CPU
    2. Preemptive:
      當process正在執行時,有可能被迫放棄CPU(eg. 中斷發生,time qunatum expires),將CPU交給其它process執行
  2. 比較
    Preemptive Non-preemptive
    一般而言,排班效能較佳(Avg. waiting time及Avg. turnaround time↓) Avg. waiting time可能較長(∵可能有Convoy effect)
    Context switching較多 Context switching較少
    Response time或確切的turnaround time為不可預期的 可預期
  3. CPU排班決策的發生時期:
    1. running→waiting
    2. running→ready
    3. waiting→ready
    4. running→terminate
  • Preemptive設計所需付出的額外代價:
    1. 若多個process有共享資料存取時,當一個process在存取shared data時被插隊,則有可能導致結果不正確(eg. data inconsistent)的情況
      • 解決:
        提供mutual exclusive存取機制
    2. 當系統process正在執行且對一些kernel data structure(eg. I/O queue)存取時,若被其它process插隊,亦有可能造成kernel data inconsistent情況
      • 解決:
        不允許system process被插隊,確保system process完成後才作context switching(eg. UNIX, Linux)
      • 缺點:
        造成dispatch latency太長,不利於real-time system
  • Scheduling Algorithms

    1. FCFS(or FIFO)-First Come, First Service
    2. SJF-Shrotest Job First
    3. SRJF-Shortest Remaining-time Job First
    4. Priority
    5. RR-Round-Robin
    6. Multilevel queues
    7. Multilevel feedback queues

    FCFS(First Come, First Service)

    1. Def:
      到達時間(Arrival time)越早(小)的process,優先取得CPU控制權
    2. 例:
    3. 特點:
      1. 簡單,易於實作
      2. 排班效益最差
        ie. Avg. waiting time及Avg. turnaround time最長
      3. 會有"Convoy Effect"(護衛效應)
        Def:
        許多process均在等待一個需最大量CPU time才能完成工作的process,所造成的Avg. waiting time大幅增加的不良效應
      4. Fair
      5. No starvation
      6. Non-preemptive(不可插隊)

    SJF(Shortest Job First)

    1. Def:
      CPU burst time需求越少的process,優先取得CPU控制權
    2. 例:
    3. 特點:
      1. 為排班效益最佳的法則(其Avg. waiting/turnaround time最小)
      2. Unfair
        ∵偏好short time job
      3. 可能有starvation
      4. Non-preemptive(Preemptive SJF即為SRJF)
      5. SJF不適用於short-term scheduler
        ∵此scheduler執行頻率高
        ∴很難在極短時間內算出各process精確的next CPU burst time並挑出最小值,故不適用
      6. SJF適用於Long-term scheduler
        ∵其執行頻率較低

    證明:"SJF is the optimal scheduling algorithm"(with最低的Avg. waiting/turnaround time)

    Pf:
    設原先Gantt Chart中有下列形式存在:

    在經由SJF排班後,其Gantt chart:

    使得short time job所減少的waiting time必定大(等)於long time job所增加的waiting time
    ∵若將每個short time job都依此前移,必使得Avg. waiting time為最小

    預測next CPU burst time之公式

    τn+1=ατn+(α-1)Tn

    其中

  • 一般而言,α=1/2(指數平均時間)
    τ2=1/2α1+1/2T1
    τ3=1/2α2+1/2T2=1/4α1+1/4T1+1/2T2
    ...
  • SRJF(Shortest Remaining-time Job First)

    1. Def:
      為preemptive SJF,當process執行時,若其剩餘的CPU burst time大於新到達的process之CPU burst time,則此process會被迫放棄CPU,交由新process執行
    2. 例:

    3. 特點:
      1. Unfair
      2. 會有starvation
      3. Preemptive

    Priority scheduling Alogrithm

    1. Def:
      具有最高優先權的process,優先取得CPU控制權
    2. 關鍵在於priority value的定義方式
      定義觀點:外部 vs 內部、static(changable) vs dynamic
    3. priority與其它法則的關係(在於優先權的定義方式)
      eg.
      1. Arrival time越小,則優先權越高→FCFS,FCFS包含於priority
      2. Process CPU burst time越小,則priority月高→SJF(SRJF)包含於priority
    4. 例:

    5. 特點:
      1. Unfair
      2. 可能有starvation
      3. 可分為non-preemptive或preemptive

    Round-Robin Algorithm

    1. Def:
      常用在Time-sharing system
      OS規定每個process使用CPU的time quantum,一旦process取得CPU後,若未能在此quantum內完成工作,則此process會被迫放棄CPU,等待下一輪再度使用CPU
    2. 製作:需要Hardware:Timer支援
      作法:當process取得CPU後,Timer的初值設為Quantum值,隨著process執行時,Timer值會逐次遞減直到Quantum值為0,會發出"Time out"通知OS,OS會強迫目前的process放棄CPU
    3. 例:

    4. 特點:
      1. Time-sharing system使用
      2. Fair
      3. No starvation
      4. Preemptive
      5. 排班效益取決於Quantum大小之制訂
        兩個極端:
        • Time quantum=∞
          →RR會退化為FCFS(∵FCFS包含於RR)
        • Time quantum=極小
          →Context switch太頻繁,CPU未花時間在process execution上
          ∴throughput極低
  • 一般而言,Quantum的大小讓80%的工作可在此Quantum內完成,效益較佳
  • Multilevel Queue

    1. Def:
      1. 將單一一層的ready queue進一步分成許多不同優先權等級的ready queue
      2. Queue與Queue之間的排班是採取preemptive priority法則居多
      3. 每個Queue中可有自己的排班法則,如:RR, FCFS, ...
      4. 不允許process在各個queue中移動
    2. 特點:
      1. 增加scheduling design的flexibility
      2. Unfair
      3. Preemptive
      4. 會有starvation

    Multilevel Feedback Queue

    1. Def:
      與Multilevel Queue類似(1,2,3相同)
      差別在於"允許process在各個queue之間移動",以防止starvation情況
    2. 作法:
      1. 採取類似"Aging"技術,每隔一段時間,將各process往上提升到上一層Queue中
        ∴在經過有限時間後,在Lowest priority queue中的process會被至於Highest priority queue中
      2. 亦可配合"降級"之動作
        當上層queue中的process取得CPU後,若未能在quantum內完成工作,則此process在放棄CPU後,會被置於比較下層的Queue中
    3. 特點:
      1. Preemptive
      2. Unfair
      3. No starvation
      4. 設計上最為複雜
    4. RR包含於Multilevel(Feedback) Queue
      (通常,越上層的Queue,其Quantum較小,越下層越大)

    Summary

    1. Fair:
      1. FCFS
      2. RR
      3. (HRRN)
    2. No starvation:
      1. FCFS
      2. RR
      3. Multilevel Feedback Queue
      4. (HRRN)
    3. Non-preemptive:
      1. FCFS
      2. SJF
      3. Non-preemptive priority
      4. (HRRN)

    Multiprocessor system的排班考量(設計原則)

    Real-time system之考量

    Thread Management

    Thread

    Def:
    類似process,又稱Lightweight process,是unit of the CPU utilization Thread creation會包含 所不同的是同一process內的不同Threads彼此可以共享
    1. Code Section
    2. Data Section
    3. Other OS resources(eg. openfiles)
    圖示:

    Thread vs Process

    Thread Process
    Lightweight process Heavyweight process
    同一個process內的Threads可以共享Code、Data Section及OS Resources process與process並無實質的共享,互為獨立的Address space
    Context Switching負擔輕 負擔較重
    Thread Management cost較低 Process Management cost較高
    一個process內有多條Threads存在 一個process內只有一條Thread
    較能充分利用Multiprocessors架構之效益
    (同一個process的不同Threads可以同時Run on不同CPUs)
    較無法有效發揮
    當process內的某Thread Block,則可切到其它Thread執行
    ∴process不會因而Block(kernel thread)
    傳統的process不是如此
    必須提供對Shared Data的互斥存取控制,以防止不正常Thread存取所造成危害 process與process無共享,所以較無必要

    Thread種類(角度:Thread Management由誰負責)

    1. User(-Level) Threads
    2. Kernel(-Level) Threads
    User Threads Kernel Threads
    Def:
    Thread Management is supported by the "Thread Library" at user-Level
    Def:
    Thread管理是由kernel所負責
    優點:
    Thread之間的scheduling、context switching等,不需kernel介入
    ∴Fast context switching and creation
    缺點:
    Slower context switching and creation
    user Thread管理成本較低 kernel Thread較貴
    kernel不知道user Threads存在 kernel掌握所有Threads之管理
    缺點:
    當user Thread發出Blocking System call,且kernel為single-Threaded(process-oriented)
    會導致整個process亦被Blocked
    優點:
    Thread發Blocking System call,不會使整個process Blocked
    缺點:
    無法有效利用Multiprocessor之效益
    優點:
    可以安排不同Threads在不同CPUs上平行執行,發會Multiprocessors效益
    eg.
    • POSIX Pthreads
    • Solaris 2 UI-threads、Green threads
    • Mach C-threads
    eg.
    • Windows NT
    • Windows 2000
    • Solaris 2
    • Tru64 UNIX

    Thread好處(可與定義合併寫)(P.4-36)

    1. Responsiveness(回應程度)
    2. Resource sharing
    3. Economy
    4. Utilization of multiprocessor architectures

    Thread Models

    Thread Issues

    Issue 1:Fork()

    Issue 2:Signal Handling

    Signal

    1. Def:(★)
    2. A signal is used in UNIX systems to notify a process that a particular event has occurred.
      (通知process某特定事件發生)
    3. pattern
      1. -
      2. -
      3. -
    4. 種類(★)
    5. Signal對Thread之issues(P.41下~42)

    Issue 3:Thread pool