1、齊齊哈爾大學操作系統課程綜合實踐題目：段頁式存儲算法班級： 計本131 姓名： 學號：指導教師：2016年 6月段頁式存儲算法摘要：分頁和分段存儲管理方式都各有其優缺點，分頁系統能有效地提高內存利用率，而分段系統則能很好滴滿足用戶需要。對兩種存儲管理方式“各取所長”，則可以將兩者結合成一種新的存儲管理方式系統。這種新系統既具有分段系統的便于實現、分段可共享、易于保護、可動態鏈接等一系列優點，又能像分頁系統那樣很好地解決內存的外部碎片問題，以及可為各個分段離散的分配內存等問題。把這種結合起來形成的新系統稱為“段頁是系統”。關鍵字：存儲分配；內存塊； 進程 一、實訓內容與目的1、內容 編寫程序完成

2、段頁式虛擬存儲管理存儲分配、地址重定位和缺頁中斷處理。（1）為一個進程的內存申請（多少個段，每個段多大）分配內存，當一個進程（完成）結束時回收內存；（2）對一個給定邏輯地址，判斷其是否缺段、缺頁，若不缺段、不缺頁，則映射出其物理地址；（3）若缺段則進行缺段中斷處理，若缺頁則進行缺頁中斷處理。假定內存64K，內存塊（頁框）大小為1K，進程邏輯地址空間最多4個段，每個段最大16K，進程駐留集大小為8頁。假設進程運行前未預先裝入任何地址空間，頁面淘汰策略采用局部（駐留集內）置換策略。輸出每次存儲分配/回收時，內存自由塊分布情況、相關進程的段表和頁表信息。2. 目的（1）加深理解段頁式虛擬存儲管理的概

3、念和原理。（2）掌握段頁式存儲管理中存儲分配（和回收）方法；（3）深入了解段頁式虛擬存儲管理中地址重定位（即地址映射）方法。（4）深入理解段頁式虛擬存儲管理中缺段、缺頁中斷處理方法。二、主要設計思路和流程圖1、設計思路（1）內存大小為64K，頁框大小為1K，駐留集最多放8個頁，在初始時所有塊都空閑，并輸出空閑狀態和所有可用的空閑塊。（2）進程、段表和頁表均用結構體數組存儲，其中每個進程對應一個段表，每個段表可以有一個或多個頁表。每次查詢一個頁時，要通過進程號找相應的段，通過段號找到該頁。（3）給出一個功能菜單，用戶可以選擇“創建進程”、“結束進程”、“查看內存”或地址映射。（4）當用戶選擇“創

4、建進程”時，現輸入此次內存的總需求，即段號和相應的頁數，并保存在一個全局的二維數組中，用于后面每個進程空間申請的數量的檢查。用戶分別輸入進程號，每個進程需要的段數，段號和相應的頁號，并標記好是否要調入駐留集。輸入完成后，系統進行內存空間和駐留集空間的檢查，若均未滿，則分配成功；如果內存已滿，則此次分配失敗；如果駐留集已滿，則修改溢出部分的標志位（即P位）。（5）分配好空間后，將輸出每個進程相應的段表和頁表項。（6）當用戶選擇“結束進程”時，清空該進程的段表和頁表，修改標志位，釋放掉在內存中的空間。（7）當用戶選擇“查看內存”時，輸出當前在內存中的進程個數、已用的內存塊數和空閑的內存塊數，并顯示

5、所用可用的空閑塊。（8）當用戶選擇“地址映射”時，先輸入想查找的進程號，在檢驗正確的情況下，輸入段號和段內偏移量，判斷段的標志位，若該段不在駐留集中，則為虛段，進行缺段中斷處理；若在駐留集中，檢驗偏移量是否越界，在不越界的前提下，根據偏移量計算頁號并判斷頁的標志位，若該頁不在駐留集中，則為虛頁，進行缺頁中斷處理，若在駐留集中，則計算出相應的物理地址并輸出。2.程序流程圖(1)總體流程圖Menu();Init()othersExit;choice4132Finish_Pro()Check_Mem()Addr_Exchange()Apply_Mem()是否缺段、頁頁Alloc_Mem()否給出物理

6、地址是FIFO_Strategy() Print_Table() Print_Table()（2） 進程創建流程圖Input seg_sum_numInput seg_sumi0，seg_sumi0輸入段號和相應的頁數Input pro_numprocessCount += pro_numpro_numpro_num <= 0 | pro_num > Pro_sum_sizepro_num >= 0 && pro_num < Pro_sum_sizei = 0 , i < pro_numInput P_id;Input P

7、rocessesi.Snum;i+;Int j = 0 , j < Processesi.SnumInput Processesi.Segmentsj.seg_id;Input Processesi.Segmentsj.is_p;J+;Processesi.Segmentsj.is_p01Int k = 0 ; k < Processesi.Segmentsj.Pnum ;k+Input Processesi.Segmentsj.Pagesk.page_id;Input Processesi.Segmentsj.Pagesk.is_p;Int k = 0 ; k < Proc

8、essesi.Segmentsj.Pnum ;k+Input Processesi.Segmentsj.Pagesk.page_id;Input Processesi.Segmentsj.Pagesk.is_p;Alloc_Mem()Print_Table()(3) 地址映射流程圖Input pro_id輸入映射的進程號Input s_id , offset輸入段號和段內偏移量段地址越界地址映射失敗段地址未越界FIFO_Strategy()該段為虛段該段為實段根據段表查頁表，找到頁框號該頁為虛頁FIFO_Strategy()計算出物理地址輸出物理地址三、主要數據結構及其說明1、進程、段表及頁表

9、的存儲（使用結構體數組）/自定義頁表 struct Pageint block;int is_p; /記錄是否想調入內存int page_id ; /記錄頁號int frame_id ; /記錄頁框號int p_p ; /修改位，表示對應的頁是否在內存中，0表示不在，1表示在int p_m ; /修改位，表示對應的頁的內容從上一次裝入到內存中到現在是否改變，0表示沒有改變，1表示有;/自定義段表 struct Segmentint Pnum; /記錄頁數Page PagesMem_Size; int is_p; /記錄是否想調入內存int seg_id ; /記錄段號int p ;/頁表指針，

10、指向相應頁的起始地址int s_p ; /修改位，表示對應的段是否在內存中，0表示不在，1表示在int s_m ; /修改位，表示對應的段的內容從上一次裝入到內存中到現在是否改變，0表示沒有改變，1表示有;/自定義進程結構體struct Processint pro_id ;/記錄進程號int IsInMem;/記錄進程是否在內存int Total;/記錄某進程所需的總頁數int Snum; /記錄該進程的段數Segment Segments10;/進程數組的定義 Process ProcessesPro_sum_size; Segment SegmentsSeg_sum_size; Page

11、 PagesMem_Size; 2、使用一維數組存儲駐留集int Res_Set Res_Set_Size;3、函數介紹 Init(); /最初的內存初始化 Apply_Mem();/手工輸入進程個數、段數以及段內地址的賦值函數 Alloc_Mem(); /系統分配內存 Check_Mem(); /查看內存 Finish_Pro(); /手動結束進程，釋放相應空間 Print_Table();/段表和頁表的打印 Addr_Exchange(); /地址轉換函數 FIFO_Strategy(); /先進先出策略處理中斷 Menu();/一個功能菜單函數一、 程序運行時的初值和運行結果1、輸入：（

12、1）創建進程：1. 共三個段，其中1號段8個頁，2號段8個頁，3號段8個頁。2. 創建兩個進程：P1：2個段，1號段，調入內存，共5個頁，1、2、4、5頁調入駐留集，3號頁不調入；2號段，不調入，兩個頁，分別為2號頁和6號頁。P2：1個段，3號段，調入內存，共5個頁，1、2、3、4、5，全部調入駐留集。 （2）地址映射：P2： 3 123P1： 1 2050P1: 2 256 2、運行結果輸入進程號和相應的內存需求后，顯示每個進程的段表和頁表：（此時駐留集已滿！）查看內存，結果如下：進行地址映射：結束進程，釋放空間：四、結束語經過了兩周的學習和實驗，我終于完成了段頁式存儲算法，從開始做到系統實

13、現，再到論文的完成，每一步對我來說都是新的嘗試與挑戰。在這段時間，我學到了很多知識也有很多感受，查看相關的資料和書籍，讓自己頭腦中段頁是存儲管理的概念逐漸清晰，了解了段式存儲、頁式存儲以及段頁式存儲的的優缺點。使自己非常稚嫩作品一步步完善起來，每一次改進都是我學習的收獲，每一次試驗的成功都會讓我興奮好一段時間。這次做論文的經歷也會使我終身受益，我感受到做論文是要真真正正用心去做的一件事情，是真正的自己學習的過程和研究的過程，沒有學習就不可能有研究的能力，沒有自己的研究，就不會有所突破，那也就不叫論文了。希望這次的經歷能讓我在以后學習中激勵我繼續進步。參考文獻1 計算機操作系統（實驗指導書），滕

14、艷平等編，哈爾濱工業大學出版社，2008年9月2操作系統習題解答與實驗指導（第二版），張明等編，中國鐵道出版社，2007年12月3操作系統實驗教程，張麗芬等編，清華大學出版社，2006年4操作系統學習輔導，張獻忠編，清華大學出版社，2004年五、 源程序#define _CRT_SECURE_NO_DEPRECATE#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#define Mem_Size 64#define Block_Size 1#define Res_Set_Size 8 /駐留集

15、空間為8個頁#define Pro_sum_size 5 /定義全局變量int blockMem_Size; / 內存塊狀態標志數組，0：空閑，1：使用int seg_sumMem_Size2; /建立總的段數的二維數組int processCount = 0; / 記錄當前進程數int pageTotal; /總頁數int count = 0; /記錄進程已經占用的內存塊數int in_mem_seg = 0;/記錄調入內存的段數int in_mem_page = 0;/記錄調入內存的段數int seg_sum_num = 0 ;/需要的總段數int seg_Pnum = 0; /記錄每個段

16、需要的內存int i_min , j_min ,k_min , t_min;/在LRU算法中記錄使用時間最久的進程號、段號、頁號和該/頁在駐留集中的位置bool flag = true ;int pro_num = 0;/每一次進行進程申請的進程數量/自定義頁表struct Pageint block;int is_p; /記錄是否想調入內存int page_id ; /記錄頁號int frame_id ; /記錄頁框號int p_p ; /修改位，表示對應的頁是否在內存中，0表示不在，1表示在int p_m ; /修改位，表示對應的頁的內容從上一次裝入到內存中到現在是否改變，0表示沒/有改變

17、，1表示有;/自定義段表struct Segmentint Pnum; /記錄頁數struct Page PagesMem_Size; int is_p; /記錄是否想調入內存int seg_id ; /記錄段號int p ;/頁表指針，指向相應頁的起始地址int s_p ; /修改位，表示對應的段是否在內存中，0表示不在，1表示在int s_m ; /修改位，表示對應的段的內容從上一次裝入到內存中到現在是否改變，0 表/示沒有改變，1表示有;/自定義進程結構體struct Processint pro_id ;/記錄進程號int IsInMem;/記錄進程是否在內存int Total;/記錄

18、某進程所需的總頁數int Snum; /記錄該進程的段數struct Segment Segments10;/進程數組的定義 struct Process Processes5; struct Segment Segments10; struct Page PagesMem_Size; int Res_Set Res_Set_Size;/內存空間使用輸出void Menu();void FIFO_Strategy(); /先進先出策略void Check_Mem(); /查看內存void Init(); /進行初始化void Alloc_Mem(); /分配內存void Apply_Mem()

19、;/進程個數、段數以及段內地址的賦值函數void Addr_Exchange(); /地址轉換函數void Finish_Pro(); /手動結束進程，釋放相應空間void Print_Table();/段表和頁表的dayinvoid FIFO_Strategy()int p_id , s_id ,pa_id;int t , i , j , k;int temp1 = 0 , temp2 = 0 ;if(in_mem_page = Res_Set_Size)for(i = 0 ; i < processCount ; i+)for(j = 0 ; j < Processesi.Sn

20、um ;j+)for(k = 0 ; k < Processesi.Segmentsj.Pnum ; k+)if(Processesi.Segmentsj.Pagesk.frame_id = Res_Set0)Processesi.Segmentsj.Pagesk.p_p = 0;else if(Processesi.Segmentsj.Pagesk.p_p = 1)temp1+;if(temp1 = 0)Processesi.Segmentsj.s_p = 0;printf("段S%d已經被調出內存！n",Processesi.Segmentsj.seg_id);i

21、n_mem_seg-;temp2-;else if(Processesi.Segmentsj.s_p = 1)temp2+;if(temp2 = 0)Processesi.IsInMem = 0;printf("進程%d已經被調出內存！n",P_id);printf("被淘汰的頁框號為：%dn",Res_Set0);for(t = 1 ; t < Res_Set_Size ; t+)Res_Sett-1 = Res_Sett;for(i = 0 ; i < processCount ; i+)for(j = 0 ;

22、j < Processesi.Snum ; j+)for(k = 0 ; k < Processesi.Segmentsj.Pnum ; k+)if(Processesi.Segmentsj.Pagesk.frame_id = Res_Set0 | Processesi.Segmentsj.Pagesk.frame_id = Res_Set1|Processesi.Segmentsj.Pagesk.frame_id = Res_Set2|Processesi.Segmentsj.Pagesk.frame_id = Res_Set3|Processesi.Segmentsj.Page

23、sk.frame_id = Res_Set4|Processesi.Segmentsj.Pagesk.frame_id = Res_Set5|Processesi.Segmentsj.Pagesk.frame_id = Res_Set6)Processesi.Segmentsj.Pagesk.p_p = 1;elseProcessesi.Segmentsj.Pagesk.p_p = 0;Res_SetRes_Set_Size-1 = -1;in_mem_page-;printf("請輸入您想要調入內存的進程號和相應的段號、頁號，中間用空格隔開：n");scanf("

24、;%d %d %d", &p_id , &s_id , &pa_id);for(i = 0 ; i < processCount ; i+) if(P_id = p_id) for(j = 0 ; j < Processesi.Snum ; j+) if(Processesi.Segmentsj.seg_id = s_id) for(k = 0 ; k < Processesi.Segmentsj.Pnum ; k+)if(Processesi.Segmentsj.Pagesk.page_id = pa_id) if

25、(Processesi.Segmentsj.Pagesk.p_p = 0)printf("頁%d已經成功調入內存!n", Processesi.Segmentsj.Pagesk.page_id);Processesi.Segmentsj.Pagesk.p_p = 1;in_mem_page+;Res_Setin_mem_page-1 = Processesi.Segmentsj.Pagesk.frame_id;Print_Table();elseprintf("頁%d已經在內存中了!n",Processesi.Segmentsj.Pagesk.page_

26、id);Menu();void Check_Mem()int k,i;printf("n內存總量：%d 塊 n已用空間：%d 塊n剩余空間：%d 塊n進程總數：%d 個n", Mem_Size, count, Mem_Size-count, processCount);if (flag && count < Mem_Size)printf("下面是可用的空閑塊：n");for (k = 0 , i = 0 ; k < Mem_Size ; k+)if (blockk = 0)printf("%2d ", k

27、, +i);if (i = 10)putchar('n');i = 0;putchar('n');Menu();void Init()int i;/ 初始化內存狀態標志數組for (i = 0 ; i < Mem_Size ; i+)blocki = 0;/ 初始化駐留集for (i = 0 ; i < 30 ; i+)Res_Seti = -1;printf("-n");printf("初始化結果如下：n");Check_Mem();flag = false;void Print_Table()int i,j

28、,k;for(i = 0 ; i < processCount ; i+) printf("進程p%d已經分配好內存!n",P_id); Processesi.IsInMem = 1; printf("該進程的段表內容如下：n"); for(j = 0 ; j < Processesi.Snum ; j+) printf("段號： 段的長度： 頁的起始地址： P位： M位：n"); printf("%dt%dtt%dtt%dt%dn",Processesi.Segmentsj.

29、seg_id,Processesi.Segmentsj.Pnum,Processesi.Segmentsj.p,Processesi.Segmentsj.s_p,Processesi.Segmentsj.s_m); printf("該段的頁表內容如下：n"); printf("頁號： 頁框號： P位： M位：n"); for(k = 0 ; k < Processesi.Segmentsj.Pnum ; k+) printf("%dt%dt%dt%dtn",Processesi.Segmentsj.Pagesk.page_id,

30、Processesi.Segmentsj.Pagesk.frame_id,Processesi.Segmentsj.Pagesk.p_p,Processesi.Segmentsj.Pagesk.p_m); void Alloc_Mem()int i,j,k,t;printf("nn*n");for(i = 0 ; i < pro_num ; i+)Processesi.Total = 0;if(count+Processesi.Total > Mem_Size) for(j = 0 ; j < Processesi.Snum ; j+) Processes

31、i.Total += Processesi.Segmentsj.Pnum;printf("內存空間不足,進程p%d及以后的內存分配失敗!",i+1);break;break; else for(j = 0 ; j < Processesi.Snum ; j+) Processesi.Segmentsj.p = count ;if( Processesi.Segmentsj.is_p = 1) Processesi.Segmentsj.s_p = 1; else Processesi.Segmentsj.s_p = 0; for(k = 0 ; k < Proce

32、ssesi.Segmentsj.Pnum ; k+)Processesi.Segmentsj.Pagesk.frame_id = count; blockcount = 1;if(Processesi.Segmentsj.Pagesk.is_p = 1) Processesi.Segmentsj.Pagesk.p_p = 1; Res_Setin_mem_page = Processesi.Segmentsj.Pagesk.frame_id; in_mem_page+;elseProcessesi.Segmentsj.Pagesk.p_p = 0;count+; if(in_mem_page

33、> Res_Set_Size)printf("駐留集已滿！頁框號為%d以后的頁沒能進入駐留集。n",Res_SetRes_Set_Size-1);for(t = Res_Set_Size ; t < in_mem_page ; t+)for(j = 0 ; j < Processesi.Snum ; j+)for( k = 0 ; k < Processesi.Segmentsj.Pnum ; k+)if(Res_Sett = Processesi.Segmentsj.Pagesk.frame_id)Processesi.Segmentsj.Page

34、sk.p_p = 0;in_mem_page = Res_Set_Size; printf("nn"); Print_Table();Menu();void Apply_Mem()int i,is,ts,j,tp,ip; int l = 0;int temp_count = 0;/輸入內存總需求（多少段，每個段多大）printf("現記錄您需要的總內存大?。簄");printf("請輸入您需要的總段數：");scanf("%d",&seg_sum_num);printf("請輸入段號和相應的頁數，

35、中間用空格隔開:n");for (i = 0 ; i < seg_sum_num ; i+)scanf("%d %d",&seg_sumi0,&seg_sumi1);getchar();printf("nn");printf("進程內存空間申請！n"); printf("請輸入進程的數目(大于0,小于等于5的整數):"); scanf("%d",&pro_num);processCount += pro_num;while(pro_num<=0 |

36、pro_num > Pro_sum_size) printf("您輸入的進程個數超出閾值！n");printf("請輸入進程的數目(大于0,小于等于5的整數):"); scanf("%d",&pro_num);processCount += pro_num; for(is = 0 ; is < pro_num ; is+) printf("n*n");printf("請輸入第%d個進程的進程號：", is+1);scanf("%d",&Proces

37、_id);printf("請輸入進程p%d的段數:",P_id);scanf("%d",&Processesis.Snum);while(Processesis.Snum > seg_sum_num )printf("您輸入的段數超值！n");printf("請輸入進程p%d的段數:",P_id);scanf("%d",&Processesis.Snum);printf("請輸入該進程需要的

38、段號和是否需要調入內存，中間用空格可開（1->是/0->否）：n");for(ts = 0 ; ts < Processesis.Snum ; ts+)scanf("%d %d",&Processesis.Segmentsts.seg_id , &Processesis.Segmentsts.is_p);Processesis.Segmentsts.s_m = 0;getchar();for(j = 0 ; j < Processesis.Snum ; j+)printf("請輸入段S%d所需的頁數：",

39、Processesis.Segmentsj.seg_id);scanf("%d",&Processesis.Segmentsj.Pnum);while(Processesis.Segmentsj.Pnum > seg_sumj1)printf("您輸入的頁數超值！n");printf("請輸入段S%d所需的頁數：",Processesis.Segmentsj.seg_id);scanf("%d",&Processesis.Segmentsj.Pnum);for(tp = 0 ; tp <

40、 Processesis.Snum ; tp+)if(Processesis.Segmentstp.is_p = 1)printf("請輸入段S%d中的頁號和是否需要調入內存，中間用空格可開（1->是/0->否）:n",Processesis.Segmentstp.seg_id);for(ip = 0 ; ip < Processesis.Segmentstp.Pnum ; ip+)scanf("%d %d",&Processesis.Segmentstp.Pagesip.page_id , &Processesis.S

41、egmentstp.Pagesip.is_p);Processesis.Segmentstp.Pagesip.p_m = 0;getchar();elseprintf("請輸入段S%d中的頁號（中間用空格隔開）:n",Processesis.Segmentstp.seg_id);for(ip = 0 ; ip < Processesis.Segmentstp.Pnum ; ip+)scanf("%d",&Processesis.Segmentstp.Pagesip.page_id);Processesis.Segmentstp.Pagesi

42、p.p_m = 0;getchar();Alloc_Mem();void Finish_Pro()int p_id;int i , j , k;printf("請輸入您想結束的進程號：");scanf("%d",&p_id);for(i = 0 ; i < processCount ; i+)if(P_id = p_id && Processesi.IsInMem != 1)printf("該進程不在內存中！n");break;else if(P_id

43、= p_id && Processesi.IsInMem = 1) Processesi.IsInMem = 0;for(j = 0 ; j < Processesi.Snum ; j+)if(Processesi.Segmentsj.s_p = 1)Processesi.Segmentsj.s_p = 0 ;in_mem_seg-;for(k = 0 ; k < Processesi.Segmentsj.Pnum ; k+)if(Processesi.Segmentsj.Pagesk.p_p = 1)Processesi.Segmentsj.Pagesk.p_p

44、= 0;in_mem_page-; blockProcessesi.Segmentsj.Pagesk.frame_id = 0;count-; processCount-;printf("進程%d已經成功退出內存了！n",P_id);break;Menu();void Addr_Exchange()int p_id,s_id,offset;int i ,j , k;int address;printf("請輸入進程號:");scanf("%d",&p_id);for(i = 0 ; i < processCount ; i+)if(P_id = p_id)if