計(jì)算機(jī)專業(yè)基礎(chǔ)知識(shí)

計(jì)算機(jī)的字符與編碼集

使用unicode

中文編碼集，windows默認(rèn)使用GBK

編程推薦使用UTF-8

文件的編碼集 GB2312 支持中文

馮諾依曼機(jī)

輸入設(shè)備

輸出設(shè)備

存儲(chǔ)器

運(yùn)算器

控制器

計(jì)算機(jī)硬件：CPU 內(nèi)存 硬盤 鼠標(biāo) 鍵盤 顯示器 網(wǎng)卡 電源 顯卡 聲卡 主板

CPU：存儲(chǔ)器，運(yùn)算器，控制器(里面有高速緩存)

計(jì)算機(jī)總線和IO設(shè)備

計(jì)算機(jī)的總線，計(jì)算機(jī)的輸入/輸出設(shè)備

總線的概述：USB(通用串行總線)

作用：提供了對(duì)外鏈接的接口，不同設(shè)備可以通過USB鏈接，促使外圍設(shè)備接口的統(tǒng)一

PCI總線：顯卡

沒有總線需要各自設(shè)備之間的互相鏈接，有了總線就可以通過總線進(jìn)行鏈接

總線的分類：片內(nèi)總線，系統(tǒng)總線

片內(nèi)總線：芯片內(nèi)部的總線(高速緩存，控制器，中斷系統(tǒng)，運(yùn)算器)

總線可以簡(jiǎn)化 內(nèi)部的電路結(jié)構(gòu)

片內(nèi)總線：高集成度芯片內(nèi)部的信息傳輸線

系統(tǒng)總線：鏈接w外部設(shè)備的總線

系統(tǒng)總線：數(shù)據(jù)總線，地址總線 控制總線

數(shù)據(jù)總線：雙向傳輸各個(gè)部件的數(shù)據(jù)信息

地址總線：傳輸數(shù)據(jù)的地址，尋址的作用，地址總線的位數(shù)與存儲(chǔ)單元的位數(shù)有關(guān)

控制總線：監(jiān)視不同組件的狀態(tài)，是否準(zhǔn)備就緒

總線的仲裁

主存和硬盤，IO設(shè)備交換數(shù)據(jù) ，總線通過控制優(yōu)先級(jí)來爭(zhēng)奪資源，解決總線使用權(quán)的沖突問題

總線仲裁的方法：鏈?zhǔn)讲樵兎?計(jì)時(shí)器定時(shí)查詢法 獨(dú)立請(qǐng)求法

鏈?zhǔn)讲樵儯?

問題：如果設(shè)備1,2同時(shí)發(fā)出仲裁請(qǐng)求，先到設(shè)備1，再到2

優(yōu)點(diǎn)：電路復(fù)雜度低，仲裁方式簡(jiǎn)單

缺點(diǎn)：優(yōu)先級(jí)低的設(shè)備難以獲得總線的使用權(quán)

計(jì)時(shí)器定時(shí)查詢

通過仲裁控制器發(fā)出1,2,3,4等信息，匹配到第幾個(gè)第幾個(gè)響應(yīng)

獨(dú)立請(qǐng)求法

每個(gè)設(shè)備均有總線獨(dú)立鏈接仲裁器

設(shè)備科單獨(dú)向沖裁器發(fā)送請(qǐng)求和接受請(qǐng)求

當(dāng)同時(shí)收到多個(gè)請(qǐng)求信號(hào)，仲裁器有權(quán)限優(yōu)先級(jí)分配使用權(quán)

優(yōu)點(diǎn)：響應(yīng)速度快，優(yōu)先順序可以改變

缺點(diǎn)：設(shè)備連線多，總線控制復(fù)雜

CPU與IO設(shè)備通信

輸入輸出接口的通用設(shè)計(jì)

CPU與IO設(shè)備的通信

程序程序中斷

DMA(直接存儲(chǔ)器訪問)

CPU速度與IO設(shè)備速度不一致

程序中斷：當(dāng)外圍s設(shè)備IO準(zhǔn)備就緒時(shí)，向CPU發(fā)出中斷信號(hào)

程序中斷：提供了設(shè)備通知CPU的一種異步的方式，CPU可以高速運(yùn)轉(zhuǎn)的同時(shí)兼顧低俗設(shè)備響應(yīng)

頻繁打斷CPU會(huì)降低效率

DMA(直接存儲(chǔ)訪問) DMA直接連接主存與I設(shè)備

DMA工作時(shí)不需要CPU的參與

有了DMA不需要打斷CPU 工作，類似于脊髓

硬盤 顯卡都有DMA的設(shè)備

計(jì)算機(jī)的存儲(chǔ)器

計(jì)算機(jī)的存儲(chǔ)器概覽，計(jì)算機(jī)的高速存儲(chǔ)器，計(jì)算機(jī)的主存儲(chǔ)器與輔助存儲(chǔ)器

存儲(chǔ)器的分類：內(nèi)存，U盤，固態(tài)硬盤，磁帶，磁盤

存儲(chǔ)介質(zhì)分類

隨機(jī)存儲(chǔ)器(RAM)可讀可寫，與位置無關(guān)

串行存儲(chǔ)器 與位置有關(guān)

只讀存儲(chǔ)器(ROM) 只讀不寫

計(jì)算機(jī)存儲(chǔ)概覽

1.緩存(容量最低，速度最快)

2.主存(內(nèi)存)

3.輔存(硬盤)

計(jì)算機(jī)的CPU

計(jì)算機(jī)機(jī)的指令系統(tǒng)，計(jì)算機(jī)的運(yùn)算器，計(jì)算機(jī)的控制器，指令的執(zhí)行過程

由于CPU和存儲(chǔ)器速度不一樣所以引入cache

CPU—cache—主存—輔存

緩存—主存 將常用的軟件進(jìn)行內(nèi)存置換(解決速度不匹配)

主存—輔存 解決主存容量不足的問題

主存儲(chǔ)器(內(nèi)存)----本質(zhì)是RAM 隨機(jī)存取存儲(chǔ)器

為什么內(nèi)存斷電就會(huì)失去數(shù)據(jù)呢?

RAM是通過電容存儲(chǔ)數(shù)據(jù)的，必須每隔一段時(shí)間刷新一次，刷新需要有電的存在，沒有電，電子就會(huì)丟失

CPU里面的：

主存數(shù)據(jù)寄存器(MDR)----數(shù)據(jù)總線

主存地址寄存器(MAR)----地址總線

連接內(nèi)存和CPU

32位最多只有4G的地址尋址空間 所以加再多的內(nèi)存條沒有用

64位操作系統(tǒng)地址范圍有，支持2的34次方GB

電梯算法(磁盤的讀取)

先來先服務(wù)算法

最短尋道時(shí)間算法

掃描算法(電梯算法)：每次只往一個(gè)方向移動(dòng)，到達(dá)一個(gè)方向需要服務(wù)的勁頭再反方向

循環(huán)掃描算法：只往一個(gè)方向讀取到勁頭置到最開始的地方

計(jì)算機(jī)的高速緩存

高速緩存的原理

字：放在存儲(chǔ)單元中二進(jìn)制代碼的組合(計(jì)算機(jī)的最小的單位)

字塊：可以理解為一組字(字塊包含多個(gè)字)

主存：2的n次方個(gè)字，一個(gè)存儲(chǔ)單元可以理解為一個(gè)字。一組字塊就是字塊。

尋址過程：所尋找的字屬于哪個(gè)字塊，字，字塊的地址

字的地址：前m位指字塊的地址

后b位指定字在字塊中的地址

一個(gè)字塊共B個(gè)字，主存共M個(gè)字塊

字塊數(shù)和地址之間的關(guān)系：2的對(duì)數(shù)之間的關(guān)系

字節(jié)：B(byte) 1kb = 1024byte 位：bit(0,1)

計(jì)算地址的時(shí)候需要log2操作

主存的容量大于緩存的容量，說明主存的字塊數(shù)大于緩存的字塊數(shù)

CPU所需要的數(shù)據(jù)在緩存中就從cache中拿，不在就在主存中拿

量化CPU從cache中的幾率：緩存命中率(衡量緩存的性能指標(biāo))

從主存中替換到cache中的策略：

隨機(jī)算法：隨機(jī)選取一個(gè)位置來替換

先進(jìn)先出算法(FIFO)：看做是一個(gè)先進(jìn)先出的隊(duì)列，cache滿了之后淘汰1號(hào)位，進(jìn)來9號(hào)位

最不經(jīng)常使用算法(LFU)：使用額外的空間記錄字塊使用的頻率，計(jì)數(shù)法

最近最少使用算法(LRU)：優(yōu)先淘汰一段時(shí)間沒有使用的字塊，可以使用雙向鏈表，將當(dāng)前訪問節(jié)點(diǎn)置于鏈表前面(保證頭部節(jié)點(diǎn)是最近使用的)，滿了之后就開始淘汰，每次最近使用就將其置到最前面

計(jì)算機(jī)的指令系統(tǒng)

操作碼字段 ：操作碼指明指令要完成的操作，操作碼的位數(shù)反映了機(jī)器的操作種類

地址碼字段：指定數(shù)據(jù)的地址

三地址指令，二地址指令，一地址指令

機(jī)器指令的操作類型：寄存器之間，寄存器與存儲(chǔ)單元之間，存儲(chǔ)單元之間

數(shù)據(jù)讀寫，jiaohua 地址數(shù)據(jù)，清零置一等操作

計(jì)算機(jī)尋址系統(tǒng)

機(jī)器指令的尋址方式：順序?qū)ぶ?，跳躍尋址

數(shù)據(jù)尋址：立即尋址，直接尋址，間接尋址

計(jì)算機(jī)的控制器(CPU)

控制器是協(xié)調(diào)控制計(jì)算機(jī)的運(yùn)行的

程序計(jì)數(shù)器用來存儲(chǔ)下一條指令的地址，循環(huán)從程序計(jì)數(shù)器中拿出指令，當(dāng)指令被拿出時(shí)指向下一條指令

時(shí)序發(fā)生器：發(fā)送時(shí)序脈沖，CPU根據(jù)不同的時(shí)序脈沖進(jìn)行工作

指令譯碼器：是控制器主要部件之一，計(jì)算機(jī)指令由操作碼和地址碼組成，翻譯操作碼對(duì)應(yīng)的操作以及控制傳輸?shù)刂反a對(duì)應(yīng)的數(shù)據(jù)

指令寄存器：從主存或高緩取計(jì)算機(jī)指令

主存地址寄存器：保存當(dāng)前CPU正要訪問的內(nèi)存單元地址

主存數(shù)據(jù)寄存器：保存當(dāng)前CPU正要讀寫的主存數(shù)據(jù)

通用寄存器：用于暫時(shí)存放或傳送數(shù)據(jù)的

計(jì)數(shù)，發(fā)生，譯碼， 寄存，總線

計(jì)算機(jī)的運(yùn)算器

數(shù)據(jù)緩沖器，ALU，通用寄存器，狀態(tài)字寄存器，總線

數(shù)據(jù)緩沖器：分為輸入緩沖和輸出緩沖

輸入緩沖暫時(shí)存放外設(shè)送來的數(shù)據(jù)

輸出緩沖暫時(shí)存放送往外設(shè)的數(shù)據(jù)

ALU

算數(shù)邏輯單元，是運(yùn)算器的重要組成

完成常見的位運(yùn)算，算數(shù)運(yùn)算(加減乘除)

計(jì)算機(jī)指令的執(zhí)行過程

取指令-----分析指令-----執(zhí)行指令

從指令緩存中取指令-----送到指令寄存器-----送到指令譯碼器進(jìn)行譯碼-----發(fā)出控制信號(hào)-----程序計(jì)數(shù)器+1指向下一條指令-----裝載數(shù)據(jù)到寄存器------ALU處理數(shù)據(jù)-----記錄運(yùn)算狀態(tài)------送出運(yùn)算結(jié)果

CPU的流水線設(shè)計(jì)(類似于工廠裝配線)

流水線效率提升3倍

進(jìn)制運(yùn)算的基礎(chǔ)知識(shí)：進(jìn)制運(yùn)算的基礎(chǔ)

二進(jìn)制數(shù)據(jù)的表示方法：有符號(hào)數(shù)與無符號(hào)數(shù)，二進(jìn)制的補(bǔ)碼表示法，二進(jìn)制的反碼表示法，小數(shù)的二進(jìn)制補(bǔ)碼表示

二進(jìn)制數(shù)據(jù)的運(yùn)算：定點(diǎn)數(shù)與浮點(diǎn)數(shù)，定點(diǎn)數(shù)的加減法運(yùn)算，浮點(diǎn)數(shù)的減法運(yùn)算，浮點(diǎn)數(shù)的乘除法運(yùn)算

操作系統(tǒng)

操作系統(tǒng)的演進(jìn)：無操系統(tǒng)

人工操作

用戶獨(dú)占

CPU等待人工操作

資源利用率很低

批處理系統(tǒng)

無需等待人工操作

批量處理任務(wù)

資源利用率提升

多道程序設(shè)計(jì)

分時(shí)系統(tǒng)：

人機(jī)交互

多用戶共享

即時(shí)調(diào)試程序

資源利用率提升

多道程序設(shè)計(jì)：早期批處理系統(tǒng)一次只能處理一個(gè)任務(wù)

多道程序設(shè)計(jì)：計(jì)算機(jī)內(nèi)存中可以存放多個(gè)程序，多道程序在計(jì)算機(jī)的管理程序下互相穿插運(yùn)行

五大功能

進(jìn)程管理(進(jìn)程管理之進(jìn)程實(shí)體，進(jìn)程管理之五狀態(tài)模型，進(jìn)程管理之進(jìn)程同步，Linux的進(jìn)程管理)

存儲(chǔ)管理(內(nèi)存的分配與回收，段夜式存儲(chǔ)管理，虛擬內(nèi)存，Linux的存儲(chǔ)管理)

作業(yè)管理(進(jìn)程調(diào)度，死鎖)

文件管理(操作系統(tǒng)的文件管理，Linux的文件系統(tǒng)，Linux的文件的基本操作)

設(shè)備管理

操作系統(tǒng)概覽

what & why

操作系統(tǒng)是管理硬件和軟件資源的計(jì)算機(jī)程序。

管理配置內(nèi)存，決定供需順序，控制輸入輸出設(shè)備。

操作系統(tǒng)提供讓用戶和系統(tǒng)交互的的操作界面。

在不同的設(shè)備上，操作系統(tǒng)可以向用戶呈現(xiàn)不同的狀態(tài)。

管理硬件，提供用戶交互軟件的系統(tǒng)

我們不能直接操作硬件

提供了統(tǒng)一的操作界面

操作系統(tǒng)也使更多人使用了計(jì)算機(jī)

操作系統(tǒng)的基本功能

處理器資源

存儲(chǔ)器資源

IO設(shè)備資源

文件資源

用戶無需面向硬件接口編程

IO設(shè)備管理軟件，提供讀寫文件接口

文件管理軟件，提供文件接口

操作系統(tǒng)實(shí)現(xiàn)了對(duì)計(jì)算機(jī)資源的抽象

操作系統(tǒng)提供了用戶與計(jì)算機(jī)之間的接口

操作系統(tǒng)的基本功能

圖像窗口形式

命令形式

系統(tǒng)調(diào)用形式

操作系統(tǒng)的相關(guān)概念

并發(fā)性

多道程序概念是并發(fā)的基礎(chǔ)

共享性

多個(gè)程序可以同時(shí)使用主存資源

共享根據(jù)屬性可分為兩種方式：互斥共享形式，同時(shí)訪問形式

當(dāng)A占用資源，等釋放了之后才能使用

同時(shí)是宏觀的，看上去是同時(shí)訪問

短時(shí)間看還是互斥的

虛擬性

虛擬性表現(xiàn)為把一個(gè)物理實(shí)體轉(zhuǎn)變?yōu)槿舾蓚€(gè)邏輯實(shí)體

物理實(shí)體是真實(shí)存在的，邏輯實(shí)體是虛擬的

虛擬的技術(shù)主要有時(shí)分復(fù)用技術(shù)，空分復(fù)用技術(shù)

時(shí)分復(fù)用技術(shù)：資源在時(shí)間上進(jìn)行復(fù)用，不同程序并發(fā)使用

多道程序分時(shí)使用計(jì)算機(jī)資源

時(shí)分復(fù)用技術(shù)

空分復(fù)用技術(shù)

空分復(fù)用技術(shù)用來實(shí)現(xiàn)虛擬磁盤，虛擬內(nèi)存等

提高資源利用率，提升編程效率

虛擬磁盤技術(shù)

物理磁盤虛擬為邏輯磁盤C,D,E等邏輯盤

使用起來更加方便

虛擬內(nèi)存技術(shù)

在邏輯上擴(kuò)大程序的存儲(chǔ)容量

使用比實(shí)際內(nèi)存更大的容量

大大提升編程效率

異步性

在多道程序下面允許多個(gè)程序并發(fā)執(zhí)行

進(jìn)程在使用資源時(shí)可能等待或放棄

進(jìn)程執(zhí)行不是一氣呵成，是走走停停的

進(jìn)程管理之進(jìn)程實(shí)體

為什么需要進(jìn)程

進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位

進(jìn)程作為獨(dú)立運(yùn)行的載體保障程序的正常運(yùn)行

進(jìn)程的存在使操作系統(tǒng)資源利用率大大提升

進(jìn)程實(shí)體

主存中的進(jìn)程形態(tài)：標(biāo)識(shí)符，狀態(tài)，優(yōu)先級(jí)，程序計(jì)數(shù)器，內(nèi)存指針，上下文數(shù)據(jù)，IO狀態(tài)信息，記賬信息

標(biāo)識(shí)符：標(biāo)識(shí)唯一的進(jìn)程(進(jìn)程ID)

狀態(tài)：標(biāo)記進(jìn)程的狀態(tài)(運(yùn)行態(tài)，阻塞態(tài))

程序計(jì)數(shù)器：進(jìn)程即將被執(zhí)行的下一條指令的地址

內(nèi)存指針：程序代碼，進(jìn)程數(shù)據(jù)相關(guān)的指針

上下文數(shù)據(jù)：進(jìn)程執(zhí)行時(shí)處理器存儲(chǔ)的數(shù)據(jù)(寄存器，cache)

IO狀態(tài)信息：被進(jìn)程IO操作所占用的文件列表

記賬信息：使用處理器時(shí)間，時(shí)鐘總和等

總結(jié)起來：進(jìn)程的標(biāo)識(shí)符，處理機(jī)的狀態(tài)，進(jìn)程調(diào)度信息，進(jìn)程控制信息

進(jìn)程控制塊

用于描述和控制進(jìn)程運(yùn)行的通用數(shù)據(jù)結(jié)構(gòu)(每個(gè)進(jìn)程都有PCB進(jìn)程控制塊)

記錄進(jìn)程當(dāng)前狀態(tài)和控制進(jìn)程運(yùn)行的全部信息

PCB的使得進(jìn)程能夠獨(dú)立運(yùn)行的基本單位

PCB是操作系統(tǒng)進(jìn)行調(diào)度經(jīng)常會(huì)被讀取到的信息

PCB是常駐內(nèi)存的，存放在系統(tǒng)專門開辟的PCB區(qū)域內(nèi)

操作系統(tǒng)對(duì)進(jìn)程的調(diào)度其實(shí)是對(duì)線程的調(diào)度

進(jìn)程：資源分配的基本單位，獨(dú)立調(diào)度的基本單位，進(jìn)程系統(tǒng)開銷大，進(jìn)程IPC

線程：不擁有資源，獨(dú)立調(diào)度的最小單位，線程系統(tǒng)開銷小，讀寫同一進(jìn)程數(shù)據(jù)通信

進(jìn)程管理之無狀態(tài)模型

創(chuàng)建 就緒 終止 阻塞 執(zhí)行

當(dāng)進(jìn)程被分配到除CPU以外所必要的資源后

只要再獲得CPU的使用權(quán)，就可以立即運(yùn)行

其他資源都準(zhǔn)備好，只差CPU資源的狀態(tài)就為就緒狀態(tài)

就緒進(jìn)程就會(huì)排成就緒隊(duì)列

進(jìn)程獲得CPU，其程序正在執(zhí)行成為執(zhí)行狀態(tài)

在單核處理器時(shí)，在某個(gè)時(shí)刻只能有一個(gè)進(jìn)程處于執(zhí)行狀態(tài)

進(jìn)程的阻塞狀態(tài)

進(jìn)程因某種原因：其他設(shè)備為準(zhǔn)備就緒而無法繼續(xù)執(zhí)行，從而CPU放棄的狀態(tài)為阻塞狀態(tài)

阻塞隊(duì)列：存放阻塞的進(jìn)程

創(chuàng)建狀態(tài)：分配PCB，插入就緒隊(duì)列

創(chuàng)建進(jìn)程時(shí)擁有PCB但其他資源尚未就緒的狀態(tài)為創(chuàng)建狀態(tài)

操作系統(tǒng)提供fork函數(shù)接口創(chuàng)建進(jìn)程

系統(tǒng)清理，PCB歸還

進(jìn)程結(jié)束由系統(tǒng)清理或者歸還PCB的狀態(tài)稱為終止?fàn)顟B(tài)

進(jìn)程管理之進(jìn)程同步

進(jìn)程間同步：

為什么需要進(jìn)程間同步

進(jìn)程間同步的原則

線程同步

生產(chǎn)者消費(fèi)者問題

進(jìn)程的同步：

空閑等待

忙則等待

有限等待

讓權(quán)等待

進(jìn)程間同步的方法：

消息隊(duì)列

共享存儲(chǔ)

信號(hào)量

進(jìn)程間同步：

互斥量

讀寫鎖

自旋鎖

條件變量

Linux分為前臺(tái)進(jìn)程，后臺(tái)進(jìn)程，守護(hù)進(jìn)程

占用終端：前臺(tái)進(jìn)程

沒有占用終端，不和用戶進(jìn)行交互 & 符號(hào)結(jié)束就可以

可以將內(nèi)容重定向到文件里面

linux中以d結(jié)尾的一般為守護(hù)進(jìn)程(sshd，httpd，mysqld)

linux中進(jìn)程的狀態(tài)

R：運(yùn)行狀態(tài)

S：睡眠狀態(tài)

D：IO等待狀態(tài)

T：暫停狀態(tài)

Z：退出狀態(tài)(僵尸進(jìn)程)

作業(yè)管理之進(jìn)程調(diào)度

進(jìn)程調(diào)度的概述

進(jìn)程調(diào)度是值計(jì)算機(jī)通過決策決定哪個(gè)就緒程序可以獲得CPU使用權(quán)(多道程序設(shè)計(jì))

保存舊進(jìn)程的運(yùn)行信息，請(qǐng)出舊進(jìn)程

選擇新進(jìn)程，準(zhǔn)備運(yùn)行換將并分配CPU

進(jìn)程的調(diào)度

就緒隊(duì)列的排隊(duì)機(jī)制

為了提高進(jìn)程調(diào)度的效率(排隊(duì))

選擇運(yùn)行進(jìn)程的委派機(jī)制

調(diào)度進(jìn)程按照一定的策略選擇就緒進(jìn)程，將CPU資源分配給它

新老進(jìn)程的上下文切換機(jī)制

進(jìn)程的調(diào)度

搶占式，非搶占式

搶占式切換頻繁，開銷大，相對(duì)公平

非搶占式切換次數(shù)少，開銷小，不公平

進(jìn)程調(diào)度的算法

先來先服務(wù)

短進(jìn)程優(yōu)先調(diào)度算法

高優(yōu)先權(quán)優(yōu)先調(diào)度算法(前臺(tái)進(jìn)程的優(yōu)先級(jí)會(huì)高于后臺(tái)進(jìn)程)

時(shí)間片輪轉(zhuǎn)算法

作業(yè)管理之死鎖

死鎖的產(chǎn)生：競(jìng)爭(zhēng)資源，進(jìn)程調(diào)度順序不當(dāng)

競(jìng)爭(zhēng)資源不夠共享資源的數(shù)量不滿足各個(gè)進(jìn)程的需求

會(huì)因?yàn)楣蚕碣Y源的競(jìng)爭(zhēng)造成死鎖

死鎖的必要條件

互斥條件

請(qǐng)求保持條件(可以一次性申請(qǐng)所有需要的資源)

不可剝奪條件(當(dāng)一個(gè)進(jìn)程請(qǐng)求新的資源得不到滿足，必須釋放資源)

環(huán)路等待條件(按照線性排序，申請(qǐng)必須按照需要遞增申請(qǐng)，按照順序申請(qǐng))

銀行家算法

客戶申請(qǐng)貸款有限，每次申請(qǐng)需要聲明最大的資金量

銀行家能在滿足貸款時(shí)，都應(yīng)該給用戶貸款

客戶在使用貸款后，能夠及時(shí)歸還

存儲(chǔ)管理之內(nèi)存分配與回收

單一連續(xù)分配的方法(只能在單用戶，單進(jìn)程的操作系統(tǒng)中使用)

固定分區(qū)分配方法

固定分區(qū)分配支持多道程序最簡(jiǎn)單的存儲(chǔ)分配方式

內(nèi)存空間被劃分為若干固定大小的區(qū)域

每個(gè)分區(qū)只提供給一個(gè)程序使用，互不干擾

動(dòng)態(tài)分區(qū)分配

內(nèi)存分配的過程

首次適應(yīng)算法(FF算法)(循環(huán)適應(yīng)算法)

分配內(nèi)存是從開始順序查找適合內(nèi)存區(qū)(鏈表)，遍歷鏈表若沒有合適的空閑區(qū)，則該次分配失敗

最佳適應(yīng)算法(BF算法)

按照內(nèi)存大小進(jìn)行排序(避免一些大材小用的情況)

快速適應(yīng)算法(QF算法)

操作系統(tǒng)如何管理進(jìn)程的空間

頁式存儲(chǔ)管理

段式存儲(chǔ)管理

段頁式存儲(chǔ)管理

存儲(chǔ)管理之虛擬內(nèi)存

虛擬內(nèi)存概述

有些進(jìn)程實(shí)際需要內(nèi)存很大，超過物理內(nèi)存的容量

多道程序設(shè)計(jì)，使得每個(gè)程序可用的物理內(nèi)存更加稀缺

不可能無線增加物理內(nèi)存，物理內(nèi)存總有不夠的時(shí)候

把程序的內(nèi)存劃分，將暫時(shí)不使用的內(nèi)存放在輔存中

程序的局部性原理

CPU訪問存儲(chǔ)器時(shí)，無論是存儲(chǔ)指令還是存取數(shù)據(jù)，所訪問的存儲(chǔ)單元都趨于聚集在一個(gè)較小的連續(xù)趨于中

程序運(yùn)行時(shí)，無需全部轉(zhuǎn)載至內(nèi)存，裝載部分即可

從用戶層面來看，程序擁有很大的空間(虛擬內(nèi)存

)

虛擬內(nèi)存的置換算法

先入先出

最不經(jīng)常使用算法

最近最少使用的算法

主存頁面替換的時(shí)機(jī)：當(dāng)主存缺頁的時(shí)候就會(huì)進(jìn)行替換

虛擬內(nèi)存的置換算法

替換策略發(fā)生在cache-主存層次，主存-輔存層次

cache-主存層次的替換策略主要是為了解決速度問題

主存-輔存層次主要是為了解決容量問題

linux的存儲(chǔ)管理

buddy內(nèi)存管理算法

buddy算法是經(jīng)典的內(nèi)存管理算法

算法基于計(jì)算機(jī)處理二進(jìn)制的優(yōu)勢(shì)具有極高的效率

算法主要為了解決內(nèi)存碎片的問題

內(nèi)存頁內(nèi)碎片，內(nèi)存頁外碎片

頁內(nèi)碎片：已經(jīng)被分出去不能再利用了

頁外碎片：沒有被分出去也不能被利用了

向上取整2的冪大小

伙伴系統(tǒng)buddy

回收分配的內(nèi)存，找伙伴內(nèi)存。

buddy算法是經(jīng)典的內(nèi)存管理算法

算法基于計(jì)算機(jī)處理二進(jìn)制的具有極高的效率

算法主要為了解決內(nèi)存外碎片的問題

將內(nèi)存外碎片問題轉(zhuǎn)化為內(nèi)存內(nèi)碎片問題

linux交換空間

swap(交換空間)是磁盤的一個(gè)分區(qū)

linux物理內(nèi)存滿時(shí)，會(huì)把一些內(nèi)存交換swap空間

linux中輸入 top命令

是冷啟動(dòng)的依賴，啟動(dòng)需要大量的內(nèi)存，將不怎么使用的內(nèi)存交換到物理內(nèi)存中

系統(tǒng)睡眠依賴

大進(jìn)程空間依賴

swap空間 VS 虛擬內(nèi)存

操作系統(tǒng)的文件管理

文件的邏輯結(jié)構(gòu)

輔存的存儲(chǔ)空間分配(磁盤)

目錄管理

邏輯結(jié)構(gòu)文件的類型

有結(jié)構(gòu)文件(文本文件，文檔，媒體文件)

無結(jié)構(gòu)文件(二進(jìn)制文件，鏈接庫(kù))

文件的邏輯結(jié)構(gòu)

文件內(nèi)容由定長(zhǎng)記錄和可變長(zhǎng)記錄組成

定長(zhǎng)記錄存儲(chǔ)文件格式，文件描述等結(jié)構(gòu)化數(shù)據(jù)項(xiàng)

可變長(zhǎng)記錄存儲(chǔ)文件的具體內(nèi)容

無結(jié)構(gòu)文件

也成流式文件

文件內(nèi)容長(zhǎng)度以字節(jié)為單位

例：EXE文件 dll文件 so文件

順序文件

順序文件是按照順序存放在介質(zhì)中的文件

磁帶的存儲(chǔ)特性使得磁帶文件只能順序存儲(chǔ)文件

順序文件是所有邏輯文件中存儲(chǔ)效率最高的

但是對(duì)順序文件的增刪改查效率比較低

為了解決此問題引出了索引文件

有一張索引表

輔存的存儲(chǔ)空間分配

鏈接分配可以將文件存儲(chǔ)在離散的盤塊中

需要額外的存儲(chǔ)空間存儲(chǔ)文件盤塊的鏈接順序

FAT表：FAT文件系統(tǒng) 類似于路由表

讀取文件需要將整個(gè)文件加載到內(nèi)存然后進(jìn)行檢索

索引分配

把文件的所有盤塊集中存儲(chǔ)(索引)

讀取某個(gè)文件時(shí)，將文件索引讀取進(jìn)內(nèi)存即可

輔存的存儲(chǔ)空間分配

主存和輔存都用了空閑表和空閑鏈表

將所有空閑的盤塊存在一個(gè)鏈表

每個(gè)鏈表節(jié)點(diǎn)存儲(chǔ)空閑盤塊和空閑數(shù)目

重點(diǎn)：位示圖

位示圖的優(yōu)點(diǎn)：

維護(hù)成本低

位示圖可以非常容易找到空閑盤塊

位置圖使用0/1比特位，占用空間小

進(jìn)階補(bǔ)充

生產(chǎn)者，消費(fèi)者模型/哲學(xué)家進(jìn)餐問題

保護(hù)臨界資源，進(jìn)行通信

線程間同步：互斥量，讀寫鎖，自旋鎖，條件變量

進(jìn)程間同步：共享內(nèi)存，域套接字

用戶態(tài)與內(nèi)核態(tài)

上下文切換

協(xié)程

編寫性能良好的程序指南

線程同步之互斥量

兩個(gè)線程爭(zhēng)搶共享資源，互斥使用。

原子性，一系列操作不可中斷的特性

互斥量又稱互斥鎖(解鎖和加鎖)

互斥量是最簡(jiǎn)單的線程同步的方法

兩個(gè)狀態(tài)可以保證訪問資源的串行

操作系統(tǒng)直接提供了互斥量的API

開發(fā)者可以直接使用API完成資源的加鎖解鎖的操作

自旋鎖

自旋鎖的模型和互斥鎖模型一樣

自旋鎖也是一種多線程同步的變量

使用自旋鎖的線程會(huì)反復(fù)檢查鎖變量是否可用

自旋鎖不會(huì)讓出CPU

自己死循環(huán)等待鎖的釋放

自旋鎖避免了進(jìn)程或線程的上下文(因?yàn)槭亲约核姥h(huán))的開銷

操作系統(tǒng)內(nèi)部很多地方使用自旋鎖

自旋鎖不適合在單核CPU使用(因?yàn)樗姥h(huán))

讀寫鎖

對(duì)互斥資源和自旋鎖的改良

當(dāng)臨界資源(數(shù)據(jù)庫(kù))，是一種特殊的自旋鎖

臨界資源多讀少寫

不會(huì)改變臨界資源

讀和寫互斥，讀和讀不互斥

線程同步之條件變量

緩沖區(qū)沒有數(shù)據(jù)時(shí)，消費(fèi)者不許消費(fèi)，必須等待

緩沖區(qū)滿了時(shí)，不允許生產(chǎn)者往緩沖區(qū)生產(chǎn)，生產(chǎn)者必須等待

可以更加嚴(yán)謹(jǐn)?shù)募s束

條件變量也提供了API

條件變量是一種相對(duì)復(fù)雜的線程同步方法

條件變量允許線程睡眠，直到滿足某種條件

當(dāng)滿足條件時(shí)，生產(chǎn)者可以向該線程(消費(fèi)者)發(fā)信號(hào)，通知喚醒

線程同步方法總結(jié)

互斥量 自旋鎖 讀寫鎖

先加鎖，使用臨界資源，后解鎖

加鎖后其他不能訪問臨界資源

解鎖后，其他消費(fèi)者才能訪問臨界資源

使用fork系統(tǒng)調(diào)用創(chuàng)建進(jìn)程

c語言的系統(tǒng)調(diào)用

fork創(chuàng)建的進(jìn)程初始化狀態(tài)與父進(jìn)程一樣

父進(jìn)程調(diào)用時(shí)子進(jìn)程也會(huì)調(diào)用，fork函數(shù)會(huì)返回兩次

用fork可以創(chuàng)建一個(gè)新的進(jìn)程

所有語言底層創(chuàng)建進(jìn)程都是fork系統(tǒng)調(diào)用的

進(jìn)程同步之共享內(nèi)存

多進(jìn)程共享物理內(nèi)存的

由于操作系統(tǒng)的進(jìn)程管理，進(jìn)程間的內(nèi)存空間是相互獨(dú)立的

進(jìn)程空間通過頁表映射到共享內(nèi)存的一片分區(qū)中去

共享存儲(chǔ)允許不相關(guān)的進(jìn)程訪問同一片物理內(nèi)存(原理：將物理內(nèi)存映射到進(jìn)程的頁表里面去，使得進(jìn)程通過頁表訪問內(nèi)存)

共享內(nèi)存是兩個(gè)進(jìn)程之間共享和傳遞數(shù)據(jù)最快的方式

后臺(tái)很多高性能服務(wù)都是通過共享內(nèi)存實(shí)現(xiàn)

缺點(diǎn)：共享內(nèi)存未提供同步機(jī)制，需要借助其他機(jī)制管理訪問，以避免并發(fā)訪問帶來的問題

使用共享內(nèi)存的四個(gè)步驟

向操作系統(tǒng)申請(qǐng)共享內(nèi)存-----連接到進(jìn)程空間------使用共享內(nèi)存------脫離進(jìn)程空間(刪除)

client 共享內(nèi)存 server

共享內(nèi)存是傳遞數(shù)據(jù)最快的方式

Unix域套接字

客戶端創(chuàng)建套接字，綁定套接字，監(jiān)聽套接字，接受處理信息

創(chuàng)建套接字，鏈接套接字，發(fā)送信息

進(jìn)程同步之UNIX域套接字

提供了單機(jī)簡(jiǎn)單可靠的進(jìn)程同步服務(wù)

只能在單機(jī)使用，不能跨機(jī)器使用

雙向鏈表實(shí)現(xiàn)原理

往頭部加入節(jié)點(diǎn)

往頭部插入節(jié)點(diǎn)：將新的節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)，將第一個(gè)節(jié)點(diǎn)的上一個(gè)指向前一個(gè)節(jié)點(diǎn)，將頭部指針指向新的節(jié)點(diǎn)

# 實(shí)現(xiàn)鏈表節(jié)點(diǎn)

class Node:

def __init__(self,key,value):

self.key = key

self.value = value

self.prev = None

self.next = None

def __str__(self):

val = {{}: {}}.format(self.key,self.value)

return val

def __repr__(self):

val = {{}: {}}.format(self.key,self.value)

return val

# 雙向鏈表實(shí)現(xiàn)head指針 tail指針 鏈表的容量

class DoubleLinkList:

def __init__(self, cap = 0xffff):

self.cap = cap

self.head = None

self.tail = None

self.size = 0 # 當(dāng)前鏈表存儲(chǔ)了多少個(gè)節(jié)點(diǎn)

# 從頭部添加

def __add_head(self,node):

if not self.head:

self.head = node

self.tail = node

self.head.next = None

self.tail.next = None

else:

node.next = self.head

self.head.prev = node

self.head = node

self.head.prev = None

self.size += 1

return node

# 從尾部添加

def __add_prev(self,node):

if not self.tail:

self.head = node

self.tail = node

self.head.next = None

self.tail.next = None

else:

self.prev.next = node

node.prev = self.tail

self.tail = node

self.tail.next = None

self.size += 1

return node

# 刪除任意節(jié)點(diǎn)

def __del_node(self,node):

if not node:

node = self.tail

if node == self.tail:

pass

elif node == self.head:

pass

else:

node.prev.next = node.next

node.next.prev = node.prev

self.size -= 1

return node

# 彈出頭部節(jié)點(diǎn)

def __del_head(self):

pass

# 彈出尾部節(jié)點(diǎn)

def __del_prev(self):

pass