作業系統筆記

chapter 1

電腦的基本架構:

作業系統核心概念:

• 資源分配器

  • Manages all resources
  • Decides between conflicting requests for efficient and fair resource use

• 控制程式

  • Controls execution of programs to prevent errors and improper use of the computer

• interupt base : 呼叫才會做處理

• 作業系統中永遠運行的程式就是kernel，除了kernel以外的，都叫system program或application program

• CPU會把資料從memory裡丟到local buffer，然後memory會直接跟buffer做溝通
  

• interrupt比喻:櫃台叫你去填表單，填完後再告訴他，你填東西的這段時間，櫃台還可以服務其他人

• device drive(hardware)或application(software)做完後，會發出interrupt告訴CPU任務做完了

• interrupt handling

  • polling:一個一個檢查誰需要interrupt
  • vector:回傳一個值告訴作業系統誰需要interrupt，較有效率，OS大多採用這個

• Storage-Device Hierarchy 越往下越慢，容量越大
  

• bootstrap program:把kernel load進去

• timesharing:透過很短暫的時間快速切換工作，讓user有種OS只服務他一人的感覺(時間管理大師)

• Memory Layout for Multiprogrammed System
  

• dual mode : 有些東西不能讓使用者直接碰觸到，所以要有區分

  • user mode : user可以直接存取呼叫
  • kernel mode : user要透過system call來存取呼叫

• system call : 讓user存取system program的介面，user呼叫interrup，讓kernel去存取受到限制的資源(kernel mode)
  

chapter 2

• Operating System Services
  • User interface
  • Program execution
  • I/O operations
  • File-system manipulation
  • Communications
  • Error detection
  • Resource allocation
  • Accounting
  • Protection and security
• 作業系統為甚麼不採取完全沒有錯誤的方法:會運行的很慢，找出問題並解決，才是重點
• 作業系統架構:
  
• API:再對system call做一層包裝，因為sys call會隨版本更新變動，透過一個共用介面來簡化程式
• 一個sys call後會做非常多事
  
• 只服務一個user single tasking，memory只有一個process:
  
• 單晶片，沒有作業系統，用bootloader載入程式，更簡單基本
  
• 多人多工OS，memory有多個process
  
• link and load
  • link:把函式庫link進二進位檔
  • load:把執行檔從disk載入到memory
    
• monolithic structure:UNIX使用，不把系統分太細，主要分為兩大塊:
  • system programs
  • the kernel
    • system call interface
    • file sys、CPU scheduling、memory management…
• UNIX的架構，沒有layer的概念:
  
• linux structure:在unix加入modular design
  • 原先的設計是有新的裝置controller要加入，整個系統就要重新compile
  • modular:可以把一些功能load到kernel裡，不用重新compile
• layer approach:
  • 每一層depend on上一層
  • 沒效率，因為底下operation都會做到
  • 中間的層難以排序，沒有一定的相依性
    
• micro kernel:減少kernel大小，需要用到時再從user space載入到kernel
  

chapter 3

• process:執行檔load到memory後就稱為process
  
• memory layout
  
• 程式 to 程序
  • 程式檔案的頭部會存放資訊告訴OS怎麼把它放到記憶體裡，程式進入點在哪
  • windows: PE(Portable Executable) Header
  • Linux:ELF(Executable and Linkable Format)
• process state
  
• 前面的layout沒有儲存process state的資訊，所以要有PCB(process control block)
  
• 一個process對應一個PCB
• PCB內會有pointer指向真實在memory的位址
• CPU Switch From Process to Process
  
• context snapshot:將被switch out的process的資訊(register、IO、進度)存回PCB，讓下一次再選到這支process執行時，可以重新載入
• process內可能會有很多thread，可以假想成有很多program counter在跑
• process含有兩大部分，PCB與process真實存放的記憶體位址
  
• PCB與PCB之間會用雙向linked list連接
• process scheduling
  • 為了避免去檢查整個list，所以用queue存放，增加效率
  • ready queue : 存已經可以執行的process的PCB
  • wait queues : 存還不能馬上執行(等待IO、…)的process的PCB
• schedulers
  • long term/job scheduler : 每幾秒甚至每幾分鐘才執行一次，挑一批process進入ready queue，限制多少process可以進入ready queue
    • 會盡量讓I/O 與 CPU bound process各佔一半比例，避免太多人排隊給CPU執行
    • 隨著電腦越來越強，這種機制已漸漸被淘汰
  • short term/CPU scheduler : 幾ms執行一次，挑一個process執行，限制每個process可以執行的時間
  • medium term scheduler : 因為某些原因導致ready queue內放的不是想要的，這時候就用swapping
    • swapping : 把process直接從memory丟到disk去(並非丟執行檔，而是記憶體原封不動的丟)
  • 比喻:long term->會議室外的等待空間，short term->每個人可以報告的時間
• context switch
  • context就是PCB
  • context switch的時間，CPU無法做任何事
  • context switch時間減少，CPU效率提升
• process creation
  • 用parent產生children的概念
  • 會用parent process來產生新process是因為這樣會更方便複製process的資料結構也就是直接把parent複製一份fork，然後改pid即可
  • 父子process可以share記憶體，所以設計可以非常靈活
  • process在fork完後才會將執行檔load進memory，然後存指標到PCB
  • 父process會等待子process結束後才能結束
  • 執行一個程式 : 父process執行fork -> 子process執行exec
• fork，假設child的pid都為0
  • fork回傳的是自己的pid，並非child process的pid
  • fork完後產生child，parent與child除了pid之外都一模一樣
  • 當CPU選中child去執行時，就會跑到case pid==0裡，然後執行exec把這段程式碼蓋掉成想要的
    
• process termination : process結束後釋放記憶體
  • parent process有權限把child process終止，以避免沒有把記憶體釋放乾淨
• thread概念:一個process裡有不同的program counter，所以一個process裡可能有多個TCB(thread control block)
• chrome記憶體用量大原因:每開一個分頁就是一個process，會這樣做是為了避免某個分頁掛掉，其他分頁也跟著掛掉
• interprocess communication(IPC)
  • shared memory : 兩個process共用一塊記憶體，存取快速便利，但不安全
    • 問題:要如何解決寫入到一半時被interrupt後，造成其他人讀取到不正確的值?(同步問題)
  • message passing : process之間透過類似system call的方式從kernel讀取共用的記憶體，較安全
  • communication
    • direct : 直接發送接收資訊，1對1
    • indirect : 放到mailbox，別人再從mailbox拿出來
• synchronization
  • blocking : 等到receive完後才能結束send，等到send完所有message後才能receive
  • non-blocking : 丟完後就可以結束send，接受訊息也不管有沒有正確
• pipe : 用父子process的關係讓溝通變簡單(約定某塊記憶體收發訊息)
• remote procedure call(RPC):執行遠端電腦的system call或程式

chapter 4

• Single and Multithreaded Processes
  • 一個PCB可能指向多個TCB(依實作而定)
    
• 為何要用thread : 不用每次都複製一大堆相同程式碼，節省記憶體
  • Responsiveness
  • Resource Sharing
  • Economy
  • Scalability
• concurrency : 快速切換來同時運行多個task，但實際上同時只執行一個
• parallelism : 用multicore來同時執行多個task，真正意義上的同時執行多個
  • data parallelism : 資料分成不同core來執行，某段只由一個core執行
  • task parallelism : 同一段資料可能有多個core來執行
    
• user and kernel threads
  • many to one : 有一個thread call system call後就interrupt process，造成其他thread也跟著被暫停
  • one to one : user thread自動產生或對應到一個kernel thread，library與kernel息息相關
  • many to many : 可以提供1對1，也可以提供多對多，自動判斷如何對應(檢查thread pool)
  • two level : kernel thread被綁定在user thread
• implicit threading : compiler自動幫你multithread，但並沒有在程式碼裡實作multithread，顯性則反之
• fork-join parallelism : compiler自動把task切割fork出去執行，然後把結果join起來
• grand central dispatch : runtime時才變成multithread
  • serial queue: 序列化執行，無法平行化的程式會丟到這個queue
  • concurrent queue: 平行化執行
• multithread process執行exec後會將所有thread覆蓋掉
• multithread下的fork有兩種
  • 複製所有thread
  • 只複製執行到fork的thread : 通常會用後fork後馬上exec
• signal handling : 其他process對發生例外狀況的process發出通知，做後續處理(關閉某個或某些thread)
• thread cancellation
  • asynchronous : 立即cancel thread
  • deferred : 檢查現在是否可以被cancel，不行的話就等待thread做完後才cancel
  • off : 無法被cancel
• thread-local storage(TLS) : 存一些function與function之間的information，thread特有的資訊
• scheduler activations : user thread與kernel thread之間溝通的流程
  • light weight process(LWP) : 存user thread與kernel thread之間的關聯對應資訊的資料結構，位於kernel space
  • 讓user thread以為LWP是一個virtual process
  • 
  • 每個user thread都會對應到一個LWP，LWP也只會對應到一個user thread，但可能對應到多個kernel thread
  • upcall : kernel thread通知user thread訊息
  • 可以是kernel thread產生多個LWP，也可以是多個LWP assign到不同的kernel thread，有很多種做法
  • LWP就是user thread在kernel的代理人

chapter 5

• CPU scheduler : 在ready queue中尋找下一個適合的process執行，雖然真正的最小執行單位是thread，但是存放的資訊還是在process裡，所以scheluder是選擇process而不是thread，process選完後才近一步選thread，thread再去選用哪個CPU來執行。

• preemptive vs non-preemptive

  • preemptive : 執行到一半時可能因scheduler而被強制交出CPU使用權，有效率
  • non-preemptive : 會等到該process離開running state後才執行scheduler，running自己主動呼叫scheduler的情形就屬於non-preemptive，沒效率

• 呼叫scheduler時機 #必考

  • running state to waiting state (做IO) => non-preemptive
  • running to ready state (interrupt occurs、時間用光了) => preemptive
  • waiting to ready (IO完成)，比喻:填完表單的人可以讓櫃台決定要不要先服務你，而不用從頭開始排隊 => preemptive
  • running terminate (執行結束) => non-preemptive
    

• dispatcher : scheduler選好下個process後，就交給dispatcher，做以下處理:

  • context switch
    • 把現在的process存回PCB
    • 把選定的下個process的PCB資訊載入到CPU register
  • switching to user mode
    • user mode之間的轉換
  • jumping to the proper location in the user program to restart that programjum
    • program counter指到接下來要執行的process的程式碼
  • dispatch latency : 執行dispatch的時間
    
  • 沒有人可以打斷dispatch，比喻:皇帝旁的太監

• scheduling criteria

  • CPU utilization : CPU越忙越好，榨乾時間
  • throughput : 單位時間處理越多process越好
  • turnaround time : 每個process從開始處理到結束的時間越短越好
  • waiting time : process在ready queue裡等待時間越短越好
  • response time : 從request到response的時間越短越好
  • 不可能全部都同時優化

• First Come First Served(FCFS) : 依據進來的順序去執行，也就是直接拿ready queue的第一個element

  • 
  • 但average waiting time是17，如果先做P2、P3，可以讓average waiting time減少
  • 
  • convoy effect : 讓short process先做，就可以降低waiting time
  • 為了降低waiting time，所以有了SJF

• Shortest Job First (SJF)

  • 但問題是還沒執行前都不知道burst time是多少，所以通常用預估的方式來決定burst time
    
  • 預估方法:
    
  • EX: 下一次預估 = 本次預估*0.5 + 實際時間*0.5
    

• shortest remaining time first : FCFS與SJF結合

  • 看剩多少時間要執行，先選最少的，此方法為preemtive，如果出現一個更少剩餘時間的process，就會強制切換
  • 

• priority scheduling

  • 選低priority值的process執行

• Round Robin

  • 每個process執行一段時間(time quantum q)就換人，一直輪流下去
    • time quantum q usually 10-100 ms,context switch < 10us
    • quantum 通常設計為 80% of CPU bursts should be shorter than q
      
  • 在現實中很少見，因為人腦無法快速切換工作

• Multilevel queue : 把不同種類的process丟到不同的queue，現在OS大多用這種方法

  • 用不同排程演算法處理不同queue
    
  • queue之間也有priority
    
  • Multilevel Feedback queue : process可以在不同queue之間移動，會有一些機制來把process丟到其他queue，避免等太久

• 各種排程的比較
  

• 期中必考1
  

• 期中必考2
  

  

• Multiple Processor scheduling
  • Homogeneous processors : processor之間的運算能力是一樣的
  • Asymmetric multiprocessing : 有一個專門負責scheduling的processor
  • Symmetric multiprocessing(SMP) : 現代OS常用，每個processor自己決定CPU scheduling
    • 所有thread存在common ready queue
    • 所以多個processor有可能選到同一個thread，產生大問題
    • 因此現在改變為每個processor都有一個ready queue
    • 每個thread會被分配到不同的ready queue裡
• 把所有multiple processor放到同一個chip就叫multicore processor
• Multithreaded Multicore System
  • 趁其他thread在存取記憶體時切換到另一個thread執行
    
  • Chip-multithreading : 每個core裡都有2條hardware thread，完全由硬體實現，會多一套register來存另一個thread的register值
    • hyperthreading in Intel
      
  • two level of schduling
    • kernel thread對應到hardware thread就會用前面提到的排程演算法
      
• load balancing : 不讓每個CPU上面放的task太多
  • push migration : 把overloaded CPU的task push到其他CPU
  • pull migration : 閒置的CPU把task從overloaded CPU拉過來
• Processor Affinity : 盡量讓task留在同一個CPU，讓快取起到作用
  • soft affinity : OS想辦法讓task只在一個CPU上執行，但不保證
  • hard affinity : 保證task只在某幾個CPU上執行
• Non-uniform memory access (NUMA) :
  • 移動task後，CPU就要存取到其他CPU的memory，這樣的速度很慢
  • 因此盡量避免移動task到其他CPU
  • 
• 一個core同時只能處理一個hardware thread，這是concurrency而非parallelism
• Real time CPU scheduling : 要求在很準確時間執行的task(EX火箭)，不能被其他process影響
  • soft real-time : priority高的先處理，但無法保證高priority一定可以被schedule
  • hard real-time : 一定滿足條件，重點放在執行的時間
    • event latency : event發生到被serve的這段時間
      • interrupt latency : interrupt進來後直到執行完interrupt的時間
      • dispatch latency : 選好下個process到執行完dispatch的時間
  • 
  • dispatch有可能conflict，也就是要等別人處理完資料，花額外時間去處理conflict
• preemptive,priority based scheduling : 一個更緊急的事件出現後，要把現在的process換掉
  • 每個thread會periodic的出現，每p秒出現一次，執行t秒(event latency)，deadline是d
  • 需求 : 0 ≤ t ≤ d ≤ p
  • 
• Rate Montonic Scheduling
  • 給每個thread或process一個period或priority，週期越長，priority越低，週期越短，表示常常執行，priority越高
    
  • missed deadline
    
  • 公式算出來是83%小於2個utilization相加的0.94，因此會miss
• Earliest Deadline First Scheduling(EDF) : 依據離deadline的時間來排程
  
  • 最佳theoretically optimal solution 比rate montonic好
  • 但經常切換，所以要考慮到context switch的時間，所以不一定適用所有狀況
• Proportional Share Scheduling
  • 所有process有T個share
  • 現在已經有N個share
  • 
  • 判斷D進來後是否有辦法分配下去，無法的話就拒絕
• linux scheduling
  • version 2.4
    • global runqueue/expired queue
    • 把所有thread丟到runqueue
    • runqueue的process執行完後丟到expired，直到runqueue都被執行完後，就開始執行expired queue
    • 高priority得到更大的quantum
  • version 2.5
    • priority從0~140，用140個queue的array存放所有thread
    • CPU可以直接從priority最高的queue內拿出thread
    • 有thread存於queue的priority就會把該priority的bit變為1，使搜尋時間達到O(1)
    • 高priority得到更大的quantum
  • version 2.6.23
    • completely fair scheduler(CFS) : 值的部分重新設計
    • 
    • virual run time : 記錄每個thread用了多少時間
    • 根據virual run time來決定下個選誰，不只考慮priority

chapter 6 & 7

• race condition : 多個process在同時競爭(使用)相同的資源，結果與存取資源的順序性有關連時，race condition就會發生

• Synchronization : 避免race condition的發生

• critical section problem

  • critical section : 會動到與其他人share data的程式碼段落，簡稱CS
  • critical section protocol : 在執行到critical section之前與之後去做一些措施保證critical section執行期間不會被schedule out
    • entry section
    • exit section

  

  • solution
    • mutual exclusion : 在執行critical section期間，只有該process可以做，沒有其他process可以中途插入，一定會等critical section做完
      • 晚到的entry會被block起來
      • 執行結束後知會其他process可以進入critical section了
    • progress : 要持續進展，否則其他人會被卡死，無法執行下去
      • 在多個entry中決定下個進入的entry
    • bounded waiting : 要保證不會無限地等下去，遲早有天會輪到你去存取
    • 不能根據速度去決定下個entry否則會不符合bounded waiting，可能有人無限等下去，永遠選不到他

• EX

  • 只判斷是不是輪到自己
  • 無法滿足progress與bounded waiting條件，因為如果只有一個process，而且turn又不符合條件，就會無限等下去

• EX

  • 只判斷對方要不要做，對方要做，就等對方
  • 也無法滿足progress與bounded waiting條件，如果同時執行到while，則兩邊會互相等待，無限等下去

• peterson's combined solution

  • LOAD與STORE都不可被中斷
  • 同時判斷 是不是輪到自己 與 對方要不要做
  • 
  • 滿足所有條件

• Prove the validity of a critical section?

  • Mutual exclusion
    – 假設兩個（以上） 的processes可以同時進出CS，找出其矛盾
  • Progress
    – 沒有process在CS中，一個process要進去CS，一定可以進去
    – 多個process要進CS，在有限的時間內做出決定
  • Bounded waiting
    – 找出次數的上限

• peterson's solution
  

  • comiler或硬體可能把x = 100;與flag = true調換順序，使Mutual exclusion條件無法符合
    
  • 所以需要有hardware支援才能真正解決Synchronization問題

• Synchronization Hardware

  • Memory barriers : 實現某些單位的memory之更改可以馬上被別人知道
    • memory model
      • strongly ordered : 一個processor對memory做任何動作會馬上讓其他processor知道
      • weakly ordered : 以上反之
    • 
  • Hardware instructions : 透過硬體確保不會在執行過程中被interrupt，不滿足bounded waiting，有機會永遠等不到

    • Test and Set Instruction

      • 

    • Compare and Swap Instruction

      • 至少確保不會有多個人去使用
      • 實作出lock的概念
        

      

    • 在entry與exit section內都有可能發生race condition，所以其實這些解法都只是將複雜的大問題(critical section)轉化成小問題(entry與exit section)，但問題本身還是存在，在讀寫lock變數時還是有機會被interrupt。

    • Bounded-waiting Mutual Exclusion with compare-and-swap
      

  • Atomic variables : 確保寫入變數時不會被interrupt

• Bakery Algorithm

  • 麵包店算法
    

• 為何不使用hardware解決Synchronization就好?

  • 因為hardware較適用於實作entry section的single且簡單的資料結構(int、bool…)，而無法處理CS內複雜的資料結構(buffer、array…)
  • 無法達成Bounded waiting條件，無法確保所有人都會被選中，可能一直等下去
  • 解法 : 軟硬兼施，改用mutex lock或semaphore

• busy waiting : 不context switch，而是一直不斷檢查，用於context switch cost 很高的情形

• mutex lock : 在OS層面實作lock的library

  • (mutual exclusion) lock
  • lock變數都是使用Atomic variables
  • 可以滿足三大條件
  • busy waiting
  • 

• Semaphore

  • busy waiting
  • user可以確保哪個process先執行
  • 
  • 
  • 
  • 等到P1跑完signal(synch);後，P2才可以進入S2;

• 不用busy waiting的方法?

  • 改用waiting queue(list指標)
    

  

• Four Typical Uses of Semaphores

  • Mutual exclusion
  • Force suspend : 強制某個process先執行， Keep the execution in a particular order
  • Count-down lock : 限制可以進入的process數量
    
  • Notification : Indicate that an event has occurred
    

• deadlock and starvation

  • starvation
    • indefinite blocking
    • A process may never be removed from the semaphore queue in which it is suspended.
    • 
  • priority inversion
    • 高priority因為lock的關係導致必須等待低priority的人
      
    • Priority Inheritance : 低priority的task卡住要高priority的task，就要把priority繼承過去，避免之後被其他較低priority的task(Task2(M)) preempt
      

• Monitor : 自己定義資料結構(ADT)，OS會自動保證Mutual exclusion，不會有deadlock的狀況
  

  • signal and wait : 離開去等待，通知下一個人
  • signal and continue : 繼續做完剩下的事才離開
    
  • 針對每筆資料都可以有一個condition

• 用Semaphore實作出Monitor
  

• What’s the different between semaphore and monitor?

  • 比喻 : monitor像公廁，一個人進去其他人就不行進去
  • 比喻 : semaphore像bicycle hire，大家共用某幾台bicycle

• Classical Problems of Synchronization

  • Bounded-Buffer Problem
    • 
    • 
    • 如果wait (mutex);與wait (empty);寫反，則可能造成deadlock的狀況
  • Readers and Writers Problem
    • 有一shared data set
    • reader : 只會讀取，不會寫入data set
    • writer : 可讀可寫
    • problem
      • 多個reader同時讀取
      • 同時只能有一個writer存取
      • writer寫入時，reader不能讀取
      • 如果有reader在讀，writer必須等待
  • Dining-Philosophers Problem
    

期中考古題