一、梗概
- 本章讨論了塊裝置 I/O 和緩沖區管理;解釋了塊裝置 I/O 的原理和 I/O 緩沖的優點;論述了 Unix 的緩沖區管理算法，并指出了其不足之處;還利用信号量設計了新的緩沖區管理算法，以提高 1/O 緩沖區的緩存效率和性能:表明了簡單的 PV 算法易于實作，緩存效果好，不存在死鎖和饑餓問題;還提出了一個比較 Unix 緩沖區管理算法和 PV算法性能的程式設計方案。
二、知識點歸納
1、塊裝置I/O
塊裝置基本概念
塊裝置将資訊存儲在固定大小的塊中，每個塊都有自己的位址。對作業系統來說，塊裝置是以字元裝置的外觀展現的，雖然對這種字元裝置可以按照位元組為機關進行通路，但是實際上到塊裝置上卻是以塊為機關（最小512byte，既一個扇區）。這之間的轉換是由作業系統來完成的。
- 下面介紹塊裝置的基本概念：
扇區：磁盤盤片上的扇形區域，邏輯化資料，友善管理磁盤空間，是硬體裝置資料傳輸的基本機關，一般為512byte。
塊：塊是VFS（虛拟檔案系統）和檔案系統資料傳輸的基本機關，必須是扇區的整數倍，格式化檔案系統時，可以指定塊大小。
- 塊裝置I/O棧的基本概念。
bio：bio是通用塊層I/O請求的資料結構，表示上層送出的I/O求情。一個bio包含多個page（既page cache 核心緩沖頁 在記憶體上），這些page對應磁盤上的一段連續的空間。由于檔案在磁盤上并不連續存放，檔案I/O送出到塊這杯之前，極有可能被拆分成多個bio結構。
request：表示塊裝置驅動層I/O請求，經由I/O排程層轉換後（既電梯算法合并）的I/O請求，将會被發送到塊裝置驅動層進行處理。
request_queue： 維護塊裝置驅動層I/O請求的隊列，所有的request都插入到該隊列，每個磁盤裝置都隻有一個queue（多個分區也隻有一個）。
這三個結構的關系如下圖所示，一個request_queue中包含多個request，每個request可能包含多個bio，請求的合并就是根據各種算法（1.noop 2.deadline 3.CFQ）将多個bio加入到同一個request中。
實體塊裝置1/O:每個裝置都有一個I/O 隊列，其中包含等待 I/O 操作的緩沖區。緩沖區上的 start io0 操作如下:
start_io(BUFFER *bp)
{
enter bp into device I/O queuei
if(bp is first buffer in I/o queue)
issue I/o command for bp to devicei
}
當 I/O 操作完成後，裝置中斷處理程式會完成目前緩沖區上的 I/O 操作，并啟動I/O隊列中的下一個緩沖區的I/O(如果隊列不為空)。裝置中斷處理程式的算法如下:
InterruptHandler()
{
bp = dequeue(device I/0 queue):// bp e remove head of I/o queue(bp->opcode ASYNC)? brelse(bp)+ unblock process on bpi if(!empty(device I/o queue))
issue I/o command for first bp in I/o queuei
}
2、Unix I/O緩沖區管理算法
(1)I/O 緩沖區:核心中的一系列 NBUF 緩沖區用作緩沖區緩存。每個緩沖區用一個結構體表示。
typdef struct buf{
struct buf *next_freei // freelist pointer
struct buf inext devi // dev list pointer
int dev,blki // assigmed disk block;
int opcode; //READ|WRITE
int airty: // buffer data modified
int asynci // ASYNC write flag
int valid; // buffer data valid
int buayi // buffer is in use
int wanted; // some process needs this buffer
struct gemaphore 1ock=1; // buffer 1ocking semaphore; value=1
struct semaphore iodone=0:// for process to wait Eor I/O completioni
char buf[BLKSIZE]1 // block data area
}BUFFER:
BUFFER buf[NBUFl,*freelist; // NBUF buffers and free buffer list
緩沖區結構體由兩部分組成:用于緩沖區管理的緩沖頭部分和用于資料塊的資料部分。為了保護核心記憶體，狀态字段可以定義為一個位向量，其中每個位表示一個唯一的狀态條件。為了便于讨論，這裡将它們定義為inte
(2)裝置表:每個塊裝置用一個裝置表結構表示。
struct devtab{
u16 devi // major device number
BUFFER *dev 1ist; /l device buffer 1ist
BUFFER +io_queuel // device I/O queue
}devtab[NDEV];
每個裝置表都有一個dev list，包含目前配置設定給該裝置的I/O緩沖區，還有一個io qucue，包含裝置上等待 I/O操作的緩沖區。I/O 隊列的組織方式應確定最佳 I/O 操作。例如，它可以實作各種磁盤排程算法，如電梯算法或線性掃描算法等。為了簡單起見，Unix 使用 FIFO I/O 隊列。
(3)緩沖區初始化:當系統啟動時，所有 I/O緩沖區都在空閑清單中，所有裝置清單和 I/O 隊列均為空。
(4)緩沖區清單:當緩沖區配置設定給(dev,blk)時，它會被插入裝置表的dev_list 中。如果緩沖區目前正在使用，則會将其标記為 BUSY(繁忙)并從空閑清單中删除。繁忙緩沖區也可能會在裝置表的I/O 隊列中。由于一個緩沖區不能同時處于空閑狀态和繁忙狀态，是以可通過使用相同的 next free 指針來維護裝置 1/O 隊列。當緩沖區不再繁忙時，它會被釋放回空閑清單，但仍保留在dev list中，以便可能重用。隻有在重新配置設定時，緩沖區才可能從一個dev list更改到另一個dev list中。如前文所述，讀/寫磁盤塊可以表示為 bread bwrite 和 dwrite，它們都要依賴于 getblk 和 brelse。是以，getblk 和 brelse 構成了 Unix 緩沖區管理方案的核心。getblk 和 brelse 算法如下。
(5)Unix getblk/brelse 算法((Lion 1996;(Bach 1990)第3章)。
Unix算法的缺點
1）效率低下
2）緩存效果不可預知
3）可能會出現饑餓
4）該算法隻适用于單處理系統的休眠/喚醒操作
3、新的I/O緩沖區管理算法
假設有一個單處理器核心(一次運作一個程序)。使用計數信号量上的 P/V 來設計滿足以下要求的新的緩沖區管理算法:
-
(1)保證資料一緻性。
(2)良好的緩存效果。
(3)高效率:沒有重試循環，沒有不必要的程序“喚醒”。
(4)無死鎖和饑餓。
注意，僅通過信号量上的P/V來替換 Unix 算法中的休眠/喚醒并不可取，因為這樣會保留所有的重試循環。我們必須重新設計算法來滿足所有上述要求，并證明新算法的确優于 Unix 算法。首先，我們定義以下信号量。
BUFFER buf[NBUF]; // NBUF I/O buffers
SEMAPHORE free = NBUF; // counting semaphore for FREE buffers
SEMAPHORE buf[i].sem = 1; // each buffer has a lock sem=1;
為了簡化符号，我們将用緩沖區本身來表示每個緩沖區的信号量。與Unix 算法一樣，最開始，所有緩沖區都在空閑清單中，所有裝置清單和 1/0 隊列均為空。下面展示一個使用信号量的簡單緩沖區管理算法。pv算法，參考哲學家進餐問題。
三、實踐内容
模拟實作信号量實作程序間通信
參考代碼：
#include <stdio.h>
#include <stdlib.h>
#include <semaphore.h>
#include <errno.h>
#define total 20
sem_t remain, apple, pear, mutex;
static unsigned int vremain = 20, vapple = 0, vpear = 0;
void *father(void *);
void *mather(void *);
void *son(void *);
void *daughter(void *);
void print_sem();
int main()
{
pthread_t fa, ma, so, da;
sem_init(&remain, 0, total);//總數初始化為20
sem_init(&apple, 0, 0);//盆子中蘋果數, 開始為0
sem_init(&pear, 0, 0);//盆子中梨子數, 開始為0
sem_init(&mutex, 0, 1);//互斥鎖, 初始為1
pthread_create(&fa, NULL, &father, NULL);
pthread_create(&ma, NULL, &mather, NULL);
pthread_create(&so, NULL, &son, NULL);
pthread_create(&da, NULL, &daughter, NULL);
for(;;);
}
void *father(void *arg)
{
while(1)
{
sem_wait(&remain);
sem_wait(&mutex);
printf("父親: 放蘋果之前, 剩餘空間=%u, 蘋果數=%u\n", vremain--, vapple++);
printf("父親: 放蘋果之後, 剩餘空間=%u, 蘋果數=%u\n", vremain, vapple);
sem_post(&mutex);
sem_post(&apple);
sleep(1);
}
}
void *mather(void *arg)
{
while(1)
{
sem_wait(&remain);
sem_wait(&mutex);
printf("母親: 放梨子之前, 剩餘空間=%u, 梨子數=%u\n", vremain--, vpear++);
printf("母親: 放梨子之後, 剩餘空間=%u, 梨子數=%u\n", vremain, vpear);
sem_post(&mutex);
sem_post(&pear);
sleep(2);
}
}
void *son(void *arg)
{
while(1)
{
sem_wait(&pear);
sem_wait(&mutex);
printf("兒子: 吃梨子之前, 剩餘空間=%u, 梨子數=%u\n", vremain++, vpear--);
printf("兒子: 吃梨子之後, 剩餘空間=%u, 梨子數=%u\n", vremain, vpear);
sem_post(&mutex);
sem_post(&remain);
sleep(3);
}
}
void *daughter(void *arg)
{
while(1)
{
sem_wait(&apple);
sem_wait(&mutex);
printf("女兒: 吃蘋果之前, 剩餘空間=%u, 蘋果數=%u\n", vremain++, vapple--);
printf("女兒: 吃蘋果之前, 剩餘空間=%u, 蘋果數=%u\n", vremain, vapple);
sem_post(&mutex);
sem_post(&remain);
sleep(3);
}
}
void print_sem()
{
int val1, val2, val3;
sem_getvalue(&remain, &val1);
sem_getvalue(&apple, &val2);
sem_getvalue(&pear, &val3);
printf("Semaphore: remain:%d, apple:%d, pear:%d\n", val1, val2, val3);
}
運作結果：
四、問題與解決
1、為什麼要有輸入輸出緩沖區？
答：
有輸入輸出緩沖區用以暫時存放讀寫期間的檔案資料而在記憶體區預留的一定空間。即利用主存的存儲空間來暫存從磁盤中輸入輸出的資訊。目的是緩和CPU 與 I/O 裝置間速度不比對的沖突。減少對 CPU 的中斷頻率，放寬對 CPU 中斷響應時間的限制。提高 CPU和 I/O 裝置之間的并行性。
2、日常較為常見的計算機緩沖區有哪幾種類型？
日常較為常見的緩沖區，根據緩沖的應用層次不同，分别可以分為以下幾種類型：主機闆與CPU的緩存，這兩者是基于計算機硬體層次的緩沖區，能夠有效地提高計算機的資料處理能力；作業系統與網絡協定層的緩沖區，這則是在系統軟體層的分類，為了提高通路速度，網站門戶常常會基于緩沖原理使用一些元件，以實作資訊的快速互動；在應用程式這一次層，緩沖區又可分為應用程式、資料庫系統的緩沖區等等，一般來說，開發較為完善的大型軟體會自己配備記憶體管理程式，在運作軟體運作時自動進行對緩沖區的管理。