① 2.採用首次適應演算法和最佳適應演算法模擬實現可變分區管理。
#define MAX 100
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int b;//存放進程本次結束時的時間
void main()
{
int i,N,t,k;
int a[MAX];//存放進程的剩餘時間
int cnt[MAX];//存放進程調度次數
printf("請輸入進程數N:");
scanf("%d",&N);
printf("\n請輸入時間片t大小:");
scanf("%d",&t);
printf("\n請依次輸入各個進程的服務時間");
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
cnt[i]=0;
}
printf("被調度進程\t進程調度次數 \t本次運行時間結果\t剩餘時間\n");
k=1;
while(k)
{
for(i=0;i<N;i++)
{
if(a[i]!=0)
if(a[i]>=t)
{
a[i]-=t;
b+=t;
cnt[i]=cnt[i]+1;
printf("\n\t%d\t\t%d\t\t%d\t\t%d",i+1,cnt[i],b,a[i]);
}
else
{
b=b+a[i];
cnt[i]=cnt[i]+1;
a[i]=0;
printf("\n\t%d\t\t%d\t\t%d\t\t%d",i+1,cnt[i],b,a[i]);
}
else continue;
}
for(i=0;i<N;i++)
if(a[i]!=0)
{ k=1;break;}
else continue;
if(i>=N)
k=0;
}
printf("\n");
printf("進程全部運行完成!");
printf("\n");
}
② 主存空間的分配和回收，
#include "iostream.h"
#include "iomanip.h"
#define nofreearea 2
#define noadequacyarea 3
#define allocated 4
#define noprocess 2
#define nosuchprocess 3
#define reclaimed 4
typedef struct TUN
{
int address;
int size;
char name;
struct TUN *next;
} usedarea , *usedtable;
typedef struct TFN
{
int address;
int size;
struct TFN *next;
} freearea, *freetable;
usedtable usedTable = NULL;
freetable freeTable = NULL;
int alloc( char processname , int processsize )
{
if( freeTable == NULL )
return 1;
freetable p = freeTable;
freetable q = p;
while( p != NULL && p->size < processsize )
{
q = p;
p = p->next;
}
if( p == NULL )
return 3;
usedtable x = new usedarea;
x->address = p->address;
x->size = processsize;
x->name = processname;
x->next = NULL;
if( p->size > processsize )
{
p->size -= processsize;
p->address += processsize;
}
else
{
if( p == freeTable )
freeTable = NULL;
else
q->next = p->next;
delete p;
}
usedtable r = usedTable;
usedtable t = r;
while( r != NULL && r->address < x->address )
{
t = r;
r = r->next;
}
if( usedTable == NULL )
usedTable = x;
else
{
x->next = r;
t->next = x;
}
return 4;
}
int Reclaim( char processname )
{
if( usedTable == NULL )
return 1;
usedtable p = usedTable;
usedtable q = p;
while( p != NULL && p->name != processname )
{
q = p;
p = p->next;
}
if( p == NULL )
return 3;
freetable r = freeTable;
freetable t = r;
freetable x;
while( r != NULL && r->address < p->address )
{
t = r;
r = r->next;
}
x = new freearea;
x->address = p->address;
x->size = p->size;
x->next = NULL;
if( r == freeTable )
{
x->next = r;
freeTable = x;
t = freeTable;
}
else
{
x->next = r;
t->next = x;
}
while( t->next != NULL && t->address + t->size == t->next->address )
{
t->size += t->next->size;
r = t->next;
t->next = t->next->next;
delete r;
}
if( p == usedTable )
{
usedTable = usedTable->next;
}
else
q->next = p->next;
delete p;
return 4;
}
int Init()
{
freeTable = new freearea;
freeTable->address = 0;
freeTable->size = 128;
freeTable->next = NULL;
return 1;
}
void processrequest()
{
char processname;
int processsize;
cout<<"...................."<<endl;
cout<<"作業名: ";
cin >> processname;
cout<<"作業長度: ";
cin >> processsize;
if(processsize<=128)
{int i;
if( alloc( processname , processsize) == 4 )
{
i=i+processsize;
if(i>128)
{cout<<"該作業超出空間"<<endl;
}
if(i<=128)
cout<<"該作業已成功獲得所需空間"<<endl;
i=i+processsize;
cout<<"........................................"<<endl;
}
else
cout<<"該作業超出空間,沒有獲得所需空間"<<endl;
cout<<"........................................"<<endl;
return;
}
if(processsize>128)
{cout<<"該作業超出空間"<<endl;
cout<<"........................................"<<endl;
}
}
void processreclaim()
{
int processname;
cout<<"...................."<<endl;
cout<<"作業名: ";
cin >>processname;
int result = Reclaim( processname );
if( result == 4 )
cout<<"該作業已成功回收"<<endl;
else if( result == 2 || result == 1 )
cout<<"系統沒有作業或該作業不存在"<<endl;
cout<<"...................."<<endl;
}
void freeTablePrint()
{
cout<<endl<<endl<<endl<<"***********************************"<<endl;
cout<<setw(10)<<"address"<<setw(10)<<"length"<<setw(10)<<"state"<<endl<<endl;
freetable p = freeTable;
usedtable q = usedTable;
int x , y;
while( p || q )
{
if( p )
x = p->address;
else
x = 0x7fffffff;
if( q )
y = q->address;
else
y = 0x7fffffff;
if( x < y )
{
cout<<setw(10)<<p->address<<setw(10)<<p->size<<setw(10)<<"空閑"<<endl;
p = p->next;
}
if( x > y )
{
cout<<setw(10)<<q->address<<setw(10)<<q->size<<setw(10)<<"已分配"<<setw(10)<<"ID="<<q->name<<endl;
q = q->next;
}
}
cout<<endl<<endl<<endl<<"************************************"<<endl<<endl<<endl;
}
void main()
{
Init();
int choose;
bool exitFlag = false;
while( !exitFlag )
{
cout<<"************************0 - 退出 ************************"<<endl;
cout<<"************************1 - 分配主存 ************************"<<endl;
cout<<"************************2 - 回收主存 ************************"<<endl;
cout<<"************************3 - 顯示主存 ************************"<<endl<<endl<<endl;
cout<<"************************選擇所要執行的操作:";
cin>>choose;
switch( choose )
{
case 0:
exitFlag = true;
break;
case 1:
processrequest();
break;
case 2:
processreclaim();
break;
case 3:
freeTablePrint();
break;
}
}
}
③ 存儲器管理的連續分配存儲管理方式有哪些
連續分配方式．它是指為了一個用戶程序分配一個連續的內存空間．可以分為單一連續分配、固定分區分配、動態分區分配以及動態重定位分區分配四種方式。不過今天我們講的是固定分區分配和動態分區分配。
固定分區分配是最簡單的一種可運行多道程序的存儲管理方式。 一、基本思想：在系統中把用戶區預先劃分成若干個固定分區（每個分區首地址固定，每個分區長度是固定），每個分區可供一個用戶程序獨占使用。注意：每個分區大小可以相同，也可以不相同。 二、主存分配與回收：藉助主存分配表。 三、地址轉換（靜態重定位）：物理地址=分區起始地址+邏輯地址。其中劃分分區方法包括分區大小相等和分區大小不等。
動態分區分配是根據進程的實際需要，動態地為之分配內存空間。一、基本思想：按用戶程序需求動態劃分主存供用戶程序使用。（每個分區首地址是動態的，每個分區的長度也是動態的） 二、主存分配與回收-->（1）未分配表（登記未分配出去的分區情況）；（2）已分配表（登記已經分配出去的分區情況）。 三、地址轉換：物理地址=分區起始地址+邏輯地址。 四、分區分配演算法：從空閑分區中選擇分區分www.hbbz08.com 配給用戶程序的策略。 （1）首次適應演算法（最先適應）順序查詢為分配表，從表中找出第一個可以滿足作業申請的分區劃分部分分配給用戶作業。 （2）循環首次適應演算法 （3）最佳適應演算法：從空閑分區中找出一個能滿足用戶作業申請的最小空閑分區劃分給用戶作業使用（有利於大作業執行） （4）最壞適應演算法：從空閑分區中挑最大的分區劃分給用戶程序使用（有利於中、小作業執行）
④ 內存管理
在一段時間內，程序的執行僅限於某個部分，相應地，它所訪問的存儲空間也局限於某個區域。
局部性原理的 分類 ：
將編譯後的目標模塊裝配成一個可執行程序。
可執行程序以 二進制可執行文件 的形式存儲在磁碟上。
鏈接程序的 任務 ：
程序的鏈接，可劃分為：
重定位 ：將邏輯地址（相對地址）轉換為物理地址（絕對地址）的過程。
物理地址 = 邏輯地址 + 程序在內存中的起始地址
程序的裝入，可劃分為：
任何時刻主存儲器 最多隻有一個作業 。
每個分區 大小固定不變 ：分區大小相等、分區大小不等。
每個分區可以且 僅可以裝入一個作業 。
使用 下限寄存器 和 上限寄存器 來保存當前作業的起始位置和結束位置。
使用 固定分區說明表 區分各分區的狀態。
分區 大小不是預先固定的 ，而是按作業（進程）的實際需求來劃分的。
分區 個數也不是預先固定的 ，而是由裝入的作業數決定的。
使用 空閑分區表 說明空閑分區的位置。
使用 空閑分區鏈 說明空閑分區的位置。
首次適應演算法的 過程 ：
外部碎片：空閑內存 沒有在 分配的 進程 中。
內部碎片：空閑內存 在 分配的 進程 中。
從 上次找到的 空閑分區的 下一個 空閑分區開始查找。
優點：空閑區分布均勻、查找開銷較小。
缺點：缺乏大空閑區。
最佳適應演算法的 過程 ：
優點：提高內存利用率。
注意點：每次在進行空閑區的修改前，需要先進行 分區大小遞增 的排序。
頁 ：將一個 進程 的 邏輯地址空間 分成若干個 大小相等 的 片 。
頁框 ：將 物理內存空間 分成與頁大小相同的若干個 存儲塊 。
分頁存儲 ：將進程的若干 頁 分別裝入多個 可以不相鄰 的 頁框 中。
頁內碎片 ：進程 最後一頁 一般裝不滿一個頁框，形成 頁內碎片 。
頁表 ：記錄描述頁的各種數據，實現從 頁號 到 頁框號 的映射。
注意： 頁內偏移量 的單位是 位元組 。
分頁地址變換指是： 邏輯地址 通過 地址變換機構 變換為 物理地址 。
分頁地址變換的 過程 ：
操作系統在修改或裝入頁表寄存器的值時，使用的是 特權級 指令。
頁大小：512B ~ 4KB，目前的計算機系統中，大多選擇 4KB 大小的頁。
頁大小的 選擇因素 ：
快表也稱為「轉換後援緩沖」，是為了提高CPU訪問速度而採用的專用緩存，用來存放 最近被訪問過的頁表項 。
英文縮寫：TLB。
組成： 鍵和值 。
在TLB中找到某一個頁號對應的頁表項的百分比稱為 TLB命中率 。
當 能 在TLB中找到所需要的頁表項時：
有效訪問時間 = 一次訪問TLB 的時間 + 一次訪問內存 的時間（訪問內存讀寫數據或指令）
當 不能 在TLB中找到所需要的頁表項時：
有效訪問時間 = 一次訪問TLB 的時間 + 兩次訪問內存 的時間（一次訪問內存頁表，一次訪問內存讀寫數據或指令）
將頁表再分頁，形成兩級或多級頁表，將頁表離散地存放在物理內存中。
在進程切換時，要運行的進程的頁目錄表歧視地址被寫入 頁表寄存器 。
在二級分頁系統中，為頁表再建立一個頁目錄表的目的是為了能在地址映射時得到頁表在物理內存中的地址，在頁目錄表的表項中存放了每一個 頁表 在物理內存中所在的 頁框號 。
虛擬存儲器 ：是指具有 請求調入功能 和 置換功能 ，能 從邏輯上對內存容量進行擴充 的一種存儲系統。
請求調入 ：就是說，先將進程一部分裝入內存，其餘的部分什麼時候需要，什麼時候請求系統裝入。
置換 ：如果請求調入時，沒有足夠的內存，則由操作系統選擇一部分內存中的進程內容移到外存，以騰出空間把當前需要裝入的內存調入。
為了實現請求分頁，需要：
保證進程正常運行的所需要的最小頁框數。
最小頁框數與進程的大小沒有關系，它與計算機的 硬體結構 有關，取決於 指令的格式、功能和定址方式 。
內存不夠時，從進程本身選擇淘汰頁，還是從系統中所有進程中選擇？：
採用什麼樣的演算法為不同進程分配頁框？：
常用的兩種 置換策略 ： 局部置換 和 全局置換 。
從分配給進程的頁框數量上看，常使用的兩種 分配策略 ： 固定分配 和 可變分配 。
用新調入的頁替換 最長時間沒有訪問 的頁面。
找到 未來最晚被訪問 的那個頁換出。
，P為缺頁率。
有效訪問時間與缺頁率成 正比 ，缺頁率越高，有效訪問時間越長，訪問效率越低。
工作集 ：某段時間間隔里，進程實際要訪問的頁的集合。
引入工作集的 目的 ：降低缺頁率，提高訪問內存效率。
抖動 ：運行進程的大部分時間都用於頁的換入換出，幾乎不能完成任何有效果工作的狀態。
抖動的 產生原因 ：
抖動的 預防方法 ：
在分段存儲管理的系統中，程序使用 二維 的邏輯地址，一個數用來表示 段 ，另一個數用來表示 段內偏移量 。
引入分段的 目的 ：
引入分段的 優點 ：
進程的地址空間被劃分成 若干個段 。
每個段定義了一組邏輯信息，每個段的大小由相應的邏輯信息組的長度確定， 段的大小不一樣 ，每個段的邏輯地址從0開始，採用一段 連續的地址空間 。
系統為每個段分配一個 連續的物理內存區域 ，各個 不同的段可以離散 地放入物理內存不同的區域。
系統為 每個進程建立一張段表 ，段表的每一個表項記錄的信息包括： 段號、段長和該段的基址 ，段表存放在內存中。
分段的 邏輯地址結構 ：
段表是由操作系統維護的用於支持分段存儲管理 地址映射 的數據結構。
每個進程有一個段表，段表由段表項構成。每個段表項包括： 段號、段長（段的大小）和該段的基址（段的起始地址） 。
若已知邏輯單元的地址為 S:D （段號:段內偏移量），求相應物理地址的步驟如下：
相同點 ：分頁和分段都屬於 離散 分配方式，都要通過數據結構與硬體的配合來實現 邏輯地址到物理地址 的映射。
不同點 ：
將用戶進程的邏輯空間 先劃分為若干個段 ， 每個段再劃分成若干個頁 。
進程以頁為單位在物理內存中 離散 存放，每個段中被離散存放的頁具有 邏輯相關性 。
為了實現地址映射，操作系統為 每個進程建立一個段表 ，再為 每個段建立一個頁表 。
進程段表的段表項組成：
滿足以下條件的兩個塊稱為 夥伴 ：
⑤ 求首次適應演算法的c語言程序！（計算機操作系統的）
最佳適應演算法C++程序：
struct list // 初始化數據的結構體
{
int num;
int adr;
int end;
int size;
}s[]={{1,1000,2999,2000},{2,500,799,300},{3,3500,3699,200},{4,4000,4499,500}}; // 初始化空閑分區
/*void print(struct list *p,int n) // print函數作用輸出結果
{
int flag1=1;
int flag2=1;
int i,j=0;
cout<<"-------------------------------------\n";
for(i=0;i {
if(p->size==0) // 控制不輸出size=0的空閑塊
{
flag2=0;
j++;
continue;
}
else
flag2=1;
if(p->size!=0&&flag2!=0)
{
flag1=0;
cout<<"序號:"<num-j/*輸出的序號仍然是從1開始*//*<<" 起始位置:"<adr<<" 終止位置:"<end<<" 空閑塊大小:"<size< }
}
if(flag1==1) // 當所有的空閑塊正好被分配完時
cout<<"\n空閑內存已被分配完，請回收！\n";
cout<<"-------------------------------------\n";
}*/
void print(struct list a[],int n) // print函數作用輸出結果
{
int i;
cout<<"-------------------------------------\n";
if(a[0].size==0)
{
for(i=0;i {
a[i].adr=a[i+1].adr;
a[i].size=a[i+1].size;
a[i].end=a[i+1].end;
}
k=k-1;
}
if(k==0)
cout<<"\n空閑塊已經分配完畢,需要再分配,請回收!\n";
for(i=0;i cout<<"序號:"< cout<<"-------------------------------------\n";
}
未完。請自己從參考資料上復制。
⑥ 文件存儲空間管理
上篇文章介紹了文件的物理結構並介紹了文件分配的三種方式——連續分配、鏈接分配和索引分配。
本文介紹操作系統對文件存儲空間的管理。
本文內容
存儲空間的劃分： 將物理磁碟劃分為一個個文件卷（邏輯卷、邏輯盤） 。
在存儲空間初始化時，需要將各個文件卷劃分為目錄區、文件區。
有些系統支持超大型文件，可支持由多個物理磁碟組成一個文件卷。
空閑表法：即用一張表記錄磁碟中空閑的盤塊。空閑表的表項由 空閑盤的起始塊號 和 空閑盤塊數 組成。如下圖所示
如何分配磁碟塊：與內存管理中的動態分區分配類似，為一個文件分配連續的存儲空間。同樣可以採用 首次適應演算法、最佳適應演算法、最壞適應演算法，臨近適應演算法 來決定要為文件分配哪些區間。
空閑表法適用於連續分配方式。
例如，如果新創建的文件請求3個塊，按照首次適用演算法，從10號塊開始有5個連續的塊可以滿足需求，所以把10、11、12三個塊分配給文件，分配後的空閑盤塊表如下
這里以回收區前後都是空閑區為例，磁碟是第一幅圖的狀態，如果回收21、22號磁碟塊，那麼回收後的空閑盤塊表如下圖所示。
空閑鏈表法分為兩種： 空閑盤塊鏈和空閑盤區鏈
下圖分別表示空閑盤塊鏈和空閑盤區鏈。
操作系統保存著 鏈頭、鏈尾指針。
如何分配：如過某文件申請K個盤塊，則從鏈頭開始依次摘下K個盤塊分配，並修改空閑鏈的鏈頭指針。
如何回收：回收的盤塊依次掛到鏈尾，並修改空閑鏈的鏈尾指針。
下圖表示分配了3個盤塊
從上面可以看出，空閑盤塊法適用於 離散分配 的物理結構。為文件分配多個盤塊時可能要重復多次操作。
操作系統保存著 鏈頭、鏈尾指針 。
如何分配：若某文件申請K個盤塊，由於空閑盤區鏈將連續的盤塊組成一個盤區，所以若某個盤區大小滿足可以實現一次分配，同樣可以採用首次適用、最佳適用等演算法，從鏈頭開始檢索，按照一定的規則找到一個大小符合要求的空閑盤區分配給文件。若沒有合適的連續空閑塊，也可以將不同的盤區的盤同時分配給一個文件，同樣分配後也需要修改相應的指針鏈和盤區大小等數據。
如何回收：若回收區和某個空閑盤區相鄰，則需要將回收區合並到空閑盤區中。若回收區沒有和任何空閑區相鄰，將回收區作為一個單獨的一個空閑盤區掛到鏈尾。同樣也需要修改鏈表指針和盤區大小等信息。
下圖表示按照首次適用演算法分配3個盤區
從上面可以看出，空閑盤區鏈對 離散分配、連續分配 都適用。為一個文件分配多個盤塊時 效率更高 。
位示圖：磁碟內存被劃分為一個個磁碟塊，可以用二進制位對應一個盤塊。「0」代表盤塊空閑，「1」代表盤塊已分配。位示圖一般用連續的「字」來表示，下圖中一個字的字長是16位，字中的每一位對應一個盤塊。因此可以用（字型大小，位號）對應一個盤塊號。
如何分配：若文件需要K個塊，①順序掃描位示圖，找到K個相鄰或不相鄰的「0」；②根據字型大小、位號算出對應的盤塊號，將相應的盤塊分配給文件；③將相應的位設置為「1」。
如何回收：①根據回收的盤塊號計算出對應的字型大小、位號；②將相應的二進制位設置為「0」。
從上面可以看出：位示圖法對 連續分配和離散分配 都適用。
空閑表法、空閑鏈表法不適用大型文件系統，因為空閑表或空閑聯保可能過大。UNIX系統中採用了 成組鏈接法 對磁碟空閑塊進行管理。這是將上述兩種方法相結合的而形成的一種空閑管理方法。
文件卷的目錄區中專門用一個磁碟塊作為 超級塊 ，當系統啟動時需要將 超級塊讀入內存 。並且要保證與外存中的「超過塊」的數據一致。
內存的分配過程：分配過程是從棧頂取出一空閑盤塊號，將與之對應的盤塊分配給用戶，然後將棧頂指針下移一格，若該盤塊號已是棧底（即第一個盤塊），這是當前棧中最後一個可分配的盤塊號。由於在該盤塊號所對應的盤塊中記有下一組可用的盤塊號，因此，不能直接將它分配掉，需要將它記錄的下一組信息保存下來，所以比須調用磁碟讀過程，將棧底盤塊號所對應盤塊的內容讀入棧中，作為新的盤塊號棧的內容，並把原棧底對應的盤塊分配出去(其中的有用數據已讀入棧中)。然後，再分配一相應的緩沖區(作為該盤塊的緩沖區)。最後，把棧中的空閑盤塊數減1 並返回。
下面舉例說明
如果此時新建一個文件需要一個磁碟塊，那麼此時第一組有100個空閑塊，所以是足夠分配的，將棧頂的盤塊號即201號盤塊對應的盤塊分配出去，如下圖
如果此時又創建一個新的文件，需要99個磁碟塊，就需要將剩下的99個盤塊全部分配出去，但是此時300號盤塊記錄了下一組信息，如果分配出去，信息就是丟失，所以需要將300號盤塊從外存（磁碟）讀入內存，將300號盤塊記錄的信息，寫入空閑盤塊號棧，然後才能將這99塊空閑塊分配出去。具體過程如下圖所示
內存的回收過程：在系統回收空閑盤塊時，須調用盤塊回收過程進行回收。它是將回收盤塊的盤塊號記入空閑盤塊號棧的頂部，並執行空閑盤塊數加 1 操作。當棧中空閑盤塊號數目已達 100 時，表示棧已滿，便將現有棧中的100 個盤塊號記入新回收的盤塊中，再將其盤塊號作為新棧底。
以分配的第一個圖為例，201盤塊被分配出去了，如果此刻有個文件被刪除了，其佔用的盤塊是199號，系統需要回收這個盤塊，發現此時空閑盤塊號棧中記錄空閑塊數為99，直接將盤塊號記錄棧頂，將空閑盤塊數加1即可。
如果此時又有一個文件被刪除了，其佔用的盤塊是190，此時空閑盤塊號數已經達到100了，就需要將現在空閑盤塊棧中信息記入新回收的塊中。