目录

一、实验目的

二、实验内容

三、实验原理

四.算法流程图

 六.运行结果

七.实验小结

一、实验目的

1. 在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。
2. 当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。
3. 本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。

二、实验内容

1. 设计一个程序,根据不同的调度算法模拟操作系统对进程的调度。 
2. 动态优先级法 
3. 设计进程控制块PBC表结构，分别适用优先数调度算法 
4.  PBC结构通常包括以下信息：进程名、进程优先数、轮转时间片、进程的CPU时间，进程状态等。根据调度算法不同，PCB结构可作适当的调整。 
5.  建立进程队列。对不同的算法编制不同的入链程序。 
6. 程序要求达到的运行效果：在设置好进程数量、调度算法后，系统能按设定的参数运行，并在屏幕上交替显示就绪队列和完成队列的进程名等信息。

三、实验原理

设计一个按优先数调度算法实现处理器调度的程序。

•  假定系统有五个进程每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：

其中，进程名——作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。

指针——按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。

要求运行时间——假设进程需要运行的单位时间数。

优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。

状态——可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。

•  在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。
• 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例：

  队首标志

         K2    

•  处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：

优先数-1

要求运行时间-1

来模拟进程的一次运行。

提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。

• 进程运行一次后，若要求运行时间¹0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。
• 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。
•  在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。
• 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。

四.算法流程图

五.源程序及注释

struct pcb   /* 定义进程控制块PCB */ {

    char name[10];//存储进程名
    struct pcb* next;  //指针
    int super;        //优先级数
    int ntime;       //运行时间
    int rtime;
    char state;       //进程状态
}*ready = NULL, *p;
typedef struct pcb PCB;  

• 程序包含函数:

 input(); /* 建立进程控制块函数*/
sort(); /* 建立对进程进行优先级排列函数*/  
disp(PCB * pr) ;/*建立进程显示函数,用于显示当前进程*/
check() ;// 建立进程查看函数 
destroy(); /*建立进程撤消函数(进程运行结束,撤消进程)*/
running(); /* 建立进程就绪函数(进程运行时间到,置就绪状态*/ 
 main(void) {
}/*主函数*/
                                                           

• 打印一份源程序并附上注释。

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <stdlib.h> 

#define getpch(type) (type*)malloc(sizeof(type)) 



struct pcb   /* 定义进程控制块PCB */ {
	char name[10];//存储进程名
	struct pcb* next;  //指针
	int super;        //优先级数
	int ntime;       //运行时间
	int rtime;
	char state;       //进程状态
}*ready = NULL, *p;
typedef struct pcb PCB;

void sort() /* 建立对进程进行优先级排列函数*/ {
	PCB *first, *second;
	int insert = 0;
	if ((ready == NULL) || ((p->super) > (ready->super))) /*优先级最大者,插入队首*/
	{
		p->next = ready;//插入的数据作为链表头结点
		ready = p;//头结点指针指向插入数
	}

	else /* 进程比较优先级,插入适当的位置中*/ {
		first = ready;
		second = first->next;
		while (second != NULL)
		{
			if ((p->super) > (second->super)) /*若插入进程比当前进程优先数大,*/
			{ /*插入到当前进程前面*/
				p->next = second;
				first->next = p;
				second = NULL;
				insert = 1;
			}
			else /* 插入进程优先数最低,则插入到队尾*/
			{

				first = first->next;
				second = second->next;
			}
		}
		if (insert == 0)
			first->next = p;
	}
}

void input() /* 建立进程控制块函数*/
{
	int i, num;
	printf("\n 请输入进程数:");
	scanf("%d", &num);
	for (i = 0; i < num; i++)
	{
		printf("\n 进程号%d:\n", i + 1);
		p = getpch(PCB);
		printf("\n 输入进程名:");
		scanf("%s", p->name);
		printf("\n 输入进程优先数:");
		scanf("%d", &p->super);
		printf("\n 输入进程运行时间:");
		scanf("%d", &p->ntime);
		printf("\n");
		p->rtime = 0; p->state = 'w';
		p->next = NULL;
		sort(); //调用sort函数
	}
}

int space()
{

	int len = 0; PCB* pr = ready;
	while (pr != NULL)
	{
		len++;
		pr = pr->next;
	}
	return(len);
}

void disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/
{
	printf("\n qname \t state \t super \t ndtime   runtime \n");
	printf("|%s\t", pr->name);
	printf("|%c\t", pr->state);
	printf("|%d\t", pr->super);
	printf("|%d\t", pr->ntime);
	printf("|%d\t", pr->rtime);
	printf("\n");

}

void check() // 建立进程查看函数 
{
	PCB* pr;
	printf("\n **** 当前正在运行的进程是:%s", p->name); //显示当前运行进程
	disp(p);
	pr = ready;
	printf("\n ****当前就绪队列状态为:\n"); //显示就绪队列状态
	while (pr != NULL)
	{
		disp(pr);
		pr = pr->next;
	}
}

void destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/
{
	printf("\n 进程 [%s] 已完成.\n", p->name);
	free(p);
}

void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/

{
	(p->rtime)++;
	if (p->rtime == p->ntime)
		destroy(); /* 调用destroy函数*/
	else
	{
		(p->super)--;
		p->state = 'w';
		sort(); /*调用sort函数*/
	}
}
int main(void) /*主函数*/
{
	while (true)
	{
		int len;//
		char ch;
		input();
		len =space();
		while ((len != 0) && (ready != NULL))
		{
			ch = getchar();
			p = ready;
			ready = p->next;
			p->next = NULL;
			p->state = 'R';
			check();
			running();
			system("pause");
		}

		printf("\n\n 进程已经完成.\n");
	}
	system("pause");
	return 0;
}

 六.运行结果

七.实验小结

1.基本思想：为每个进程设置一个优先级，在调度的时候，选取优先级最大的任务去执行。

2.优先级可以是静态赋予：创建任务的时候，就指定优先级大小，并且保持不变，直到任务结束。

3.也可以是动态赋予：优先级在执行任务中动态改变。

4.为了防止高优先级进程无休止地运行下去，调度程序可以在每个时钟中断降低当前进程的优先级。

5.在平时中，我们可以把不同的任务划分为不同的优先级，然后在相同优先级的任务中使用时间片轮转。

一、实验目的
在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。

二、实验内容
(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：
进程名
指针
要求运行时间
优先数
状态
其中，进程名——作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。
指针——按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。
要求运行时间——假设进程需要运行的单位时间数。
优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。
状态——可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。
(2) 在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。
(3) 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例：
队首标志
K2
K1 P1 K2 P2 K3 P3 K4 P4 K5 P5
0 K4 K5 K3 K1
2 3 1 2 4
1 5 3 4 2
R R R R R
PCB1 PCB2 PCB3 PCB4 PCB5

(4) 处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：
优先数-1
要求运行时间-1
来模拟进程的一次运行。
提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。
(5) 进程运行一次后，若要求运行时间¹0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。
(6) 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。
(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。
(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。

三、算法流程图

四、源程序及注释
附录中
五、测试数据及运行结果
K2
K1 P1 K2 P2 K3 P3 K4 P4 K5 P5
0 K4 K5 K3 K1
2 3 1 2 4
1 5 3 4 2
R R R R R
PCB1 PCB2 PCB3 PCB4 PCB5

开始执行P2进程
进程名:P2//需要运行的时间:3//优先级:5//状态:R
P2进程执行一次完毕
进程队列的所有进程信息:
进程名:P4//需要运行的时间:2//优先级:4//状态:R
进程名:P2//需要运行的时间:2//优先级:4//状态:R
进程名:P3//需要运行的时间:1//优先级:3//状态:R
进程名:P5//需要运行的时间:4//优先级:2//状态:R
进程名:P1//需要运行的时间:2//优先级:1//状态:R

开始执行P4进程
进程名:P4//需要运行的时间:2//优先级:4//状态:R
P4进程执行一次完毕
进程队列的所有进程信息:
进程名:P2//需要运行的时间:2//优先级:4//状态:R
进程名:P3//需要运行的时间:1//优先级:3//状态:R
进程名:P4//需要运行的时间:1//优先级:3//状态:R
进程名:P5//需要运行的时间:4//优先级:2//状态:R
进程名:P1//需要运行的时间:2//优先级:1//状态:R

开始执行P2进程
进程名:P2//需要运行的时间:2//优先级:4//状态:R
P2进程执行一次完毕
进程队列的所有进程信息:
进程名:P3//需要运行的时间:1//优先级:3//状态:R
进程名:P2//需要运行的时间:1//优先级:3//状态:R
进程名:P4//需要运行的时间:1//优先级:3//状态:R
进程名:P5//需要运行的时间:4//优先级:2//状态:R
进程名:P1//需要运行的时间:2//优先级:1//状态:R

开始执行P3进程
进程名:P3//需要运行的时间:1//优先级:3//状态:R
P3进程执行一次完毕
P3运行结束
进程名:P3//需要运行的时间:0//优先级:2//状态:E
进程队列的所有进程信息:
进程名:P2//需要运行的时间:1//优先级:3//状态:R
进程名:P4//需要运行的时间:1//优先级:3//状态:R
进程名:P5//需要运行的时间:4//优先级:2//状态:R
进程名:P1//需要运行的时间:2//优先级:1//状态:R

开始执行P2进程
进程名:P2//需要运行的时间:1//优先级:3//状态:R
P2进程执行一次完毕
P2运行结束
进程名:P2//需要运行的时间:0//优先级:2//状态:E
进程队列的所有进程信息:
进程名:P4//需要运行的时间:1//优先级:3//状态:R
进程名:P5//需要运行的时间:4//优先级:2//状态:R
进程名:P1//需要运行的时间:2//优先级:1//状态:R

开始执行P4进程
进程名:P4//需要运行的时间:1//优先级:3//状态:R
P4进程执行一次完毕
P4运行结束
进程名:P4//需要运行的时间:0//优先级:2//状态:E
进程队列的所有进程信息:
进程名:P5//需要运行的时间:4//优先级:2//状态:R
进程名:P1//需要运行的时间:2//优先级:1//状态:R

开始执行P5进程
进程名:P5//需要运行的时间:4//优先级:2//状态:R
P5进程执行一次完毕
进程队列的所有进程信息:
进程名:P1//需要运行的时间:2//优先级:1//状态:R
进程名:P5//需要运行的时间:3//优先级:1//状态:R

开始执行P1进程
进程名:P1//需要运行的时间:2//优先级:1//状态:R
P1进程执行一次完毕
进程队列的所有进程信息:
进程名:P5//需要运行的时间:3//优先级:1//状态:R
进程名:P1//需要运行的时间:1//优先级:0//状态:R

开始执行P5进程
进程名:P5//需要运行的时间:3//优先级:1//状态:R
P5进程执行一次完毕
进程队列的所有进程信息:
进程名:P1//需要运行的时间:1//优先级:0//状态:R
进程名:P5//需要运行的时间:2//优先级:0//状态:R

开始执行P1进程
进程名:P1//需要运行的时间:1//优先级:0//状态:R
P1进程执行一次完毕
P1运行结束
进程名:P1//需要运行的时间:0//优先级:-1//状态:E
进程队列的所有进程信息:
进程名:P5//需要运行的时间:2//优先级:0//状态:R

开始执行P5进程
进程名:P5//需要运行的时间:2//优先级:0//状态:R
P5进程执行一次完毕
进程队列的所有进程信息:
进程名:P5//需要运行的时间:1//优先级:-1//状态:R

开始执行P5进程
进程名:P5//需要运行的时间:1//优先级:-1//状态:R
P5进程执行一次完毕
P5运行结束
进程名:P5//需要运行的时间:0//优先级:-2//状态:E
进程控制块中的所有进程执行完毕

Process finished with exit code 0

代码

package 进程调度算法;

class PCB {
    public String name;
    public PCB next;
    public int time;
    public int priority;
    public char state; //'R'就是就绪状态  'E'为结束状态

    //指针的话 我们在插入的时候就那个是那个的指针了
    public PCB(String name, int time, int priority, char state) {
        this.name = name;
        this.time = time;
        this.priority = priority;
        this.state = state;
    }

    @Override
    public String toString() {
        return "进程名:" + name +  "//需要运行的时间:" + time + "//优先级:" + priority
                + "//状态:" + state;
    }
}


public class Process {
    private PCB head;//规定一个头节点

    //插入操作
    public void addPCB(PCB node) {

        //当一个进程运行完毕的时候也就是time = 0 或者 state = 'E'的时候
        //我们就不需要将这个进程插入到控制块中了
        //直接结束
        if (node.state == 'E') {
            System.out.println(node.name + "运行结束");
            System.out.println(node);
            return;
        }
        //如果所需运行时间为0,状态改为E 退出进程队列 E就是结束
        if (node.time == 0) {
            node.state = 'E';//将状态改为E
            System.out.println(node.name + "运行结束");
            System.out.println(node);
            return;
        }

        //头节点为空的时候 直接插入就好了
        if (this.head == null) {
            this.head = node;
            return;
        }

        //插入的时候需要按优先级进行排序
        //如果这个节点的优先级比头结点大
        //我们需要进行头插法
        if (node.priority > this.head.priority) {
            node.next = this.head;
            this.head = node;
            return;
        }

        //优先级和头结点优先级相同的时候,插到头节点的后面就好了(先来服务)
        if (node.priority == this.head.priority) {
            node.next = this.head.next;
            this.head.next = node;
            return;
        }

        //如果节点的优先级在中间我们需要挨个比较后然后插入
        //我们需要设置两个节点 进行比较后 然后插入
        PCB cur = this.head.next;
        PCB parent = this.head;
        while (cur != null) {
            //当前的节点的优先级小于node的优先级
            if (node.priority > cur.priority) {
                node.next = parent.next;
                parent.next = node;
                return;

            //当前的节点优先级等于node的优先级，同样遵循先来服务
            } else if (node.priority == cur.priority) {
                parent = cur;
                node.next = parent.next;
                parent.next = node;
                return;
            }
            //向后跳一步
            parent = cur;
            cur = cur.next;
        }

        //走到的这里的时候cur已经为空了，那木证明前面的节点的优先级都大于这个节点的优先级了
        //也就是说我们只需要进行尾插就好了
        parent.next = node;
        node.next = null;
    }

    //如何去运行进程
    public void run() {
        while (this.head != null) {
            //我们插入的时候是按照优先级来进行的
            //那木我们的运行的时候就从头节点开始运行
            PCB cur = this.head;//创建一个当前的节点指向头节点
            this.head = this.head.next;
            System.out.println();
            System.out.println("开始执行" + cur.name + "进程");
            System.out.println(cur);
            //当前的节点的时间-1 并且优先级-1
            cur.priority -= 1;
            cur.time -= 1;
            //执行一次后我们需要将这个进程再次插入,不管它的运行时间是否完毕，我们在插入的时候会判断
            System.out.println(cur.name + "进程执行一次完毕");
            //将cur再插入进程队列
            addPCB(cur);

            //当头节点给为null的时候 也就是这个进程控制块中的所有内容已经执行完毕了
            //我们就直接return可以了 不在需要去执行了
            if (this.head == null) {
                System.out.println("进程控制块中的所有进程执行完毕");
                return;
            }
            System.out.println("进程队列的所有进程信息:");
            display();
        }
    }

    //遍历这个队列，我们确定来看看这个队列中每一个pcb的状态
    public void display() {
        for (PCB pcb = this.head; pcb != null; pcb = pcb.next) {
            System.out.println(pcb);
        }
    }
}

怎木调就不用我写了吧。