操作系统：操作系统知识点总结
操作系統(tǒng)知識點總結
1. 基礎知識
1.1 內核態(tài)和用戶態(tài)
多數(shù)計算機有兩種運行模式，用戶態(tài)和內核態(tài)。軟件中最基礎的部分是操作系統(tǒng)，它運行在內核態(tài)。在這個模式中，操作系統(tǒng)具有對所有硬件的完全訪問權，可以執(zhí)行機器能夠運行的任何指令。軟件的其余部分運行在用戶態(tài)，在用戶態(tài)下，只使用了機器指令中的一個子集。
核心態(tài)和用戶態(tài)各有優(yōu)勢：運行在核心態(tài)的程序可以訪問更多資源，但可靠性、安全性要求高，維護管理都較復雜；用戶態(tài)程序訪問資源受限，但可靠性、安全性要求低，編寫維護較簡單。
為了從操作系統(tǒng)中獲得服務，用戶程序必須使用系統(tǒng)調用陷入內核并調用操作系統(tǒng)。TRAP指令把用戶態(tài)切換成內核態(tài)（上下文切換），并啟用操作系統(tǒng)。當有關工作完成之后，在系統(tǒng)調用后面的指令把控制權返回給用戶程序。
1.2 什么是操作系統(tǒng)
操作系統(tǒng)是一種運行在內核態(tài)的軟件，執(zhí)行以下兩個基本任務：為應用程序提供一個資源集的清晰抽象，并管理這些硬件資源。
1.3 計算機硬件
計算機硬件包括：CPU、內存以及IO設備。
CPU負責從內存中取出指令并執(zhí)行。由于用來訪問內存以及得到指令或數(shù)據(jù)的時間要比執(zhí)行指令花費的時間長得多，因此所有的CPU內都有一些用來保存關鍵變量和臨時數(shù)據(jù)的寄存器。除此之外，計算機還有一些對程序員可見的專用寄存器：
·????????程序計數(shù)器：用于保存下一條指令的內存地址。
·????????堆棧指針：指向內存中當前棧的頂端。
·????????PSW程序狀態(tài)字寄存器：包含了條件碼位，CPU優(yōu)先級，模式（用戶態(tài)或內核態(tài)），以及各種控制位。
2. 進程與線程
2.1 進程與線程的區(qū)別
進程：進程是一個正在執(zhí)行程序的示例，擁有自己的程序計數(shù)器和內部狀態(tài)，是系統(tǒng)進行資源分配和調度的一個獨立單位（具有動態(tài)、并發(fā)、獨立、異步的特性，以及就緒、執(zhí)行、阻塞3種狀態(tài)，資源擁有單位等屬性）；引入進程是為了使多個程序可以并發(fā)的執(zhí)行，以提高系統(tǒng)的資源利用率和吞吐量。
線程：是比進程更小的可獨立運行的基本單位，可以看做是輕量級的進程（具有輕型實體，獨立調度分派單位，可并發(fā)執(zhí)行，共享進程資源等屬性）；引入目的是為了減少程序在并發(fā)執(zhí)行過程中的開銷，使OS的并發(fā)效率更高。
兩者的對比：
1.???調度方面：在引入線程的OS中，線程是獨立的調度和分派單位，而進程作為資源的擁有單位(相當于把未引入線程的傳統(tǒng)OS中的進程的兩個屬性分開了)。由于線程不擁有資源，因此可以顯著的提高并發(fā)度以及減少切換開銷。
2.???并發(fā)性：引入了線程的OS中，進程間可以并發(fā)，而且一個進程內部的多個線程之間也是可以并發(fā)的，這就使OS具有更好的并發(fā)性，有效的提高了系統(tǒng)資源利用率和吞吐量。
3.????擁有資源：處于安全和方便管理的因素，一個進程往往會獨占一些資源，如地址空間、全局變量、打開的文件、子進程、信號和賬戶信息等；而為了處理各自的任務，線程也會獨占一些資源，如棧、寄存器、程序計數(shù)器和狀態(tài)等。
4.????系統(tǒng)開銷：創(chuàng)建或者撤銷進程的時候，系統(tǒng)要為之創(chuàng)建或回收PCB，系統(tǒng)資源等，切換時也需要保存和恢復CPU環(huán)境。而線程的切換只需要保存和恢復少量的寄存器，不涉及存儲器管理方面的工作，所以開銷較小。此外，同一個進程中的多個線程由于共享地址空間，所以通信同步等都比較方便。
例題：同一個進程中的線程不共享的部分是（F）。（2017阿里巴巴實習生筆試題）
?????A、信號????B、堆????C、文件描述符????D、進程組id????E、代碼段????F、棧空間
2.2 進程的三種狀態(tài)
1.???就緒狀態(tài)：進程獲得了除了CPU之外的所有的必要資源，只要獲得CPU就可以立即執(zhí)行，此時的進程處于就緒態(tài)。
2.???運行狀態(tài)：進程已經獲得CPU，正在運行，在多處理其系統(tǒng)中，會有多個進程同時處于運行狀態(tài)。
3.???阻塞狀態(tài)：處于執(zhí)行狀態(tài)的進程由于發(fā)生某些事件而暫時無法繼續(xù)執(zhí)行，放棄處理機而處于暫停狀態(tài)，此時進程就處于阻塞（執(zhí)行受到阻塞）狀態(tài)。
進程的三種狀態(tài)之間有4種可能的轉換關系：
?
2.3 線程的實現(xiàn)方式
在用戶空間中實現(xiàn)線程
? ? 一個線程阻塞會導致整個進程（包括進程里的所有線程）都阻塞
? ?頁面失效也會導致整個進程被掛起
用戶級線程指不需要內核支持而在用戶程序中實現(xiàn)的線程，其不依賴于操作系統(tǒng)核心，應用進程利用線程庫提供創(chuàng)建、同步、調度和管理線程的函數(shù)來控制用戶線程。不需要用戶態(tài)/核心態(tài)切換，速度快，操作系統(tǒng)內核不知道多線程的存在，因此一個線程阻塞將使得整個進程（包括它的所有線程）阻塞。由于這里的處理器時間片分配是以進程為基本單位，所以每個線程執(zhí)行的時間相對減少。
在內核中實現(xiàn)線程
內核級線程由操作系統(tǒng)內核創(chuàng)建和撤銷。內核維護進程及線程的上下文信息以及線程切換。一個內核線程由于I/O操作而阻塞，不會影響其它線程的運行。
在用戶空間中實現(xiàn)線程的優(yōu)勢
·????????可以在不支持線程的操作系統(tǒng)中實現(xiàn)。
·????????創(chuàng)建和銷毀線程、線程切換代價等線程管理的代價比內核線程少得多。
·????????允許每個進程定制自己的調度算法，線程管理比較靈活。（每個線程自定義線程調度算法）
·????????線程能夠利用的表空間和堆棧空間比內核級線程多。
在用戶空間中實現(xiàn)線程的缺點
?
·????????同一進程中只能同時有一個線程在運行，如果有一個線程使用了系統(tǒng)調用而阻塞，那么整個進程都會被掛起。
·????????頁面失效也會導致整個進程都會被掛起。
?
內核線程的優(yōu)缺點剛好跟用戶線程相反。實際上，操作系統(tǒng)可以使用混合的方式來實現(xiàn)線程。
2.4 線程同步
（數(shù)據(jù)爭用導致線程之間的不同步問題，使得系統(tǒng)紊亂）
競爭條件：兩個或多個線程讀寫某些共享數(shù)據(jù)，而最后的結果取決于線程運行的精確時序。為避免競爭條件，需要找到某種途徑組織多個線程同時讀寫共享的數(shù)據(jù)。這里，我們把對共享數(shù)據(jù)（共享內存）進行訪問的程序片段稱之為臨界區(qū)，只要我們能夠使兩個線程不可能同時處于臨界區(qū)，就能夠避免競爭條件。
同步機制需要遵循的原則：
1.???空閑讓進：當沒有線程處于臨界區(qū)的時候，應該許可其他線程進入臨界區(qū)的申請。
2.???忙則等待：當前如果有線程處于臨界區(qū)，如果有其他線程申請進入，則必須等待，保證對臨界區(qū)的互斥訪問。
3.???有限等待：對要求訪問臨界資源的線程，需要在有限時間內進入臨界區(qū)，防止出現(xiàn)死等。
4.???讓權等待：當線程無法進入臨界區(qū)的時候，需要釋放處理機，別陷入忙等。
線程同步的常用方法：互斥鎖，條件變量，信號量。
互斥鎖：同一時刻只允許一個線程進入臨界區(qū)。互斥鎖有兩個基本操作，加鎖和解鎖。一個線程如果想要進入臨界區(qū)，它首先需要嘗試鎖住相關的互斥量。如果互斥量沒有加鎖，那么這個線程可以立即進入，并對互斥量進行加鎖以防止其他線程進入。如果互斥量已經被加鎖，則調用線程被阻塞，直至該互斥量被解鎖。
條件變量：允許線程由于一些未達到的條件而阻塞，通常與互斥鎖配合使用。條件變量的基本操作有：觸發(fā)條件(當條件變?yōu)?true 時)；等待條件，掛起線程直到其他線程觸發(fā)條件。（條件變量一般需要觸發(fā)條件，這個在編寫代碼的時候，用戶自定義）
·????????在等待進程中，需要等待該條件，即需要_cond.wait()；wait()過程將會把調用線程放到等待條件的線程列表上，然后對該互斥量解鎖；此時在互斥量解鎖期間，又有新的線程進入該臨界區(qū)，條件尚未發(fā)生，wait()會繼續(xù)這一過程。
·????????在喚醒進程中，首先會進行條件檢查（已經被同一個互斥量鎖住，睡眠的線程不可能錯過）；如果條件成立，則喚醒等待進程。（因此，wait()一般要放置在循環(huán)中，或者使用double check）
·????????需要使用while(_count > 0)，而不是if (_count > 0)，（可以使用兩個if來代替while），原因為當線程從_cond.wait()喚醒時，此時互斥量會繼續(xù)被鎖住（此時多個線程對互斥量爭用的問題），很有可能此時的條件會被其他線程修改，造成_count > 0的條件不成立，因此需要繼續(xù)判斷的。
信號量：為控制一個具有有限數(shù)量的用戶資源而設計。它允許多個線程在同一個時刻去訪問同一個資源，但一般需要限制同一時刻訪問此資源的最大線程數(shù)目。
Pthread中的函數(shù)調用
創(chuàng)建互斥鎖：int pthread_mutex_init(pthread_mutex_t*mutex,const pthread_mutexattr_t*restrict attr)
加鎖：int pthread_mutex_lock(pthread_mutex_t*mutex)
解鎖：int pthread_mutex_unlock(pthread_mutex_t*mutex)
銷毀互斥鎖：pthread_mutex_destroy ()
?
初始化條件變量：pthread_cond_init(pthread_cond_t*cond,pthread_condattr_t *cond_attr)
無條件等待：pthread_cond_wait(pthread_cond_t*cond,pthread_mutex_t *mutex)
計時等待：pthread_cond_timewait(pthread_cond_t*cond,pthread_mutex *mutex,const timespec *abstime)
激活一個等待該條件的線程：pthread_cond_signal(pthread_cond_t*cond)
激活所有等待線程：pthread_cond_broadcast(pthread_cond_t*cond)
銷毀條件變量：pthread_cond_destroy(pthread_cond_t*cond)
經典的進程同步問題：生產者-消費者問題；
哲學家進餐問題；讀者-寫者問題。
2.5 進程間通信
進程間通信的方式有管道、消息隊列、共享內存、信號、信號量和套接字等。
1.???管道：管道是連接兩個一個讀進程和一個寫進程之間用于實現(xiàn)數(shù)據(jù)交換的一個共享文件。為了協(xié)調管道通信雙方，需要管道機制實現(xiàn)如下功能：
1）互斥：同一時刻只能有一個進程對管道進行讀寫；（半雙工）
2）同步：當讀端發(fā)現(xiàn)管道為空的時候需要睡眠等待，直到有數(shù)據(jù)時候被喚醒（空了沒得讀），相應的寫端也是在管道已滿的時候等待直到被喚醒（滿了寫不進去）；
3）確定對方的存在性：只有同時有讀端和寫端，管道才有存在意義。它包括無名管道和有名管道（FIFO）兩種，前者用于父進程和子進程間的通信，后者用于運行于同一臺機器上的任意兩個進程間的通信（）。
?無名管道：int pipe(int fd);
?有名管道：int??mkfifo(const char* pathname,mode_t mode);?
2.???信號量是一個計數(shù)器，可以用來控制多個進程對共享資源的訪問。它常作為一種鎖機制，防止某進程正在訪問共享資源時，其他進程也訪問該資源。因此，主要作為進程間以及同一進程內不同線程之間的同步手段。
3.??消息隊列是由消息存放在內核中并由消息隊列標識符標識。消息隊列克服了信號傳遞信息少、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點。其基本思想是根據(jù)”生產者-消費者”原理，利用內存中公用消息緩沖區(qū)實現(xiàn)進程之間的信息交換。每當一個進程向另一個進程發(fā)送消息時，便申請一個消息緩沖區(qū)，并把已準備好的消息送到緩沖區(qū)，然后把該消息緩沖區(qū)插入到接收進程的消息隊列中，最后通知接收進程。接收進程收到發(fā)送里程發(fā)來的通知后，從本進程的消息隊列中摘下一消息緩沖區(qū)，取出所需的信息，然后把消息緩沖區(qū)不定期給系統(tǒng)。系統(tǒng)負責管理公用消息緩沖區(qū)以及消息的傳遞。
4.???信號是一種比較復雜的通信方式，用于通知接收進程某個事件已經發(fā)生。
5.???共享內存就是映射一段能被其他進程所訪問的內存，這段共享內存由一個進程創(chuàng)建，但多個進程都可以訪問。共享內存是最快的IPC方式，它是針對其他進程間通信方式運行效率低而專門設計的。它往往與其他通信機制，如信號量，配合使用，來實現(xiàn)進程間的同步和通信。
6.???套接字也是一種進程間通信機制，可以實現(xiàn)不同主機間的進程通信。一個套接口可以看做是進程間通信的端點，每個套接口的名字是唯一的，其他進程可以訪問，連接和進行數(shù)據(jù)通信。
2.6 進程調度算法
基本調度算法：
1.???先來先服務FCFS：既可以作為作業(yè)調度算法也可以作為進程調度算法；按作業(yè)或者進程到達的先后順序依次調度；因此對于長作業(yè)比較有利。
2.???短作業(yè)優(yōu)先SPF：作業(yè)調度算法，算法從就緒隊列中選擇估計時間最短的作業(yè)進行處理，直到得出結果或者無法繼續(xù)執(zhí)行；
缺點：不利于長作業(yè)；未考慮作業(yè)的重要性；運行時間是預估的，并不靠譜。
3.???** 高優(yōu)先權優(yōu)先HRRF**：既可以作為作業(yè)調度也可以作為進程調度算法；調度作業(yè)時，從就緒隊列中選擇優(yōu)先級最高的作業(yè)進行處理；由于涉及到了優(yōu)先級，因此可以分為搶占式和非搶占式；而且優(yōu)先級的確定也可以分為靜態(tài)優(yōu)先級（事先根據(jù)進程類型，進程對資源的需求，用戶要求等方面確定一個固定值）；動態(tài)優(yōu)先級（隨進程的推進或者等待時間而增加或者減少）。
4.???最高響應比優(yōu)先HRN：FCFS可能造成短作業(yè)用戶不滿，SPF可能使得長作業(yè)用戶不滿，于是提出HRN，選擇響應比最高的作業(yè)運行。（考慮等待和處理時間因素）響應比=1+作業(yè)等待時間/作業(yè)處理時間。
5.???時間片輪轉：按到達的先后對進程放入隊列中，然后給隊首進程分配CPU時間片，時間片用完之后計時器發(fā)出中斷，暫停當前進程并將其放到隊列尾部，循環(huán)。
6.???多級反饋隊列：目前公認較好的調度算法；設置多個就緒隊列并為每個隊列設置不同的優(yōu)先級，第一個隊列優(yōu)先級最高，其余依次遞減。優(yōu)先級越高的隊列分配的時間片越短，進程到達之后按FCFS放入第一個隊列，如果調度執(zhí)行后沒有完成，那么放到第二個隊列尾部等待調度，如果第二次調度仍然沒有完成，放入第三隊列尾部…。只有當前一個隊列為空的時候才會去調度下一個隊列的進程。
3. 死鎖
死鎖是指多個進程在運行過程中，因為爭奪資源而造成的一種僵局，如果沒有外力推進，處于僵局中的進程就無法繼續(xù)執(zhí)行。
3.1 死鎖原因：
1.???競爭資源：請求同一有限資源的進程數(shù)多于可用資源數(shù)
2.???進程推進順序是非法的：進程執(zhí)行中，請求和釋放資源順序不合理，如資源等待鏈
3.2 死鎖產生的必要條件：
1.???互斥條件:進程對所分配的資源進行排他性的使用
2.???請求和保持條件：進程被阻塞的時候并不釋放鎖申請到的資源
3.???不可剝奪條件：進程對于已經申請到的資源在使用完成之前不可以被剝奪
4.???環(huán)路等待條件：發(fā)生死鎖的時候存在的一個進程-資源環(huán)形等待鏈
3.3 死鎖處理：
1.???預防死鎖：破壞產生死鎖的4個必要條件中的一個或者多個；實現(xiàn)起來比較簡單，但是如果限制過于嚴格會降低系統(tǒng)資源利用率以及吞吐量
2.???避免死鎖：在資源的動態(tài)分配中，防止系統(tǒng)進入不安全狀態(tài)(可能產生死鎖的狀態(tài))-如銀行家算法
3.???檢測死鎖：允許系統(tǒng)運行過程中產生死鎖，在死鎖發(fā)生之后，采用一定的算法進行檢測，并確定與死鎖相關的資源和進程，采取相關方法清除檢測到的死鎖。實現(xiàn)難度大
4.???解除死鎖：與死鎖檢測配合，將系統(tǒng)從死鎖中解脫出來（撤銷進程或者剝奪資源）。對檢測到的和死鎖相關的進程以及資源，通過撤銷或者掛起的方式，釋放一些資源并將其分配給處于阻塞狀態(tài)的進程，使其轉變?yōu)榫途w態(tài)。實現(xiàn)難度大
例題：列舉一種死鎖發(fā)生的場景，并給出解決方案。（PPS2013校園招聘筆試題）
答：最經典的場景就是生產者/消費者，生產者線程生產物品，然后將物品放置在一個空緩沖區(qū)中供消費者線程消費。消費者線程從緩沖區(qū)中獲得物品，然后釋放緩沖區(qū)。由于生產者/消費者都在操作緩沖區(qū)，容易導致死鎖的發(fā)生。可以通過添加鎖的保護來對緩沖區(qū)進行互斥的訪問，保證某一時刻只有一個線程對緩沖區(qū)進行操作，當緩沖區(qū)滿的時候，生產者線程就會掛起，同時通知消費者線程。而緩沖區(qū)空的時候，消費者線程就會掛起，同時通知生產者線程。
4. 存儲管理
4.1 內存管理方式
由于連續(xù)內存分配方式(單一連續(xù)分配，固定分區(qū)分配，動態(tài)分區(qū)分配，動態(tài)重定位分區(qū)分配)導致的內存利用率偏低以及內存碎片的問題，進而引出離散的內存分配方式。離散內存分配可以從OS的內存管理角度引出頁式(離散分配的基本單位是頁)管理，也可以從程序編制角度引出段式(離散分配的基本單位是段)管理。
基本分頁存儲管理
基本分頁存儲管理中不具備頁面置換功能(即沒有實現(xiàn)虛擬內存的功能)，因此需要整個程序的所有頁面都裝入內存之后才可以運行。因為程序數(shù)據(jù)存儲在不同的頁面中，而頁面又離散的分布在內存中，因此需要一個頁表來記錄邏輯地址和實際存儲地址之間的映射關系，以實現(xiàn)從頁號到物理塊號（頁框）的映射。由于頁表也是存儲在內存中的，因此和不適用分頁管理的存儲方式相比，訪問分頁系統(tǒng)中內存數(shù)據(jù)需要兩次的內存訪問(一次是從內存中訪問頁表，從中找到指定的物理塊號，加上頁內偏移得到實際物理地址；第二次就是根據(jù)第一次得到的物理地址訪問內存取出數(shù)據(jù))。
為了減少兩次訪問內存導致的效率影響，分頁管理中引入了快表(或者聯(lián)想寄存器)機制（緩存TLB），包含快表機制的內存管理中，當要訪問內存數(shù)據(jù)的時候，首先將頁號在快表中查詢，如果查找到說明要訪問的頁表項在快表中，那么直接從快表中讀取相應的物理塊號；如果沒有找到，那么訪問內存中的頁表，從頁表中得到物理地址，同時將頁表中的該映射表項添加到快表中(可能存在快表換出算法)。
基本分段存儲管理方式
分頁是為了提高內存利用率，而分段是為了滿足程序員在編寫代碼的時候的一些邏輯需求(比如數(shù)據(jù)共享，數(shù)據(jù)保護，動態(tài)鏈接等)。
分段內存管理當中，地址是二維的，一維是段號，一維是段內地址；其中每個段的長度是不一樣的，而且每個段內部都是從0開始編址的。由于分段管理中，每個段內部是連續(xù)內存分配，但是段和段之間是離散分配的，因此也存在一個邏輯地址到物理地址的映射關系，相應的就是段表機制。段表中的每一個表項記錄了該段在內存中的起始地址和該段的長度。段表可以放在內存中也可以放在寄存器中。
訪問內存的時候根據(jù)段號和段表項的長度計算當前訪問段在段表中的位置，然后訪問段表，得到該段的物理地址，根據(jù)該物理地址以及段內偏移量就可以得到需要訪問的內存。由于也是兩次內存訪問，所以分段管理中同樣引入了聯(lián)想寄存器。
分段和分頁的對比：
1.???頁是信息的物理單位，是出于系統(tǒng)內存利用率的角度提出的離散分配機制；段是信息的邏輯單位，每個段含有一組意義完整的信息，是出于用戶角度提出的內存管理機制。
2.???頁的大小是固定的，由系統(tǒng)決定；段的大小是不確定的，由用戶決定。
3.???頁地址空間是一維的，段地址空間是二維的。
段頁式存儲管理
先將用戶程序分為若干個段，然后再把每個段分成若干個頁，并且為每一個段賦予一個段名稱。這樣在段頁式管理中，一個內存地址就由段號，段內頁號以及頁內地址三個部分組成。
段頁式內存訪問：系統(tǒng)中設置了一個段表寄存器，存放段表的起始地址和段表的長度。地址變換時，根據(jù)給定的段號（還需要將段號和寄存器中的段表長度進行比較防止越界）以及寄存器中的段表起始地址，就可以得到該段對應的段表項，從段表項中得到該段對應的頁表的起始地址，然后利用邏輯地址中的段內頁號從頁表中找到頁表項，從該頁表項中的物理塊地址以及邏輯地址中的頁內地址拼接出物理地址，最后用這個物理地址訪問得到所需數(shù)據(jù)。由于訪問一個數(shù)據(jù)需要三次內存訪問，所以段頁式管理中也引入了高速緩沖寄存器。
4.2 虛擬內存
如果存在一個程序，所需內存空間超過了計算機可以提供的實際內存，那么由于該程序無法裝入內存所以也就無法運行。單純的增加物理內存只能解決一部分問題，但是仍然會出現(xiàn)無法裝入單個或者無法同時裝入多個程序的問題。
虛擬內存就是具有請求調入功能和置換功能，可以從邏輯上對內存容量加以擴充的一種存儲器系統(tǒng)。它使得應用程序認為它擁有連續(xù)可用的內存（一個連續(xù)完整的地址空間），允許運行比實際系統(tǒng)擁有的內存大得多的程序。而實際上，它通常被分割成多個物理內存碎片，還有部分暫時存儲在外部磁盤存儲器上，在需要時進行數(shù)據(jù)交換。
虛擬內存的基本思想：每個程序擁有自己的地址空間，這個空間被分割成很多塊，每一塊稱作一頁或頁面。每一頁有連續(xù)的地址范圍。這些也被映射到物理內存，但并不是所有的頁都必須在內存中才能運行程序。當程序引用到一部分在物理內存中的地址空間時，由硬件立刻執(zhí)行必要的映射。當程序引用到一部分不再物理內存中的地址空間時，由操作系統(tǒng)負責將缺失部分裝入物理內存并重新執(zhí)行失敗的指令，這個過程或陷阱稱為缺頁中斷（或頁錯誤）。
虛存的代價：
·????????虛存的管理需要建立很多數(shù)據(jù)結構，占用額外內存。
·????????虛擬地址到物理地址的轉換，增加了指令執(zhí)行時間。
·????????頁式的換入換出需要磁盤I/O，耗費時間。
·????????如果一頁中只有部分數(shù)據(jù)，浪費內存。
例題：計算缺頁中斷次數(shù)。（2014淘寶筆試題）
有一虛擬存儲系統(tǒng)，若進程在內存中占3頁（開始時內存為空），若采用先進先出頁面置換算法，當執(zhí)行如下訪頁頁號序列后1，2，3，4，1，2，5，1，2，3，4，5，會產生（10）次缺頁？
4.3 頁面置換算法
1.???最優(yōu)頁面置換算法：只具有理論意義的算法，用來評價其他頁面置換算法。置換策略是將當前頁面中在未來最長時間內不會被訪問的頁置換出去。
2.???先進先出置換算法：由操作系統(tǒng)維護一個所有當前在內存中的頁面的鏈表，最新進入的頁面放在表尾，最早進入的頁面放在表頭；當發(fā)生缺頁中斷時，淘汰表頭的頁面并將新調入的頁面追加到表尾。簡單粗暴的一種置換算法，沒有考慮頁面訪問頻率信息。
3.???最近最少使用算法LRU：算法賦予每個頁面一個訪問字段，用來記錄上次頁面被訪問到現(xiàn)在所經歷的時間t，每次置換的時候把t值最大的頁面置換出去(實現(xiàn)方面可以采用寄存器或者棧的方式實現(xiàn))。
4.???時鐘置換算法(也被稱為最近未使用算法NRU)：頁面設置一個訪問位，頁面被訪問的時候訪問位設置為1；并將所有頁面保存在一個循環(huán)隊列中，表針指向最老的頁面。頁面置換的時候，如果當前指針所指頁面訪問為為0，那么置換，否則將其置為0，循環(huán)直到遇到一個訪問為位0的頁面。
5.???改進型Clock算法：在Clock算法的基礎上添加一個修改位，替換時根究訪問位和修改位綜合判斷。優(yōu)先替換訪問為何修改位都是0的頁面，其次是訪問位為0修改位為1的頁面。
6.???最少使用算法LFU：設置寄存器記錄頁面被訪問次數(shù)，每次置換的時候置換當前訪問次數(shù)最少的。存在問題是該訪問寄存器并不能真正反映當前頁面訪問次數(shù)，因為訪問速度比較快，所以在更新寄存器的時間間隔內訪問1次和訪問100次都是一樣的。另外，LFU和LRU是很類似的，支持硬件也是一樣的，但是區(qū)分兩者的關鍵在于一個以時間為標準，一個以次數(shù)為標準(例如對于寄存器 pa 001111 和pb 111000，兩個頁面，如果采用LRU，那么被淘汰的是pa，如果采用LFU那么被淘汰的是pb)。
7.???頁面緩沖算法PBA：置換的時候，頁面無論是否被修改過，都不被置換到磁盤，而是先暫留在內存中的頁面鏈表(已修改頁面鏈表和未修改頁面鏈表，也可以不區(qū)分)里面，當其再次被訪問的時候可以直接從這些鏈表中取出而不必進行磁盤IO，當鏈表中已修改也難數(shù)目達到一定數(shù)量之后，進行依次寫磁盤操作(相當于將多次IO合并為一次)
5. 鏈接
**靜態(tài)鏈接庫的優(yōu)點 **
·????????代碼裝載速度快，執(zhí)行速度略比動態(tài)鏈接庫快；
·????????只需保證在開發(fā)者的計算機中有正確的.LIB文件，在以二進制形式發(fā)布程序時不需考慮在用戶的計算機上.LIB文件是否存在及版本問題，可避免DLL地獄等問題。
動態(tài)鏈接庫的優(yōu)點
·????????更加節(jié)省內存并減少頁面交換；
·????????DLL文件與EXE文件獨立，只要輸出接口不變（即名稱、參數(shù)、返回值類型和調用約定不變），更換DLL文件不會對EXE文件造成任何影響，因而極大地提高了可維護性和可擴展性；
·????????不同編程語言編寫的程序只要按照函數(shù)調用約定就可以調用同一個DLL函數(shù)；
·????????適用于大規(guī)模的軟件開發(fā)，使開發(fā)過程獨立、耦合度小，便于不同開發(fā)者和開發(fā)組織之間進行開發(fā)和測試。
不足之處
·????????使用靜態(tài)鏈接生成的可執(zhí)行文件體積較大，包含相同的公共代碼，造成浪費；
·????????使用動態(tài)鏈接庫的應用程序不是自完備的，它依賴的DLL模塊也要存在，如果使用載入時動態(tài)鏈接，程序啟動時發(fā)現(xiàn)DLL不存在，系統(tǒng)將終止程序并給出錯誤信息。而使用運行時動態(tài)鏈接，系統(tǒng)不會終止，但由于DLL中的導出函數(shù)不可用，程序會加載失敗；速度比靜態(tài)鏈接慢。當某個模塊更新后，如果新模塊與舊的模塊不兼容，那么那些需要該模塊才能運行的軟件，統(tǒng)統(tǒng)撕掉。這在早期Windows中很常見。
?
總結
以上是生活随笔為你收集整理的操作系统：操作系统知识点总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 系统设计：负载均衡（负载均衡算法、转发实
- 下一篇： 操作系统：进程的三种状态