2017/10/17 AndyLee
Batch Processing System:將同類的工作集合起來一起執行,以減少重複且瑣碎的動作,並減少工作切換的時間,以提升系統效率。
Interactive system:在terminal的使用者送出指令後,系統必須立即作出回應,並將結果送回使用者的系統。
Timesharing System:利用CPU scheduling 和multiprogramming技術將一份程式分配一個time quantum,即使沒有執行完,時間一到還是要交出控制權給其他使用者。
Multiprocessing System:(Tightly Coupled的多處理機系統)
Distributed System:(Loosely Coupled的多處理機系統)
Real-time System:
通常用在專業應用系統,必須在有限的時間內作出正確的反應。
主要特徵:處理程序必須儲存在memory中,在限時內作出的反應必須是精確且準時的
系統必須支援"Priority scheduling",real-time之process必須具有最高的priority,且不隨時間改變
由於page fault會造成不可預期的延遲,故不採用virtual memory
Hard real-time system:考慮某些工作在限期內完成具有很高的價值,反之則毫無用處,而用戶也願意付出較高的費用。
Soft real-time system:使用priority scheduling,重要的工作priority較高,且priority是固定的,不隨時間而改變。
Monolithic system:
優點:
缺點:overhead較大。
允許使用者向系統要求kernel mode下的服務的一個介面,若是user需要系統提供kernel mode下的服務就呼叫system call,利用此軟體中斷並從user mode切換到kernel mode,然後系統會執行對應的system call routine,將結果傳回給user。
OS中的參數如何傳遞:
主要用於資料的大量傳輸,負責I/O devices和memory間的資料傳輸,不須CPU的監督,使CPU可以同時運作,增進效率。
cycle stealing:當DMA controller存取記憶庫時,CPU只能存取cache的資料,因此DMA可盜取CPU的存取週期。
將讀到的command解譯成procedure及參數,確定命令無誤則交由系統呼叫對應的程式來執行命令。
與kernel分開的原因:
優點:(1)系統安全性佳,且debug較為容易 (2)提供user一個好平台,可以安裝各種不同的os,對於新系統的研究與發展相當適合。
缺點:(1)製作困難且資源共享不易 (2)利用模擬方式執行,performance較差
set timer,turn off interrupt,change to kernel mode,clear memory,read / write to kernel memory。
turn on interrupt,change to user mode,read the clock,increase value of register,Fetch an instruction from kernel memory。
(1) Mode bit:用來區分user mode和kernel mode。
(2) Timer:用來控制process的執行時間,保護系統資源不被獨占。
(3) Register set:用來存取process的資訊或小型的page table等。
相異處:
相似處:
提供一些系統已寫好的procedure 和 system call,讓使用者不須浪費額外的時間去寫 I/O 或 開檔讀檔 等常用的基本指令,可節省使用者開發程式的時間,若是許多使用者在系統中更可節省memory。
用來儲存process相關狀態,資訊的資料結構,每個process都有一個PCB。
create,destroy,switch都不需透過kernel的處理,所以速度較快。
create,destroy,switch都必須經由system call來透過kernel處理,所以速度較慢。
Java以java.lang.Thread這個類別來表示Thread。
Class Thread有兩個Constructor:
目的:決定哪些job可以從hold state進入ready state。當一個工作結束時,此排程就會啟動。
目的:從ready queue中挑選一個process來獲得CPU的使用權。
目的:為了提升系統效能及降低系統負荷,將一些process swap到disk中,等系統負荷較低的時候再載入到memory執行。
允許priority較高的process進入ready queue後可以作context switch將priority較低的process置換掉,並取得CPU的使用權。
preemptive優點
preemptive缺點
除非是process自己放棄CPU使用權或是已經執行完畢,不然不允許系統作context switch把它的CPU使用權交給其它的process。
Non-preemptive優點
Non-preemptive缺點
當process被強迫離開CPU時,必須將現在process information儲存起來,並載入新的process information,這種額外的負擔稱之context swith。
(1) 替每個process準備一獨立的register set,即若是register的數目夠多,則OS只要改變register的point即可。
(2) 利用thread可降低context switch的負擔,由於同一個process下的thread可以共享memory,所以需要的independent register數目較少,使負擔較輕。
(3) Dispatcher:
可以把CPU的控制權交給經由short-term scheduling所選出來的process。
優點:
(1) program size大於physical memory size時仍可執行。
(2) 提高 memory utilization,degree of multiprogramming。
(3) 降低programmer overhead。
缺點:
(1) 增加memory access time。
(2) 需要硬體的支援。
(3) 有可能會發生Trashing的現象。
設計一個critical section的Algorithm須符合三個條件:
一個整數變數,允許N個thread同時存取,提供兩種atomic運作:wait與signal,用來完成critical section設計及解決同步問題的機制。
定義如下:
Semaphore的兩種製作方式:
(1) Spin-lock:對於多處理機系統很有用,優點是可以省去process進入critical section時的context switch時間,使process可以用極短的時間進入c.s.。
(2)Suspend-lock:可以用來解決busy waiting的現象,充分的利用CPU資源。
Semaphore 與 Monitor的比較:使用monitor可以輕易地模仿出semaphore的效果,可是使用semaphore來模擬monitor卻會十分複雜。
忙碌等待就是在一個迴圈裡,不斷等待某個條件的成立,必須等該條件成立之後,才會離開該迴圈。例如:
若eventFlag為false,那麼迴圈就會持續執行,直至同一個程序中的另一個執行緒,將eventFlag值改為非false時,才會離開迴圈。
這在邏輯上一點問題也沒有,但因為多工作業系統的特性,因而衍生出效能的問題,佔據了CPU可供執行的時間,讓其他程式無法分配到足夠的CPU時間,使得其他程式呈現反應遲滯的現象。就像上面的程式片段中,該迴圈不斷持續地忙著檢查eventFlag的值,所以被稱為是一個忙碌的迴圈。
critical section造成的busy waiting是因為waiting process佔用CPU time執行迴圈卻沒有真正進行運算,浪費CPU time。
I/O造成的busy waiting是因為CPU必須不斷去檢查I/O是否完成,而造成在等待I/O的運作完成過程中,CPU雖然busy ,但實際上沒有增加 throughout。
Rendezvous:
在message passing下,當兩個process要溝通,則會執行send及receive指令,如果link buffer已滿,則sender送出的訊息無法在link中停留,所以sender必須等待直到receive那端收到訊息,造成雙方在此同步稱為rendezvous。
Swap:為了提升memory utilization,而利用medium-term scheduler將某些process暫時swap out到disk,等memory空間足夠的時候在重新載入。
數個process之間採用shared-memory的方式溝通,每個process都有一段稱為critical section的code,process要存取必須滿足mutual exclusion。
在系統中存在一組processes互相等待對方資源,使得process無法皆無法繼續執行,使得CPU執行效率大幅下降。
形成DeadLock必須四要素,缺一不可
哲學家就餐問題
假設有五位哲學家圍坐在一張圓形餐桌旁,做以下兩件事情之一:吃飯,或者思考。吃東西的時候,他們就停止思考,思考的時候也停止吃東西。
餐桌中間有一大碗義大利麵,每兩個哲學家之間有一隻餐叉。因為用一隻餐叉很難吃到義大利麵,所以假設哲學家必須用兩隻餐叉吃東西。他們只能使用自己左右手邊的那兩隻餐叉。
哲學家從來不交談,這就很危險,可能產生死結,每個哲學家都拿著左手的餐叉,永遠都在等右邊的餐叉(或者相反)。
即使沒有死結,也有可能發生資源耗盡。例如,假設規定當哲學家等待另一隻餐叉超過五分鐘後就放下自己手裡的那一隻餐叉,並且再等五分鐘後進行下一次嘗試。這個策略消除了死結(系統總會進入到下一個狀態),但仍然有可能發生「活鎖」。如果五位哲學家在完全相同的時刻進入餐廳,並同時拿起左邊的餐叉,那麼這些哲學家就會等待五分鐘,同時放下手中的餐叉,再等五分鐘,又同時拿起這些餐叉。
一種常用的電腦技術是資源加鎖,用來保證在某個時刻,資源只能被一個程式或一段代碼存取。當一個程式想要使用的資源已經被另一個程式鎖定,它就等待資源解鎖。
當多個程式涉及到加鎖的資源時,在某些情況下就有可能發生死結。例如,某個程式需要存取兩個檔案,當兩個這樣的程式各鎖了一個檔案,那它們都在等待對方解鎖另一個檔案,而這永遠不會發生。
系統利用algorithm對於process的request進行評估,若可以找出一組safe sequence,使系統進入safe state就核准其要求,否則拒絕此process的request。
Bankers Algorithm:計算系統是否處於safe state,用在multiple instance。
優點:可以避免系統進入deadlock。
缺點:
(a)每次process提出資源要求,系統皆須要額外的花費去執行此algorithm。
(b)資源使用率不佳,因為unsafe state不代表一定會deadlock,但是會被拒絕。
Internal Resource:可以使用resource ordering技術解決。
Job Resource:利用deadlock avoidance的方法。
Central Memory:利用preemption的方式。
Swappable space:事先配置最大需要空間。
Starvation 在沒有deadlock的狀態下,是指某些process因為一直分配不到執行所需要的資源,而發生indefinite postponement的現象。
Deadlock 則是一群process為了搶奪資源而造成全部的process都無法執行。
Program:尚未開始執行的程式。尚未載入主記憶體,不擁有計算機資源。沒有對應之PCB(process control block)。不是scheduler排程的對象。
Process :正執行中的程式,有ready、run、blocked等process狀態。已載入主記憶體,擁有計算機資源,如I/O設備、CPU等。有對應之PCB(process control block),記載process之狀態、所擁有計算機之資源,I/O buffer之位址等。CPU排程的對象。
erlay:只保留執行時所需要的指令和資料在記憶體內,當需要其它指令時,再載入到已經不需要使用的指令空間中。
(1) Register:優點:速度快。缺點:若page table太大則造價昂貴不適合。
(2) Memory:優點:允許較大的page table。缺點:memory access兩次造成有效存取時間太長。
(3) TLB(Translation look-aside buffers):一般由associative register製成。
優點:在hit ratio高的情況下速度與register一樣高。
缺點:hit ratio低時,速度慢。
用來實現virtual memory的技術,不把整個process需要的page載入記憶體,而採用Lazy Swapper,只載入執行所需的頁面。
Pure Demand Page:當process執行時需要某page才將其載入記憶體,不需要的page都不須載入(不預先猜測)。
Copy on write bit:所有共用同page的process都會將其page table對應到此page的entry的copy-on-write-bit設定為1,表示對此page有write必須另行copy。
Contiguous Allocation:檔案被分配在disk中連續的位址上,而目錄只需要記錄此檔案的第一個block位址即可。
優點:隨機存取容易可以直接計算出磁區之實際位址,速度最快。
缺點:
Linked Allocation:將分配給檔案的空間用pointer連起來,而目錄只需要記錄此檔案的第一個block位址即可。
優點:a. 沒有External Fragmentation的現象。 b. 配置空間給檔案很容易,也容易擴充。
缺點:a. 支援循序存取,但是不適用direct access b. 鏈結的指標需要佔用額外的空間。 c. 可靠度較差,發生link lose的時候較難處理。
Index Allocation:每個檔案使用一個block當作index,來記錄檔案所使用的block位址(大部分系統採用)
優點:a. 沒有External Fragmentation的現象。 b. 支援direct access,空間容易擴充。
缺點:索引區的大小難以決定,太大浪費空間,太小怕不夠用。
解決索引區大小之方法:(1)Linked Index (2)Multilevel Index (3)Combination
(1)FCFS (2)SSTF (3)SCAN Scheduling (4)C-SCAN Scheduling (5)Look Scheduling
Disk cache:由OS所控制,disk cache內儲存最近曾被存取過的磁碟資料,當應用程式提出對磁碟存取要求,若disk cache 已有這筆資料,則從cache存取
RAM Disk:為使用者控制,OS 將一部分的主記憶體作為RAM Disk,開機時,將磁碟資料全部載入此段空間並且在memory內執行這些作業,而不是在disk上執行,速度快,但僅能暫時儲存,關機時,則將資料存回磁碟。
Difference:RAM disk內容完全由user控制,無hit/miss等問題,開始或結束時須將資料載入或回存於disk內,資料僅能暫時保存。
Disk cache內容完全由O.S.控制,有hit/miss的問題,若miss則仍要到disk存取資料,資料可以永久保存並來自不同disk。
(1)Sequential access method:檔案中的資訊是按記錄次序一筆接一筆處理的,為目前最通用的檔案存取方式。
(2)Direct access method:檔案由固定長度的邏輯記錄所組成,讓程式採用直接存取法,讀出或寫入檔案的任意區段,常用於大型資料庫。
(3)Indexed sequential access method:利用primary index file包含指向secondary index file的指標,而secondary index file則包含指向實際data block的指標。
快取記憶體是界於cpu和主記憶體之間的高速記憶單元,通常較常用到的資料會被存放於快取記憶體中,以減少CPU存取主記憶體的次數,以提高處理速度。
Problem 1 : 在cache找不到需要的資料時則必須到主記憶體中讀取,造成大量資料再兩層記憶體中傳輸,使overhead過高,此問題和Hit Ratio有關,通常程式指令執行上都有固定形式,因此不需太大快取就有不錯的Hit Ratio了。
Problem 2 : 快取記憶體和主記憶體有可能會造成兩份資料一致性的問題。
(a)write back資料寫回快取記憶體即可,將來釋放快取再存回主記憶體,這種方式資料有數個copy在存回主記憶體前容易造成不一致。
(b)write through資料不只寫回快取也同時寫到主記憶體,寫入速度慢。
Disk striping:利用一群disk來改善disk速度,每個data block被打散成數個sub-blocks存在每一個disk中,因為這些sun-blocks利用平行處理的方式transfer into memory,所以可以加快速度。