清大OCW 作業系統 筆記

希望我能持續下去:D
4/19: 我真的要瘋了 真的看不完了 所以我已經放棄全部讀完ㄌ:D

簽到表:

日期	課程
113/03/25	ch0 1A~2D
113/03/27	ch1 3A
113/04/01	ch1 3B~4A
113/04/04	ch1 4B~4D
113/04/12	ch2 5A~5B
113/04/14	ch2 5C~5D
113/04/15	ch2 6A~6B ch3 7A~7B
113/04/19	ch3 8B~9B

---

期中考範圍: 讀書進度安排

章節	影片範圍	時間	簡報
Ch0(期中不會考?)	1A~2D (*6)	-	Ch0
Ch1	3A~4D (*6)	2:14:34	Ch1
Ch2	5A~6B (*6) (6A、6B各一半)	2:01:52	Ch2
Ch3	6A~9B (*10) (6A、6B各一半)	3:24:16	Ch3
Ch4	15A~16B (*4)	1:26:13	Ch4
Ch5	16C~18B (*6)	2:25:06	Ch5
Ch6	18C~21B (*10)	4:04:46	Ch6
Ch7	22A~22D (*4)	1:29:36	Ch7
Ch8	10A~12B (*8)	3:50:56	Ch8
Ch9	13A~14D (*6)	2:24:19	Ch9

考古專區

---

期末考範圍:

章節	影片範圍	簡報
Text	Text	Text

預計進度:

---

課程影片
講義

看同一個OS開放式課程的筆記

---

• 清大OCW 作業系統 筆記
• PART 1 Overview
  • • Mainframe Systems
    • Computer-System Architecture
    • Special-Purpose Systems
    • 大總結
  • Ch1 Introduction
    • What is OS?
    • Computer-System Organization
    • Storage-Device Hierarchy
    • Hardware Protection
  • Ch2 System Structures
    • OS Services
    • Applications-OS Interface
    • System Structure
• PART 2 Process Management
  • Ch3 Process Concept
    • Process Concept
    • Process Scheduling
    • Operations on Processes
    • Interprocess Communication (IPC)
  • Ch4 Multithreaded Programming
  • Ch5 Process Scheduling
• PART 3 Process Coordination
  • Ch6 Synchronization
  • Ch7 Deadlocks
• PART 4 Memory Management
  • Ch8 Memory-Management Strategies
  • Ch9 Virtual-Memory Management
• PART 5 Storage Management
  • Ch10 File System
  • Ch11 Implementing File Systems
  • Ch12 Mass Storage Structure
  • Ch13 I/O Systems

---

PART 1 Overview

Mainframe Systems

• one of the earliest computers
• evolution: batch -> multi-programmimg -> time-shared

Batch

• 一次只能處理一個程式
• steps:
  1. users submit jobs (program, data, control card) (上圖那些卡片)
  2. operator sort jobs with similar requirements (一綑一綑的卡片排順序)
  3. OS simply transfer control from one job to the next
• drawbacks:
  • one job at a time
  • no interaction between users and jobs
  • CPU is often idle
    • I/O速度比CPU慢非常多
• OS doesn't need to make any decision

Multi-programmimg

• overlap: 多個program
  • keep both CPU and I/O devices working at higher rates
• spooling (Simultaneous Peripheral Operation On-Line)
  • I/O is done with no CPU intervention
  • CPU just needs to be notified when I/O is done
    
  • 用interrupt實現 (Ch1)
• 先把 jobs load 到 memory (Job Scheduling)，再挑 job 到 CPU 去執行 (CPU Scheduling)
  
• OS tasks
  • memory management
  • CPU scheduling
  • I/O system

Time-Sharing (Multi-tasking)

• An interactive system provides direct communication between the users and the system
  • CPU switches among jobs so frequently that users may interact with programs (一有input就interact)
• Multiple users can share the computer simultaneously
• switch job when
  • finish
  • waiting I/O
  • a short period of time
• OS tasks
  • virtual memory
  • file system & disk management
  • process synchronization & deadlock

Mainframe System Summary

Computer-System Architecture

Desktop Systems: single processor

personal computers

Parallel Systems: multiprocessor (tightly coupled)

• usually communicate through shared memory
  • 有 shared memory，用 hardware 的方式把它們連起來

Processor 角度

1. Multi-Core Processor
   
2. Many-Core Processor

Memory 角度

1. Uniform Memory Access (UMA)
   
   • 所有CPU都用同樣的方式接到memory
   • memory access time 都一樣
   • 最適合SMP
2. Non-Uniform Memory Access (NUMA)
   
   • 每塊 memory 就像是 local memory，其他是 remote memory
   • 當CPU想要access其他塊的memory時，需先跟別人的controller溝通 (間接)
   • 較大的電腦用 (多CPU)
   • local memory比較快，remote memory比較慢

Symmetric Multiprocessor System (SMP)

• each processor runs the same OS
• most popular

Asymmetric Multiprocessor System (AMP)

• each processor is assigned a specific task
• one master CPU & multiple slave CPUs
• more common in extremely large systems

Distributed Systems: loosely coupled

• each processor has its own local memory (沒有share memory -> 獨立)
• resource sharing
• load sharing

Client-Server Distributed System

• easier to manage and control resources
• server becomes the bottleneck and single failure point

Peer-to-Peer Distributed System

• every machine is identical -> decentralized

Clustered Systems

• cluster computers share storage and are closely linked via a local area network (LAN) or a faster interconnect
• Asymmetric vs. Symmetric Clustering
  • asymmetric clustering: one server runs the application while other servers standby
  • symmetric clustering: two or more hosts are running application and are monitoring each other

System Architecture Summary

Special-Purpose Systems

Real-Time Operating Systems

• 在 deadline 之前做完就好ㄌ (跟名字 real-time 相反)
  • deadline: guaranteed response and reaction times
• Soft vs. Hard Real-Time
  • Soft real-time requirements: 盡量完成deadline，沒完成也不會怎樣 (根據priorty)
    • ex. multimedia streaming (先跑出來框框，再跑出來影片…)
  • Hard real-time requirements: 沒完成會有嚴峻的懲罰
    • 通常沒有 secondary storage (memory以外的storage)

Multimedia Systems

audio and video files

Handheld/Embedded Systems

mobile device

大總結

Ch1 Introduction

What is OS?

Computer System

four components:

• User: 人、機器、其他computer
• Application: 定義系統資源用於解決計算問題的方式
• OS: 控制(control) 和 協調(coordinate) hardware/資源的使用
• Hardware: 提供基本計算資源(e.g. CPU、內存、I/O設備)

What is an Operating System?

An OS system is the permanent(永恆的) software that controls/abstracts hardware resources for user applications.

Provides Applications Programming Interface (API) for user applications

General-Purpose OS

• system library(定義很多的function，package在一起) -> API

OS的定義

• 資源分配器: 管理和分配資源以確保效率和公平
• 控製程序: 控制user program的執行和I/O設備的操作，防止computer出錯和不當使用
• 內核Kernel(kernel就是OS): 一直運行的一個程序(其他都是系統/應用程序)

OS的目標

• 方便(使computer system易於使用和計算，適用於小型PC)
• 效率(有效率使用電腦硬體，適用於大型、共享、多用戶系統)

OS的重要性

• system API是user application和hardware間的唯一介面
• OS code不能有bug(任何中斷（例如無效訪問）就要重開)
• OS和computer architecture會相互影響

Computer-System Organization

• 一或多個CPU和device controller透過common bus連接，share memory。
  
  
• 運作方式:
  • 每個device controller都有一個local buffers
  • status/data register -> 因為有讀&寫
  • I/O是從device到device controller的local buffers
  • CPU將數據從內存移動到device controller的local buffers
    
    

I/O的操作有兩種:

• Busy/wait output
  CPU不斷監控等待I/O，但是CPU在監控device時不能做其他工作，很難同時進行其他I/O。
• Interrupt I/O
  Interrupt允許device改變CPU的控制流，透過改變CPU的控制流在I/O與user process間切換。

Interrupt

• Interrupt-Driven I/O

  • timeline
    

    
    1和2的藍線:
    1. I/O的buffer填滿資料 (1)
    2. I/O發出interrupt
    3. I/O把資料丟到CPU的memory (2)

  • 

• signal by an interrupt from
  • hardware (signal): 可以隨時通過向 CPU 發送信號signal來觸發中斷
    
    
  • software (trap): 可能會因 error 或user對OS service的request (system call) 而觸發中斷
    
    
• common function
  • interrupt一般通過 interrupt vector (含所有service routine的address(function pointer))，將控制轉移到interrupt service routine (ISR，中斷處理程式)
  • 必須記錄被中斷指令的address
  • 在處理一個interrupt時，禁止傳入其他interrupt，以防 lost interrupt

Storage-Device Hierarchy

• memory
  • main memory: CPU唯一一個可以直接訪問的大型storage (ex. RAM)
  • secondary storage: main memory的extension，提供大容量的非揮發性storage (ex. 磁碟magnetic disk)
• Disk Mechanism
  
  
  • 旋轉磁盤，並透過磁頭去去讀取(寫入)磁盤資料
  • transfer time = data size / transfer rate
    (傳輸時間 = data大小 / 傳輸速度)
  • positioning time (random access time) = seek time (cylinder) + rotational latency (sector)
    (seek time: 找資料的時間)
• caching
  • 使用中的資料暫時從較慢的存儲，複製到較快的存儲
    
    
  • coherency(連貫性) and consistency(一致性) issue
    • 更改register中的copy，使其與其他copy不一致
    • single task accessing：使用highest level的copy
    • multi-task accessing：需要獲取recent的值
      
      
    • distributed system：difficult, because copies are on different computers

Hardware Protection

Dual-Mode Operation

• shared system resources需要OS保證不正確的程序不會導致其他程序錯誤執行
• 提供hardware support以區分至少兩種操作模式(最基本的)
  • user mode: 來自使用者 (OS以外的動作)
  • monitor mode(kernel mode): OS送出來的instruction
• 在hardware中加入mode bit以指定當前模式
  • 0: kernel
  • 1: user
• 當interrupt/trap或故障發生時，hardware會切換到monitor mode
  (system call (interrupt) -> 執行OS的程式碼)
  
  
• privileged(特權) instructions
  • 必須在monitor mode才能執行
  • 使用者只能透過system call才能動作

I/O Protection

• 所有I/O instructions 都是 privileged instructions
  (因為都是shared)

Memory Protection

• 保護interrupt vector和interrupt service routines、data access，避免被其他program over-write
• HW support: 超出定義範圍的內存受到保護
  
  
  
  
  看有沒有在 (base) register~(base+limit) register 的範圍內
  • base register: 保存最小的合法physical memory address
  • limit register: 包含範圍的大小

CPU Protection

• 避免user program霸佔CPU，不給OS用
  ex. 寫了一個無限迴圈，還是可以按ctrl+c暫停執行程式碼
• HW support - timer
  • 在指定時間後interrupts computer
  • 經過一個clock就遞減
  • 當timer=0，就interrupt
  • 用於實現time sharing
  • load-timer(load: load到HW register，override目前的設定) 是一個privileged instruction

Ch2 System Structures

OS Services

User Interface

• CLI (Command Line Interface)
  • 獲取user的指令並執行
  • shell: command-line interpreter
    • ex. CSHELL, BASH
• GUI (Graphic User Interface)
  • usually mouse, keyboard, and monitor
  • icon代表文件、programs、actions等
• CLI和GUI的目的相同

Communication Models

communication 分成兩大類:

• message passing
  
  
  1. process A 把資料 copy 到 OS 的 memory
  2. process B 從 OS 把資料 copy 到自己這邊
  • 為何不能直接 A copy 到 B?
    • protection
• shared memory
  
  
  • 如果要有 shared memory，要先跟 OS 講，透過 system call 建一個 shared memory

Applications-OS Interface

System Calls

• OS唯一的interface
• 通過software interrupt向kernel發出的request
• 通常用組合語言
• passing parameters
  • registers
  • pointer: store the parameters in a table in memory, and the table address is passed as a parameter in a register
  • push (store) the parameters onto the stack by the program, and pop off the stack by operating system

API (Application Program Interface)

• user通常針對API寫程式，而非system call (API比system call方便)
• 通常由language libraries實現，例如 C Library (libc)
• 一個API的function call可能需要多個(或0個)system call來完成它
• why use API?
  • 簡單
  • 可移植性 (API是統一定義的interface)
  • 效率 (並非所有功能都需要OS services或涉及kernel)

System Structure

Simple OS Architecture

• only one or two levels of code
• 缺點: 不安全、難改善
• ex. 只有最上面那兩層是OS
  
  

Layered OS Architecture

• 下層獨立於上層 (第N層只能訪問第0~(N-1)層提供的服務)
  外層可以call內層，內層不能call外層
  
  
• 優點: 好debug、維護
• 缺點: 效率較差、難定義層

Microkernel OS

• microkernel的上面都算是user space
  
  $\to$ kernel程式碼越少越好 (user space東西越多越好)
• 透過message passing
• 優點: 容易擴展和移植
• 缺點: 效能差 (所有的動作都要再透過kernel)

Modular OS Structure

• 現代大多數ㄉOS都有用kernel modules
• 跟microkernel OS的差別: 全部都在kernel space
• 用到object-oriented的概念
• 每個core component都是獨立的
• 每個module都通過已知interface與其他module溝通

Virtual Machine

• 它把hardware和operating system kernel都視為hardware
• VM執行在user space
  
  $\to$ critical instruction (user space和kernel space執行的結果不一樣) 難處理
  
  $\to$ 當遇到無效的instruction 時，會透過 interrupt 去call底層的 kernel space 執行

Java Virtual Machine (JVM) (就是Java)

• 已編譯的Java程式是由JVM執行與平台無關的bytecodes
• Just-In-Time(JIT)編譯器可提高性能

PART 2 Process Management

Ch3 Process Concept

Process Concept

• Program vs. Process
  • Program:
    • 被動ㄉentity
    • 只是存在disk上，等著被執行的binary file (就4程式碼)
  • Process:
    • 主動ㄉentity
    • 在memory裡面
    • 正在執行
• a process include
  • code segment (text section)
  • data section: global variables
  • stack: temporary local variables and functions (方便使用後直接pop掉)
  • heap: dynamic allocated variables or classes
  • current activity (program counter, register contents): 管理process的meta data
  • a set of associated resources (ex. open file handlers，(檔案的開啟、或是跟OS要某些硬體的控制權)): 相關資源的set
• process in memory
  
  
  stack和heap的大小會變化

Threads

• a.k.a lightweight process，使用CPU的最小單位
  (一個process可以切成很多個threads)

• 同process的threads會共用
  • code section
  • data section
  • OS resources (e.g. open files & signals)
• 但以下部份各自獨立
  • stack
  • register set
  • thread ID
  • program counter

Process State

• new
  • process被創建出來
  • 把program load到memory，並將前述記憶體狀態初始化
• ready
  • process在memory中等待被指派到哪個processor(CPU核心)
  • 在等待被執行的階段，會被放在queue當中
• running
  • instruction可以被CPU執行ㄌ
  • running
    $\to$ ready: 為了把主控權還給OS，一段時間(timer)就會interrupt(hardware signal)，把CPU switch給OS scheduler
• waiting
  • 目前不需要CPU，等其他動作做完才需要，如I/O，完成後再重新放回Ready state
• terminated
  • 把資源release掉 (還給OS)

Process Control Block (PCB)

記錄process的狀態

當一個process建立時，OS會allocate一個table

• process state
• program counter
• CPU registers
• CPU scheduling information (ex. priority)
• memory management information (ex. base/limit register): 只有process在執行時才會把這兩個值從memory load進CPU的register
• I/O status/information
• accounting information

Context Switch

圖中有兩個context switch
0.

$P_0$ 正在執行

1. interrupt或system call打斷process
2. 把
   $P_0$ 在CPU的state存起來
3. 讀取
   $P_1$ 的state
4. $P_1$ 執行

• context switch的過程中，
  
  $\because$ CPU沒有執行任何instrunction，且都會有process idle
  
  $\therefore$ context switch 其實是overhead，浪費CPU的資源

Process Scheduling

Process Scheduling Queues

• job queue (New State): 系統中所有的 Process
• ready queue (Ready State): 在main memory中正在及等待執行的process
• device queue (Wait State): 等待event處理(ex.I/O)的process

• queue之間的tail和head會串起來

• ready queue 中的 process 會等待被 load 進 CPU
• wait queue發生的原因
  • I/O request (自己發出I/O request)
  • time slice expired (time sharing)
  • fork a child (create process)
  • wait for an interrupt

Schedulers (8A先跳過)

Operations on Processes

Tree of Processes

• 每個 process 都會有自己的 unique 的 ID (processor identifier (pid))
• processes 一定可以畫成如下的樹狀結構
  
  

Process Creation

• 資源之間的關聯性可能如下
  • Process 的 Parent 及 Child (完全)共享資源
  • Child Process 共享部份 Parent 的資源
  • Parent 及 Child 完全不分享資訊
• 兩種可能的執行方式
  • Parent 及 Children 同時執行
  • Parent 等到 Children 結束後才執行 (wating queue)
• 兩種可能的記憶體空間
  • Child 為 Parent 的複製 (執行碼、counter 等與 Parent 完全一樣)，透過 sharing variable 溝通 (address 不同)
    • 行為、內容物完全一樣，memory addr. 不一樣
  • 將特定的 program 丟進 Child 的 code section，重設 counter，讓 Child 變成完全不同狀態的 Process，透過 message passing 溝通

UNIX/Linux Process Creation

• fork system call
  • create new child process
  • duplicate its parent (完全複製、完全一模一樣)
  • concurrent execution (沒有先後順序 (不用等))
  • child: return value of fork is 0
  • parent: return value of fork is PID of the child process
  • memory space of fork()
    
    
    (中fork跟右execlp比較)
    • copy-on-wirte技術: runtime時發現值改變，儲存 Child 的與 Parent 的不同處 (child 在執行過程中會慢慢增長)
    • fork會比較省空間
• execlp system call
  • load a new binary file into memory (reset)
    
    $\to$ 等於 new child process 在執行完全不同的程式
• wait system call
  • parent waits for one of its child processes
    
    $\to$ 強迫 parent 放到 waiting queue

範例:

Process Termination

• exit()
• 把資源還給OS (deallocation)
• parent 可利用 PID(abort) 來中止特定 child process
• cascading termination: killing parent
  $\to$ killing all its children

Interprocess Communication (IPC)

• 定義: 在多個 processes / threads 間 (內部) 溝通的機制

Communication Methods

[Ch2 System Structures - OS Services - Communication Models]

• shared memory
  • 共用記憶體空間
  • 透過 memory 的 address 存取資料
  • 優點: 快
  • 缺點: synchronization
  • Consumer & Producer Problem
    • producer 負責產生information，
      consumer 負責消耗這些數據
    • 
      • buffer 是大小為 B (有限空間) 的 circular array
      • next free: in
      • first available: out
      • empty: in = out (out 拿光)
      • full: (in + 1) % B = out (buffer 放滿了)
      • 為了 sync，避免無法判斷 in = out 時是 empty 還是 full，必須使用 in+1 留一個空格
• message passing
  • 透過 memory 的 copy，網路或跨電腦的程式通常都是以這種作法溝通
  • 使用 send/recv message
  • 優點: 沒有 conflict 的問題
  • 缺點: 慢 (
    $\because$ 使用 system call)
  • 藉由 Send/Receive 交換資訊
  • communication link (這邊只寫logical，懶惰打physical)
    • Direct or indirect
      • direct
        $\to$ 打電話
        • 指定要溝通的人是誰
        • send(P, message) / receive(Q, message)
      • indirect
        $\to$ 寄email
        • 不會直接寄到別人手上 (mailbox (底下的A))
        • send(A, message) / receive(A, message)
    • Synchronous or asynchronous
      • blocking (synchronous)
        • blocking send / receive: 很明顯就是會等 message 送完才會繼續送 / return message
      • non-blocking (asynchronous)
        • non-blocking send / recieve: 很明顯就是不管怎樣都會馬上送 / return message
      • buffer implementation
        
        
    • Automatic or explicit buffering
• socket
  
  
  • 透過 IP & Port 來 identify 使用者，port number 指的就是 process
  • 藉由 unstructed stream of bytes 來溝通 (low level)(傳訊息)
• Remote Procedure Calls (RPC)
  
  
  • 可以呼叫其他的 process 甚至其他電腦的 process
  • 參數以及回傳值以 message 傳遞
  • 我累了，我要放棄這個東西了 ;)

Ch4 Multithreaded Programming

Ch5 Process Scheduling

PART 3 Process Coordination

Ch6 Synchronization

Ch7 Deadlocks

PART 4 Memory Management

Ch8 Memory-Management Strategies

Ch9 Virtual-Memory Management

PART 5 Storage Management

Ch10 File System

Ch11 Implementing File Systems

Ch12 Mass Storage Structure

Ch13 I/O Systems