作业调度&&页面置换算法
由于惰性，本来可以早点写完《计算机操作系统》的上机实验，硬是拖到了寒假。
现在还是无聊时候写下的这篇博文，寒假真的是没啥事干，所以强制自己学吧，同时补上之前的坑。
题目
- 设计一个内存分配模拟程序。假定在计算机系统作业后备队列中有六个等待调度运行的作业，参与分配的内存大小为32KB，采用简单页式管理，每个页帧的大小为1KB。根据要求进行内存的分配和回收。要求打印内存分配表。有关作业的组织和作业有关参数的设置请自行设计，要大致符合实际情况。
- 对访问串：1，2，3，4，1，2，5，1，2，3，4，5，驻留集大小分配为3，4时，试指出在淘汰算法FIFO、LRU和OPT控制下的页故障数，要求列表显示和比较。
- 设计一个比较完善的随机数发生器和指令地址流，使能更接近实际情况。
简单解释
对于第一题来说，要求我们模拟程序内存的分配任务，题目意思相当于把32KB大小的内存分为32个以1KB大小的盒子，用这些盒子来装载我们的6个目标作业，实现内存的简单分配与回收。
对于第二题来说，所谓的页面置换就是说：在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
- ==先进先出置换算法（FIFO）==
当需要置换一页时，选择在主存中停留时间最长的一页置换，即先进入内存的页，先退出内存。（计数（标记）不清零，取最大的替换） -
==最近最久未使用算法（LRU）==
当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。（相当于每次替换或命中需要把相应那一页计数（标记）清零） -
==最佳置换算法（OPT）==
发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。（计数（标记）最大的页应该被置换）
那么经过前面的简单解释后，我们来调度这些页面，完成该题吧。
实验结果
- 作业调度（使用优先级调度方案）
由于作业调度过程过多，所以只显示开始与结束的相关信息。
作业开始状态：内存使用情况（Memory Usage）是显示该作业使用了哪些内存的页帧号，空白表示未装入内存，处于等待状态。
作业结束状态：当作业处于完成状态时，该作业的内存被回收，供其他作业使用，最终结果如下图。
- 页面置换算法
- 驻留集为3时：
- 驻留集为4时：
大自然的搬运工
- 作业调度（优先级）
//
// Created by CongTsang on 2018/10/27.
//
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define Ready 1
#define Run 2
#define Block -1
#define Finish 3
#define Wait 4
#define SPACE 32
typedef struct node
{
int name;
int cpuTime;
int needTime;
int priority;
int state;
int capacity;
struct node* next;
}PCB;
typedef struct node2
{
int ID; // Process name
int flag; // used or not
node2()
{
ID = 0;
flag = 0;
}
}page;
PCB *run, *ready, *finish, *wait;
page *Memory = new page[SPACE];
int N; //Processes
int LEFT = SPACE; // remaining of page
void allocMem(PCB *p)
{
int size = p->capacity;
for (int i = 0; i < SPACE; ++i) {
if (Memory[i].flag == 1) continue;
if (size > 0)
{
Memory[i].ID = p->name;
Memory[i].flag = 1;
size--;
}
}
}
void freeMem(PCB *p)
{
for (int i = 0; i < SPACE; ++i) {
if (Memory[i].ID != p->name) continue;
Memory[i].ID = 0;
Memory[i].flag = 0;
}
LEFT += p->capacity;
}
string state_to_str(int _state)
{
switch(_state)
{
case Ready: return "Ready";
case Run: return "Run";
case Block: return "Block";
case Wait: return "Wait";
case Finish: return "Finish";
default: return "";
}
}
void mem_to_str(PCB *p)// 打印内存使用情况
{
cout<<" Memory Usage: ";
for (int i = 0; i < SPACE; ++i)
{
if (p->name == Memory[i].ID)
cout<<i<<" ";
}
cout<<endl;
}
void display(char algo, PCB *head)
{
if (algo == 'P')
{
while (head != NULL)
{
cout<<" --------------------------------------------------------------------------------------------"<<endl;
printf(" %-14d%-14d%-19s%-16d%-17d%d\n",
head->name,head->priority,state_to_str(head->state).c_str(),head->cpuTime,head->needTime,head->capacity);
mem_to_str(head);
head = head->next;
}
}else {
cout<<"R";
}
}
void showProcess(char algo)
{
cout<<" ============================================================================================="<<endl;
PCB *tmp;
if (algo == 'P')
{
cout<<"| ProsId | Prio | ProsState | CPUTime | needTime | needSize |"<<endl;
if (run != NULL)
display(algo,run);
tmp = ready;
if (tmp != NULL)
display(algo,tmp);
tmp = wait;
if (tmp != NULL)
display(algo,tmp);
tmp = finish;
if (tmp != NULL)
display(algo,tmp);
}else {
cout<<"1"<<endl;
}
}
void insert(PCB *p)
{
if (p->state == Ready)// 插入Ready队列
{
PCB *cur, *pre;
cur = ready, pre = NULL;
while (cur && cur->priority >= p->priority)
{
pre = cur;
cur = cur->next;
}
if (pre == NULL)
{
p->next = cur;
ready = p;
}else {
p->next = pre->next;
pre->next = p;
}
}else if (p->state == Finish) // 插入Finish队列
{
PCB *cur, *pre;
cur = finish, pre = NULL;
while (cur && cur->priority >= p->priority)
{
pre = cur;
cur = cur->next;
}
if (pre == NULL)
{
p->next = cur;
finish = p;
}else {
p->next = pre->next;
pre->next = p;
}
}else if (p->state == Wait) // 插入Wait队列
{
PCB *cur, *pre;
cur = wait, pre = NULL;
while (cur && cur->capacity <= p->capacity) // 按照大小排序，从小到大
{
pre = cur;
cur = cur->next;
}
if (pre == NULL)
{
p->next = cur;
wait = p;
}else {
p->next = pre->next;
pre->next = p;
}
}
}
void Priority(char algo)
{
while (ready != NULL || wait != NULL)
{
if (wait != NULL && LEFT >= wait->capacity)
{
PCB *tmp = wait;
wait = wait->next;
tmp->next = NULL;
LEFT -= tmp->capacity;
tmp->state = Ready;
allocMem(tmp);
insert(tmp);
showProcess(algo);
}
run = ready;
run->state = Run;
ready = ready->next;
run->next = NULL;
while (run != NULL)
{
run->priority -= 3;
run->cpuTime += 1;
run->needTime -= 1;
showProcess(algo);
if (run->needTime > 0)
{
if (ready == NULL)continue;
if (run->priority < ready->priority)
{
run->state = Ready;
insert(run);
run = NULL;
}
}else {
run->state = Finish;
freeMem(run);
insert(run);
run = NULL;
}
showProcess(algo);
}
}
}
void createP(char algo)
{
PCB *p;
int i;
int _needTime,_priority,_capacity;
run=NULL;
ready=NULL;
finish=NULL;
for(i=1; i <= N; i++)
{
_needTime = rand()%10+1;
_priority = rand()%20+1;
_capacity = rand()%25+1;
p=(PCB*)malloc(sizeof(PCB));
p->name = i;
p->needTime = _needTime;
p->priority = _priority;
p->capacity = _capacity;
p->cpuTime = 0;
if (_capacity <= LEFT)
{
LEFT -= _capacity;
p->state = Ready;
allocMem(p);
insert(p);
} else {
p->state = Wait;
insert(p);
}
}
cout<<" !!Here they come!!"<<endl;
showProcess(algo);
Priority(algo);
}
int main()
{
char i = 'p';
cout<<"How many Processes: ";
cin>>N;
i = (char)(toupper(i));
createP(i);
}
- 页面置换算法
由于OPT我始终没理清楚用我的代码方法来实现，所以直接搬运参考代码了，海涵海涵。
//
// Created by CongTsang on 2018/11/14.
//
#include <iostream>
#include <stdlib.h>
using namespace std;
int pageFlow[] = {1,2,3,4,1,2,5,1,2,3,4,5};
int flowSize = sizeof(pageFlow)/sizeof(int);
int Block;
int showTable[15][8];
char aimed[15];
typedef struct node
{
int No;
int Time;
struct node *next;
}pageTable;
pageTable *replace, *head;
void initShowTable()
{
for (int i = 0; i < 15; i++)
{
aimed[i] = 'N';
for (int j = 0; j < 8; j++)
{
showTable[i][j] = -1;
}
}
}
void allocPage(pageTable *p)
{
pageTable *cur, *pre;
cur = head, pre = NULL;
while (cur)
{
pre = cur;
cur = cur->next;
}
if (pre == NULL)
{
p->next = cur;
head = p;
} else {
p->next = pre->next;
pre->next = p;
}
}
void storeGroup(int index)
{
pageTable *cur;
cur = head;
int i = 0;
while (cur)
{
showTable[index][i++] = cur->No;
cur = cur->next;
}
}
void show()
{
for (int i = 0; i < flowSize; i++)
cout<<pageFlow[i]<<" ";
cout<<endl<<"----------------------------------\n";
for (int i = 0; i < Block; i++)
{
for (int j = 0; j < flowSize; j++)
{
if (showTable[j][i] != -1)
cout<<showTable[j][i]<<" ";
else cout<<" ";
}
cout<<endl;
}
cout<<"----------------------------------\n";
for (int i = 0; i < flowSize; i++) cout<<aimed[i]<<" ";
cout<<endl;
}
void runTime() // all page's time++
{
pageTable *cur;
cur = head;
while (cur)
{
cur->Time++;
cur = cur->next;
}
}
pageTable* findReplace() // Normal findPage
{
pageTable *cur, *rep;
cur = head, rep = head;
while (cur)
{
if (cur->Time > rep->Time) rep = cur; // find longest
cur = cur->next;
}
return rep;
}
bool findPageF(int target)
{
pageTable *cur;
cur = head;
while (cur)
{
if (cur->No == target)
{
// cur->Time = 0;// LRU core
return true;
}
cur = cur->next;
}
return false;
}
bool findPageL(int target)
{
pageTable *cur;
cur = head;
while (cur)
{
if (cur->No == target)
{
cur->Time = 0;// LRU core
return true;
}
cur = cur->next;
}
return false;
}
void FIFO(int N)
{
pageTable *p;
int m = 0;
int miss = 0;
double Mispc = 0.0;
replace = NULL;
head = NULL;
cout<<"=================================="<<endl;
cout<<" ***Here goes the FIFO****"<<endl;
cout<<"----------------------------------\n";
for(int i = 0; i < flowSize; i++)
{
if (m < N && !findPageF(pageFlow[i])) // Enough room but cannot find page
{ // add page
p = (pageTable*)malloc(sizeof(pageTable));
p->No = pageFlow[i];
p->Time = 0;
p->next = NULL;
miss++;
m++;
allocPage(p);
} else {
if (!findPageF(pageFlow[i])) // Not enough and cannot find page
// start to replace
{
replace = findReplace();
replace->No = pageFlow[i];
replace->Time = 0;
miss++;
} else { // Find page (whatever room left)
aimed[i] = 'Y';
}
}
runTime();
storeGroup(i);
}
show();
cout<<"The num of missing pages is : "<<miss<<endl;
Mispc = double(miss)/double(flowSize)*100;
cout<<"The rate of missing pages is : "<<Mispc<<" %"<<endl;
cout<<"=================================="<<endl;
}
void LRU(int N)
{
pageTable *p;
int m = 0;
int miss = 0;
double Mispc = 0.0;
replace = NULL;
head = NULL;
cout<<"=================================="<<endl;
cout<<" ****Here goes the LRU****"<<endl;
cout<<"----------------------------------\n";
for(int i = 0; i < flowSize; i++)
{
if (m < N && !findPageL(pageFlow[i])) // Enough room but cannot find page
{ // add page
p = (pageTable*)malloc(sizeof(pageTable));
p->No = pageFlow[i];
p->Time = 0;
p->next = NULL;
miss++;
m++;
allocPage(p);
} else {
if (!findPageL(pageFlow[i])) // Not enough and cannot find page
// start to replace
{
replace = findReplace();
replace->No = pageFlow[i];
replace->Time = 0;
miss++;
} else { // Find page (whatever room left)
aimed[i] = 'Y';
}
}
runTime();
storeGroup(i);
}
show();
cout<<"The num of missing pages is : "<<miss<<endl;
Mispc = double(miss)/double(flowSize)*100;
cout<<"The rate of missing pages is : "<<Mispc<<" %"<<endl;
cout<<"=================================="<<endl;
}
int findP(int head,int tail,int B[],int Target,int num)
{
while(head!=tail)
{
if(B[head]==Target)
return 1;
head=(head+1)%num;
}
return 0;
}
int findPos(int num,int B[],int Target,int POS)
{
int pos,Max=0;
int findP;
int j;
for(int i=0;i<num;i++)
{
findP=0;
j=POS+1;
while(j<flowSize&&!findP)
{
if(B[i]==pageFlow[j])
{
findP=1;
if((j-POS)>Max)
{
Max=j-POS;
pos=i;
}
}
j++;
}
if(!findP)
{
Max=1000;
pos=i;
}
}
return pos;
}
void initB(int *B)
{
for(int i = 0; i < 10; i++)
{
B[i] = -1;
}
}
void storeG(int head,int tail,int B[],int index)
{
for (int i = head; i < tail; i++)
{
if (B[i] != -1) showTable[index][i] = B[i];
}
}
void OPT(int N)
{
int B[10];
initB(B);
int miss=0;
int use=0;
int pos;
double Mispc=0.0;
cout<<"=================================="<<endl;
cout<<" ****Here goes the OPT****"<<endl;
cout<<"----------------------------------\n";
for(int i=0;i<flowSize;i++)
{
if(use<N && !findP(0,use,B,pageFlow[i],N+1))
{
B[use]=pageFlow[i];
use++;
miss++;
}
else{
if(!findP(0,N,B,pageFlow[i],N+1))
{
miss++;
pos=findPos(N,B,pageFlow[i],i);
B[pos]=pageFlow[i];
}
else aimed[i] = 'Y';
}
storeG(0,N,B,i);
}
show();
cout<<"The num of missing pages is : "<<miss<<endl;
Mispc = double(miss)/double(flowSize)*100;
cout<<"The rate of missing pages is : "<<Mispc<<" %"<<endl;
cout<<"=================================="<<endl;
}
int main()
{
cout<<"Wellcome to @Page Replace Management@ "<<endl;
cout<<"The page Flow is : ";
for(int i = 0; i < flowSize; i++)
cout<<pageFlow[i]<<" ";
cout<<endl;
cout<<"The room of page(0 to exit) : ";
while(cin>>Block && Block)
{
initShowTable();
FIFO(Block);
initShowTable();
LRU(Block);
initShowTable();
OPT(Block);
}
return 0;
}
叨叨几句... 2 条评论
好长啊，博主辛苦了
@天津网站建设
谢谢夸奖鸭！还好吧，细看都是些重复的代码。