操作系統(tǒng)：12第十三章 UNIX操作系統(tǒng)（1）

1、第十三章 UNIX操作系統(tǒng)歷史回顧(Historical Perspective)系統(tǒng)結(jié)構(gòu)(System Structure) 進(jìn)程管理(Process Management)存儲管理(Memory Management)文件系統(tǒng)(File System)設(shè)備管理(Device Management)系統(tǒng)調(diào)用(System Calls)外殼語言(Shell)13.1 歷史回顧1969年由美國Bell實驗室的兩名程序員K.Thompson和 D.M.Ritchie設(shè)計 ; 最初該系統(tǒng)是采用匯編語言編寫的 .incorporated features of other operating syst

2、ems, especially MULTICS.后來二人專門為UNIX設(shè)計了C語言,并用它重新改寫了UNIX中的大部分源代碼, 形成第三版 .13.1 歷史回顧在70年代初期, UNIX在Bell實驗室及許多大學(xué)中獲得了廣泛的應(yīng)用, 這也促進(jìn)了UNIX系統(tǒng)的進(jìn)一步發(fā)展 .1973年推出第五版1976年推出第六版1978年第七版正式發(fā)行 .由于UNIX結(jié)構(gòu)良好,并被迅速地移植到Interdata 8/32及VAX等機器上 第1版（1971）第3版（1973）第6版（1975）第7版第8版第9版SVR4（1989）IBM AIXSystemIII(1982)SystemV(1983)SVR2（19

3、84）SVR3（1987）1BSD（1978）2BSD（1978）3BSD（1979）4.0BSD（1980）4.4BSD（1993）Sun Solaris第10版發(fā)展與版本:13.2系統(tǒng)結(jié)構(gòu) 系統(tǒng)進(jìn)程（#1），shell，shell，其它用戶進(jìn)程核外 內(nèi)核socket文件子系統(tǒng)進(jìn)程控制網(wǎng)絡(luò)協(xié)議設(shè)備文件目錄與普通文件虛擬存儲系統(tǒng)RawIO字符緩沖高速緩沖 頁緩沖網(wǎng)絡(luò)設(shè)備驅(qū)動字符設(shè)備驅(qū)動塊設(shè)備驅(qū)動內(nèi)存管理處理機調(diào)度，同步機制硬件路由選擇終端終端UNIX系統(tǒng)組成 內(nèi)核部分 內(nèi)核由兩類模塊構(gòu)成 被動的, 即普通模塊 主動的, 即進(jìn)程模塊 普通模塊 進(jìn)程控制文件管理存儲管理設(shè)備管理原語管理中斷處理處理

4、機管理系統(tǒng)初啟 內(nèi)核部分進(jìn)程模塊 process #0交換進(jìn)程(sched)process #1初始進(jìn)程(init) 交換進(jìn)程及初始進(jìn)程是兩個系統(tǒng)進(jìn)程, 它們運行操作系統(tǒng)核心程序, 完成操作系統(tǒng)的某些功能. 外殼部分 外殼部分運行命令解釋程序, 讀入、解釋并處理終端用戶鍵入的命令. 將命令解釋程序由操作系統(tǒng)核心中分離出來的好處在于: 縮減操作系統(tǒng)內(nèi)核的規(guī)模 不同用戶可以使用不同的外殼 13.3 進(jìn)程管理進(jìn)程組成進(jìn)程控制塊進(jìn)程狀態(tài)與狀態(tài)轉(zhuǎn)換進(jìn)程調(diào)度進(jìn)程互斥進(jìn)程同步進(jìn)程通訊13.3.1 進(jìn)程組成(映像)Proc 結(jié)構(gòu)Text結(jié)構(gòu)系統(tǒng)空間用戶空間User結(jié)構(gòu)系統(tǒng)棧進(jìn)程堆棧進(jìn)程數(shù)據(jù)進(jìn)程代碼常駐內(nèi)存部分

5、內(nèi)外存交換部分系統(tǒng)空間13.3.2 進(jìn)程控制塊Proc結(jié)構(gòu)所保存的信息無論當(dāng)進(jìn)程在內(nèi)存時還是在外存時都是需要的 . User結(jié)構(gòu)所保存的信息僅當(dāng)進(jìn)程在內(nèi)存時才是需要的, 因而可以與進(jìn)程的程序一起被移到外存.struct proc char p_stat; char p_flag; char p_pri; char p_sig; /signal received char p_uid; /user id char p_time; /resident time for scheduling char p_cpu; /cpu usage char p_nice; /nice for scheduli

6、ng char p_ttyp; /controlling tty int p_pid; /unique process id int p_ppid; /parent process id int p_addr; /address of swappable image int p_size; /size of swappable image (*64bytes) int p_wchan /event process is waiting int *p_textp; /pointer to text structure struct user int u_rsav2 int u_fsav25 ch

7、ar u_uid; / effective user id char u_gid; / effective group id char u_ruid; / real user id char u_rgid; / real group id int u_procp; / pointer to proc structure int *u_base; / base address for IO int *u_count; / bytes remaining for IO int *u_offset2; / offset in file for IO int *u_cdir; / pointer to

8、 inode of current dir int *u_pdir; / inode of parent directory int u_uisa16; / prototype segmentation address int u_uisd16; / prototype segmentation descript int u_ofileNOFILE; / pointers to file struct int u_arg5; / arguments to system call int u_tsize; / text size (*64) int u_dsize; / data size (*

9、64) int u_sszie; / stack size (*64) int u_utime; / this process user time int u_stime; / this process system time int u_cutime2; / child process user time int u_cstime2; / child process system time struct text int x_daddr; /disk address of segment int x_caddr; /core address if loaded int x_size; /*6

10、4 int *x_iptr; /inode of prototype char x_count; /reference count char x_ccount; /number of loaded references13.3.3 進(jìn)程狀態(tài)及其轉(zhuǎn)換p_statedefine null 0define SSLEEP 1define SWAIT 2define SRUN 3define SIDL 4define SZOMB 5define SSTOP 6p_flagdefine SLOAD 01define SSYS 02define SLOCK 04define SSWAP 010define

11、STRC 020define SWTED 040 Subset of : p_state p_flag system mode進(jìn)程狀態(tài)及其轉(zhuǎn)換換出結(jié)束跟蹤結(jié)束跟蹤換入/出換出喚醒fork處理機分派跟蹤等待終止置PSWSRUNLOADuserSRUNLOADkernelSIDL中斷睡眠換出喚醒內(nèi)存夠內(nèi)存不夠SZOMBSSLEEPLOADSWAITLOADSRUNLOADSSTOPLOADSSLEEPSWAPSWAITSWAPSRUNSWAPSSTOPSWAP喚醒結(jié)束跟蹤喚醒結(jié)束跟蹤13.3.4 進(jìn)程調(diào)度調(diào)度策略Dynamic Priority based （Low number high pri

12、ority）PreemptiveAging (no starvation)調(diào)度算法USER：100p_cpu：運行進(jìn)程，每20ms加1; 其它進(jìn)程，每1200ms減10p_nice: 用戶進(jìn)程：020，系統(tǒng)進(jìn)程：-2020進(jìn)程調(diào)度實現(xiàn)進(jìn)程P(用戶態(tài))進(jìn)程P(核心態(tài))進(jìn)程(核心態(tài))進(jìn)程(用戶態(tài))中斷中斷處理調(diào)度上下文切換置PC,PSW13.3.5 進(jìn)程互斥經(jīng)典UNIX系統(tǒng)機制關(guān)中斷互斥(提高處理機優(yōu)先級)特點簡單開銷小影響并發(fā)性關(guān)中斷后代碼很短13.3.6 進(jìn)程同步進(jìn)程同步:當(dāng)一個進(jìn)程因某種原因不能繼續(xù)運行時, 它便等待在某一個事件上, 即將等待事件記在p_wchan變量上，進(jìn)入SWAIT或SS

13、LEEP狀態(tài) 當(dāng)對應(yīng)事件發(fā)生時，系統(tǒng)喚醒等待于該事件上的所有進(jìn)程 競爭條件 :事件發(fā)生可能先于等待 .事件將被丟失 .忙式等待被喚醒進(jìn)程可能再次等待13.3.7 進(jìn)程通訊信號 (signal) From process to processFrom event to process管道(pipe) Unnamed fileNamed pipesocket通訊 Endpoint communicationSuitable for networkFew UNIX systems permitted shared memory because the PDP-11 hardware did not

14、encourage it信號(signal)特點簡單信號(類似軟中斷，共20個)異步通訊信號來源異步事件key board interrupt, error, timer, etc. 進(jìn)程，系統(tǒng)調(diào)用(如kill)from process to process, or from terminal to process使用信號處理程序的定義信號的發(fā)送與接收信號的處理信號(signal)信號處理程序的定義系統(tǒng)調(diào)用signal(sig,func)預(yù)置，其中sig為019的信號值，func為處理程序的地址該系統(tǒng)調(diào)用的作用是u_signalsig=func.當(dāng)func為0時接收信號進(jìn)程終止自己；當(dāng)func

15、為奇數(shù)時忽略信號；func為偶數(shù)時為處理程序入口進(jìn)程初創(chuàng)時自動繼承其父進(jìn)程的信號處理程序 信號(signal)信號的發(fā)送與接收進(jìn)程實際接收到的信號被記載在p_sig中由于p_sig常駐內(nèi)存，因而在任何時刻均可接受到信號. 信號可能來自進(jìn)程，也可能是事件，如鍵盤中斷信號、錯誤、定時器處于等待狀態(tài)的進(jìn)程在接收到信號后一般將被喚醒 信號(signal)信號的處理接收到信號的進(jìn)程在適當(dāng)時刻(被調(diào)度選中由核態(tài)轉(zhuǎn)到目態(tài))，發(fā)現(xiàn)p_sig中記錄有接收到的信號，根據(jù)u_signalp_sig的值確定對信號的處理. 接收信號的進(jìn)程也可以忽略信號(u_signalp_sig=奇數(shù)). 對多數(shù)信號的缺省處理動作是終

16、止收到信號的進(jìn)程. 信號很象允許用戶程序在目態(tài)處理的中斷.管道(Pipe)特點經(jīng)典UNIX最有特色的通訊機制；單方向，流式通訊；建立在文件基礎(chǔ)上，與文件界面統(tǒng)一；實現(xiàn)極為簡練；速度問題：為防止兩次I/O傳輸限制pipe文件大小(4塊)緩沖技術(shù)延遲寫管道(Pipes) 使用方法：先創(chuàng)建管道，再創(chuàng)建進(jìn)程繼承int fd2;pipe(fd)p1=fork(); p2=fork();p1: write(fd1,); p2:read(fd0,)套接字(socket)端-端通訊機制(endpointendpoint)類型Stream sockets Sequenced packet socketsData

17、gram sockets Reliably delivered message socketsRaw sockets套接字(socket)地址域使用中的socket與一地址相聯(lián)系 地址的形式由通訊域(communication domain)確定.同一域中的進(jìn)程使用相同地址格式address format4.3BSD域UNIX domain (AF_UNIX)the Internet domain (AF_INET)the XEROX Network Service (NS) domain (AF_NS)13.4 存儲管理經(jīng)典UNIX存儲管理 一個進(jìn)程兩個對界Text(共享)Data(私用)內(nèi)

18、外存不同尺寸，同一管理程序(FF算法）Core: 64bytesswap: 512bytes交換技術(shù)swapping 13.4.1存儲管理方式 采用界地址存儲管理方式一個進(jìn)程由兩個對界組成, 即占有兩個連續(xù)的內(nèi)存區(qū)域 一個區(qū)域用于保存共享代碼另個區(qū)域用于保存私用數(shù)據(jù)及用戶堆棧 存儲分配的基本單位是64個字節(jié), 而不是單個字節(jié) 13.4.2 存儲分配算法 內(nèi)存空間及外存交換區(qū)的分配均是動態(tài)的, 分配算法為最先適應(yīng)(FF). 描述內(nèi)存空間及外存空間分配狀況各需有一個數(shù)據(jù)結(jié)構(gòu).內(nèi)存的分配與外存的分配共用同一個程序.13.4.3 進(jìn)程空間擴充堆棧分配基本長度，避免浪費堆棧溢出動態(tài)擴展申請一個新的數(shù)據(jù)區(qū)

19、(原區(qū)域大小增加大?。?fù)制釋放原有區(qū)域內(nèi)存不夠交換到外存(同時擴展空間）釋放所占內(nèi)存再次由sched調(diào)入內(nèi)存時，按新長度13.4.4 交換技術(shù)(swapping)交換目標(biāo)：緩解內(nèi)存緊張矛盾交換進(jìn)程：sched(#0)交換算法移入外存中SRUN狀態(tài)進(jìn)程如內(nèi)存不夠，選擇移出內(nèi)存中處于SWAIT或SSTOP狀態(tài)進(jìn)程如還不夠，選擇移出內(nèi)存中處于SSLEEP或SRUN狀態(tài)進(jìn)程，條件待移入進(jìn)程在外時間=3秒待移出進(jìn)程在內(nèi)時間=2秒13.4.5 虛擬頁式(Paging) 4.3BSD UNIX: demand-paging + swapping主要依賴(first paging)其次是交換(secondar

20、y swapping).偷頁進(jìn)程(Page stealer process)動態(tài)跟蹤并調(diào)整進(jìn)程頁架數(shù)基于工作集模型(working set model).If the scheduler decides that the paging system is overloaded, processes will be swapped out whole until the overload is relieved.頁面置換pagedaemon processUses a modified second-chance replacement algorithm.Second chance: a va

21、riant of NUR. 8/11/02/06/14/15/07/03/1Set page 3,4reference bit to 0,replace page 50頁面置換pagedaemon processUses a modified second-chance replacement algorithm.Second chance: a variant of NUR. 8/11/02/06/14/15/07/03/1Set page 3,4reference bit to 0,replace page 500頁面置換pagedaemon processUses a modified

22、second-chance replacement algorithm.Second chance: a variant of NUR. 8/11/02/06/14/15/07/03/1Set page 3,4reference bit to 0,replace page 510013.5 UNIX文件系統(tǒng)文件類型文件體系文件結(jié)構(gòu)文件目錄文件系統(tǒng)映射文件卷安裝磁盤空間管理Inode區(qū)管理快速文件系統(tǒng)NFS文件系統(tǒng)13.5.1 文件類型普通文件內(nèi)容可以是程序、數(shù)據(jù)、圖象等，保存在磁盤塊中目錄文件(文件名，文件號)序列，保存在磁盤塊中特殊文件設(shè)備設(shè)備作為文件管理的好處界面統(tǒng)一，使用文件與使用設(shè)備命

23、令相同，申請設(shè)備open, 釋放close, 讀read, 寫write利用文件保護(hù)功能可以保護(hù)設(shè)備13.5.2 文件體系基本結(jié)構(gòu)：樹型系統(tǒng)目錄，系統(tǒng)文件用戶目錄，用戶文件連接(link)不是真正的樹，而呈格結(jié)構(gòu)連接方便文件共享13.5.3 文件結(jié)構(gòu)邏輯結(jié)構(gòu)流式文件，字節(jié)序列讀寫命令中包含字節(jié)數(shù)read(fd,buf,count)其中count為傳輸字節(jié)數(shù)模擬記錄式文件物理結(jié)構(gòu)直接與間接0級，1級，2級，3級間接尋塊13.5.4 文件目錄與連接目錄項相當(dāng)FCB次部形式為(文件名，文件號)Inode相當(dāng)于FCB主部每個inode有一個i_number多個文件名對應(yīng)同一個i_number（連接共享

24、）連接實現(xiàn)userswanglif1f2i_number=15f2 15f1 15link(“/users/wang/d1/f1”, “/users/li/f2”)d1read(4,)read(4,)write(2,)用戶空間u_ofileu_ofilefilei_node磁盤空間系統(tǒng)空間.數(shù)據(jù)塊.i_list13.5.5 文件系統(tǒng)映射相關(guān)表目1. u_ofile (每進(jìn)程一個)struct user int u_ofileNOFILE; #define NOFILE 15 2. file (系統(tǒng)一個)struct file char f_flag; /R,W,PIPE char f_coun

25、t; int f_inode; char *f_offset2;fileNFILE#define NFILE 1003. Inode表(系統(tǒng)一個)struct inode int i_flag; char i_count; char i_dev; char i_number; char i_mode; char i_nlink; char i_uid; char i_gid; char i_size0; char *i_size1; int i_addr8; int i_lastr;inodeNINODE;表間聯(lián)系：u_ofile file (n) (1)file inode (n) (1)相

26、關(guān)表目13.5.6 文件卷的安裝mount：用一個文件卷的根目錄取代一個已經(jīng)存在的空目錄節(jié)點UNIX文件卷0 1 2 k k+1 n-1導(dǎo)引塊特殊塊 inode區(qū)域每塊16個inode, 從0起依次編號 文件存儲區(qū)域(普通文件,目錄文件)超級塊塊1#(super block)： (1) 記載文件卷上k+1塊到n-1塊中所有空閑塊， (2) inode區(qū)中100個空閑inode. (緩沖) 文件安裝(mount)后超級塊讀入內(nèi)存。注：占用區(qū)域已經(jīng)記載在各個文件的inode中。Struct filesys int s_isize; /size in blocks of i list int s_f

27、size; /size in blocks of entire volume int s_nfree; /number of in core free blocks int s_free100; /in core free blocks int s_ninode; /number of in core I list int s_inode100; /in core free I nodes char s_flock; /free list locking char s_ilock; /i list locking char s_fmod; /super block modified flag

28、char s_ronly; /mounted read only flag char s_time2; /current date of last update int pad50;超級塊結(jié)構(gòu)（安裝后讀入內(nèi)存，卸下時回寫磁盤）13.5.7磁盤空間管理 ：100個空閑塊為一組，組之間相互鏈接。s_nfree=100s_free0s_free1.s_free99.Super block .特點：速度快，空間省。13.5.8 空閑inode管理：s_inode最多可以記載100個空閑inode(編號)申請時： (1) s_ninode0, 取s_inode-s_ninode; (2) s_ninod

29、e=0, 由磁盤inode區(qū)順取100個空閑I節(jié)點(i_nlink=0) 將其編號填入s_inode表中，修改s_ninode，然后分配。釋放時： (1) s_ninode100, s_inodes_ninode+=i_number (釋放的); (2) s_ninode=100, 丟棄。13.5.9 快速文件系統(tǒng)經(jīng)典UNIX文件系統(tǒng)Inode區(qū)與內(nèi)容存儲區(qū)相分離查找速度慢(引臂在inode區(qū)與塊存儲區(qū)之間往復(fù)移動，尤其長路徑名）文件長度大于5120字節(jié)：間接尋塊文件名長度14字節(jié)以內(nèi)Fast File System(FFS)1984UC Berkeley被許多現(xiàn)代UNIX采用，包括4.3BSD效率提高一個數(shù)量級13.5.9 快速文件系統(tǒng)快速文件系統(tǒng) FFS將磁盤卷劃分為若干個柱面組(cylinder group)，每個柱面組占若干連續(xù)的柱面，作為相對獨立的文件卷管理 FFS采用較大的磁盤塊以減少I/O間址并提高I/O效率 (達(dá)8KB)FFS打破了文件名長度最多為14字節(jié)的限制，文件名長度可達(dá)255字節(jié) FFS支持符號連接(symbolic link)，這種連接可以跨文件卷或主機 13.5.9 快速文件系統(tǒng)UNIX 4.3BSD柱面組 數(shù)據(jù)塊 數(shù)據(jù)塊 Super block Cylinder block Inode 13.5.10 NFS網(wǎng)絡(luò)文件系統(tǒng)NFS體系結(jié)構(gòu)每個站點