理工類專業(yè)課復習資料-操作系統(tǒng)期末復習資料(知識點匯總)

開放性理計算機系統(tǒng)資源、實現(xiàn)對計算機資源的抽象式、單道批處理系統(tǒng)、多道批處理系統(tǒng)、分時系統(tǒng)、實順序性：各道作業(yè)是順序進入內存，順序完成操作(類似隊列)行成一個隊列，稱為后備隊列；之后，由作業(yè)調度程序按一定的算法從后備隊列中選擇若干作業(yè)調入內存，共享CPU和系統(tǒng)資源。資源利用率高、系統(tǒng)吞吐量(單位時間內完成的總工作量)大、平均周轉時間(從作業(yè)進入系統(tǒng)，到完成并退出系統(tǒng)為止的時間)長，缺點在于無交互能力。O題，引入分時系統(tǒng)，可以將一臺計算機提供給多個用個終端較短時間內相應時間內完成對該事件的處理，并控制所有實時序。多用戶多任務利用進程的資源。進程是分配資源的基本單位，線程1度必然小于等于1/N。類似，空分復用實現(xiàn)虛擬，空間利用也小于等于1/N。進程，撤銷結束的進程，以及控制進程的狀態(tài)轉換互斥、進程同步兩種方式干作業(yè)調入內存，為其建立進程，使之成為就需進程，并間輯地址轉換為內存空間的物理地址設備分配：根據(jù)用戶進程的I/O請求，為之分配所需設備。設備處理：實現(xiàn)CPU與設備控制器之間的通信分配外存空間設計分為若干子功能，每個子功能為一個模塊，再進一步細分，使若干層，每層由若干模塊組成。各層之間只存在單向息，客戶機接受消息。此種模式實現(xiàn)了數(shù)據(jù)的分布存儲，便于2個操作完成后開始全部資源，不受外界影響初始條件相同，當程序重復執(zhí)行時，結果相同制約。將導去了再現(xiàn)性。即使執(zhí)行環(huán)境和初始條件相同，結果卻程由程序段，相關數(shù)據(jù)段和PCB三部分組成獨立性：進程實體可以獨立運行，獨立分配資源和獨立接受調度(線程)。而未建立PCB的。就緒狀態(tài)：進程已分配到除了CPU之外的所有必要資源，只要再獲得CPU，便可立即執(zhí)行。起。許可創(chuàng)建就緒I/0完成進程調度時間片完I/O請求執(zhí)行進程終止：首先等待操作系統(tǒng)進行善后處理，然后清空PCB，并將PCB空間返還系統(tǒng)。3進程狀態(tài)、進程優(yōu)先級、進程調度所需其他信息、事件(阻塞原因)。原語：由若干指令組成，用于完成一定功能的一個過程，是原子操作。在管態(tài)(核心態(tài))下進程才能在系統(tǒng)中運行，為了能讓程序運行，需要建立進程。引起正常結束、異常結束、外界干預(父進程請求，父進程終止，操作系統(tǒng)干預等)2.若該進程正處于執(zhí)行狀態(tài)，則立即終止其執(zhí)行，并置調度狀態(tài)為真，表示該進程被終止止進程的全部資源，或歸還父進程，或歸還操作系統(tǒng)5.將被終止進程的PCB從所在隊列中移出。在執(zhí)行的進程，發(fā)現(xiàn)阻塞事件時，由于無法繼續(xù)執(zhí)行，于是進程調用block為。進程的喚醒過程：首先將被阻塞的進程從等待隊列中移出，將其PCB中的現(xiàn)行狀態(tài)改為就B4掛起進程的狀態(tài)，若處于活動就緒狀態(tài)，便將其改為靜止就緒；對于存調入內存，檢查其現(xiàn)行狀態(tài)，若是靜止就緒，便改為活動就緒；若作臨界資源實例-生產(chǎn)者消費者/*#include<stdio.h>#defineMAX10typedefstructqueue{AXevoidproducer(queue&q,intdata){if(isfull(q)==1){//如果隊列為滿，生產(chǎn)者無法插入數(shù)據(jù)}else{ueqdata}}voidcustomer(queue&q){if(isempty(q)==1){//如果隊列為空，消費者取不到東西}else{intdata=outqueue(q);}}那段代碼稱為臨界區(qū)，臨界區(qū)前面需要增加一段用于沖突檢驗的代，在臨界區(qū)后面加上一段退出區(qū)代碼，用于將臨界區(qū)正被訪問的標5子操作wait(),signal()來訪問，即P，V操作。原子操作在執(zhí)行時不可中斷。voidwait(ints){while(s<=0)//當沒有資源可以利用時，等待;s=s-1;//當有資源時，使用。每使用一個，資源個數(shù)減一}voidsignal(ints){s=s+1;//釋放資源，資源個數(shù)加一}當信號量S<=0時，就會不斷檢測，未遵循讓權等待。因此，除了需要一個用于代表資源數(shù)//記錄型結構體typedefstructsemaphore{intvalue;//記錄資源個數(shù)structsemaphore*L;//鏈接等待進程phorevoidwait(semaphore&s){//value表示系統(tǒng)中某類資源數(shù)目，每次wait操作，系統(tǒng)中可供分配的資源數(shù)減一s.value=s.value-1;//value值可以一直減下去，為負數(shù)也可以，當為負數(shù)的時候，說明有進程自我阻塞了lueblock(s.L);//當沒有資源可用時，進程調用block將自己阻塞。}voidsignal(semaphore&s){valuesvalueif(s.value<=0)//若加一后，value值還是小于等于.則說明鏈表中還有阻塞的進程，需調用喚醒wakeup(s.L);}注：若value初值為1，表示只允許一個進程訪問臨界資源，此時的信號量化為互斥信號量Dtypedefstructsource{intarr[MAX];//source資源結構體，數(shù)組中存放每種資源的對應可用數(shù)目intlength;//總的資源種類數(shù)ce6voidsignal(source&s){for(inti=0;i<s.length;i++)s.arr[i]++;//一次性全部釋放}voidwait(source&s){agfor(inti=0;i<s.length;i++){if(s.arr[i]>=1)//判斷所需的全部種類資源是否都能夠分配給進程flag=1;else{flag=0;break;}}if(flag==1){//如果能，則一次性全部分配給相應的進程forinti0;i<s.length;i++)s.arr[i]--;}else{}}為了使多個進程能互斥地訪問謀臨界資源，只需為該資源設置一互斥信號量mutex(資源個操作之間。在使用信號量實現(xiàn)互斥時，wait操作和signal操作需要成對出現(xiàn)。結構，對該數(shù)據(jù)結構進行操作的一組過程，對管publicclassMonitor{public};emonitornamevoidinit_value();voiduse_value();voidpublic_use_value();7題voidinit(semaphore&s){emptyMAXsfull;s.mutex=1;}//這些操作都可以循環(huán)執(zhí)行，如下的只是他們的一次活動voidproducer(queue&q,semaphore&s){wait(s.empty);//先執(zhí)行對資源信號量的操作wait(s.mutex);//再執(zhí)行對互斥信號量的操作eqdatanalsmutexlsfull}voidcustomer(queue&q,semaphore&s){waits.full);wait(s.mutex);ueqnalsmutexalsempty}的號量的P,V操作也要成對出現(xiàn)。每個程序的多個P,V操作必須成對出現(xiàn)。其次，對于資源信Dtex用Swait(full,mutex);替換/采用循環(huán)隊列方式，假設有N==5個哲學家，//所有信號量初始化為，第i為哲學家一次的活動方式如下，可以循環(huán)執(zhí)行如下活動voidprofess(semaphore&s){//采用記錄型方式wait(s.chopstick[i]);//拿左邊的筷子wait(s.chopstick[(i+1)mod(s.n)]);//拿右邊的筷子gnalschopstickisignalschopsticki)mod(s.n)]);k8}voidprofess(semaphore&s){//采用AND信號量方式kSwaitschopstickischopsticki1)mod(s.n));Ssignalschopstickischopsticki)mod(s.n)]);}置了一個互斥信號量Wmutex,另外，再設置一個voidinit(semaphore&s){s.rmutex=1;s.wmutex=1;sreadcount;}voidreader(semaphore&s){wait(s.rmutex);//判斷有沒有其他讀者dcountwait(s.wmutex);//有沒有作者正在寫s.readcount++;//沒有，則讀者數(shù)加一read;//閱讀wait(s.rmutex);//判斷有沒有其他讀者s.readcount--;readcountsignal(s.wmutex);//只有當沒有讀者時，才執(zhí)行此操作，為寫操作提供資源nalsrmutex}voidwriter(semaphore&s){waits.wmutex);writelswmutex}9建立建程。基本單位、可并發(fā)執(zhí)行、共享進程資源程。效率較高，但如果一個線程執(zhí)行阻塞，其他線程三處理機調度和死鎖才能得到，這些步驟叫做作業(yè)步(jobstep)。的編譯、連接裝配(將若干程序段裝配為可執(zhí)行程序)、運行(目標程序調入內存)流。作業(yè)控制塊JCB：銷JCB。于調度算法。最簡單的2.低級調度(進程調度)：調度算法選取進程、把處理器分配給進程列入分派程序的上下文，以便分派程序運行。在第二對上下2．短作業(yè)(進程)優(yōu)先原則：當新到達的作業(yè)(進程)比正在執(zhí)行的作業(yè)(進程)明顯短時，將暫停當前長作業(yè)(進程)的執(zhí)行，使短作業(yè)優(yōu)先執(zhí)行。3中級調度(中程調度)：開始，到作業(yè)完成的這段時間間隔。包括四部分，作業(yè)在就緒隊列上等待調度時間，進程執(zhí)行時間，以及進程等待I/O操作完成的時間。T=sT=信息傳送到處理機的時間，處理機對請求信息進行處理的時開始執(zhí)行的最晚時間，或必須完成的最晚時間個重要指標先來先服務FCFS調度算法：FCFS算法有利于長作業(yè)(進程)，而不利于短作業(yè)(進程)。有利于而不利于I/O繁忙型的作業(yè)。短作業(yè)(進程)優(yōu)先SJ(P)F調度算法：進程類型、進程對資源的需求、用戶要求優(yōu)先權=(等待時間+要求服務時間)/要求服務時間=(響應時間)/要求服務時間CPU并令其執(zhí)行一個時間片，當執(zhí)行的時間片用完，由FCFS算法排隊等待調度，。若其未能完成，則調度程序將其轉到下一個隊列的隊尾，同樣按FCFS方式等待調度。如此繼續(xù)下去。當一個長進程或長作業(yè)從第一個隊列依此降至第n個隊列后，在第n個隊列中便采用按時間片輪轉方僅當?shù)?-(i-1)隊列均空時，才會調度第i個隊列的進程運行。若處理機正在第i個隊列奪性資源。前者指進程在獲得這類資源后，該。例如，系統(tǒng)中只有一個打印機和一個磁帶機，供兩個進程共享。若A進程已占用了打印塞；若A有要求磁帶機，則A也阻塞。因而兩者都等待對方的資源，但它們又因為阻塞。能產(chǎn)生死鎖ELEASESELEASESELEASES環(huán)路等待條件：指發(fā)生死鎖時，必然存在一個進程-資源的環(huán)形鏈。必要條件中的一個或幾個條件分配過程中，用某種方式阻止系統(tǒng)進入不安全狀態(tài)不檢測系統(tǒng)是否進入不安全區(qū)，而是通過檢測機制，及時檢測出。#defineMAX10/*置的該類全部可用資源的數(shù)目。如果MAXn個進程對iRjavaliablejk則表示k分配矩陣allocation[i][j]=k,表示進程i當前獲得的資源Rj有k個needijkiRj類資源k個dijMaxijAllocationijtypedefstructbank{intavaliable[MAX];//可利用資源向量intMax[MAX][MAX];//最大需求矩陣intAllocationMAXMAX/分配矩陣intneed[MAX][MAX];//需求矩陣設request_i是進程Pi的請求向量，如果request_i[j]=k,表示進程Pi需要K個Rj類requestijneedij轉向2，否則認為出錯。2)若request_i[j]<=avaliable[j],則轉向3，否則認為出錯3)系統(tǒng)分配資源給進程，并修改數(shù)據(jù)結構中數(shù)據(jù)Avaliable[j]=avaliable[j]-request_i[j];Allocation[i][j]=allocation[i][j]+request_i[j];jneedijrequestijvoidallocate(bank&ba,intrequest[][MAX],inti,intj){ifrequestijbaneedi][j]){if(request[i][j]<=ba.avaliable[i][j]){資源分配baavaliableijbaavaliableijrequestij];baAllocationijbaAllocationijrequestij;baneedijbaneedijrequestij];}}}work類資源數(shù)目，初始，work=lable量Finish，表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。初始，voidcheck(bank&ba,intwork[],boolfinish[],inti,intj){if(finish[i]==false&&ba.need[i][j]<=work[j]){Pi未結束，其所需資源系統(tǒng)可以滿足它的資源。workj]=work[j]+ba.Allocation[i][j];finish[i]=true;}else{if(finish[i]==true)終止}}死鎖檢測可以利用資源分配圖來描述。該圖由一組節(jié)點N和一組邊E所組成的一個對偶把N分為兩個互斥的子集，即一組進程節(jié)點P和一組資源節(jié)點R，N=P并R。凡是屬于E的邊，都連接著jR1R2源點統(tǒng)處于S狀態(tài)時是否為死鎖狀態(tài)。方法為：在資源分配圖中，找一個既不阻塞又非獨立的進程節(jié)點Pi,在順利的情況下，Pi可以獲得所需資源而繼續(xù)運行，直至運行完畢，再釋放其所占的所有資源，相當于消去Pi如上圖，將P1兩個分配邊和一個請求邊消去，留下一個孤立的P1節(jié)點。這樣，圖中所有的資源由P2使用，當P2獲得資源并執(zhí)行完畢后，將P2的邊也刪去。利用這用簡化方式，如進程四存儲器結構一個可在內存中執(zhí)行的程序，首先要編譯，由編譯程序將源程序鏈接程序將編譯后的目標模塊，以及所需庫函數(shù)鏈接起知道程序將駐留在內存的什么位置，則，編譯程序將產(chǎn)生絕將各自目標模塊及其所需庫函數(shù)，鏈接成一個裝入模塊，以后CALLC語句。欲將A,B,C裝配成一個裝入模塊。需要修改兩個東西：)對相對地址進行修改2)變換外部調用符號，將調用符號換成相對地址0塊ACALLBL-10模塊AJSRL0M-10L-1L模塊BCALLCL+M-1模塊C模塊BJSRL+M模塊CN-1L+M+N-1次適應FF算法：空閑分區(qū)為止，然后再按照作業(yè)的大小，從該分區(qū)中劃，不再是每次都從鏈首開始查找，而是從上一次找到的空閑分塊滿足要3)最佳適應BF算法：4)最壞適應WF算法：，總是挑選一個最大的空閑分區(qū)分割給作業(yè)，優(yōu)點在于可5)快速適應QF算法：大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨存在多個空閑分區(qū)鏈表，同時在內存中設立一張閑分區(qū)類型，并記錄該類型空閑分區(qū)鏈表頭中，主要操作是分配內存和回收內存，無論分配分區(qū)還是空閑分區(qū)，分區(qū)大小均為序，緊湊后的用戶程序在內存中的位置發(fā)生改變，因此，需要重和>=請求區(qū)進行緊湊形成連續(xù)空閑區(qū)按動態(tài)分區(qū)方式進行分配修改有關數(shù)據(jù)結構修改有關數(shù)據(jù)結構別稱之為。內碎片”。頁面大小一般為2的冪。分頁地址由頁號，偏移量(頁內地址)組成。如下例：位移量若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號和頁內地址D為：D=[A]MODL將頁表地址與頁號和頁表項長度的乘積相加(即，基地址+偏移量)得到該表項在頁表中的CPU構自動將頁號送入快表，并將此以32位邏輯空間為例，當頁面大小為4KB(12位)，若采用一級頁表結構，對應(32-12)20位的頁號。若采用二級頁表，則需要對頁表分頁，外層頁表中的頁內地址為10位，外層頁號也為10位。頁表的首表結構的情況下，對于正在運行的進程，必須將1)方便編程：用戶把作業(yè)按照邏輯關系劃分為若干段，每段從0開始編址2)信息共享：分頁系統(tǒng)中的頁只存放信息的物理塊，無完整意義，而段是信息的邏輯單位3)信息保護4)動態(tài)增長：處理數(shù)據(jù)段的動態(tài)增長5)動態(tài)鏈接：只有當目標程序運行過程中，才將某段目標程序調入內存并鏈接少個段，段內地址顯示出段的大小項，物理地址=