-齐齐哈尔大学操作系统课程综合实践题目：段页式存储算法班级：计本131：学号：指导教师：2016年6月段页式存储算法摘要：分页和分段存储管理方式都各有其优缺点，分页系统能有效地提高内存利用率，而分段系统则能很好滴满足用户需要。
对两种存储管理方式“各取所长”，则可以将两者结合成一种新的存储管理方式系统。
这种新系统既具有分段系统的便于实现、分段可共享、易于保护、可动态链接等一系列优点，又能像分页系统那样很好地解决内存的外部碎片问题，以及可为各个分段离散的分配内存等问题。
把这种结合起来形成的新系统称为“段页是系统”。
关键字：存储分配；内存块；进程一、实训内容与目的1、内容编写程序完成段页式虚拟存储管理存储分配、地址重定位和缺页中断处理。
（1）为一个进程的内存申请（多少个段，每个段多大）分配内存，当一个进程（完成）结束时回收内存；（2）对一个给定逻辑地址，判断其是否缺段、缺页，若不缺段、不缺页，则映射出其物理地址；（3）若缺段则进行缺段中断处理，若缺页则进行缺页中断处理。
假定内存64K，内存块（页框）大小为1K，进程逻辑地址空间最多4个段，每个段最大16K，进程驻留集大小为8页。
假设进程运行前未预先装入任何地址空间，页面淘汰策略采用局部（驻留集内）置换策略。
输出每次存储分配/回收时，内存自由块分布情况、相关进程的段表和页表信息。
2.目的（1）加深理解段页式虚拟存储管理的概念和原理。
（2）掌握段页式存储管理中存储分配（和回收）方法；（3）深入了解段页式虚拟存储管理中地址重定位（即地址映射）方法。
（4）深入理解段页式虚拟存储管理中缺段、缺页中断处理方法。
二、主要设计思路和流程图1、设计思路（1）内存大小为64K，页框大小为1K，驻留集最多放8个页，在初始时所有块都空闲，并输出空闲状态和所有可用的空闲块。
（2）进程、段表和页表均用结构体数组存储，其中每个进程对应一个段表，每个段表可以有一个或多个页表。
每次查询一个页时，要通过进程号找相应的段，通过段号找到该页。
（3）给出一个功能菜单，用户可以选择“创建进程”、“结束进程”、“查看内存”或地址映射。
（4）当用户选择“创建进程”时，现输入此次内存的总需求，即段号和相应的页数，并保存在一个全局的二维数组中，用于后面每个进程空间申请的数量的检查。
用户分别输入进程号，每个进程需要的段数，段号和相应的页号，并标记好是否要调入驻留集。
输入完成后，系统进行内存空间和驻留集空间的检查，若均未满，则分配成功；如果内存已满，则此次分配失败；如果驻留集已满，则修改溢出部分的标志位（即P位）。
（5）分配好空间后，将输出每个进程相应的段表和页表项。
（6）当用户选择“结束进程”时，清空该进程的段表和页表，修改标志位，释放掉在内存中的空间。
（7）当用户选择“查看内存”时，输出当前在内存中的进程个数、已用的内存块数和空闲的内存块数，并显示所用可用的空闲块。
（8）当用户选择“地址映射”时，先输入想查找的进程号，在检验正确的情况下，输入段号和段内偏移量，判断段的标志位，若该段不在驻留集中，则为虚段，进行缺段中断处理；若在驻留集中，检验偏移量是否越界，在不越界的前提下，根据偏移量计算页号并判断页的标志位，若该页不在驻留集中，则为虚页，进行缺页中断处理，若在驻留集中，则计算出相应的物理地址并输出。
2.程序流程图(1)总体流程图（2）进程创建流程图Input seg_sum_numInput seg_sum[i][0]，seg_sum[i][0] 输入段号和相应的页数i = 0 , i < pro_numInput Processes[i].pro_id; Input Processes[i].Snum; i++;pro_num >= 0 && pro_num < Pro_sum_sizeInt j = 0 , j < Processes[i].SnumInput Processes[i].Segments[j].seg_id; Input Processes[i].Segments[j].is_p; J++;(3)地址映射流程图Int k = 0 ; k < Processes[i].Segments[j].Pnum ;k++ Input Processes[i].Segments[j].Pages[k].page_id;Input Processes[i].Segments[j].Pages[k].is_p;Int k = 0 ; k < Processes[i].Segments[j].Pnum ;k++ Input Processes[i].Segments[j].Pages[k].page_id; Input Processes[i].Segments[j].Pages[k].is_p;Print_Table()Input pro_id 输入映射的进程号Input s_id , offset 输入段号和段内偏移量该段为实段 根据段表查页表，找到页框号三、主要数据结构及其说明1、进程、段表及页表的存储（使用结构体数组） //自定义页表 struct Page {int block;int is_p; //记录是否想调入内存 int page_id ; //记录页号 int frame_id ; //记录页框号int p_p ; //修改位，表示对应的页是否在内存中，0表示不在，1表示在int p_m ; //修改位，表示对应的页的内容从上一次装入到内存中到现在是否改变，0表示没有改变，1表示有 };//自定义段表 struct Segment {int Pnum; //记录页数 Page Pages[Mem_Size];int is_p; //记录是否想调入内存 int seg_id ; //记录段号int p ;//页表指针，指向相应页的起始地址int s_p ; //修改位，表示对应的段是否在内存中，0表示不在，计算出物理地址 输出物理地址1表示在int s_m ; //修改位，表示对应的段的内容从上一次装入到内存中到现在是否改变，0表示没有改变，1表示有};//自定义进程结构体struct Process{int pro_id ;//记录进程号int IsInMem;//记录进程是否在内存int Total;//记录某进程所需的总页数int Snum; //记录该进程的段数Segment Segments[10];};//进程数组的定义Process Processes[Pro_sum_size];Segment Segments[Seg_sum_size];Page Pages[Mem_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、输入：（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 2562、运行结果输入进程号和相应的内存需求后，显示每个进程的段表和页表：（此时驻留集已满！）查看内存，结果如下：进行地址映射：结束进程，释放空间：四、结束语经过了两周的学习和实验，我终于完成了《段页式存储算法》，从开始做到系统实现，再到论文的完成，每一步对我来说都是新的尝试与挑战。
在这段时间，我学到了很多知识也有很多感受，查看相关的资料和书籍，让自己头脑中段页是存储管理的概念逐渐清晰，了解了段式存储、页式存储以及段页式存储的的优缺点。
使自己非常稚嫩作品一步步完善起来，每一次改进都是我学习的收获，每一次试验的成功都会让我兴奋好一段时间。
这次做论文的经历也会使我终身受益，我感受到做论文是要真真正正用心去做的一件事情，是真正的自己学习的过程和研究的过程，没有学习就不可能有研究的能力，没有自己的研究，就不会有所突破，那也就不叫论文了。
希望这次的经历能让我在以后学习中激励我继续进步。
参考文献[1] 计算机操作系统（实验指导书），滕艳平等编，哈尔滨工业大学出版社，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 //驻留集空间为8个页#define Pro_sum_size 5//定义全局变量int block[Mem_Size]; // 内存块状态标志数组，0：空闲，1：使用int seg_sum[Mem_Size][2]; //建立总的段数的二维数组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; //记录每个段需要的内存int i_min , j_min ,k_min , t_min;//在LRU算法中记录使用时间最久的进程号、段号、页号和该//页在驻留集中的位置bool flag = true ;int pro_num = 0;//每一次进行进程申请的进程数量//自定义页表struct Page{int block;int is_p; //记录是否想调入内存int page_id ; //记录页号int frame_id ; //记录页框号int p_p ; //修改位，表示对应的页是否在内存中，0表示不在，1表示在int p_m ; //修改位，表示对应的页的内容从上一次装入到内存中到现在是否改变，0表示没//有改变，1表示有};//自定义段表struct Segment{int Pnum; //记录页数struct Page Pages[Mem_Size];int is_p; //记录是否想调入内存int seg_id ; //记录段号int p ;//页表指针，指向相应页的起始地址int s_p ; //修改位，表示对应的段是否在内存中，0表示不在，1表示在int s_m ; //修改位，表示对应的段的内容从上一次装入到内存中到现在是否改变，0 表//示没有改变，1表示有};//自定义进程结构体struct Process{int pro_id ;//记录进程号int IsInMem;//记录进程是否在内存int Total;//记录某进程所需的总页数int Snum; //记录该进程的段数struct Segment Segments[10];};//进程数组的定义struct Process Processes[5];struct Segment Segments[10];struct Page Pages[Mem_Size];int Res_Set [Res_Set_Size];//内存空间使用输出void Menu();void FIFO_Strategy(); //先进先出策略void Check_Mem(); //查看内存void Init(); //进行初始化void Alloc_Mem(); //分配内存void Apply_Mem();// 进程个数、段数以及段内地址的赋值函数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 < Processes[i].Snum ;j++){for(k = 0 ; k < Processes[i].Segments[j].Pnum ; k++){if(Processes[i].Segments[j].Pages[k].frame_id == Res_Set[0])Processes[i].Segments[j].Pages[k].p_p = 0;else{if(Processes[i].Segments[j].Pages[k].p_p = 1)temp1++;}}if(temp1 == 0){Processes[i].Segments[j].s_p = 0;printf("段S%d已经被调出内存！\n",Processes[i].Segments[j].seg_id);in_mem_seg--;temp2--;}else{if(Processes[i].Segments[j].s_p == 1)temp2++;}}if(temp2 == 0){Processes[i].IsInMem = 0;printf("进程%d已经被调出内存！\n",Processes[i].pro_id);}}printf("被淘汰的页框号为：%d\n",Res_Set[0]);for(t = 1 ; t < Res_Set_Size ; t++)Res_Set[t-1] = Res_Set[t];for(i = 0 ; i < processCount ; i++){for(j = 0 ; j < Processes[i].Snum ; j++){for(k = 0 ; k < Processes[i].Segments[j].Pnum ; k++){if(Processes[i].Segments[j].Pages[k].frame_id == Res_Set[0] ||Processes[i].Segments[j].Pages[k].frame_id == Res_Set[1]||Processes[i].Segments[j].Pages[k].frame_id == Res_Set[2]||Processes[i].Segments[j].Pages[k].frame_id == Res_Set[3]||Processes[i].Segments[j].Pages[k].frame_id == Res_Set[4]||Processes[i].Segments[j].Pages[k].frame_id == Res_Set[5]||Processes[i].Segments[j].Pages[k].frame_id == Res_Set[6]){Processes[i].Segments[j].Pages[k].p_p = 1;}elseProcesses[i].Segments[j].Pages[k].p_p = 0;}}}Res_Set[Res_Set_Size-1] = -1;in_mem_page--;}printf("请输入您想要调入内存的进程号和相应的段号、页号，中间用空格隔开：\n"); scanf("%d %d %d", &p_id , &s_id , &pa_id);for(i = 0 ; i < processCount ; i++){if(Processes[i].pro_id == p_id){for(j = 0 ; j < Processes[i].Snum ; j++){if(Processes[i].Segments[j].seg_id == s_id){for(k = 0 ; k < Processes[i].Segments[j].Pnum ; k++){if(Processes[i].Segments[j].Pages[k].page_id == pa_id){if(Processes[i].Segments[j].Pages[k].p_p == 0){printf("页%d已经成功调入内存!\n", Processes[i].Segments[j].Pages[k].page_id);Processes[i].Segments[j].Pages[k].p_p = 1;in_mem_page++;Res_Set[in_mem_page-1] = Processes[i].Segments[j].Pages[k].frame_id;Print_Table();}elseprintf("页%d已经在内存中了!\n",Processes[i].Segments[j].Pages[k].page_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 (block[k] == 0)printf("%2d ", k, ++i);if (i == 10){putchar('\n');i = 0;}}putchar('\n');}Menu();}void Init(){int i;// 初始化内存状态标志数组for (i = 0 ; i < Mem_Size ; i++)block[i] = 0;// 初始化驻留集for (i = 0 ; i < 30 ; i++){Res_Set[i] = -1;}printf("---------------------------------------\n");printf("初始化结果如下：\n");Check_Mem();flag = false;}void Print_Table(){int i,j,k;for(i = 0 ; i < processCount ; i++){printf("进程p%d已经分配好内存!\n",Processes[i].pro_id);Processes[i].IsInMem = 1;printf("该进程的段表内容如下：\n");for(j = 0 ; j < Processes[i].Snum ; j++){printf("段号：段的长度：页的起始地址：P位：M位：\n");printf("%d\t%d\t\t%d\t\t%d\t%d\n",Processes[i].Segments[j].seg_id,Processes[i].Segments[j].Pnum,Processes[i].Segments[j].p,Processes[i].Segments[j].s_p,Processes[i].Segments[j].s_m);printf("该段的页表内容如下：\n");printf("页号：页框号：P位：M位：\n");for(k = 0 ; k < Processes[i].Segments[j].Pnum ; k++){printf("%d\t%d\t%d\t%d\t\n",Processes[i].Segments[j].Pages[k].page_id,Processes[i].Segments[j].Pages[k].frame_id,Processes[i].Segments[j].Pages[k].p_p,Processes[i].Segments[j].Pages[k].p_m);}}}}void Alloc_Mem(){int i,j,k,t;printf("\n\n*******************************\n");for(i = 0 ; i < pro_num ; i++){Processes[i].Total = 0;if(count+Processes[i].Total > Mem_Size){for(j = 0 ; j < Processes[i].Snum ; j++){Processes[i].Total += Processes[i].Segments[j].Pnum;printf("内存空间不足,进程p%d及以后的内存分配失败!",i+1);break;}break;}else{for(j = 0 ; j < Processes[i].Snum ; j++){Processes[i].Segments[j].p = count ;if( Processes[i].Segments[j].is_p == 1)Processes[i].Segments[j].s_p = 1;elseProcesses[i].Segments[j].s_p = 0;for(k = 0 ; k < Processes[i].Segments[j].Pnum ; k++){Processes[i].Segments[j].Pages[k].frame_id = count;block[count] = 1;if(Processes[i].Segments[j].Pages[k].is_p == 1){Processes[i].Segments[j].Pages[k].p_p = 1;Res_Set[in_mem_page] =Processes[i].Segments[j].Pages[k].frame_id;in_mem_page++;}elseProcesses[i].Segments[j].Pages[k].p_p = 0;count++;}}if(in_mem_page > Res_Set_Size){printf("驻留集已满！页框号为%d以后的页没能进入驻留集。