一、试验目的
理解操作系统内存管理的原理及分页内存管理方案
二、试验要求
1、实现分页内存管理方案,假定页和帧的大小均为4KB,物理内存为128MB
2、输入为进程ID,所需内存大小等,输出为页表。
3、请按要求撰写实验报告,并和源程序一起打包上传
4、实验平台不限,linux和windows均可
5、与第一次实验的程序整合成一个程序
三、试验环境
Windows XP Visual C++ 6.0
四、试验内容
为了与上一个实验结合,并且考虑到可能需要兼容以后的实验,所以本次实验不但重写了PCB,而且按照自己对操作系统的理解构造出了一虚拟的I/O设备和两套调度程序(作业调度程序和CPU调度程序)
一、
首先从与内存分配相关的作业调度函数说起,程序中为Jobs_scheduler。 Job_scheduler的作用如下图所示;
Job_scheduler从大容量存储设备上的缓冲池中载入新生成的进程到内存,同时生成新的PCB到就绪队列中。 这里涉及到了两个数据结构cla Program,cla PCB。 Program :
PCB:
PCB中的state包含五个状态NEW、READY、RUN、WAITING、TERMINATED,加入到ReadyQueue中等待运行的PCB均为READY状态的,运行中会被置为RUN,
WAITNG状态为等待I/O设备的进程,如果进程状态为TERMINATED,将会被移出作业队列。
Job_scheduler函数在将program装入内存前,会查看帧表内空闲的帧的数目是否大于等于program所需的页数目,如果成立才装入,并且为PCB构造页表。构造时,先按照帧表通过顺序查找找到可用的帧,然后就将页的内容加载上去。
二、
接下来是CPU调度程序,也成为短期调度程序。
CPU_scheduler所做的工作如下图所示,其操作的队列是就绪队列RedayQueue
本程序采用的调度算法为分时调度,时间片大小TimeSlice取为1(当然这个随时都可用改动),
里面执行程序的函数Run是模拟CPU功能的,它会返回一个值,Normal表示执行正常,若是返回了INTERRUPT 中断;ERROR 出错就会中断此次运行,并且将所指PCB从ReadyQueue中移除。
这里的Run函数其实模拟了CPU的取指令和翻译指令的功能,本程序只有一个有实际作用的指令,\'O\',如果内存中的内容为\'0\'(十进制ASCⅡ码值),则代表需要利用I/O设备输出该地址内容。如上图所示,PCB会加入到WaitingQueue中等待I/O,并判断此时I/O设备是否开启,如果未开启则开启设备。Run函数也因此返回一个interrupt值。 运行结果
在编号为1的进程中的第一个内存单位设置了一条I/O指令,可以看出其发生中断后等待I/O完成才重新回到ReadyQueue中并执行完毕。
以上结果是在内存足够大的情况,下面再看一组内存不能同时满足需求的情况
此次内存设为11帧,编号为1的进程需要10帧,编号为2的进程需要1帧,我们看到,2号进程顺利载入并执行了,但其他进程都要等到1号进程执行完释放内存后才能载入内存,符合预期情况。
五、心得体会
为了很好的仿真,本次试验尽可能地模拟了硬件的工作,,如输入输出设备和模拟CPU的run函数,基本上把教材77页调度问题的队列图所示功能模拟出来了,也大体实现了从用户程序到系统进程再到硬件的执行过程。
对于本次实验的核心内容——内存管理,实现了从磁盘到内存额装载过程,实现了页表的创建,实现了内存的释放。缺陷是没有考虑到换入换出等动态的情况,也就是说在此做了一个假设:每个进程相互独立且对于每个单独的进程来说,内存空间是足够大的。
第二点缺陷是,没有按照题目要求分配那么多的内存空间,因为那么大输入输出不好控制。
在本程序中,输入输出与要求有出入,并没有输入进程需要的时间,而是以进程的具体内容代替,在这里又有一个假设:假设进程在CPU中每执行一步需要一个单位的时间,这样进程的大小也就等价于进程需要的时间了(排除有I/O请求的情况),个人认为这样假设比人工限定执行时间更加贴近现实情况。
程序的输入非即时的,而是通过事先设定好的5个进程加上运行后随机生成的若干进程,也是为了模拟实际情况考虑。
因为全手工输入需要输入进程的到达时间,也就是需要根据到达时间来为缓冲池中进程排序的问题,但实际情况下到达时间是多余的,先创建的先加入队列即可,所以采用了随机生成的方式。
为了此次实验,复习了调度和内存管理两章的大部分内容,对操作系统对进程调度和内存分配管理有了更深入的认识,但只是从概念上,没有看到真正操作系统的代码或者算法实例,所以可能很多地方的代码与实际情况出入很大。
代码:
#include #include #include #include #include #include #include #include using namespace std ;
/***************
随机数,后面随机生成进程用的 *************/ void rand_seed() { int seed = static_cast(time(0)) ; srand(seed) ; }
int rand_int(int a, int b) { return a + rand() % (b1)
{
pc[1]++ ;
}
else
{
pc[0]++ ;
pc[1] = 0 ;
}
pcb.state = READY ; } else if (pc[1]
pc[1]++ ; } else
pcb.state = TERMINATED ; }
bool io_equipment = OFF ; /* I/O设备(DMA) */ DWORD WINAPI IOEquipment(LPVOID lpParamter) { io_equipment = ON ; list::iterator pw = WaitingQueue.begin() ; while( pw != WaitingQueue.end() ) {
/* 为了体现I/O设备速度较慢,所以在此用了Sleep函数 */
Sleep(1000);
cout number
if (pw->state == WAITING )
pw->state = READY ;
ReadyQueue.push_back(*pw) ;
pw = WaitingQueue.erase(pw) ;
if( pw != WaitingQueue.end())
pw++ ;
else
pw = WaitingQueue.begin() ; } io_equipment = OFF ; return FINISH ; }
HANDLE ioEquipment ; /**
模拟CPU执行
只实现了部分功能,并没有完全按照原理模拟
**/ int Run(PCB& pcb) { pcb.state = RUN ; list::iterator p = pcb.PageTable.begin() ; int addr[2] ;
addr[1] = pcb.pc[1] ; addr[0] = pcb.findframe(pcb.pc[0]) ;
switch ( Memory[addr[0] * FRAME + addr[1]] ) { case \'O\': //如果指令触发了输出设备
pcb.state = WAITING ;
pcr[0] = pcb.pc[0] ;
pcr[1] = pcb.pc[1] ;
IncPc(pcb, pcr) ;
pcb.pc[0] = pcr[0] ;
pcb.pc[1] = pcr[1] ;
AddOfIO = addr[0] * FRAME + addr[1] ;
WaitingQueue.push_back(pcb) ;
/* 如果I/O设备未开启,则打开,否则什么都不做 */
if(io_equipment == OFF)
ioEquipment = CreateThread(NULL, 0, IOEquipment, NULL, 0, NULL) ;
else
;
return INTERRUPT; default :
break ; }
/* 在没有跳转的情况下,运行之后,pc自加 */ pcr[0] = pcb.pc[0] ; pcr[1] = pcb.pc[1] ; IncPc(pcb, pcr) ; pcb.pc[0] = pcr[0] ; pcb.pc[1] = pcr[1] ;
return NORMAL ; }
HANDLE hMutex = CreateMutex(NULL, FALSE, \"screen\");
/* 长期调度程序,将缓冲池中的进程加载到内存上 */ DWORD WINAPI Jobs_scheduler(LPVOID lpParamter) { list::iterator p = BufferList.begin() ; while( true ) {
//WaitForSingleObject(hMutex, INFINITE);
if( p != BufferList.end() && p->page_numbers
{
ReadyQueue.push_back(PCB(*p)) ;
p = BufferList.erase(p) ;
}
else if( p != BufferList.end())
p++ ;
else
p = BufferList.begin() ;
//ReleaseMutex(hMutex);
} }
/* 利用RR算法的短期调度程序 */ DWORD WINAPI CPU_scheduler(LPVOID lpParamter) { list::iterator p = ReadyQueue.begin() ; int run_time = 0 ; int total_time = 1 ; while( true ) {
WaitForSingleObject(hMutex, INFINITE);
if ( p == ReadyQueue.end() )
p = ReadyQueue.begin() ;
while ( run_time state == READY )
{
p->run_time++ ;
run_time++ ;
//cout
cout number run_time
if(Run(*p) == NORMAL)
/* do nothing */ ;
else
{
p = ReadyQueue.erase(p) ;
break ;
}
/* 操作系统负责计时 */
}
run_time = 0 ;
if ( p->state == TERMINATED )
{
Release(*p) ;
p = ReadyQueue.erase(p) ;
}
else
{
p++ ;
}
ReleaseMutex(hMutex); } }
int main() { int num = 1 ; Program p1(num++, \"O123456089\") ; Program p2(num++, \"0\") ; Program p3(num++, \"01\") ; Program p4(num++, \"01\") ; Program p5(num++, \"01234\") ; BufferList.push_back(p1) ; BufferList.push_back(p2) ; BufferList.push_back(p3) ; BufferList.push_back(p4) ; BufferList.push_back(p5) ;
HANDLE hThread1 = CreateThread(NULL, 0, Jobs_scheduler, NULL, 0, NULL) ; HANDLE hThread2 = CreateThread(NULL, 0, CPU_scheduler, NULL, 0, NULL) ; while( true )
{
if (num
BufferList.push_back(Program(num++, \"156789\")) ; }
return 0 ; }