# 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
![](https://i.imgur.com/FPOmVzu.png)
* 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
![](https://i.imgur.com/sJeNdOH.png)
* 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
![](https://i.imgur.com/E7EssFk.png)
* 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
![](https://i.imgur.com/B48Vm5A.png)
### 電腦系統架構(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):目前常見,每個處理器同等
![](https://i.imgur.com/B6RPerw.png)
* 多元處理可以讓一個系統以下面兩種方式改變它的記憶體存取模式
* 一致(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):允許系統連接儲存單位
![](https://i.imgur.com/9zyOdvP.png)
### 作業系統結構(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
![](https://i.imgur.com/pn3k1Pz.png)
* 可以擴展到超過兩個模式
* 虛擬機器管理程式(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和暫存器間通常是硬體功能,沒有作業系統介入
* 主記憶體可視為輔助記憶體的快取
![](https://i.imgur.com/ZtbDhyK.png)
* 在多處理器的環境下,每個CPU包含一個快取,必須確保一個快取的更新,能立即反映到其他快取上,導致有快取記憶體(cache coherency)一致性的問題
* A從磁碟到暫存器的過程
![](https://i.imgur.com/yrD4G0a.png)
* 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):每一項指向它的下一項
![](https://i.imgur.com/SrcwC7a.png)
* 雙向鍊接串列(doubly linked list):每一項指向它的前一項和下一項
![](https://i.imgur.com/EEEgX3K.png)
* 環狀鍊接串列(circularly linked list):最後一項指向第一項
![](https://i.imgur.com/d3RjH0y.png)
* 堆疊(stack):後進先出(LIFO,last in first out)
![](https://i.imgur.com/ePil8M4.png)
* 佇列(queue):先進先出(FIFO,first in first out)
![](https://i.imgur.com/DS3b0NE.png)
* 樹(tree):
* 二元樹(binary tree):1個父節點至多有2個子節點
* 二元搜尋樹(binary search tree):額外要求所有左子節點<右子節點
![](https://i.imgur.com/krRIP9V.png)
* 平衡的二元搜尋樹(Balanced binary search tree):每棵子樹中的左子樹和右子樹的深度差不能超過1
![](https://i.imgur.com/A1WMy9K.png)
![](https://i.imgur.com/bD2x6UL.png)
* 雜湊函數(hash function)和對映(hash map):
* 雜湊函數(hash function):將資料當成輸入,對資料執行數值運算,然後回傳一個值
* 雜湊函數在最糟的情況可以好到O(1),因此廣泛的運用在作業系統
* 雜湊對映(hash map):使用一個雜湊函數將key、value組成關聯
![](https://i.imgur.com/IwJOhYG.png)
* 位元對映(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)所產生的要求
![](https://i.imgur.com/Xoa99qI.png)
* 運算伺服器系統(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
![](https://i.imgur.com/5ybqMkN.png)
* 雲端運算(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
![](https://i.imgur.com/apMCRsp.png)
* 即時嵌入系統(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):自由軟體基金會"著佐權",是自由軟體發行的共用版權