# OS筆記-Chapter 1: Introduction

###### tags: `OS`
---
#### 目錄
* 總論
<font color="red">Chapter 1: Introduction</font>
[Chapter 2: Operating-System Structures](https://hackmd.io/OKykRLBESI6v9a13HgS35A)
* 行程管理
[Chapter 3: Processes](https://hackmd.io/HOqN-iQ3RIKIC-NB9QjBIQ)
[Chapter 4: Threads](https://hackmd.io/qzAIHeSASmKuecdkqidmHw)
[Chapter 5: CPU Scheduling](https://hackmd.io/IT5g2wHzTdOtMSDXPVEpOw)
[Chapter 6: Process Synchronization](https://hackmd.io/rv-PNe3ESxi08PElyUTc4Q)
[Chapter 7: Deadlocks](https://hackmd.io/Uu0jDK-rSyKNKq690y146g)
* 記憶體管理
[Chapter 8: Main Memory](https://hackmd.io/4KS_yPkBQzGZfHDisPciog)
[Chapter 9: Virtual Memory](https://hackmd.io/yirxZFn8Rz2wT56AAR7Sxw)
* 儲存裝置
[Chapter 10: File-System Interface](https://hackmd.io/aNPWKsFhTlGc-WFgQ__KRg)
[Chapter 11: File System Implementation](https://hackmd.io/bFcrlmefQsGp6hZdbI1MHQ)
[Chapter 12: Mass-Storage Systems](https://hackmd.io/9Y7Qo0OERda6htK7OOI36Q)
[Chapter 13: I/O Systems](https://hackmd.io/VNwXrhJPSo-l_t9tUBhYIg)
* 保護和安全
[Chapter 14: Protection](https://hackmd.io/izkd4JwXRwub_ZmhSMTlNw)
[Chapter 15: Security](https://hackmd.io/ofyvDidvQf-PxLMMZYhtsg)
---

### 什麼是作業系統(Operating System)
* A program that acts as an intermediary between a user of a computer and the computer hardware

* Operating system goals:
* Make the computer system convenient to use(方便)
* Use the computer hardware in an efficient manner(效率)

* 電腦系統大致上能分為四個單元：
* 硬體(Hardware)： provides basic computing resources
* 作業系統(Operating System)：Controls and coordinates use of hardware among various applications and users
* 應用程式(Application programs)：define the ways in which the system resources are used to solve the computing problems of the users
* 使用者(Users)：People, machines, other computers

* What Operating Systems Do：
* 使用者觀點：
* ease of use, do not care about resource utilization
* 若是使用大型主機(mainframe)或迷你電腦(minicomputer)，則被設計發揮資源使用的最大效用，確保所有使用者的使用
* Users of dedicate systems such as workstations(工作站) have dedicated resources but frequently use shared resources from servers(伺服器)
* 系統觀點：
* 資源分配者(resource allocator)：Manages all resources and decides between conflicting requests for efficient and fair resource use
* 是一套控制程式(control program)：Controls execution of programs to prevent errors and improper use of the computer

* Operating System Definition：
* 作業系統是一個電腦內部隨時都在執行的程式："The one program running at all times on the computer" is the kernel.
* 行動作業軟體通常除了包含核心外，還包含中介軟體(middleware)

### 電腦系統組織(Computer System Organization)
* Computer-system operation：
* One or more CPUs, device controllers connect through common bus providing access to shared memory
* Concurrent execution of CPUs and devices competing for memory cycles

* Computer Startup：
* 靴帶式程式(bootstrap program)：存在唯讀記憶體(ROM,read-only memory)或EEPROM(electrically erasable programmable read-only memory)，通常稱為韌體(firmware)
* 靴帶式程式必須知道如何載入作業系統和使作業系統開始執行
* 有些服務在核心(kernel)外提供，由啟動時載入記憶體的系統程式，或是在核心執行時會一直執行的系統守護程式(system process、system daemon)提供

* Common Functions of Interrupts
* 發生一個事件時：Device controller informs CPU by causing an interrupt(中斷)
* 硬體可以藉由系統匯流排，送給CPU一個信號觸發中斷(interrupt)，軟體可以藉由執行系統呼叫(system call)來觸發中斷
* 中斷向量(interrupt vector)這個陣列提供產生中斷服務常式的位置：which contains the addresses of all the service routines
* Interrupt architecture must save the address of the interrupted instruction
* A trap(陷阱) or exception(例外) is a software-generated interrupt caused either by an error or a user request
* An operating system is interrupt driven

* I/O Structure：
* 同步：
* After I/O starts, control returns to user program only upon I/O completion
* Wait instruction idles the CPU until the next interrupt
* Wait loop (contention for memory access)
* At most one I/O request is outstanding at a time, no simultaneous I/O processing
* 非同步：
* After I/O starts, control returns to user program without waiting for I/O completion
* System call(系統呼叫)：request to the OS to allow user to wait for I/O completion
* Device-status table()：contains entry for each I/O device indicating its type, address, and state
* OS indexes into I/O device table to determine device status and to modify table entry to include interrupt
* 基本上作業系統在每個裝置上都有裝置驅動程式(device driver)
* 直接記憶體存取(DMA,direct memory access)：Used for high-speed I/O devices able to transmit information at close to memory speeds

* Storage Structure：
* 主記憶體(main memory)：only large storage media that the CPU can access directly
* 以動態隨機存取記憶體(DRAM,dynamic random-access memory)製成
* Typically volatile(揮發性)
* 輔助記憶體(Secondary storage)：extension of main memory that provides large nonvolatile storage capacity
* 最常見的為磁碟(Magnetic disks)：
* Disk surface is logically divided into tracks, which are subdivided into sectors
* The disk controller determines the logical interaction between the device and the computer
* 固態硬碟(ssd,Solid-state disks)：faster than magnetic disks, nonvolatile

* 快取(Cache)：copying information into faster storage system; main memory can be viewed as a cache for secondary storage
* Storage-Device Hierarchy：
* Speed
* Cost
* Volatility

### 電腦系統架構(Computer-System Architecture)

* 單一處理器系統(single processor systems)：Most systems use a single general-purpose processor

* 多處理器系統(Multiprocessors systems)：growing in use and importance
* Also known as parallel systems(平行系統), tightly-coupled systems(緊密耦合系統)
* 優點:
* Increased throughput：處理器為N時，提升速度小於N
* Economy of scale：處理器共用周邊設備
* Increased reliability ： 10台壞掉1台，還有9台能算，速度降低，並不會完全失效
*　持續提供服務的能力與尚存硬體的程度成正比，就稱為適度降級(graceful degradation)
* 有些系統能容忍任一元件失誤而持續作業，而被稱為容錯(fault tolerance)
* Two types:
* 非對稱多元處理(Asymmetric Multiprocessing)：一個主處理器控制系統，而其他的則注意主處理器的指令或已有預定的任務，主-從關係
* 對稱多元處理(SMP,Symmetric Multiprocessing)：目前常見，每個處理器同等
* 多元處理可以讓一個系統以下面兩種方式改變它的記憶體存取模式
* 一致(UMA,uniform memory access)
* 非一致(NUMA,non-uniform memory access)
* 多核心(multicore)指一個晶片上包含許多運算核心：多核心一定是多處理器系統，但多處理器系統不一定是多核心
* 刀鋒伺服器(blade server)：基座上可插置多張處理板，因狀似刀片（Blade），因此稱之為刀鋒伺服器，每個處理板獨立啟動

* 叢集式系統(Clustered Systems)
* 由兩個或多個個別系統連結在一起所組成，這種系統被認為是鬆散連結(loosely coupled)
* Provides a high-availability service which survives failures
* Two types:
* 非對稱叢集系統(Asymmetric clustering)：一台機器處於熱待機狀態(hot-standby mode)，熱待機的機器沒有做任何事，它只是監督工作，如果工作伺服器壞了，熱待機的機器就會變成工作伺服器
* 對稱叢集系統(Symmetric clustering)：多台執行，互相監督
* Some clusters are for 高效能運算(HPC,high-performance computing)
* Applications must be written to use parallelization(並行)

* 分散式上鎖管理者(DLM,distributed lock manager)：確保對於資料的存取不會發生衝突
* 儲存區域網路(SAN,storage-area network)：允許系統連接儲存單位

### 作業系統結構(Operating System Structure)

* 多元程式規劃(Multiprogramming)：讓CPU始終有工作做，增加效率
* A subset of total jobs in system is kept in memory
* 通常main memory太小，不能存所有工作，所以所有工作存在磁碟的工作池(job pool)
* One job selected and run via job scheduling(工作排班)

* 分時(Timesharing)或多工 (multitasking)：
* CPU頻繁地切換來執行許多工作
* 交談式(interactive)系統提供使用者與系統間的直接交談
* Response time(反應時間) should be < 1 second
* CPU排班(CPU scheduling)：If several jobs ready to run at the same time
* If processes do not fit in memory, swapping(置換) moves them in and out to run
* 虛擬記憶體(Virtual memory)：allows execution of processes not completely in memory

### 作業系統的操作(Operating-System Operations)

* 中斷驅動式(interrupt driven)
* interrupt driven by hardware
* Software error or request creates exception or trap

* 雙模式運作(Dual-mode)：
* 確保作業系統正常操作
* 模式位元(Mode bit)將加到電腦硬體之中，以便指出目前的模式(0 or 1)
* 使用者模式(user mode)、核心模式(kernel mode)
* 特權指令(privileged instruction)：only executable in kernel mode
* 可以擴展到超過兩個模式
* 虛擬機器管理程式(VMM,virtual machine manager)通常有一個獨立的模式

* 計時器(timer)：
* 使用計時器設定在某段時間之後中斷，確保使用者程式不會有無窮迴路的狀況
* 可變的計時器(variable timer)：使用一個固定時脈的計時器與一個計數器做成，設定計數器次數，每次時間到，計數器減一
* 更改計時器的動作屬於特權指令(privileged instruction)

### 行程管理(Process Management)

* Process(行程) v.s. Program(程式)
* A process is a program in execution.
* Program is a passive entity, process is an active entity.
* Process needs resources to accomplish its task
* Process termination requires reclaim of resources
* 藉由輪流使用CPU而能同時執行行程

* 程式計數器(program counter)：
* 指定下一個等待執行的指令
* 行程的執行是循序的
* 多執行緒(multithreading)有多個program counter

* 在行程管理方面，作業系統必需負責：
* CPU排班行程與執行緒
* 使用者和系統行程的產生與刪除
* 行程的暫停與恢復機制
* 提供行程同步的機制
* 提供行程通信的機制

### 主記憶體管理(Memory Management)

* 主記憶體通常是CPU唯一能直接定址和存取的儲存裝置

* 主記憶體管理的方法，可以改善CPU使用率與電腦對使用者的回應速度

* 在主記憶體管理方面，作業系統必需負責：
* 紀錄正在使用的記憶體部分，以及使用者
* 決定哪些資料要移入或移出記憶體空間
* 在需要時配置和回收記憶體空間

### 儲存體管理(Storage Management)

* 作業系統轉移儲存裝置的實體特性定義成邏輯儲存單元，也就是檔案(file)

* 檔案系統管理(File-System management)：
* Files usually organized into directories(目錄)
* Access control on most systems to determine who can access what
* 在檔案管理方面，作業系統必需負責：
* 建立與刪除檔案
* 建立與刪除目錄
* 作為處理檔案與目錄的原始支援
* 對應檔案到輔助記憶體
* 備份檔案到穩定(非揮發性)儲存裝置上

* 大量儲存體管理(Mass-Storage Management)：
* Usually disks(磁碟) used to store data
* 在磁碟管理方面，作業系統必需負責：
* 可用空間管理
* 記憶體配置
* 磁碟排班
* 第三儲存體(Tertiary storage)：磁帶、光碟
* 媒體格式介於WORM(write-once,read-many-times)和RW(read-write)之間

* 快取(caching)
* 較快速的儲存系統，當我們需要資訊時，應該先檢查該資訊是否在快取記憶體中
* 資料從快取記憶體送到CPU和暫存器間通常是硬體功能，沒有作業系統介入
* 主記憶體可視為輔助記憶體的快取
* 在多處理器的環境下，每個CPU包含一個快取，必須確保一個快取的更新，能立即反映到其他快取上，導致有快取記憶體(cache coherency)一致性的問題

* A從磁碟到暫存器的過程

* I/O系統
* 作業系統的目的之一是對使用者隱藏特定硬體裝置的性質，例如：UNIX中，I/O裝置的特點由作業系統的I/O子系統隱藏，只有裝置驅動程式知道特定裝置之性質
* I/O子系統(I/O subsystem)包含：
* 包括緩衝、快取和連線同時周邊作業的記憶體管理元件
* 通用裝置驅動程式介面
* 特定硬體裝置驅動程式

### 保護與安全(Protection and Security)

* 保護(protection)：控制行程或使用者存取電腦系統之定義資源的機制

* 安全(security)：系統對於內部和外部攻擊的防禦

* 保護與安全需要系統能區別它的所有使用者
* 使用者識別符號(user ID,user identifier)：以windows來說，就是安全性識別碼(SID,security ID)，每個使用者有一個唯一的ID
* 群組識別符號(group ID)：在UNIX系統中，每個群組有不同操作權限，一個使用者可以在一個或多個群組
* 提升權限(escalate privilege)：UNIX系統中，"setuid"屬性是讓程式以檔案擁有者的ID來執行，而非目前的使用者，行程以有效使用者識別符號(effective UID)執行

### 核心資料結構(Kernel Data Structures)

* 陣列中每一項元素能直接存取，串列中必須按照特定順序存取

* 鍊接串列(linked list)：
* 單向鍊接串列(singly linked list)：每一項指向它的下一項
* 雙向鍊接串列(doubly linked list)：每一項指向它的前一項和下一項
* 環狀鍊接串列(circularly linked list)：最後一項指向第一項

* 堆疊(stack)：後進先出(LIFO,last in first out)

* 佇列(queue)：先進先出(FIFO,first in first out)

* 樹(tree)：
* 二元樹(binary tree)：1個父節點至多有2個子節點
* 二元搜尋樹(binary search tree)：額外要求所有左子節點<右子節點
* 平衡的二元搜尋樹(Balanced binary search tree)：每棵子樹中的左子樹和右子樹的深度差不能超過1

* 雜湊函數(hash function)和對映(hash map)：
* 雜湊函數(hash function)：將資料當成輸入，對資料執行數值運算，然後回傳一個值
* 雜湊函數在最糟的情況可以好到O(1)，因此廣泛的運用在作業系統
* 雜湊對映(hash map)：使用一個雜湊函數將key、value組成關聯

* 位元對映(bitmap)：n位元的二進位數字表示n個項目的狀態
* 例如：001011101，表示資源2、4、5、6、8無法使用

### 運算環境

* 傳統運算
* Portals(入口網站) provide web access to internal systems
* Network computers(thin clients,網路電腦) are like Web terminals
* 行動裝置經由無線網路(wireless network)存取內部網路資源
* 使用防火牆(firewall)保護網路安全

* 行動運算(mobile computing)
* Leaders are Apple iOS and Google Android
* Allows new types of apps like augmented reality(AR,擴增實境)

* 分散系統(Distributed system)
* 一組實體上分開的電腦系統，以網路連結的集合
* 網路(network)是通信路徑，TCP/IP是最普遍的協定
* 區域網路(LAN,Local Area Network)：連接在一個房間，一層樓或一棟建築內的電腦
* 廣域網路(WAN,Wide Area Network)：連接建築物、城市、或國家
* 都會網路(MAN,Metropolitan Area Network)：連結城市內的建築物
* 個人區域網路(PAN,Personal Area Network)：在智慧型手機與桌上型電腦與耳機間
* 網路作業系統(Network Operating System)：
* 提供不同系統上交換訊息的通訊技巧
* 不同電腦緊密的通信，以提供只有一個作業系統控制網路的錯覺

* 客戶-伺服器系統(Client-Server)
* 伺服系統(server system)：滿足客戶系統(client system)所產生的要求
* 運算伺服器系統(Compute-server system)：provides an interface to client to request services
* 檔案伺服器系統(File-server system)：provides interface for clients to store and retrieve files

* 對等式運算(P2P,Peer-to-Peer)
* P2P does not distinguish clients and servers
* each act as client, server or both
* 搜尋協定(discovery protocol)：Broadcast request for service and respond to requests for service
* Skype uses 基於IP的語音傳輸(VoIP,Voice over IP)

* 虛擬化(Virtualization)
* Allows operating systems to run applications within other OSes
* 模擬(emulation)：被用在當原是CPU型態和目的CPU型態不同時
* 直譯(Interpretation)：模擬常發生的情況，當電腦語言沒被編譯成原始碼，這稱為直譯
* host OS(主作業系統)：跑虛擬機器管理程式(VMM,Virtual Machine Manager)的主機上的系統
* 虛擬機器管理程式(VMM,irtual Machine Manager) provides virtualization services

* 雲端運算(Cloud Computing)：
* 亞馬遜彈性計算雲(Amazon Elastic Compute Cloud,EC2)：提供伺服器給使用者在網路上使用運算
* 公用雲(Public cloud)：經由網路給任何願意為此服務付費者取得的雲
* 私有雲(Private cloud)：由公司經營，給公司自己使用的雲
* 混合雲(Hybrid cloud)：包含功用與私有雲的雲
* 軟體即服務(SasS,Software as a Service)：經由網路取得一個或更多應用，例如：文書處理程式
* 平台即服務(PaaS,Platform as a Service)：經由網路準備給應用程式使用的軟體堆疊，例如：資料庫
* 基礎設施即服務(IaaS,Infrastructure as a Service)：在網路可取得的伺服器或儲存體，例如：可作為資料備份的儲存體
* Load balancers(負載平衡) spread traffic across multiple applications
* Internet connectivity requires security like firewalls

* 即時嵌入系統(Real-Time Embedded Systems)：
* 幾乎執行即時作業系統(real-time OS)
* 另外有使用特殊應用積體電路(applocation-specific integrated circuit,ASICs)的硬體裝置，在沒有作業系統下完成工作
* 即時作業系統(real-time OS)具有明確的固定時間限制
* Processing must be done within constraint
* Correct operation only if constraints met

### 開放原始碼作業系統(Open-Source Operating Systems)
* 可取得原始碼格式，而非只有編譯過的二元碼，例如：LINUX
* 封閉原始碼(closed-source)，不可取得原始碼格式，例如：Windows
* 開放原始碼的版權保護(copy protection)與數位版權管理(DRM,Digital Rights Management)將不會有效
* 自由軟體基金會(FSF,Free Software Foundation)
* 通用授權碼(GPL,GNU Public License)：自由軟體基金會"著佐權"，是自由軟體發行的共用版權