操作系统实习——进程调度算法

文章目录

• • 1 设计内容
  • 2 算法原理
  • 3 数据结构
  • 4 程序流程图
  • 5:代码

1 设计内容

设计程序模拟单处理机系统中的进程调度算法，实现动态优先权进程调度算法, 对N个进程采用动态优先权算法的进程调度.

2 算法原理

1．每个用来标识进程的进程控制块PCB，包括以下信息：进程标识数ID，进程优先数PRIORITY，进程已占用的CPU时间CPUTIME，进程还需占用的CPU时间NEEDTIME，进程状态STATE等。

2．优先数改变的原则：进程在就绪队列中呆一个时间片，优先数增加1，进程每运行一个时间片优先数减3。

3．设置调度前的初始状态。

4．将每个时间片内的进程情况显示出来。

就绪队列包含如下操作：

入队操作：将新的进程按照优先级大小插入就绪队列，保证队列按优先级大小呈递减状态。

出队操作：将就绪队列中优先级最大的进程弹出队列，由于就绪队列中是按优先级大小排列的，所以也是弹出第一个就绪进程。

队列更新操作：每个时间片后，更新就绪队列中进程的优先级。每过一个时间片段后，就绪队列中每个进程的优先级+1。

3 数据结构

(事先说明博主在实现该算法的过程中主要用到的数据结构，以下数据结构仅代表博主本人的想法，读者可以对照这里阅读代码。当然，读者也可以寻找更好的数据结构来实现该算法。)

1．一维数组：a[10]定义进程控制块pcb,一个数组空间代表一个进程；temp[10]存放进程优先数，并从大到小排序；id[10]存放进程标识符；time[10] 存放进程还需占用CPU的时间。

2．结构体：用来声明进程控制块pcb。其中包含进程标识数ID，进程优先数PRIORITY，进程已占3．用CPU时间CPUTIME，进程还需占用CPU的时间NEEDTIME。

单链表：节点数据包含进程优先数data，进程标识符id，进程进程还需占用CPU的时间needtime。

4 程序流程图

5:代码

#include<iostream>
#include <string>
#include<stdlib.h>//system()函数
#include<windows.h>
using namespace std;
int k=0;//全局变量，统计时间片
typedef struct processpcb
{
	char ID;//进程标识数
	int PRIORITY;//进程优先数
	int CPUTIME;//进程已占用的CPU时间
	int NEEDTIME;//进程还需占用的CPU时间
	int x;//进程状态，后面打印0表示就绪，1表示运行，2表示阻塞
}pcb;
int sort(int temp[10],int n)//冒泡排序，从大到小排列，方便插入链表
{
	int x;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			if(temp[j]<temp[j+1])
			{
				x=temp[j];
				temp[j]=temp[j+1];
				temp[j+1]=x;
			}
	}
	return temp[10];
}
typedef struct Node
{
     int data;//存放优先数
	 char id;//存放进程标识符
	 int needtime;//存放进程还需运行时间
     struct Node * next;
 }Node,*LinkList;
void InitList(LinkList *L)//初始化链表
{
	*L=(LinkList)malloc(sizeof(Node));     //创建头结点
    (*L)->next=NULL;
}
void CreateList(LinkList L,int temp[10],int n,pcb a[10])//尾插法建立单链表
{
    Node *s,*k=L;
    int i,j;
	char id[10];//存放进程标识符
	int time[10];//存放进程还需运行时间
	for(i=0;i<n;i++)//进程标识排序
		for(j=0;j<n;j++)
			if(temp[i]==a[j].PRIORITY)
			{
				id[i]=a[j].ID;//进程标识排序
				time[i]=a[j].NEEDTIME;//进程还需运行时间排序
				break;
			}
    for (i=0; i<n; i++)//尾插法建立单链表
    {
        s=(Node*)malloc(sizeof(Node));//创建新结点
		s->next=NULL;
        s->data=temp[i];
		s->id=id[i];
		s->needtime=time[i];
        k->next=s;         
        k=s;
    }
}
void process(LinkList L,pcb a[10],int n)
{
	Node *s,*x;
	s=L->next;
	x=s->next;
	int i;
	if(L->next!=NULL)
	{
		s->data=(s->data)-3;//运行一个时间片，优先数-3
		s->needtime=(s->needtime)-1;
		cout<<endl<<"第"<<++k<<"个时间片："<<endl;
		cout<<"正在运行的进程为："<<s->id<<"  优先数："<<s->data<<"  还需运行时间："<<s->needtime<<endl;
	    cout<<"就绪队列顺序："<<endl;
        while(x!=NULL)//输出就绪队列中的进程状态
		{
			(x->data)++; //在就绪队列中呆一个时间片，优先数+1
			cout<<"进程标识:"<<x->id<<"  优先数："<<x->data<<"  还需运行时间："<<x->needtime<<endl;
			x=x->next;
		}
		if(s->next==NULL&&s->needtime!=0)//最后一个进程，但没有运行完
			process(L,a,n);
		else if(s->next==NULL&&s->needtime==0)//最后一个进程已运行完成，就绪队列为空，结束
		{
			L->next=NULL;
			cout<<endl<<"进程已全部运行"<<endl;
           exit(0);
		}
		else if(s->next!=NULL&&s->needtime==0)//已占用CPU时间等于所需运行时间，进程完成，撤销，下一个进程
		{
			L->next=s->next;
			free(s);
			process(L,a,n);
		}
		else if(s->next!=NULL&&s->data>(s->next)->data)
			process(L,a,n);
		else
		{
			Node *p=s->next;
			Node *q=p->next;
			Node *t=s;
			while(q!=NULL)
			{
				p=p->next;
				q=q->next;
				t=t->next;
				if(p->data<s->data)
				{
					L->next=s->next;
					t->next=s;
					s->next=p;
					process(L,a,n);
				}
				else if(p->data==s->data)//插入到与该进程优先数相等的后面,一定程度上防止饥饿
				{
					L->next=s->next;
					p->next=s;
					s->next=q;
					process(L,a,n);
				}
			}
			//就绪队列中没有找到优先数比该进程小的进程，将该进程插入到队列的队尾
			L->next=s->next;
			p->next=s;
			s->next=q;
			process(L,a,n);
		}
	}
}
void texiao()//制作简单的控制台界面，此函数不作为实现算法的核心代码，删掉此函数，算法也能正常实现
{
    system("color 3F");//设置控制台界面背景颜色和前景颜色
	SetConsoleTitle("进程调度程序");//设置控制台窗口标题
}
void main()
{
	texiao();
	pcb a[10];
	LinkList L;
	int i,n,temp[10];
	cout<<"请输入需要创建的进程数"<<endl;
	cin>>n;
	cout<<"请分别输入各个进程的标识数，优先数，需要占用的CPU时间"<<endl;
	for(i=0;i<n;i++)
	{
	cin>>a[i].ID>>a[i].PRIORITY>>a[i].NEEDTIME;
	a[i].CPUTIME=0;	
	temp[i]=a[i].PRIORITY;//进程优先数存入数组，方便后面进行排序，先对优先数进行排序再插入链表
	}
    temp[10]=sort(temp,n);//排序
	InitList(&L);
    CreateList(L,temp,n,a);
	process(L,a,n);
}