多道程序的cpu调度算法

① 基于优先数的时间片轮转调度算法调度处理器

没有完全符合的,但是差不多的,你自己改改吧!
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
typedef struct PCBA
{
char name[30];
int round;
int prio;
int cputime;
int needtime;
char state;
struct PCBA *next;
} PCB,*CurrentRunPCB,*LinkQueue;
CurrentRunPCB SelMosHeiPrio(LinkQueue *Q);//从Q链表中选择一个优先级最大的进程
void InitQueue(LinkQueue *Q);//初始化链表Q，如果链表没有头指针，可以省略；
void InsertQueue(LinkQueue * Q,PCB* run);
{
}//将Run结点插入链表Q中，表示就绪队列里多了一个进程
void Priosch(LinkQueue Wait_Queue,LinkQueue Finish_Queue)//优先法运行，从就绪队列Wait_Queue中选择进程执行，（选择队列中优先级最高的进程），执行结束的进程放入完成队列中；

{ while (WaitQueue!=NULL)
{
CurrentRunPCB run=SelMosHeiPrio(&WaitQueue); //run为就绪队列中优先级最高的进程

run->cputime+=2;//时间片为2
run->needtime-=2;
run->prio=50-run->needtime;//动态优先级，但是优先级随着运行时间的增加，优先级增加，所以谁优先级高会一直占用CPU
run->state='r';
if(run->needtime>0)
{ run->state='w';
InsertQueue(&WaitQueue,run) ;
}

else
{cout<<"当前运行进称为："<<run->name<<"运行结束后就绪队列情况："<<'\n';
run->state='F';
run->needtime=0;
InsertQueue(&FinishQueue,run) ;
Print(&WaitQueue);
}
//当然可以采用不看进程运行过程，直接将优先级高的运行完，插入完成队列
/*
CurrentRunPCB run=SelMosHeiPrio(&WaitQueue);
cout<<"当前运行进称为："<<run->name<<"运行结束后就绪队列情况："<<'\n';
Print(&WaitQueue);
run->cputime=run->needtime;
run->needtime=0;
run->prio=50;//动态优先级，但是优先级随着运行时间的增加，优先级增加，所以谁优先级高会一直占用CPU
run->state='F';
InsertQueue(&FinishQueue,run) ;*/
}
void Print(LinkQueue*Q)//将队列的元素显示输出，输出包含进程名，进程CPUTIME,NEEDTIME,状态，优先级

{LinkQueue p=*Q;
cout<<"name cputime needtime state prio'"<<'\n';
while (p!=NULL)
{ cout<<p->name<<'\t'<<p->cputime<<'\t'<<p->needtime<<'\t'<<p->state<<'\t'<<p->prio<<'\n';
p=p->next;
}
}
CurrentRunPCB DeQueue(LinkQueue*Q)//从就绪队列中取出一个进程

{LinkQueue p=*Q;

*Q=(*Q)->next;
p->next=NULL;
return p;
}
void Roundsch(LinkQueue WaitQueue,LinkQueue FinishQueue)//轮转法运行，从就绪队列Wait_Queue中选择进程执行一个时间片，执行结束的进程放入完成队列中；若一个时间片未能执行完的进程再插入到就绪队列
{ while (WaitQueue!=NULL)
{
CurrentRunPCB run=DeQueue(&WaitQueue);
cout<<"当前运行进称为："<<run->name<<"运行结束后就绪队列情况："<<'\n';
run->cputime+=2;//时间片为2
run->needtime-=2;
run->prio=50- run->cputime;
run->state='r';
if(run->needtime>0)
{InsertQueue(&WaitQueue,run) ;
run->state='w';
}
else
{run->state='F';
run->needtime=0;
InsertQueue(&FinishQueue,run) ;
}

Print(&WaitQueue);
}
cout<<"完成队列情况："<<'\n';
Print(&FinishQueue);
}

void SetAllpro(LinkQueue*Q)//设置优先级函数50-p->needtime
{int max=0;
LinkQueue p,t;
t=NULL;
p=*Q;
if (p!=NULL)
{
max=p->prio;
p=p->next;
while(p)
{
if (max<p->prio) max=p->prio;
p=p->next;
}
p=*Q;
t=*Q;
if (t==p&&max==t->prio)
{*Q=(*Q)->next;
t->next=NULL;
return t;}
else{
t=t->next;
while(t)
{
if (max==t->prio)
{
p->next=t->next;
t->next=NULL;
return t;

}
else{p=t;
t=t->next;
}
}
}
}
return t;
}
void main()
{
PCBA *pcb0,*pcb1,*pcb2,*pcb3,*pcb4; //five processes 五个进程
LinkQueue Wait_Queue,Finish_Queue; //两个队列 等待和完成
Wait_Queue=NULL; //给队列赋初值，如果带有头指针的链表，可以用函数；
Finish_Queue=NULL;
//InitQueue(&Wait_Queue);
//InitQueue(&Finish_Queue);
char ch;
//给各个进程设置初值
pcb0= new PCBA();
pcb1= new PCBA();
pcb2= new PCBA();
pcb3= new PCBA();
pcb4= new PCBA();
//example
strcpy(pcb0->name,"process1");
pcb0->round=2;
pcb0->prio=0;
pcb0->cputime=0;
pcb0->needtime=5;
pcb0->state='W';
pcb0->next=NULL;
strcpy(pcb1->name,"process2");
pcb1->round=2;
pcb1->prio=0;
pcb1->cputime=0;
pcb1->needtime=7;
pcb1->state='W';
pcb1->next=NULL;
strcpy(pcb2->name,"process3");
pcb2->round=2;
pcb2->prio=0;
pcb2->cputime=0;
pcb2->needtime=3;
pcb2->state='W';
pcb2->next=NULL;
strcpy(pcb3->name,"process4");
pcb3->round=2;
pcb3->prio=0;
pcb3->cputime=0;
pcb3->needtime=11;
pcb3->state='W';
pcb3->next=NULL;
strcpy(pcb4->name,"process5");
pcb4->round=2;
pcb4->prio=0;
pcb4->cputime=0;
pcb4->needtime=8;
pcb4->state='W';
pcb4->next=NULL;

//将各个进程插入就绪队列中
InsertQueue(&Wait_Queue,pcb0);
InsertQueue(&Wait_Queue,pcb1);
InsertQueue(&Wait_Queue,pcb2);
InsertQueue(&Wait_Queue,pcb3);
InsertQueue(&Wait_Queue,pcb4);
//利用此算法实现Wait_Queue中prio=50-needtime;
SetAllpro(&Wait_Queue);

cout<<"请输入选择的调度算法(1 or 2 or anykey exit!)："<<endl;
cin>>ch;
switch(ch)
{
case '1':
Print(&Wait_Queue);
Roundsch(Wait_Queue,Finish_Queue);
break;
case '2':
Print(&Wait_Queue);
Priosch(Wait_Queue,Finish_Queue);
break;
default :
cout<<"你选择了退出!"<<endl;
system("pause");
return;
}

return;
}

② 作业调度算法：编写并调度一个多道程序系统的作业调度模拟程序

回答：benben
新手
5月8日 08:33 作业调度的方法一般有：先来先服务算法，短程作业优先算法，响应比高者优先算法等等把
他就是把你要处理的总的作业，根据系统允许并行的工作得道数和系统的可利用的资源，调入内存的一种算法，如果要简单地说就是挑选最有者的过程！

③ 操作系统的调度算法

1)10:00Job1到达并投入运行。此时内存中有作业:Job1
2)10:05 Job2到达并进入内存。此时，Job1运行时间剩余是25min， Job2运行剩余时间是20min，根据SRTF，Job2开始运行。
3)10:25 Job2运行结束。Job3、Job4在后备队列中，据SJF，Job3进入内存，据SRTF，Job3开始运行。内存：Job1、Job3
4)10:30 Job3运行结束。Job4在后备队列中，Job4进入内存，据SRTF，Job4开始运行。内存：Job1、Job4
5)10:40 Job4运行结束。Job1重新继续运行。
6)11:05 Job1运行结束。

④ 处理机调度模拟程序：选择一个调度算法，实现处理机调度。

七、源程序：

#include <stdio.h>

int m1; //共享变量
int m2; //共享变量
struct{
int id; //进程标号
int waiter1; //指针，用于标识等待队列的下一个进程
int priority; //进程优先级
char status; //进程状态
}pcb[4];
struct{
int value; //信号量的值
int waiter2; //指针，用于标识等待此信号量队列的第一个进程
}sem[3];
char stack[11][4]; //现场保护堆栈
int i； //cpu中的通用寄存器
int ep; //当前运行进程指针
char addr; //程序运行时的地址
void init(); //初始化
int find(); //找出就绪进程
int w2(); //
int process1(); //进程1
int process2(); //进程2
int process3(); //进程3
int p(int,int ,char); //P原语
int v(int,int ,char); //V原语

main()
{

init();
printf("系统程序开始执行\n");
for(;;){
if(find()!=0) //找出就绪进程
w2(); //进程调度
else break;//退出程序
}
printf("系统程序结束\n");
}

void init() //初始化进程
{
int j,k;
pcb[0].status='w'; //进程状态设置为等待
pcb[0].priority=4; //进程的优先级别
for(j=1;j<=3;j++){
pcb[j].id=j; //进程编号
pcb[j].status='r'; //进程状态设置为就绪
pcb[j].waiter1=0; //进程指针初始化为0
pcb[j].priority=j; //设置进程优先级
}
for(j=1;j<=2;j++){
sem[j].value=1; //信号量赋值为1
sem[j].waiter2=0; //等待信号量队列的初始化
}
i=0; //CPU通用寄存器初始化
ep=0; //
addr='0'; //程序运行地址
m1=0; //共享变量初始化
m2=0; //共享变量初始化
for(j=1;j<=10;j++){
for(k=1;k<=3;k++)
stack[j][k]='0'; //现场保护堆栈初始化
}
}

int find(){ //查找初始化变量
int j;
for(j=1;j<=3;j++)
if(pcb[j].status=='r') return(j); //如果pcb队列中有就绪进程，返回进程编号
return(0);
}

int w2(){ //进程调度程序
int pd;
pd=find(); //找出就绪进程编号
if(pd==0) return(0); //如果没有找到就绪进程，退出程序
else if(ep==0){ //如果当前运行进程是否为0
pcb[pd].status='e'; //直接将当前进程设置为运行状态
ep=pd; //当前运行进程设置为pd
printf("进程%d正在执行\n",ep);
}
else
if(pcb[pd].priority<pcb[ep].priority)//如果当前进程比待调入进程优先级进行比较
{//调入进程优先级别高
pcb[ep].status='r'; //把CPU运行进程执行状态设置为就绪
printf("读取进程%d\n",pcb[pd].id);
pcb[pd].status='e'; //将待调入进程执行状态设置为执行
ep=pd; //将当前运行进程指针为待调入进程
}

printf("运行进程%d\n",ep);
i=stack[1][ep]; //恢复进程的通用寄存器中的值和运行地址。
addr=stack[2][ep];
switch(ep){ //根据当前运行的进程选择运行
case 1:process1();
break;
case 2:process2();
break;
case 3:process3();
break;
default:printf("当前进程出现错误%d\n",ep);
break;
}
}

int process1(){//进程1
if(addr=='m') goto m; //如果当前运行地址是m，跳到m运行
i=1;
a:
printf("进程1在信号量sem[1]上调用P操作\n");
if(p(1,1,'m')==0) return(0); //进行p操作，m表示程序执行到m
else goto m;
m:
printf("打印进程1...m1=%d\n",m1); //进程1的操作，打印，寄存器i＋5
printf("打印进程1...i=%d\n",i);
i+=5;

goto a; //跳回a执行
}

int process2(){//进程分为3部分
if(addr=='m') goto m;
if(addr=='n') goto n;
i=1;

a:
printf("进程2在信号量sem[2]上调用P操作\n");
if(p(2,2,'m')==0) return(0);

m:
m1=2*m2;
printf("进程2在信号量sem[1]上调用V操作m1=%d\n",m1);
if(v(1,2,'n')==0) return(0);
else{

n:
printf("打印进程2...i=%d\n",i);
i+=10;
goto a;
}
}

int process3(){
if(addr=='m') goto m;
if(addr=='n') goto n;
i=1;
a:
if(i>4){
printf("进程3在信号量sem[2]上调用P操作\n");
if(p(2,3,'n')==0) return(0);
}
n:
m2=i;
printf("进程3在sem[2]信号量上调用V操作m=%d\n",m2);
if(v(2,3,'m')==0) return(0);
else{
m:
i+=1;
goto a;
}
}

int p(int se,int p,char ad){
int w;
sem[se].value--; //信号量减1
if(sem[se].value==0) return(1); //如果信号量＝0，返回1，说明阻塞
printf("阻塞当前进程%d\n",p);
pcb[p].status='w'; //改变进程状态
ep=0; //运行进程为空
pcb[p].waiter1=0; //设为尾末
w=sem[se].waiter2; //找出等待队列的队尾
if(w==0) sem[se].waiter2=p; //插入等待队列
else{
while(pcb[w].waiter1!=0) w=pcb[w].waiter1;
pcb[w].waiter1=p;
}
stack[1][p]=i; //保存现场
stack[2][p]=ad;
return(0);
}

int v(int se,int p,char ad){
int w;
sem[se].value++; //信号量加1
if(sem[se].value>0) return(1); //信号量>0，无等待进程
w=sem[se].waiter2; //返回第一个等待进程
sem[se].waiter2=pcb[w].waiter1; //调整位置
pcb[w].status='r'; //进程改变状态
printf("唤醒进程%d\n",w);
stack[1][p]=i; //进程状态进栈
stack[2][p]=ad;
return(0);
}

⑤ 计算机操作系统知识点

计算机操作系统知识点

网络的神奇作用吸引着越来越多的用户加入其中，正因如此，网络的承受能力也面临着越来越严峻的考验―从硬件上、软件上、所用标准上......，各项技术都需要适时应势，对应发展，这正是网络迅速走向进步的催化剂。下面是关于计算机操作系统知识点，希望大家认真阅读!

4.1.1操作系统的概念

操作系统：是管理计算机软硬件资源的程序，同时它又是用户与计算机硬件的接口。

4.1.2操作系统的构成

进程管理、内存管理、文件管理、输入/输出系统管理、二级存储管理、联网、保护系统、命令解释程序

4.2.1操作系统的类别

经过多年的发展，操作系统多种多样。为提高大型计算机系统的资源利用率，操作系统从批处理，多道程序发展为分时操作系统。为了满足计算机处理实时事件的需要，就有实时操作系统。为适应个人计算机系统的需要又出现了桌面操作系统。为适应并行系统的需要，就有了多处理器操作系统。为满足网络和分布计算的需要，就有了网络操作系统和分布式操作系统。此外，还有为支持嵌入式计算机的嵌入式操作系统。

4.2.2计算环境

从计算机诞生至今，操作系统总是与具体的计算环境相联系，它总是在某种计算环境中设置和使用，就目前来看计算环境可分为以下几类：

1.传统计算环境

指普通意义下的独立或联网工作的通用计算机所形成的计算环境。

2.基于Web的计算环境

互联网的普及使得计算被延伸到Web环境。

3.嵌入式计算环境

嵌入式计算机就是安装在某些设备上的计算部件，其计算相对比较简单。

4.3.1进程的概念

什么是进程?它与程序有什么区别?

程序：用户为完成某一个特定问题而编写的操作步骤。

进程：可以简单地被看作是正在执行的程序。但是进程需要一定的资源来完成它的任务(例如CPU时间、内存、文件和I/O设备)。

进程与程序的区别在于进程是动态的、有生命力的，而程序是静态的。一个程序加载到内存，系统就创建一个进程，程序执行结束后，该进程也就消亡了。

在计算机中，由于多个程序共享系统资源，就必然引发对CPU的争夺。如何有效地利用CPU资源，如何在多个请求CPU的进程中选择取舍，这就是进程管理要解决的问题。

4.3.3进程控制块PCB(略)

为了控制进程，操作系统就必须知道进程存储在哪里，以及进程的一些属性。

进程控制块是进程实体的一部分，是操作系统中记录进程的专用数据结构。一个新的进程创建时，操作系统就会为该进程建立一个进程控制块。操作系统根据进程控制块对并发进程进行控制。

4.3.4进程调度及队列图

计算机采用多道程序的目的是使得计算机系统无论何时都有进程运行，单处理器的计算机在某一时刻CPU只能运行一个进程，如果存在多个进程，其它进程就需要等待CPU空闲时才能被调度执行。

当一个进程处于等待或CPU时间片用完时，操作系统就会从该进程中拿走CPU控制权，然后再交给其它进程使用，这就是进程的调度。

4.3.5CPU调度及其准则

在设计CPU调度程序时主要应该考虑的准则包括：

(1)CPU使用率。让CPU尽可能地忙。

(2)吞吐量。让CPU在一定时间内完成的进程数尽可能多。

(3)周转时间。让进程从提交到运行完成的时间尽可能短。

(4)等待时间。让进程在就绪队列中等待所花时间之和尽可能短。

(5)响应时间。让进程从提交请求到产生第一响应之间的时间尽可能短。

主要的CPU调度算法

1、先到先服务

2、最短作业优先

3、优先权

4、轮转

5、多级队列

6、多级反馈队列

4.3.7进程的同步与互斥

进程的同步就是指相互协作的进程不断调整它们之间的相对速度，以实现共同有序地推进。

换句话说,在操作系统中，允许多个进程并发运行。然而，有些进程之间本身存在某种联系，它们在系统中需要一种协作，以保证进程能正确有序地执行并维护数据的一致性。

在操作系统中，可能存在着多个进程。而系统中一些资源一次只允许一个进程使用，这类资源被称为临界资源。在进程中访问临界资源的那段程序称为临界区。当一个进程进入临界区执行时，其它进程就不允许进入临界区执行，否则就会导致错误结果。由此得出:

多个进程并发执行时，只允许一个进程进入临界区运行，这就是进程的互斥。

例如：多个进程在竞争使用打印机时表现为互斥。

一个文件可供多个进程共享，其中有一个进程在写操作时，其它进程则不允许同时写或读，表现为互斥。

4.3.8进程的死锁及处理方法

在多道程序设计中，多个进程可能竞争一定数量的资源。一个进程在申请资源时，如果所申请资源不足，该进程就必须处于等待状态。如果所申请的资源被其它进程占有，那么进程的等待状态就可能无法改变，从而形成进程之间相互一直等待的局面，这就是死锁。

竞争资源引起死锁

引起死锁的四个必要条件：

互斥：任一时刻只能有一个进程独占某一资源，若另一进程申请该资源则需延迟到该资源释放为止。

占有并等待：即该进程占有部分资源后还在等待其它资源，而该资源被其它进程占有。

非抢占：某进程已占用资源且不主动放弃它所占有的资源时，其它进程不能强占该资源，只有等其完成任务并释放资源。

循环等待：在出现死锁的系统中，一定存在这样一个进程链，其中每个进程至少占有其它进程所必需的资源，从而形成一个等待链。

处理死锁问题的三种方式：

可使用协议预防和避免死锁，确保系统从不会进入死锁状态。

可允许系统进入死锁状态，然后检测出死锁状态，并加以恢复。

可忽略进程死锁问题，并假装系统中死锁从来不会发生。即没有必要把精力花在小概率事件上。

处理死锁优先考虑的顺序：先预防和避免再检测和恢复

4.4内存管理

内存是现代操作系统的核心。内存用于容纳操作系统和各种用户进程，是可以被CPU和I/O设备所共同访问的数据仓库。计算机的所有程序运行时都要调入内存。

内存管理的主要工作是：为每个用户进程合理地分配内存，以保证各个进程之间在存储区不发生冲突;当内存不足时，如何把内存和外存结合起来，给用户提供一个比实际内存大得多的虚拟内存，使得程序能顺利执行。内存管理包括内存分配、地址映射、内存保护和扩充。

4.4.1用户程序执行与地址映射

用户编写程序在执行前，需要多个处理步骤，这些步骤可将源程序转变为二进制机器代码，然后在内存中等待执行。当然有时并非每个步骤都是必需的。

通常，将指令和数据的.地址映射成内存地址可以发生在以下三个执行阶段。(了解)

1.编译阶段:如果在编译时就知道进程将在内存中的什么位置驻留，那么编译器就可以直接以生成绝对地址代码。

2.加载阶段:不知道进程将驻留在什么位置，那么编译器就必须生成程序的逻辑地址，在加载阶段再转变成内存的绝对地址。

3.执行阶段:如果进程在执行时可以从一个内存段移动到另一个内存段，那么进程的绝对地址映射工作只能延迟到执行时进行。

4.4.2物理地址空间与逻辑地址空间

物理地址:是计算机内存单元的真实地址。

物理地址空间:由物理地址所构成的地址范围。

逻辑地址:用户程序地址，从0开始编址。

逻辑地址空间:由逻辑地址所构成的地址范围。

地址映射:用户程序在运行时要装入内存，这就需要将逻辑地址变换成物理地址，这个过程称为地址映射，也称重定位。

用户编写的源程序是不考虑地址的，源程序经CPU编译后产生逻辑地址。从CPU产生的逻辑地址转换为内存中的物理地址的映射是由计算机中被称为内存管理单元的硬件设备来实现的，将逻辑地址与内存管理单元中存放的内存基址相加就得到了物理地址。

4.4.3进程使用内存的交换技术

为了更加有效地使用内存，进程在不运行时，可以暂时从内存移至外存上，直到需要再运行时再重新调回到内存中。也就是说内存管理程序可将刚刚运行过的进程从内存中换出以释放出占用的内存空间，然后将另一个要运行的进程占据前者释放的内存空间。

计算机工作时，为了将多个进程放入到内存就必须考虑在内存中如何放置这些进程。

4.4.4内存分配方案-连续

对于连续内存分配方案，开始时所有内存是一个大的孔，随着内存分配的进行就会形成位置上不连续的大小不一的孔。在连续内存分配方案中，当新进程需要内存时，为其寻找合适的孔，实现内存分配。该方案为每个进程所分配的内存物理地址空间在位置上是连续的。

4.4.5内存分配方案-分页式

分页管理基本思想：

o内存物理地址空间划分为若干个大小相等的块(页框)

o进程的逻辑地址空间也划分为同样大小的块(页面)

o内存分配时每个页面对应地分配一个页框，而一个进程所分得页框在位置上不必是连续的。

页表：操作系统为每个用户程序建立一张页表，该表记录用户程序的每个逻辑页面存放在哪一个内存物理页框。

4.5虚拟内存方案

虚拟内存是一个容量很大的存储器的逻辑模型，它不是任何实际的物理存储器，它一般是借助硬盘来扩大主存的容量。

虚拟内存：对于一个进程来讲，如果仅将当前要运行的几个页面装入内存便可以开始运行，而其余页面可暂时留在磁盘上，待需要时再调入内存，并且调入时也不占用新的内存空间，而是对原来运行过的页面进行置换。这样，就可以在计算机有限的内存中同时驻留多个进程并运行。而对用户来讲感觉到系统提供了足够大的物理内存，而实际上并非真实的，这就是虚拟内存。

4.5.2页面请求与页面置换算法

页面请求:在虚拟内存技术中，进程运行时并没有将所有页面装入到内存，在运行过程中进程会不断地请求页面，如果访问的页面已在内存，就继续执行下去;但如果要访问的页面尚未调入到内存，便请求操作系统将所缺页面调入内存，以便进程能继续运行下去。

页面置换:如果请求页面调入内存时，分配给该进程的页框已用完，就无法立即装入所请求页面。此时，必须将进程中的某个页面从内存的页框调出到磁盘上，再从磁盘上将所请求的页面调入到内存的该页框中。这个过程叫做页面置换。

4.6文件管理

文件管理是操作系统最常见的组成部分。文件管理主要提供目录及其文件的管理。

4.6.1文件的概念

文件：保存在外部存储设备上的相关信息的集合。

文件命名：文件主名+扩展名

文件存取属性：

只读：只允许授权用户进行读操作。

读写：只允许授权用户进行读和写的操作。

文档：允许任何用户进行读写操作。

隐藏：不允许用户直接看到文件名。

文件系统：是对文件进行操作和管理的软件，是用户与外存之间的接口。这个系统将所有文件组织成目录结构保存在外存，一个文件对应其中的一个目录条。目录条记录有文件名、文件位置等信息。

操作系统对文件的基本操作包括：

创建文件、文件写、文件读、文件重定位、文件删除、文件截短。

对文件的其它操作包括：文件复制、重命名、更改属性等。