操作系统原理
课程设计
课程名称： 模拟请求分页存储管理方式中的
地址转换和缺页中断
专业班级：
组 长：
成 员：
指导教师：
2012 / 20## 学年 第 1 学期
目录
设计题目... 3
设计简介... 3
设计目标... 3
设计步骤... 3
1.设计概要... 3
2.详细设计... 4
3.程序流程图... 6
程序截图... 6
设计总结... 7
参考文献... 8
程序代码... 8
设计题目
《模拟请求分页存储管理方式中的地址转换和缺页中断》
设计简介
在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。通过这次实习理解在分页式存储管理中怎样实现虚拟存储器。了解分页式存储管理如何实现地址转换，认识分页式虚拟存储管理中如何处理缺页中断。
设计目标
程序完成了请求分页存储管理中地址转换过程和模拟缺页中断的处理。实验具体包括：首先对给定的地址进行地址转换工作，若发生缺页则先进行缺页中断处理，然后再进行地址转换；最后编写主函数。
假定主存8KB，每个主存块2048字节，作业为16KB，系统中每个作业分得主存块3块。
设计步骤
1.设计概要
地址转换：假定主存块的大小为2n字节，主存大小为2m'字节和逻辑地址m位，则进行地址转换时，首先从逻辑地址中的高m-n位中取得页号，然后根据页号查页表，得到块号，并将块号放入物理地址的高m'-n位，最后从逻辑地址中取得低n位放入物理地址的低n位就得到了物理地址。如下图：
在分页式虚拟存储管理方式中，作业信息作为副本放在磁盘上，作业执行时仅把作业信息的部分页面装入主存储器，作业执行时若访问的页面在主存中，则按上述方式进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断”，由操作系统把当前所需的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。页式虚拟存储管理方式中页表除页号和该页对应的主存块号外，至少还要包括存在标志（该页是否在主存），磁盘位置（该页的副本在磁盘上的位置）和修改标志（该页是否修改过）。
缺页中断：
① 根据当前执行指令中逻辑地址中的页号查页表，判断该页是否在主存储器中，若该页标志为“0”，形成缺页中断。
② 操作系统处理缺页中断的方法就是查主存分配表，找一个空闲主存块；若无空闲块，查页表，选择一个已在主存的页面，把它暂时调出主存。若在执行过程中该页被修改过，则需将该页信息写回磁盘，否则不必写回；
③ 找出该页的磁盘位置，启动磁盘读出该页信息，把磁盘上读出的信息装入第2步找到的主存块，修改页表中该页的标志为“1”；
④ 由于产生缺页中断的那条指令没有执行完，所以页面装入后应重新执行被中断的指令。当重新执行该指令时，由于要访问的页面已在主存中，所以可正常执行。
本程序采用了简单的先进先出的页面置换算法。
2.详细设计
页表机制：
（1） 状态位：用于指示该页是否调入内存，供程序访问是参考。
（2） 修改位：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页的时候就不需要再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重新写回到外存上，以保证外存中所保留的始终是最新副本。
（3） 外存地址：用于指出该页在外存上的地址。
定义页表
struct
{
int page_num; //页号
int flag; //状态位 1表示在内存中，0表示不在内存中
int block_num; //物理块号
int write; //修改位 1表示修改，0表示不修改。
int out_num; //磁盘地址
}page[6]; //改程序初始页表大小为6页
页表初始化截图：
程序要求输入作业进程块的逻辑地址和此进程块是否在调入内存中执行的时候需要修改。程序会计算出此逻辑地址的页号，判断该页号是否在内存中，如果在，则程序输出该页的物理地址。如果不在内存中，则启动缺页中断程序，置换出内存中的一页，换入需要的页面。输出此时的页表和该页的物理地址。
3.程序流程图
程序截图
（1）不发生缺页中断：
输入：0 2014
（2）发生缺页中断
输入1 4000
( 3 )程序结束
输入-1 -1
设计总结
我们的题目是模拟分页式存储管理中硬件的地址转换和产生缺页中断，主要的思路和步骤就是根据流程图走下来的。
在这个实验中由于所学的知识有限，为了理解在分页式存储管理中怎样实现虚拟存储器，做了很多知识准备工作，参考了相关书籍资料，对怎样产生和处理缺页中断有了一定的了解。
在对题目深刻了解后我们就开始编程，在编程中我们遇到许多程序和算法问题。因此，在调试上运用了大量的时间。但最后在努力研究下，问题都得到了解决，收获是很大的。而且我在编程是也掌握了不少编程技巧。并在这次的编写过程中，培养了团结合作的精神，大家分工合作，共同讨论，最终完成了这次设计。
通过做本次实验，我们对分页式虚拟存储管理系统和缺页中断有了更深入的认识。在分页式虚拟存储系统中是把作业信息的副本存放在磁盘上。而在请求分页系统中，每当所要访问的页面不在内存时，便产生一次缺页中断，请求OS将所缺之页调入内存。本次实验即是做模拟分页式存储管理中硬件的地址转换和缺页中断。通过编写模拟硬件的地址转换工作的程序，不仅加深了我们对绝对地址如何转换的理解，同时也锻炼了我们的编程能力。
当然，本次设计也存在一定的缺陷。程序没有设计快表，没有设计内存是否已满。当遇到页面不在内存中，直接就是换出和换入。由于所掌握的知识有限，此程序没有使用图形界面语言编写。在以后的设计中，我们会更在注重程序的完美性和实用性。
借此机会，我们要特别感谢指导老师申志军，在我们此门课程的学习中给予悉心指导和帮助。老师的一丝不苟的工作和对教学的认真态度深深感染了我们。
最后，向支持和帮助过我们的老师和同学表示深深的谢意。
参考文献
《计算机操作系统》 汤子瀛 哲凤屏 汤小丹 编著 西安电子科技大学出版社
《操作系统习题解答与实验指导》李珍 王煜张明 编著 中国铁道出版社
《C语言程序设计》 谭浩强 编著 清华大学出版社
《数据结构(C语言版)》 吴伟民 严蔚敏 编著 清华大学出版社
程序代码
#include<iostream.h>
#include<cstdlib>
int m=3; //m为作业内存中的内存块块数
int page_length=6; //页表实际长度
int p[3]; //存放在内存中的页的页号
int head=0; //内存中页号队列的头指针
int size=1024; //系统的页面大小
struct
{
int page_num; //页号
int flag; //状态位
int block_num; //物理块号
int write; //修改位
int out_num; //磁盘地址
}page[6];
void function(int log_add,int write)
{
int ph_add,ad,block_num,page_num;
start:
page_num=log_add/size;
ad=log_add%size;
if(page_num>=page_length)
{
cout<<"不存在该页"<<endl;
exit(1);
}
if(page[page_num].flag==1)
{
block_num=page[page_num].block_num;
ph_add=block_num*size+ad;
cout<<"对应物理地址是："<<ph_add<<endl;
if (write==1)
page[page_num].write=1;
cout<<"此时页表为"<<endl;
cout<<"页号 状态位 物理块号 修改位 外存地址 "<<endl;
for(int l=0;l<6;l++)
{
cout<<" "<<page[l].page_num<<"\t"<<page[l].flag<<"\t"<<page[l].block_num<<"\t"<<page[l].write<<"\t"<<page[l].out_num<<endl;
}
}
else
{
cout<<"发生缺页中断 "<<" "; //缺页中断程序
int j;
j=p[head];
p[head]=page_num;
head=(head+1)%m;
if (page[j].write==1)
cout<<"将页"<<j<<"写回磁盘第"<<page[j].out_num<<"块"<<endl;
page[j].flag=0;
page[page_num].block_num=page[j].block_num;
page[page_num].flag=1;
page[j].write=0;
cout<<"淘汰物理块号"<<page[j].block_num<<"中的第"<<j<<"页"<<"，从磁盘第"<<page[page_num].out_num<<"块中调入第"<<page_num<<"页"<<endl;
page[j].block_num=0;
goto start;
}
}
void main()
{
int write;
int log_add;
int i=3;
for(int l=0;l<6;l++) //初始页表
{
page[l].page_num=l;
page[l].flag=0;
page[l].write=0;
page[l].out_num=i;
i++;
}
int y=2;
for(int q=0;q<3;q++)
{
page[q].block_num=y;
page[q].flag=1;
p[q]=q;
y++;
}
cout<<"初始页表\n";
cout<<"页号 状态位 物理块号 修改位 外存地址 "<<endl;
for(l=0;l<6;l++)
{
cout<<" "<<page[l].page_num<<"\t"<<page[l].flag<<"\t"<<page[l].block_num<<"\t"<<page[l].write<<"\t"<<page[l].out_num<<endl;
}
cout<<endl;
cout<<"输入write的值和逻辑地址";
cin>>write>>log_add;
while(write!=-1 ||log_add!=-1)
{
function(log_add,write);
cout<<"输入write的值和逻辑地址";
cin>>write>>log_add;
}
}
第二篇：生产者消费者问题 操作系统课程设计
课程设计报告
课程名称： 操作系统
专业 计算机科学与技术
学生姓名 班学级 号 指导教师 完成日期
信息工程学院
题目：生产者-消费者问题的模拟实现
一、设计目的
本课程设计是学习完“操作系统原理”课程后进行的一次全面的综合训练，通过课程设计，更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。
二、设计内容
（1）概述
设计目的:通过研究Linux 的进程机制和信号量实现生产者消费者问题的并发控制。
说明:有界缓冲区内设有20个存储单元,放入/取出的数据项设定为1-20这20个整型数。
设计要求:(1)每个生产者和消费者对有界缓冲区进行操作后,即时显示有界缓冲区的全部内容,当前指针位置和生产者/消费者县城的标识符。(2)生产者和消费者各有两个以上。(3)多个生产者或多个消费者之间须有共享对缓冲区进行操作的函数代码。
（2）设计原理
通过一个有界缓冲区把生产者和消费者联系起来。假定生产者和消费者的优先级是相同的，只要缓冲区未满，生产者就可以生产产品并将产品送入缓冲区。类似地，只要缓冲区未空，消费者就可以从缓冲区中取走产品。应该禁止生产者向满的缓冲区送入产品，同时也应该禁止消费者从空的缓冲区中取出产品，这一机制有生产者线程和消费者线程之间的互斥关系来实现。与计算打印两进程同步关系相同，生产者和消费者两进程P和C之间应满足下列两个同步条件：
① 只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取信息，否则消费者必须等待。
② 只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。
为了满足第一个同步条件，设置一个同步信号量full，它代表的资源是缓冲区满，它的初始值为0，它的值为n时整个缓冲池满。这个资源是消费者类进程C所有，C进 1
程可以申请该资源，对它施加P操作，而C进程的合作进程生产者进程P对它施加V操作。同样为了满足第二个同步条件，设置另一个同步信号量empty，它代表的资源是缓冲空区，它的初始值为n，表示缓冲池中所有缓冲区空。信号量full表示可用缓冲区数量，信号量empty表示缓冲区数量，设置整型变量：存入指针in和取出指针out。
为解决生产者/消费者问题，应该设置两个资源信号量，其中一个表示空缓冲区的数目，用g_hFullSemaphore表示，其初始值为有界缓冲区的大小SIZE_OF_BUFFER；另一个表示缓冲区中产品的数目，用g_hEmptySemaphore表示，其初始值为0.另外，由于有界缓冲区是一个临界资源，必须互斥使用，所以还需要在设置一个互斥信号量g_hMutex，初始值为1.
P原语的主要动作是：
① sem减1；
② 若sem减一后仍大于或等于零，则进程继续执行；
③ 若sem减一后小于零，则该进程被阻塞后入与该信号相对应的队列
中，然后转进程调度。
V原语的操作主要动作是：
① sem加1；
② 若相加结果大于零，进程继续执行；
③若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程
然后再返回原进程继续执行或转进程调度。
采用的同步方法：
1）利用函数CreateMutex(NULL,FALSE,NULL)创建互斥信号量g_hMutex，表
示缓冲区当前的状态，若为true时，则表示缓冲区正被别的进程使用。三个参数表示的意义分别为：指向安全属性的指针，初始化互斥对象的所有者,指向互斥对象名的指针。
2）利用函数CreateSemaphore(NULL,SIZE_OF_BUFFER-1,SIZE_OF_BUFFER-1, NULL)创建缓冲区满的信号量g_hFullSemaphore，值为true时表示缓冲区已满。四个参数分别为：表示是否允许继承、设置信号机的初始计数、设置信号机的最大计数、指定信号机对象的名称（-1是因为计数从开始）。
2
3）利用函数CreateSemaphore(NULL,0,SIZE_OF_BUFFER-1,NULL)创建缓冲区空的信号量g_hEmptySemaphore，该值为true时表示缓冲区为空。
5、数据定义及其详细解释
const unsigned short SIZE_OF_BUFFER = 20; //缓冲区长度 unsigned short ProductID = 0; //产品号
unsigned short ConsumeID = 0; //将被消耗的产品号
unsigned short in = 0; //产品进缓冲区时的缓冲区下标 unsigned short out = 0; //产品出缓冲区时的缓冲区下标 int g_buffer[SIZE_OF_BUFFER]; //缓冲区是个循环队列 bool g_continue = true; //使程序跳出循环，控制程序结束
HANDLE g_hMutex; //用于线程间的互斥
HANDLE g_hFullSemaphore; //当缓冲区满时迫使生产者等待 HANDLE g_hEmptySemaphore; //当缓冲区空时迫使消费者等待 DWORD WINAPI Producer(LPVOID); //生产者线程
DWORD WINAPI Consumer(LPVOID); //消费者线程
（3）详细设计及编码
流程图
生产者：
3
4
//创建各个互斥信号
g_hMutex = CreateMutex(NULL,FALSE,NULL);
g_hFullSemaphore
CreateSemaphore(NULL,SIZE_OF_BUFFER-1,SIZE_OF_BUFFER-1,NULL);
g_hEmptySemaphore = CreateSemaphore(NULL,0,SIZE_OF_BUFFER-1,NULL); //调整下面的数值，可以发现，当生产者个数多于消费者个数时， //生产速度快，生产者经常等待消费者；反之，消费者经常等待。 const unsigned short PRODUCERS_COUNT = 3; //生产者的个数 const unsigned short CONSUMERS_COUNT = 1; //消费者的个数 //总的线程数
const unsigned short THREADS_COUNT
PRODUCERS_COUNT+CONSUMERS_COUNT;
HANDLE hThreads[PRODUCERS_COUNT]; //各线程的handle DWORD producerID[CONSUMERS_COUNT]; //生产者线程的标识符 DWORD consumerID[THREADS_COUNT]; //消费者线程的标识符 //创建生产者线程
for (int i=0;i {
hThreads[i]=CreateThread(NULL,0,Producer,NULL,0,&producerID[i]); if (hThreads[i]==NULL)
return -1;
}
//创建消费者线程
for ( i=0;i {
hThreads[PRODUCERS_COUNT+i]=CreateThread(NULL,0,Consumer,NULL,0 &consumerID[i]);
if (hThreads[i]==NULL)
return -1;
}
while(g_continue)
{
if(getchar())
{ //按回车后终止程序运行
g_continue = false; }}
return 0; }
5
（2） 生产者生产一个产品的函数：
//生产一个产品。简单模拟了一下，仅输出新产品的ID号 void Produce()
{
std::cerr << "Producing " << ++ProductID << " *** "; std::cerr << "Succeed" << std::endl;
}
（3）把新生产的产品放入缓冲区的函数：
//把新生产的产品放入缓冲区
void Append()
{
std::cerr << "Appending a product *** "; g_buffer[in] = ProductID;
in = (in+1)%SIZE_OF_BUFFER;
std::cerr << "Succeed" << std::endl;
}
（4）输出缓冲区当前的状态的函数：
//输出缓冲区当前的状态
for (int i=0;i {
std::cout << i <<": " << g_buffer[i];
if (i==in)
std::cout << " <-- 生产";
if (i==out)
std::cout << " <-- 消费";
std::cout << std::endl;
}
从缓冲区中取出一个产品的函数：
//从缓冲区中取出一个产品
void Take()
{
std::cerr << "Taking a product *** ";
ConsumeID = g_buffer[out];
out = (out+1)%SIZE_OF_BUFFER;
利用信号量解决生产者消费者问题
6
std::cerr << "Succeed" << std::endl;
}
（5）输出缓冲区当前的状态的函数：
//输出缓冲区当前的状态
for (int i=0;i {
std::cout << i <<": " << g_buffer[i];
if (i==in)
std::cout << " <-- 生产";
if (i==out)
std::cout << " <-- 消费";
std::cout << std::endl;
}
}
（6）消耗一个产品的函数：
//消耗一个产品
void Consume()
{
std::cerr << "Consuming " << ConsumeID << " *** "; std::cerr << "Succeed" << std::endl;
}
3.生产者和消费者算法
（1）生产者算法：
//生产者
DWORD WINAPI Producer(LPVOID lpPara)
{
while(g_continue)
{
WaitForSingleObject(g_hFullSemaphore,INFINITE); WaitForSingleObject(g_hMutex,INFINITE); Produce();
Append();
Sleep(1500);
ReleaseMutex(g_hMutex);
ReleaseSemaphore(g_hEmptySemaphore,1,NULL); 7
}
return 0;
}
（2）消费者算法：
//消费者
DWORD WINAPI Consumer(LPVOID lpPara)
{
while(g_continue)
{
WaitForSingleObject(g_hEmptySemaphore,INFINITE); WaitForSingleObject(g_hMutex,INFINITE); Take();
Consume();
Sleep(1500);
ReleaseMutex(g_hMutex);
ReleaseSemaphore(g_hFullSemaphore,1,NULL); }
return 0;
}
（4）运行结果分析
8
9
输入输出数据说明和分析：
该程序设置的缓冲区数据长度为20，生产者个数为3，消费者个数为1，程序启动后，生产者先进行生产，当3个生产者全部生产完之后，消费者开始从缓冲区中取出产品，当消费者取出一个后，生产者开始继续生产，当生产完3个之后，消费者开始从缓冲池中取产品，依次循环。
（5）设计小结
本次课程设计主要是对操作系统中线程，进程同步互斥等知识的应用，生产者—消费者问题是很著名的同步问题，的确是既简单又复杂。此次编写的程序基本实现了设计要求的功能，对于老师提出的关于程序的一点小修改仍未能解答出来，但是给我一点时间，我相信以后定能理解。
一个课程设计让我对本学期所学的操作系统课程有了更深刻的理解，加强了对基础的实践运用能力，让我能把所学的知识融会贯通。
（6）参考文献
【1】计算机操作系统(第3版)，汤小丹，西安电子科技大学出版社.
【2】Visual C++面向对象编程教程，王育坚，清华大学出版社.
10