今天整理文件时发现了上学期做的大作业，记录一下．
1.需求分析
某多道程序系统采用可变分区存储管理，供用户使用的内存空间为200KB，磁带机5台。采用静态方式分配外部设备，且不能移动内存中的作业，进程调度采用FCFS算法，忽略用户作业I/O操作时间。现有作业序列如下：
作业号进入时间运行时间(min)内存需求(KB)磁带机(台)
A 8:30 40 30 3
B 8:50 25 120 1
C 9:00 35 100 2
D 9:05 20 20 3
E 9:10 10 60 1
求：（1）FCFS算法选中作业装入内存时间、开始执行时间、执行结束时间、执行的次序、作业平均周转时间、内存分配情况；
（2）SJF算法选中作业装入内存时间、开始执行时间、执行结束时间、执行的次序、作业平均周转时间、内存分配情况；
２．详细说明：
1 ．先来先服务算法。说明：
( 1 ) 8 : 30 作业A 到达并投入运行。注意它所占用的资源。
( 2 ) 8 : 50 作业B 到达，资源满足进主存就绪队列等CPu 。
( 3 ) 9 : 00 作业C 到达，主存和磁带机均不够，进后备作业队列等待。
( 4 ) 9 : 05 作业D 到达，磁带机不够，进后备作业队列等待。后备作业队列有C 、D 。
( 5 ) 9 : 10 作业A 运行结束，归还资源磁带，但注意主存不能移动（即不能紧缩）。作业B 投入运行。作业C 仍因主存不够而等在后备队列。这时作业E 也到达了，。也由于主存不够进入后备作业队列。此时作业D 因资源满足（主存磁带均满足），进主存就绪队列等待。后备作业队列还有C 、E 。
( 6 ) 9 : 35 作业B 运行结束，作业D 投入运行。这时作业C 因资源满足而调入主存进就绪队列等CPU 。而作业E 因磁带机不够继续在后备作业队列等待。
( 7 ) 9 : 55 作业D 运行结束，作业C 投入运行。这时作业E 因资源满足而调入主存进就绪队列等CPU 。
( 8 ) 10 : 30 作业C 运行结束，、作业E 投入运行。
( 9 ) 10 : 40 作业E 运行结束。
2 ．短作业优先算法。说明：
( 1 ) 8 : 30 作业A 到达并投入运行。注意它所占用的资源。
( 2 ) 8 : 50 作业B 到达，资源满足进主存就绪队列等CPU 。
( 3 ) 9 : 00 作业C 到达，主存和磁带机均不够，进后备作业队列等待。
( 4 ) 9 : 05 作业D 到达，磁带机不够，进后备作业队列等待。后备作业队列有C 、D .
( 5 ) 9 : 10 作业A 运行结束，归还资源磁带，但注意主存不能移动（即不能紧缩）。作业B 投入运行。作业C 仍因主存不够而等在后备队列。这时作业E 也到达了，虽然该作业最短，也由于主存不够进入后备作业队列．此时作业D 因资源满足（主存磁带均满脚，进主存就绪队列等待。后备作业队列还有C 、E 。
( 6 ) 9 : 35 作业B 运行结束，作业D 投入运行。这时作业C 和E 资源均满足，但按SJF 应把作业E 调入主存进就绪队列等CPU 。而作业C 因磁带机不够继续在后备作业队列等待。
( 7 ) 9 : 55 作业D 运行结束，作业C 调入主存进就绪队列等CPU .
( 8 ) 10 : 05 作业E 运行结束，作业C 投入运行．
( 9 ) 10 : 40 作业C 运行结束。
３.概要设计
2.1内存分配
-
要维护两条链表，已分配内存链，未分配内存链。
-
已分配内存链里的节点为进程名，内存开始地址和结束地址。
-
未分配内存链里的节点为内存开始地址和结束地址且初始化的时候首节点为（0，200）。
-
当有内存变动的时候同时修改两条链表。
2.2设备分配
2.3就绪队列
-
已分配内存的进程且设备足够的时候进入就绪队列
-
依次释放就绪队列中的进程
2.4后备队列
-
FCFS算法，后备队列按到达顺序申请内存和设备
-
SJF算法，后备队列按短作业优先的顺序申请内存和设备
2.5数据的录入
-
进程的到达时间为整型变量
-
后续的相关计算都以第一个进程的到达时间为基准进行计算
2.6进程调度
采用FCSFS算法调度
2.7作业调度算法
-
FCFS算法
-
SJF算法
2.8菜单
*******************任务2*进程调度采用FCFS********************
1-输入作业
2-选择作业调度算法(默认为FCFS)
3-显示答案
4-清屏
5-退出
*******************任务2*进程调度采用FCFS********************
完整代码
http://download.csdn.net/detail/a__yes/9184021
4. 实现与测试
4.1 进程进内存
在内存满足的情况下，在未分配链中切出一块内存，直接将切下的内存加到已分配内存链尾。
bool in(string No, int p_mem)
{
unusedlist *p, *q; //工作指针
bool sign=false; //内存改变标志
int rem; //记录要分配内存的起始地址
p = unusedhead;
while (p->next)
{
if (p->next->end - p->next->start >p_mem) //空闲分区大于请求大小
{
rem = p->next->start;
p->next->start = p->next->start + p_mem; //修改未分配链
sign = true;
break;
}
else if (p->next->end - p->next->start == p_mem) //空闲分区等于请求大小
{
rem = p->next->start;
q = p->next;
p->next = q->next;
delete q;
sign = true;
break;
}
p = p->next;
}
usedlist *x;
x = usedhead;
if (sign) //内存改变时才添加已分配节点
{
usedlist *z = new usedlist();
z->No = No;
z->start = rem; //添加已分配节点
z->end = rem + p_mem;
while (x->next)
{
x = x->next;
}
z->next = x->next;
x->next = z;
return true;
}
return false;
}
4.2 进程释放内存
将已分配链该No的节点删除，并将其加到为分配内存链中。
void del(string No) //已分配内存
{
usedlist *p,*q,*o; //加o，因为要初始化q
p= usedhead;
q = new usedlist(); //用来保存要释放的进程节点
while (p->next)
{
if (p->next->No == No) //根据进程名来删除节点
{
o = p->next;
q->start = o->start;
q->end = o->end;
q->No = o->No;
q->next = o->next;
p->next = o->next;
delete o;
break;
}
p = p->next;
}
unusedlist *x,*y,*w;
x = unusedhead; //未分配列表
while (x->next)
{ //q为已分配链里删除的节点
if (unusedhead->next == NULL) //只剩头节点
{
unusedlist *z = new unusedlist();
z->start = q->start;
z->end = q->end;
z->next = unusedhead->next;
unusedhead->next = z;
break;
}
if (x->next->end < q->start) //q的起始地址大于前面节点的结束地址
{
if (x->next->next) //q前后有节点
{
if (x->next->next->start > q->end)
{
unusedlist *z = new unusedlist();
z->start = q->start;
z->end = q->end;
y = x->next;
z->next = y->next;
y->next = z;
break;
}
else if (x->next->next->start == q->end)
{
y = x->next;
y->next->start = q->start;
break;
}
}
else //q前有节点，后无节点
{
unusedlist *z = new unusedlist();
z->start = q->start;
z->end = q->end;
y = x->next;
z->next = y->next;
y->next = z;
break;
}
}
else if (x->next->end == q->start) //q前有节点
{
if (x->next->next) //q前后有节点
{
if (x->next->next->start > q->end)
{
x->next->end = q->end;
}
else if (x->next->next->start == q->end)
{
x->next->end = x->next->next->end;
y = x->next;
w = y->next;
y->next = w->next;
delete w;
}
}
else //q前有无节点，后无节点
{
x->next->end = q->end;
}
break;
}
else //q前无节点
{
if (x->next->start == q->end)
{
x->next->start = q->start;
break;
}
else
{
unusedlist *z = new unusedlist();
z->start = q->start;
z->end = q->end;
z->next = unusedhead->next;
unusedhead->next = z;
break;
}
}
x = x->next;
}
}
4.3 输出两条链表情况
void ls()
{
usedlist *p;
p = usedhead;
cout << "已分配列表：
";
while (p->next)
{
cout << "(" <<p->next->No<<","<< p->next->start << ","
<< p->next->end << ") ";
p = p->next;
}
unusedlist *q;
q = unusedhead;
cout << "
未分配列表：
";
while (q->next)
{
cout << "(" << q->next->start << ',' << q->next->end << ") ";
q = q->next;
}
cout << endl;
}
4.4 进程进队列
调用list->in函数进行进队列区分
void in_mem(int &m_cidai, PCB pcb)
{
done = true;
if (m_cidai >= pcb.p_cidai&&list->in(pcb.No, pcb.p_mem))
{ //进就绪队列
m_cidai -= pcb.p_cidai;
pcbready[r_count] = pcb;
r_count++; //就绪队列计数
}
else
{
pcbback[b_count] = pcb; //进后备队列
b_count++; //后备队列计数
}
}
4.4 升序排序
void sort(PCB *pcb,int num)
{
for (int i = 1;i<num; i++)
{
for (int ii = 0; ii < num - i; ii++)
{
if (pcb[ii].run_time>pcb[ii+1].run_time)
{
PCB p_pcb = pcb[ii]; pcb[ii] = pcb[ii + 1]; pcb[ii + 1] = p_pcb;
}
}
}
}
4.5 作业调度
将第一个进程完成之前到达的作业，进行分别入队。在第一个进程完成之后到下一个进程完成之前到达的进程分别入队，将后备队列的进程在分别入队。以此类推。
void dispatch(int &m_cidai, int m,string way)
{
int j=0; //cpu中就绪队列进程的序号
int m_sign=0; //到达并进队的位置
int a=1; //就绪队列中已计算（其他时间）的 pcb位置
r_count = 0;
t = pcb[0].ar_time;
pcb[0].sta_time = t;
pcb[0].end_time = pcb[0].sta_time + pcb[0].run_time;
pcb[0].in_time = t; //第一个任务可以确定
pcb[0].rou_time = pcb[0].end_time - pcb[0].sta_time;
pcbready[0] = pcb[0];
while (j < m)
{
done = false;
cout << "时间："<<t << endl;
if (m_sign<m)
cout << "已到达进程尝试进内存.
";
for (int i = m_sign; i < m; i++)
{
if (pcb[i].ar_time <= t + pcbready[j].run_time||a==r_count&&b_count==0)
{ //到达的pcb 或 cpu为空且后备队列为空
in_mem(m_cidai, pcb[i]);
m_sign = i + 1;
}
}
if (done) //调用in_mem判断
list->ls();
for (int i = a; i < r_count; i++)
{
if (pcbready[i].ar_time>t)
pcbready[i].in_time = pcbready[i].ar_time;
else
pcbready[i].in_time = t;
if (pcbready[i].ar_time > pcbready[i - 1].end_time) //cpu为空
pcbready[i].sta_time = pcbready[i].ar_time;
else
pcbready[i].sta_time = pcbready[i - 1].end_time;
pcbready[i].end_time = pcbready[i].sta_time + pcbready[i].run_time;
pcbready[i].rou_time = pcbready[i].end_time - pcbready[i].ar_time;
a = i + 1;
}
cout << pcbready[j].No << "执行完,后备队列尝试进内存.
";
list->del(pcbready[j].No);
m_cidai += pcbready[j].p_cidai; //释放内存
t = pcbready[j].end_time;
j++;
int bb_count = b_count; //需要将b_count置零
b_count = 0;
for (int i = 0; i < bb_count; i++)
{
if (way=="sjf") //SJF算法判断
sort(pcbback, bb_count);
in_mem(m_cidai, pcbback[i]);
}
list->ls();
}
}