文件管理&磁盤
1.文件系統的層次結構: 對象及其屬性，操縱管理的軟件集合，文件系統接口。
2.文件的結構分為有結構(記錄型)和無結構(字節流型)；有結構文件分為順序文件，索引文件，索引順序文件,直接文件和哈希文件。順序文件有串結構，順序結構。有結構文件也可分為定長/不定長記錄文件。
3.目錄管理的要求: 1.實現按名存取2.提高目錄檢索速度3.文件共享4.允許文件重名。
4.目錄的形式有: 單級文件目錄，多級，樹型，DAG；
5.影響文件安全性的因素: 人為因素，系統因素，自然因素；
6.分別采用存取控制機制.系統容錯技術，后備系統來分別解決上述不安全因素。
7.訪問矩陣中增加拷貝權，所有權，控制權來實現有控制的更改訪問矩陣。
8.訪問矩陣可以用訪問控制表(按對象(文件)劃分)與訪問權限表來實現(按域(user/process)劃分)。
9.文件保護的方法: 口令，密碼，訪問權限表。
10.文件共享的方法 : 利用索引節點(硬鏈接)，符號鏈接(軟連接) (文件被刪除時，鏈接失效)。
11.目錄查詢的方法有: 線性檢索法， 哈希法。
11.1 在順序檢索的查找過程中，只要有一個文件分量名未能找到，便應停止查找。
12.磁盤的分配組織方法：順序，鏈接(隱式，顯式(FAT))，索引(鏈接，多級，混合索引(Unix))
13.磁盤空閑區的管理方式: 空閑表，空閑鏈表(塊，區)，位圖法，成組鏈接(Unix)；
14.位圖法: 從0開始編號: i = k/n ; j = k%n ; ?從1開始: i = (k-1)/n + 1 ; j = (k-1)%n + 1
15.提高磁盤IO速度的方式: 磁盤緩存，提前讀，延遲寫，優化物理塊布局，虛擬盤，RAID
16.文件在使用前必須先執行OPEN操作，其主要功能是把文件的FCB從外存拷貝到內存，并在用戶和指定文件之間建立一條通路，再返回給用戶一個文件描述符。
16.1 Open,Close操作提高了文件訪問的速度，無需再檢索，通過文件描述符直接找到內存中的文件FCB，可以取消顯式的open,close操作，但增加系統開銷。
17.在樹型目錄結構中，用戶對文件的首次訪問通常都采用文件路徑名，文件被打開后，對文件的訪問通常采用文件描述符，打開文件操作完成的主要工作是把指定文件的目錄項(FCB)復制到內存指定的區域。
18.利用Hash法查找文件時，如果目錄中對應的目錄項是空，則表示系統中無指定文件名，如果目錄項中的文件名與指定的文件名匹配，則表示找到了指定文件，如果目錄項中的文件名與指定的文件名不匹配，則表示發生了沖突。
19.在目錄文件中每個目錄項通常就是FCB，在Unix系統中目錄項則是文件名及其索引結點指針。?(文件名與文件描述信息相分離，減少目錄所占磁盤塊數，加快檢索目錄的速度)
20.引入索引節點后，一個文件在磁盤中占有的資源包括 目錄項，索引節點，數據塊三部分。
21.在樹形目錄結構的文件系統中，根節點表示根目錄，枝節點表示子目錄文件，葉子節點表示數據文件。
22.在執行close過程中，若系統打開文件表項引用計數f.count ≠0(多少進程打開了該文件)，則應置用戶文件描述符表項為空；若f.count = 0但內存索引節引用計數i.count ≠ 0，則應使用戶文件描述符表項和文件表項皆為空。若i.count =0則應關閉文件。
23.在create過程中，若未檢索到指定文件的索引節點，此時屬于新建文件，；檢索到指定文件的索引節點，此時若允許寫，則此時為重寫文件，否則是出錯。
24.FAT表項通常取半個字節的整數倍。
25.在隱式鏈接分配中，每個盤塊要留出幾個字節來放下一個盤塊號，FAT表項里面存儲的內容即是下一盤塊號。
26.對于一個文件的訪問常由用戶訪問權限和文件屬性共同確定。
27.Unix操作系統中，輸入輸出設備被看做是特殊文件。
28.加密保護機制更安全，訪問控制表更靈活，必須由系統實現。
29. 目錄項 = FCB (Unix 文件名+索引接點指針)
30.硬鏈接不可以直接刪除文件(count --,除非為0)，軟鏈接可以直接刪除(鏈接無效)
31.可順序存取的文件不一定能隨機存取(鏈式)，可隨機存取的文件不一定能順序存取(索引結構文件)
輸入輸出系統，設備管理
IO軟件的層次結構:(硬件，IO控制器),中斷處理程序(ISR)，設備驅動程序，設備獨立性軟件，用戶層IO軟件。為什么引入緩沖區: 緩和CPU和IO設備速度不匹配的矛盾；減少CPU的終端頻率；提高CPU與IO設備之間的并行性。為實現設備分配，應為每一個設備設置一張設備控制表DCT,為控制器設置一張COCT,為通道設置一張CHCT，在系統中設置一張系統設備表SDT。為實現設備無關性，系統中應設置一張邏輯設備表LUT。SPOOLing是對脫機IO的模擬，SPOOLing系統中的輸入井是對脫機輸入中的磁盤進行模擬，輸出井是對脫機輸出中的磁盤進行模擬，輸入進程是對脫機輸入中的外圍控制機進行模擬，輸出進程是對脫機輸出中的外圍控制機進行模擬。虛擬設備是指把一個物理設備變換為多個對應的邏輯設備。SPOOLing技術是指在多道程序環境下，利用多道程序中的一道或者兩道程序來模擬脫機輸入輸出中的外圍機的功能來達到脫機輸入輸出的目的。即在聯機的狀態下，將數據從輸入設備輸入傳送到磁盤或從磁盤傳送到輸出設備。SPOOLing技術是對脫機輸入輸出的模擬，必須建立在多道程序系統之上，而且還需要得到高速隨機外存(通常為磁盤的支持)，SPOOLing技術主要有1.輸入/輸出井(Disk)2.輸入/輸出緩沖(Memory)3.輸入進程輸出進程4.井管理程序四部分構成。SPOOLing系統中，用戶程序可以隨時將輸出數據放在輸出井中，待輸出設備空閑時再執行數據輸出操作。 輸出先放在磁盤輸出井，而不是內存。在實現后臺打印時，SPOOLing系統中的輸出進程，只為請求IO的進程做兩件事情：第一為之在輸出井中申請空閑空閑緩沖區，并把要打印的數據送入其中，第二為用戶申請一張用戶打印申請表，并把用戶的打印要求填入其中，再把該表填在假脫機文件隊列中。設備獨立性是指用戶程序獨立于物理設備。為了實現設備獨立性，應設置邏輯設備表LUT，通常包括邏輯設備名，物理設備名，設備驅動程序入口地址。設備驅動程序是進程和設備控制器之間的通信程序，它將上層發來的抽象IO請求轉換為對IO設備的具體命令與參數，并把它裝入到設備控制器中的命令和參數寄存器中，或相反。設備控制器是CPU和IO設備之間的接口，它接受CPU的IO指令，并用于控制IO設備的工作。(設備控制器，或適配器Adapter，也稱作控制卡，接口卡，網卡就是設備控制器)通道是一種特殊的處理機，具有執行IO指令集的能力，主機的CPU和通道可以并行工作，并通過IO指令和IO中斷來實現通信與同步。通道類型有字節多路通道，數組選擇通道，數組多路通道。四級: CPU -> IO通道->IO控制器->IO設備。一次磁盤訪問由尋道時間,旋轉時間.數據傳輸時間組成。其中尋道時間所占比重比較大。SSTF平均尋到時間較短，但容易產生饑餓。SSTF/SCAN/CSCAN算法可能出現磁壁粘著.使用N-step-SCAN可以避免(FCFS+SCAN)，FSCAN是其簡化版。課本的SCAN,CSCAN指的就是LOOK,CLOOK吧。磁盤使用DMA,打印機使用IO中斷。用戶層軟件: 產生IO請求，格式化IO,SPOOLing;設備獨立性軟件: 映射/保護/緩沖/分配設備驅動程序:設置控制器寄存器，檢查狀態;中斷處理程序;IO控制器&設備:執行IO操作設備分配應考慮的問題: ①設備的固有屬性(獨占，共享，虛擬)②設備分配算法(FCFS,優先級)③安全性(安全分配，不安全分配。)設備驅動程序設備控制器磁盤的第一個扇區為MBR(主引導記錄)(512Bytes) ，包含bootloader(MBR Code啟動操作系統的必要代碼，typically : GRUB) ,分區表。(有一分區被標志為引導塊)每個分區是一個邏輯磁盤。每個分區的起始扇區以及大小都被記錄在磁盤0扇區的主引導記錄分區所包含的分區表中。磁盤傳輸時間?= 傳輸字節數/(磁道總字節數) × T ?(即這些字節需要轉多少度 × 每圈T)扇區是磁盤的可編址的最小單位，磁盤地址用柱面號，盤面號，扇區號表示。磁盤的存儲能力受最內道的最大記錄密度所限制。 位密度 ： 字節數/磁道長度。磁盤格式化 ：低級(物理)格式化:分成扇區。-> 分區 -> 高級(邏輯)格式化:創建文件系統，磁盤是共享設備，在一段時間內可以有多個用戶同時訪問。但是在某一時刻，只能有一個作業可以訪問。磁臂移動調度，減少尋到時間。旋轉調度: 減少等待時間，旋轉時間。總是讓首先到達讀寫磁頭位置下的扇區先開始進行傳輸操作。優化磁盤物理塊的分布式為了減少等待時間。(同一磁道連續編號)并行交叉存取是為了減少傳輸時間。(同一柱面，不同盤面。連續編號)壞塊兩種解決方式：1.手工處理，2.維護壞塊鏈表。對壞塊的處理實質上就是采用某種機制，是系統不去使用壞塊，壞塊屬于硬件故障，操作系統是不能修復壞塊的。設備分配之動態分配(執行過程中根據需要進行分配)(可能發生死鎖)，靜態分配(一次性分配所有需要的全部設備)(不會發生死鎖)。獨占設備一般采用靜態分配，共享:動態。單緩沖MAX(C,T) + M；雙緩沖MAX(C+M,T),為什么？C,M,T含義？傳輸過程？安全分配: 破壞請求保持，；不安全分配 ：可能死鎖。請求保持。邏輯設備表 LUT ①單用戶 一張LUT, 【邏輯設備名-物理設備名-驅動程序入口】②多用戶，一張系統設備表SDT，每個用戶一個LUT 【邏輯設備名-系統設備表指針】SDT(設備類型，設備標識符，DCT,驅動程序入口),DCT(類型，id,狀態，相連控制器表指針，隊首指針),COCT(id,狀態，相連通道表指針，隊列首/尾指針),CHCT(id,狀態,連接的控制器表首地址，隊列首/尾指針)的表項。SDT中每一個表項有一個DCT指針，DCT里面有一個COCT指針，COCT里面有一個CHCT指針，CHCT里面有COCT表首地址。先分配設備，再分配控制器，最后分配通道。只有在設備，控制器，通道三者都分配成功，這次的設備分配才算成功。設備分配過程 SDT-> DCTs -> COCTs -> CHCTs ??????PCB插入DCT，COCT,CHCT等待隊列，內存映射IO 即 統一編址。存儲型設備，以塊為單位傳輸。獨占設備:一段時間內只允許一個用戶進程使用。共享設備:一段時機內允許多個進程使用，但是每一時刻只允許一個。虛擬技術是指將一個獨占設備變換為若干臺邏輯設備。?塊設備可尋址到字節，分配共享設備不會死鎖。共享設備必須是可尋址的和可隨機訪問的設備。用戶層軟件，設備無關層軟件，驅動程序，中斷處理程序，每一層都做什么事情？緩沖池:三個隊列,四種緩沖區;空/裝滿輸入數據/裝滿輸出數據隊列.收容/提取輸入/輸出。?
?
內存管理&VM
鏈接[多模塊-> exe]【靜態，裝入時動態鏈接(都鏈接,但可變)，運行時動態鏈接(不用不鏈接)】裝載【絕對裝入(單道)，靜態重定位(多道系統)，動態重定位(支持可移動,對換/緊湊/VM)】靜態重定位即可重定位裝入，地址變換裝入時一次完成。裝入時分配要求的全部內存，在運行期間不能在內存中移動，也不能再申請空間。動態重定位:裝入內存時并不立即把相對地址轉換為物理地址，而是推遲到執行時才進行。裝入內存的均為邏輯地址，需要重定位寄存器。可以分配不連續，裝入部分，動態申請。目標文件，可執行文件緊湊，覆蓋，對換在連續分配方式中，可以使用緊湊來減少內存零頭，但是需要動態重定位的支持。存儲保護: 防止地址越界，防止操作越權。內存分配 : 連續分配【單一，固定，動態】,離散分配【頁，段，段頁】分配算法：First Fit , Best Fit , Worst Fit , Next Fit.首次適應:空閑分區按照地址排序；最佳適應:按照容量大小遞增排序。最差: 大小 減。循環首次: 使得空閑分區分布的較為均勻。伙伴系統: 靜+動 分配。 分配/回收算法: 遞歸。?buddy(x) = x + 2^k (x Mod x^k+1 == 0) ; x - 2^k (x Mod x^k+1 != 0)，?buddy(x) = x + 2^k - [ (x/2^k) % 2 ]* 2^k+1 通用多級N級頁表：最多訪存N+1次；ɑ: TLB hit rate ε：TLB hit time t：Memory帶TLB 訪問: EAT =ɑ(t+ε)+(1 -ɑ)*(（N+1）*t +ε) ?過程？ 若TLB,頁表并行計算？不同!??頁表: 邏輯塊號[可略]:物理塊號?段表: 段號[可略]:段基址:短長分段有利于共享，動態鏈接，動態增長反置頁表:整個系統一張 物理頁號:進程:邏輯頁號，利用進程ID/頁號檢索->很慢 -> HASHLoad R1,1000;采用靜態重定位，該指令的第二個操作數修改為1000+起始地址。采用動態重定位則仍然為1000.靜態鏈接實在 裝入程序前 進行的。動態鏈接是在裝入時，或者運行時進行的。適合于動態鏈接的存儲方式是 分段?。產生內部碎片 ：分頁，段頁式，靜態多分區，單一連續。產生外部碎片: 動態分區，分段常規存儲器: 一次性，駐留性。虛擬存儲：多次性，對換性，虛擬性。虛擬存儲必須建立在離散分配的基礎之上，有請求分頁，分段，段頁式等方式。分配置換策略，可變分配，固定分配；局部置換，局部置換。Clock是一種常用的近似LRU算法，又稱為NRU最近未用算法。Clock 查0()整體對換從邏輯上也擴充了內存，因此也實現了虛擬存儲器的功能。 ?False錯誤。駐留集，工作集駐留集 =m?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
概論
進程管理&死鎖
PV操作
特征
操作系統的特征
進程的特征
順序執行，并發的特征
死鎖的四個條件
進程映像 = 程序段 數據段PCB
循環等待 按遞增順序申請資源
死鎖定理
單一連續分配，固定，動態多分區分配
分段，分頁，段頁式
局部性原理
一連續分配，固定，動態多分區分配
?
通道
RAID
成組鏈接
運行->> 就緒 ??時間片完，搶占原語，系統調用進程的線程共享同一個地址空間處理機中可能沒有處于運行狀態的進程，因為此時系統處于死鎖狀態，所有進程阻塞。若不處于死鎖狀態，只要就緒隊列非空，那么就可以擇一而運行。進程是資源分配/擁有以及調度的基本單位。在引入線程的系統中，線程是調度的基本單位。用戶級線程，內核級線程，映射關系多對一，一對一，多對多？優缺點高級調度，中級調度，低級調度?響應時間，等待時間，周轉時間，加權周轉時間= 周轉時間/實際執行時間->平均加權周轉時間FCFS,SJF,優先級，高響應比優先，RR，多級反饋隊列(優先級?時間片?FCFS&RR? 插隊尾)搶占式，非搶占式短作業優先都可能會產生饑餓現象。短作業優先 平均周轉時間最短優先級 IO密集型 > 計算密集型高響應比優先調度,主要用于作業調度。響應比 = (等待時間+執行時間)/執行時間多道批處理系統 作業調度(輔寸->主存Ready) ?+ 進程調度(Ready->Running)
?
?
?
?
應用層
不一定要有域名，但是一定要有IP地址一個主機可以有多個域名(虛擬主機)，也可以有多個IP(多個網卡)一個域名可以解析為多個IP (負載均衡)
?
網絡層
IP地址 ：4B 32位；IPV6 128位，16B ;MAC地址 48位，6BA類(0... , 8位網絡1 - 126)B類(10.... , 16位網絡號，128.1 - 191.255)，C類(110，24位網絡號,192.0 - 223.255)，D類(多播地址，1110，)，E類（1111，保留）
| 類 | 起 | 網絡數 | 范圍 | 最大主機數/網 |
| A | 0 | 2^7 - 2 | 1 - 126 | 2^24 - 2 |
| B | 10 | 2^14 - 1 | 128.1 - 191.255 | 2^16- 2 |
| C | 110 | 2^21 - 1 | 192.1 - 223.255.255 | 2^8 - 2 |
?
IP地址不僅指明一臺主機，而且指明了主機所連接的網絡，而MAC地址僅僅指明一臺主機。與該主機所連接的網絡毫無關系。主機號全0表示本網絡本身，主機號全1表示本網絡的廣播地址。32位全0表示本主機0.0.0.0；32位全1表示整個TCP/IP網絡的廣播地址，由于路由器對廣播域的隔離，255.255.255.255等效為本網絡的廣播地址。(A類)127.0.0.0即網絡號為127保留作為本地軟件環回測試，本主機內部進程之間通信用。目的地址為環回地址的IP數據報永遠不會出現在任何網絡上。 127.x.x.x
回環地址范圍 127.0.0.1 ~ 127.255.255.255
NAT地址范圍
10.0.0.0 ~ 10.255.255.255, ??172.16.0.0 ~ 172.31.255.255 , ????192.168.0.0 ~ 192.168.255.255
組播地址范圍
根據網絡號來轉發分組，不考慮目的主機號。A-E類(網絡號,主機號)-> 子網劃分(從主機號借)(網絡號,子網號,主機號),子網掩碼 ->CIDR(網絡前綴，主機號)/前綴長度 最長前綴匹配，路由聚合(超網)路由器具有兩個或以上的IP地址，即路由器每一個接口都有一個不同網絡號的IP地址。當兩個路由器直接相連時，在連線兩端的接口處，可以分配也可以不分配IP地址，如果分配，則這一段連線就構成了一種只包含一條線路的特殊網絡，為了節省IP地址資源，常常不分配IP地址。ARP工作流程; 本局域網內部之間; ARP請求廣播，響應單播; 不在一局域網如何？?RIP : Distance Vector, OSPF : Link State ,BGP : Path Vector?(路徑向量)RIP : 16條，每個30S交換路由表，180s不可達，UDP:520應用層協議，適合小網絡。環!OSPF：鏈路狀態變化洪泛鏈路狀態，Dijkstra,AS劃分區域，適合大網絡，IP封裝，網絡層協議。收斂速度快!BGP ：選擇較好的路由，交換可達性信息，TCP連接傳輸BGP報文，應用層協議. BGP首次發送整個路由表，之后之更新有變化的部分。RIP,OSPF,BGP都支持CIDR。RIP僅和相鄰路由器交換信息，OSPF向本AS內所有路由器發送信息。ICMP報文兩種，差錯報告報文(終點不可達，源點抑制，超時，參數問題，改變路由(重定向))，詢問報文(回送請求和回答(PING使用)，時間戳請求和回答)PING(測試兩主機間的連通性)工作在應用層，直接使用ICMP，沒有使用傳輸層協議。Traceroute(跟蹤分組經過的路由器)，工作在網絡層。PING使用ICMP回送請求和回答報文，Traceroute使用ICMP超時報文和終點不可達。不應發送ICMP差錯報文的情況:①對ICMP差錯報告報文不再發送ICMP差錯報告報文②對第一個分片的數據報片的所有后續分片都不發送ICMP差錯報告報文③對具有組播地址的數據報都不發送ICMP差錯報告報文④對特殊地址(127.0.0.0,0.0.0.0)的數據報不發送ICMP差錯報告報文。NAT 整個專用網使用少量的全球IP地址，NAT路由器，NAT轉換表({全球IP地址:port}:{私有IP地址:port})，普通路由器轉發IP數據報時不改變源/目IP，而NAT路由器在轉發IP數據報時，要更改IP地址，普通路由器工作在網絡層，NAT路由器需要查看傳輸層的端口號。
NAT表項由管理員添加。
IP多播(組播),僅應用于UDP(TCP不能用,why?),為什么組播？組播分為硬件組播(局域網內)以及因特網范圍內組播，對組播數據報不產生ICMP差錯報文。硬件組播MAC地址范圍為
01-00-5E-00-00-00~01-00-5E-7F-FF-FF(后23位是組播IP地址后23位)，組播IP地址與以太網IP地址不是一一映射的(32:1)，因此收到組播數據報的主機，還要在IP層利用軟件進行過濾。
IP組播地址，D類地址，并非所有D類地址都可以..
以太網廣播FF-FF-FF-FF-FF-FF，組播01-00-5E-....。
IGMP協議是讓連接在本地局域網上的組播路由器知道本局域網上是否有主機加入或退出了某個組播組。
組播路由選擇協議找出以源主機為根節點的組播轉發樹。三種(LinkState,DV,協議無關)。
對不同的多播組有不同的多播轉發樹，同一個，不同的源點也會有不同的轉發樹。
移動IP，移動節點，歸屬代理(本地代理【主地址，輔地址】)，外埠代理(外部代理)。通信過程。注冊/注銷轉交地址,隧道。路由器 vs. 網橋/交換機 vs. 集線器/中繼器在同一個網絡中轉遞數據無需路由器的參數，而跨網絡通信必須通過路由器進行轉發。路由表(軟件實現)[目的IP:子網掩碼:下一跳:接口]?-> 轉發表(可軟可硬)[目的IP：下一跳]IPv6雙協議棧，隧道IP地址靠軟件來維持而硬件地址。虛擬地址。主機收到廣播/多播幀: NIC網卡篩選多播，接受每一個廣播。CPU篩選廣播。IP協議規定，所有主機和路由器必須能夠處理的IP數據報不得小于576字節，也就是說，只要IP數據報不超過576字節，這樣的數據報就肯定不需要分片。(鏈路層MTU也大于之)IP數據報3個長度，首部長度4位，單位4B，IP數據報長度16位，單位字節B，分片偏移，單位8B。故首部最長為15*4B = 60B,IP數據報最長為2^16-1 = 65535B(首+數據)路由器利用IP首部校驗和檢測出差錯時，簡單丟棄。不發送ICMP報文！因為srcIP！MTU 不包含MAC幀的首部和尾部字段。因此MTU 即IP數據報的最大長度。網絡層向上傳輸層提供的服務有兩種，面向連接(虛電路)和無連接(數據報服務)。直接交付，間接交付路由器連接的多個局域網中，物理層，鏈路層，網絡層協議可以不同；靜態路由(非自適應路由)，動態路由(自適應路由)慢收斂是導致發生路由回路的根本原因。若IP數據報長度大于MTU而且，DF = 1即不允許分片，則向源主機發送ICMP差錯報告。IP數據報經過一個路由器，源IP和目的IP不改變，源MAC目的MAC改變。默認路由 ?0.0.0.0/0OSPF 通過Hello分組來維持與其鄰居的連接。當鏈路狀態改變的時候，廣播LSU分組。OSPF將一個AS劃分為若干區域，用戶規模更大的網絡。劃分區域的好處就是把洪泛法交換鏈路狀態信息的范圍局限在每一個區域而不是整個AS。每一個區域內部的路由器只知道本區域的完整拓撲。主干區域。區域內部路由器，區域邊界路由器，主干路由器，自治系統邊界路由器。路由器路由選擇部分:路由選擇處理機，路由選擇協議，路由表路由器轉發部分: 交換結構，輸入端口，輸出端口。路由器轉發速度最慢。廣域網不需要分片，因為廣域網能夠通過的最大分組長度是該廣域網內中所有節點都事先知道的。使用幾次ARP解析？如果一個路由器要同時連接再一個以太網和一個ATM網絡上，需要添加兩個硬件，一個是以太網適配器，一個是ATM適配器。IPv6 變化，零壓縮，雙協議棧，隧道
運輸層
UDP 數據報（User Datagram Protocol） TCP : 報文段 (Transmission Control Protocol)16位端口號 65536個端口 (熟知端口號0-1023,登記端口號，短暫端口號)兩臺計算機中的進程要通信，不僅要知道對方的IP地址，還要知道對方的端口號。IP層只檢驗首部，對數據部分不檢驗。傳輸層UDP/TCP對整個報文檢驗。UDP首部 : 16位源port , ?16位目的port,， ?????????????????????????長度>=8??????????16位長度 ， ?16位checksum ??數據部分(如果有) ?????????首部長8字節?UDP首部 8B,TCP 首部?20B?, IP 首部 20B , 以太網首部14B,4B(尾部FCS) TCP ：20+4NUDP是面向報文的，TCP是面向字節流的 (UDP對應用層報文直接加上頭部交付IP層，不合并，不拆分。而是保留這些報文的邊界。IP層可能會對其分片，影響效率)UDP 支持一對一，一對多，多對一和多對多的交互通信，無擁塞控制。UDP可多播TCP會根據網絡的擁塞程度以及接收方接受窗口決定發送多長字節。接受方收到有差錯的UDP用戶數據報應如何處理，簡單的丟棄! ?同IP如果應用程序愿意使用UDP完成可靠傳輸，這可能嗎??可能，由應用層來實現可靠傳輸。TCP必須先建立連接再傳送數據，TCP只能是點對點的(一對一)，全雙工(同時收發)TCP建立的連接是虛連接，不是一條真正的物理鏈路。兩個進程之間建立了TCP連接，實際上套接字之間的TCP連接，TCP連接的端點是套接字(IP : port)?IP , UDP 盡最大努力交付。TCP連接建立 ①.SYN =1 ,ACK = 0,SEQ = x;②.SYN = 1,ACK = 1,SEQ = y,ack = x+1;③.SYN = 0,SEQ = x+1,ack = y+1; ??（ACK (有效),ack(序號)，連接過程中ACK = 1）TCP 連接釋放 ①FIN = 1,SEQ = u ②SEQ = v,ack = u+1 ③FIN = 1,SEQ = w，ack = u+1④SEQ = u+1,ack = w +1SYN,FIN都消耗1個序號。 整個過程發兩個SYN,兩個FIN報文，連接確認一次SYN,釋放確認兩次FIN。ACK不消耗一個序號，計整個過程中多消耗4個序號。(2SYN,2FIN)URG,ACK,PSH,RST,SYN,FIN,窗口，緊急指針，選項（MSS最大數據部分長度）發送窗口，接受窗口，擁塞窗口， ssthresh(慢開始閾值)慢開始與擁塞避免，快重傳與快恢復以太網規定重傳16次認為傳輸失敗，但是TCP沒有規定最大重傳次數。鏈路層的HDLC協議，網絡層的X.25協議都要確認機制與窗口機制。廣泛使用的PPP，IP無。HDLC按幀確認，TCP按字節確認。TCP有重傳計時器，持續計時器，保活計時器，時間等待計時器(2MSL連接釋放最后)(why?)TCP需要計算RTT,而UDP不需要計算RTT。假定在一互聯網中，所有鏈路的傳輸都不會差錯，此時TCP的可靠交付是多余的？錯誤!?TCP報文段總長度 ≤ Min[(對方給的MSS+TCP首部) ， 65515B] ?(假定IP使用20B首部)IP數據報總長度小于65535B，若IP使用20B首部，則TCP報文段不能超過65515字節。?RTTs = (1 - α ) *舊RTTs + ?α*新RTT樣本 α常取1/8網絡層使用數據報(不可靠)或虛電路(可靠 主機與主機之間)，傳輸層仍然可能出錯，為了保證可靠通信不論網絡層提供多么可靠的服務，運輸層仍然必須由可靠交付的協議。分偽首部既不向下傳送也不向下遞交，而僅僅是為了計算運輸層校驗和。停等協議中，不使用編號不行，需使用0，1兩個編號，收到重復的報文段不予理睬也不可行(一直超時重傳)。收到重復ACK可以不予理睬，傳輸層不能使用停等協議(只用0-1編號)n位用于分組編號，GBN : ?1 ≤ Wt≤ 2^n -1??SR：Wt + Wr ≤ 2^n ;Wtmax = Wrmax = 2^n-1?在TCP如果有一個ACK丟失了，那么一定會使對應的報文段重傳。錯誤! (收到更大ACK)如果接收方UDP發現收到的報文中目的端口號不正確(即不存在對應端口號的進程)，就丟棄該報文，并由ICMP發送端口不可達差錯報文給發送方。TCP校驗和是必須的，UDP校驗和是可選的(全為0)。UDP校驗和計算結果為1，說明無誤。按照二進制反碼運算求和再取反。端到端，port-port傳輸層服務器端的資源是在第二次握手完成時分配的，而客戶端是在第三次握手時分配的，使得服務器容易受到SYN洪泛攻擊。一個套接字只能與遠程的一個套接字相連。同一個端口號既可以TCP,也TCP。
?
?
?
鏈路層
?
物理層
奈氏準則 理想無噪聲信道 極限數據傳輸速率2Wlog2(V) bit/s W,V含義？信噪比 S/N 10log10(S/N)香濃定理: Wlog2(1 + S/N)什么是編碼，調制？曼徹斯特編碼(按起始)，差分曼徹斯特編碼(起始跳變為0，不跳變為1)數字數據-> 數字信號 (非歸零，曼徹斯特，差分..)數字數據-> 模擬數據 (ASK,FSK,PSK,QAM[A+P],Wlog2(m*n))模擬數據-> 數字信號 ?PCM(抽樣，量化，編碼)模擬數據-> 模擬信號分組交換，報文交換，電路交換。電路交換時延較小，在出錯率很高的信道上，選擇數據報方式更合適。將基帶信號直接傳送到數字信道上的傳輸方式是基帶傳輸。將基帶信號經過調制之后傳送到模擬信道上的方式是頻帶傳輸。寬帶傳輸？多模光纖:近距離傳輸，發光二極管；單模光纖:遠距離傳輸。激光二極管。微波直線傳輸。PDU,SDU,PCI; n-PCI + n-SDU = n-PDU = n-1-SDU會話層5，表示層6
?
?
?
?
?
?
?
?
?
?
?
?
?
?
組成原理
概論
基準測試程序執行的越快，不能說明機器的性能越好。高級語言程序，匯編程序都不能再機器上直接執行，只有機器語言可以。馮諾依曼機: 存儲程序(stored program) (ENIAC不是)高級語言虛擬機級->匯編語言虛擬機級->OS虛擬機級->機器語言機器級同一個功能既可以用硬件實現也可以用軟件實現。總響應時間(感覺到的時間) = ?CPU 時間 + 其他時間；CPU時間 = 用戶CPU時間?+ 操作系統CPU時間；其他時間：IO/執行其他操作時間 ；性能 = 1/執行時間 ?? 性能/速度 ，時間相聯存儲器既可以按地址又可以按內容尋址。對用戶透明的寄存器IR,MAR,MDR不透明可見的PC，FLAGS，通用寄存器
數據的機器級表示
1.C語言強制類型轉換 ： 有符號數->無符號數
2.浮點數除數為0，結果是無窮大+-∞，不是溢出異常
ASCII 0-9(30-39H)，A ( 65D) , a( 97D )
3.字，字長;字長(數據通路的寬度) 字(處理信息的單位，用來度量數據類型寬度，x86 字16bit)
4.碼距(Hamming Distance海明距離) 奇偶校驗碼碼距 = 2，8421碼碼距 = 1
5.海明碼①確定位數 2^r ≥ m + r + 1，②.放在1，2，4，8....(從1開始編號)(組成原理從右開始，計網從左開始)③確定校驗位0/1 異或為0④檢錯，翻轉之。
6. L - 1 = D + C (L: 碼距 D : 檢錯位數 C :糾錯位數)
7.檢錯d位，需要d+1位碼距；糾錯d位,需要2d+1位碼距；糾錯d1位，同時檢錯d2位，則碼距d1 + d2 + 1（d2≥d1）分
8.若碼距d為奇數，則可以發現d-1位錯，或者能糾錯(d - 1)/2位
若碼距d為偶數，則可以發現d-1為錯，或者能發現d/2位并糾d/2-1位
求補碼 正:0 + ...負數各位取反末尾加1，；[x]補 = [-x]補取反 + 1求移碼，加bias,一般2^n-1,或者先求補碼，符號位取反；求移碼真值，減去bias。移碼補碼只是符號位相反，因為差2^n-1（補碼加2^n）MSB（最高有效位，最高有效字節）,LSB（最低有效位，最低有效字節）數據元素起始地址都是低地址確定一個數值元素的值需要①進制②定點/浮點③編碼方式三種補碼判斷溢出的方式(進位次進位，結果符號，變形補碼)浮點數的指數只用移碼，可以簡化對階，即比較階大小的過程。IEEE754 零的表示，正0 ：00000000H負0 ：80000000H?當10^3,6,9?時鐘頻率：GHz,MHz ,帶寬Gb/s,Mb/s,數據傳輸率，2^10,20,30 內存容量:GB,MB,KB補碼/移碼0的表示唯一，原碼/反碼表示不唯一，浮點數有+0，-0n位2進制數補碼，其模式2^n ,[x]補 = x0 . x1x2x..n的模是2。相同位數的補碼，移碼具有相同的表數范圍。CRC加零個數為G(x)次數。CRC碼 = 數據 + 校驗碼（G(x)次數）IEEE 754 float 32bit = 1+8+23 bias127;double64bit = 1+11+52 bias 1023;浮點數表示與轉換規格化尾數。原碼：尾數最高位是1；補碼：符號位，和尾數最高位異號。浮點數精度取決于尾數位數，表示范圍取決于階碼位數。
運算
浮點數沒有移位，拓展。MIPS運算指令區分有符號，無符號。無符號不檢測是否溢出。X86不區分，解釋不一樣。& | ~ ^浮點數加減法 ①對階(小向大)②尾數加減(原碼)③規格化(左歸右歸)④舍入(就近偶數，舍入位)⑤溢出判斷（上溢：階碼全1，下溢：階碼全0）【尾數為0則結果為0】移位溢出判斷：①邏輯移位：針對于無符號數，右移不考慮溢出，左移時移出位為1則移出。②算術移位：針對有符號數，右移不考慮，左移時移位前后符號改變則溢出。補碼加減法溢出判斷：①進位次進位，②結果符號③，變形補碼原碼加減法：符號位，數值位 分開運算。浮點數：大數吃小數?移碼加減法：移碼的和，差等于和，差的補碼。通過移碼計算和差的補碼，最后將符號位取反。
①②③④⑤
①②③④⑤
?
存儲器
(存儲元件，記憶單元,Bit) 0/1 --> 存儲單元(8位，16位，32位..) --> 存儲體
DRAM 地址復用(容量太大)；分時傳送地址，靠行列地址RAS,CAS選通信號來區分地址引腳線上傳送的是行地址還是列地址。N -> 2√N
主存Memory 包括RAM,ROM.并不是只用DRAM半導體存儲器都采用隨機存取方式進行讀寫。錯誤! 如相聯存儲器多模塊存儲器之所以能快速訪問，是因為各模塊有獨立的讀寫電路。虛擬內存大小由地址空間決定。邏輯地址的位數。與磁盤/內存容量沒有直接的關系。Cache不能增加存儲容量。因為存放的是放在主存里面的信息副本。TLB miss【頁表中找，找到修改TLB，訪存；不在頁表轉Page Fault】,Page Fault【調頁，修改TLB,頁表，重新執行當前指令】,Cache miss【讀miss : 調進來 寫miss :分配/不分配】分別做哪些動作？分段比分頁更利于存儲保護。每次執行存儲器訪問，都要進行邏輯地址到物理地址之間的轉換嗎？邏輯地址到物理地址之間的轉換是由硬件還是由軟件實現的？???????????
| 層次? ? ? ? ? ? ? ? ?層次 | 映射 | 置換 | 寫回 | 缺失 | 處理方 |
| Cache-? ?Cache-Memory | 全/組/直接 | LRU,FIFO,OPT,.. | WB,全寫 | 讀miss:調進來 ;寫miss :分配/不分配 | 硬件 |
| TLB-Pa??TLB-Page Table | 全/組相聯 | 隨機置換 | ????/ | 查頁表,找到修改TLB,訪存;否則轉Page Fault | 軟/硬件 |
| Memor? ?Memory(VM)-Disk | 全相聯 | LRU,FIFO,OPT,.. | WB | 調頁，修改TLB/頁表,重新執行缺頁指令 | 軟件 |
?
虛擬存儲對應用程序員透明，對系統程序員不透明。計算Cache容量 Tag valid modified,cache block4路組相連LRU為2位，2路組相連LRU為1位。全相連依次裝入，Cache地址？
?
?
?
?
指令系統
累加型指令的一個源操作數和目的操作數總是在累加器中。堆棧型:操作數和結果都在棧頂，都是零地址一地址指令，對指令序列的順序要求嚴格。對于雙目運算，采用軟堆棧(主存)需訪存4次(取指,取兩操作數,寫結果)，硬堆棧(寄存器)訪存1次。(取指)相對尋址用于公共子程序的浮動，轉移操作數可能位于寄存器，主存，堆棧，IO端口，立即數。偏移尋址有3種 ： 基址尋址，變址尋址，相對尋址。寄存器直接尋址:操作數在寄存器中，OP = R[r1]，使用寄存器編號EA = r1；寄存機間接尋址：操作數在內存中，OP = M[R[r1]]地址為寄存器內容EA = R[r1]。?基址尋址：形式地址(給出的地址值)為偏移 + 基址寄存器內容。EA = (B)+ A；變址尋址: 形式地址為數組的首地址(給出的地址為首地址)。+變址寄存器內容。EA = A + (Reigister) 如 ?mov al , [SI + 1000H]定長操作碼，拓展操作碼【不允許短碼是長碼的前綴】隱含尋址，立即尋址，直接尋址，寄存機直接尋址，寄存器間接尋址，偏移尋址(基,變,相)一次間接尋址，2次間接尋址.. ??各個尋址方式的訪存次數變址間址結合使用;先變址再間址: EA = ( (I)+A )?[先變];先間址再變址 EA = (I) + (A) [后變址]?
總線
IO
中斷
CPU
流水線
?
線性數據結構
樹
圖
查找
1.二叉排序樹：查找，插入，刪除(葉子，非葉子)
2.AVL樹：插入(LL,RR,LR,RL，根節點選擇?第一個不平衡的點)，刪除(自底向上改變bf,調整，可能調整多次)
3.B樹插入與刪除，B+ vs. B
4.BST 最壞O(n) ,AVL最壞 O(log2N)
5.除留余數法，p一般選擇≤表長的最大素數。
6.線性探測法容易產生堆積問題，平方探測法可以減少發生堆積問題，缺點是不能探查到Hash表上的所有單元，但是至少能探查到一半的單元。
排序
?
?
?
?
?
?
總結
以上是生活随笔為你收集整理的计算机考研408总结: details of OS, CN...的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
