计算机操作系统调度算法模拟程序设计（C#）

12-14· 16分钟

实验目的

用 C#语言编程实现对 N 个进程采用四种进程调度算法——先来先服务算法（FCFS）、短进程优先算法（SJF）、高响应比优先调度算法(HRRN)和时间片轮转调度算法（RR）调度执行模拟。

实验原理

先构建每个用来标识进程的进程控制块 PCB，包括以下字段：

  • 进程标识数 id
  • 进程优先数 priority，并规定优先数越大的进程，其优先权越高
  • 进程到达时间 arriveTime
  • 进程已占用 CPU 时间 serveTime
  • 进程还需占用的 CPU 时间 needTime。当进程运行完毕时，needTime 变为 0
  • 进程被阻塞的时间 blockTime，表示已阻塞的进程再等待 blockTime 个时间片后，将转换成就绪状态
  • 进程状态 state

FCFS 算法

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用 FCFS 算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，然后投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

SJ(P)F 算法

短作业(进程)优先调度算法 SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

HRRN 算法

高响应比算法，是一种动态调整优先级的算法。HRRN 算法每次都计算作业的优先级，随着作业等待时间的变长，优先级不断的提高，所以能够得到更快的执行。
这个优先级可以描述为: 优先级 = (作业已等待时间 + 作业的服务时间) / 作业的服务时间
在本实验的代码模拟中，设定初始优先级固定，之后当进程运行一个时间片后，优先级减 3，同时就绪队列中的其他进程优先级加 1。

RR 算法

RR 算法是使用非常广泛的一种调度算法。
首先将所有就绪的队列按 FCFS 策略排成一个就绪队列，然后系统设置一定的时间片，每次给队首作业分配时间片。如果此作业运行结束，即使时间片没用完，立刻从队列中去除此作业，并给下一个作业分配新的时间片；如果作业时间片用完没有运行结束，则将此作业重新加入就绪队列尾部等待调度。

代码部分

PCB 类 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using System;
public class PCB
{
    public int id { get; set; }
    public int priority { get; set; }
    public int cpuTime { get; set; }
    public int blockTime { get; set; }
    public int state { get; set; }
    public int arriveTime { get; set; }
    public int serveTime { get; set; }
    public int needTime { get; set; }
    public int finishTime { get; set; }
    //state : 1:ready,2:running
    public PCB(int id, int arriveTime, int serveTime, int state)
    {
        this.id = id;
        this.arriveTime = arriveTime;
        this.serveTime = serveTime;
        this.state = state;
    }
    public PCB(int id, int arriveTime, int serveTime, int blockTime, int state)
    {
        this.id = id;
        this.arriveTime = arriveTime;
        this.serveTime = serveTime;
        this.blockTime = blockTime;
        this.state = state;
    }

    public PCB(int id, int priority, int arriveTime, int serveTime, int state, bool isD)
    {
        this.id = id;
        this.priority = priority;
        this.arriveTime = arriveTime;
        this.serveTime = serveTime;
        this.state = state;
    }
    public void showState()
    {
        System.Console.WriteLine("{0}\t\t{1}\t\t{2}\t\t{3}\t\t{4}\t\t{5}", id, priority, arriveTime, needTime, serveTime, state);

    }
    public void showState(int i)
    {
        System.Console.WriteLine("{0}\t\t{1}\t\t{2}\t\t{3}\t\t{4}\t\t{5}\t\t{6}", id, priority, arriveTime, needTime, serveTime, blockTime, state);

    }
}

FCFS 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
using System;
using System.Threading;
using System.Collections.Generic;

class FCFS
{
    List<PCB> Ready = new List<PCB>();
    static int FCFS_PRIORITY = 15;
    int times;
    public void Init()
    {
        PCB a = new PCB(1, 0, 3, 1),
            b = new PCB(2, 2, 6, 1),
            c = new PCB(3, 4, 4, 1),
            d = new PCB(4, 6, 5, 1),
            e = new PCB(5, 8, 2, 1);
        times = 1;
        Ready.Add(e);
        Ready.Add(d);
        Ready.Add(c);
        Ready.Add(b);
        Ready.Add(a);
        //对优先权priority与服务需要的时间needTime进行赋值
        for (int i = 0; i < Ready.Count; i++)
        {
            Ready[i].priority = FCFS_PRIORITY - Ready[i].needTime;
            Ready[i].needTime = Ready[i].serveTime;
        }
        PCB temp = null;
        //对优先权排序
        for (int i = 0; i < Ready.Count - 1; i++)
        {
            for (int j = 0; j < Ready.Count - i - 1; j++)
            {
                if (Ready[j].priority < Ready[j + 1].priority)
                {
                    temp = Ready[j];
                    Ready[j] = Ready[j + 1];
                    Ready[j + 1] = temp;
                }
                else if (Ready[j].priority == Ready[j + 1].priority)
                {
                    if (Ready[j].serveTime > Ready[j + 1].serveTime)
                    {
                        temp = Ready[j];
                        Ready[j] = Ready[j + 1];
                        Ready[j + 1] = temp;
                    }
                }
            }
        }
    }

    public void Start()
    {
        System.Console.WriteLine("先来先服务(FCFS)");
        System.Console.WriteLine("进程状态标志(procState)：1：准备，2：正在运行");
        System.Console.WriteLine("===================================================================================");
        while (Ready != null && Ready.Count > 0)
        {
            System.Console.WriteLine("Id\t     Priority\t     ArriveTime\t       NeedTime\t    ServeTime\t    State\n");
            if (Ready[0] != null)
            {
                while (Ready[0].needTime > 0)
                {
                    Ready[0].state = 2;
                    // 输出单个时间片中全部进程的状态
                    // foreach (var item in Ready)
                    // {
                    //     item.showState();
                    // }
                    // 仅输出单个时间片运行中的程序状态
                    Ready[0].showState();
                    System.Console.WriteLine("time:{0}", times);
                    Thread.Sleep(1000);
                    System.Console.WriteLine("-----------------------------------------------------------------------------------");
                    Ready[0].needTime--;
                    times++;
                }
            }

            Ready[0].state = 0;
            System.Console.WriteLine("===================================================================================");
            System.Console.WriteLine("\t\t\t\t\t\t\t\t\tprocess {0} completed\n", Ready[0].id);
            Ready.RemoveAt(0);
        }
        System.Console.WriteLine("                 All processes have been completed,takes {0} times\n", times - 1);

    }
}

SJB 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using System;
using System.Threading;
using System.Collections.Generic;

class SJF
{
    List<PCB> Ready = new List<PCB>();
    static int SJF_PRIORITY = 15;
    int times;
    public void Init()
    {
        PCB a = new PCB(1, 0, 3, 1),
            b = new PCB(2, 2, 6, 1),
            c = new PCB(3, 4, 4, 1),
            d = new PCB(4, 6, 5, 1),
            e = new PCB(5, 8, 2, 1);
        times = 1;
        Ready.Add(e);
        Ready.Add(d);
        Ready.Add(c);
        Ready.Add(b);
        Ready.Add(a);
        //对优先权priority与服务需要的时间needTime进行赋值
        for (int i = 0; i < Ready.Count; i++)
        {
            Ready[i].priority = SJF_PRIORITY - Ready[i].serveTime;
            Ready[i].needTime = Ready[i].serveTime;
        }
        PCB temp = null;
        //对优先权排序
        for (int i = 0; i < Ready.Count - 1; i++)
        {
            for (int j = 0; j < Ready.Count - i - 1; j++)
            {
                if (Ready[j].priority < Ready[j + 1].priority)
                {
                    temp = Ready[j];
                    Ready[j] = Ready[j + 1];
                    Ready[j + 1] = temp;
                }
                else if (Ready[j].priority == Ready[j + 1].priority)
                {
                    if (Ready[j].arriveTime > Ready[j + 1].arriveTime)
                    {
                        temp = Ready[j];
                        Ready[j] = Ready[j + 1];
                        Ready[j + 1] = temp;
                    }
                }
            }
        }
    }

    public void Start()
    {
        System.Console.WriteLine("短作业优先(SJF)");
        System.Console.WriteLine("进程状态标志(procState)：1：准备，2：正在运行");
        System.Console.WriteLine("===================================================================================");
        while (Ready != null && Ready.Count > 0)
        {
            System.Console.WriteLine("Id\t     Priority\t     ArriveTime\t       NeedTime\t    ServeTime\t    State\n");
            if (Ready[0] != null)
            {
                while (Ready[0].needTime > 0)
                {
                    Ready[0].state = 2;
                    // 输出单个时间片中全部进程的状态
                    // foreach (var item in Ready)
                    // {
                    //     item.showState();
                    // }
                    // 仅输出单个时间片运行中的程序状态
                    Ready[0].showState();
                    System.Console.WriteLine("time:{0}", times);
                    Thread.Sleep(1000);
                    System.Console.WriteLine("-----------------------------------------------------------------------------------");
                    Ready[0].needTime--;
                    times++;
                }
            }

            Ready[0].state = 0;
            System.Console.WriteLine("===================================================================================");
            System.Console.WriteLine("\t\t\t\t\t\t\t\t\tprocess {0} completed\n", Ready[0].id);
            Ready.RemoveAt(0);
        }
        System.Console.WriteLine("                 All processes have been completed,takes {0} times\n", times - 1);
    }
}

HRRN 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
using System;
using System.Threading;
using System.Collections.Generic;

class HRRN
{
    List<PCB> Ready = new List<PCB>();
    int times;
    public void Init()
    {
        PCB a = new PCB(1, 2, 0, 3, 1, true),
            b = new PCB(2, 10, 2, 6, 1, true),
            c = new PCB(3, 5, 4, 4, 1, true),
            d = new PCB(4, 3, 6, 5, 1, true),
            e = new PCB(5, 8, 8, 2, 1, true);
        times = 1;
        Ready.Add(e);
        Ready.Add(d);
        Ready.Add(c);
        Ready.Add(b);
        Ready.Add(a);
        //对服务需要的时间needTime进行赋值
        for (int i = 0; i < Ready.Count; i++)
            Ready[i].needTime = Ready[i].serveTime;
    }

    public void Start()
    {
        System.Console.WriteLine("高响应比优先调度算法(HRRN)");
        System.Console.WriteLine("进程状态标志(State)：1：准备，2：正在运行");
        System.Console.WriteLine("===================================================================================");
        while (Ready.Count > 0)
        {
            PriorityChange();
            Ready[0].state = 2;
            System.Console.WriteLine("Id\t     Priority\t     ArriveTime\t       NeedTime\t    ServeTime\t    State\n");
            // 输出单个时间片中全部进程的状态
            // foreach (var item in Ready)
            // {
            //     item.showState(1);
            // }
            // 仅输出单个时间片运行中的进程状态
            Ready[0].showState();
            Ready[0].needTime--;
            Ready[0].priority -= 3;
            if (Ready[0].needTime == 0)
            {
                Ready[0].state = 0;
                System.Console.WriteLine("\t\t\t\t\t\t\t\t\tprocess {0} completed\n", Ready[0].id);
                System.Console.WriteLine("===================================================================================");
                Ready.RemoveAt(0);
            }
            for (int i = 1; i < Ready.Count - 1; i++)
            {
                Ready[i].priority++;
            }
            Thread.Sleep(1000);
            System.Console.WriteLine("-----------------------------------------------------------------------------------");
            System.Console.WriteLine("time:{0}", times);
            times++;
        }
        System.Console.WriteLine("                 All processes have been completed,takes {0} times\n", times - 1);
    }

    void PriorityChange()
    {
        PCB temp = null;
        //对优先权排序
        for (int i = 0; i < Ready.Count - 1; i++)
        {
            for (int j = 0; j < Ready.Count - i - 1; j++)
            {
                if (Ready[j].priority < Ready[j + 1].priority)
                {
                    temp = Ready[j];
                    Ready[j] = Ready[j + 1];
                    Ready[j + 1] = temp;
                }
                else if (Ready[j].priority == Ready[j + 1].priority) //优先权相同则短任务优先
                {
                    if (Ready[j].serveTime > Ready[j + 1].serveTime)
                    {
                        temp = Ready[j];
                        Ready[j] = Ready[j + 1];
                        Ready[j + 1] = temp;
                    }
                    else if (Ready[j].arriveTime > Ready[j + 1].arriveTime) //服务时间相同则先到优先
                    {
                        temp = Ready[j];
                        Ready[j] = Ready[j + 1];
                        Ready[j + 1] = temp;
                    }
                }
            }
        }
    }
}

RR 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
using System;
using System.Threading;
using System.Collections.Generic;

class RR
{
    List<PCB> Ready = new List<PCB>();
    List<PCB> Block = new List<PCB>();
    static int RR_PRIORITY = 15;
    int times;
    public void Init()
    {
        PCB a = new PCB(1, 0, 3, 1, 1),
            b = new PCB(2, 2, 6, 1, 1),
            c = new PCB(3, 4, 4, 1, 1),
            d = new PCB(4, 6, 5, 1, 1),
            e = new PCB(5, 8, 2, 1, 1);
        times = 1;
        Ready.Add(e);
        Ready.Add(d);
        Ready.Add(c);
        Ready.Add(b);
        Ready.Add(a);
        //对优先权priority与服务需要的时间needTime进行赋值
        for (int i = 0; i < Ready.Count; i++)
        {
            Ready[i].priority = RR_PRIORITY - Ready[i].needTime;
            Ready[i].needTime = Ready[i].serveTime;
        }
        PCB temp = null;
        //对优先权排序
        for (int i = 0; i < Ready.Count - 1; i++)
        {
            for (int j = 0; j < Ready.Count - i - 1; j++)
            {
                if (Ready[j].priority < Ready[j + 1].priority)
                {
                    temp = Ready[j];
                    Ready[j] = Ready[j + 1];
                    Ready[j + 1] = temp;
                }
                else if (Ready[j].priority == Ready[j + 1].priority)
                {
                    if (Ready[j].serveTime > Ready[j + 1].serveTime)
                    {
                        temp = Ready[j];
                        Ready[j] = Ready[j + 1];
                        Ready[j + 1] = temp;
                    }
                }
            }
        }
    }

    public void Start()
    {
        System.Console.WriteLine("时间片轮转(RR)");
        System.Console.WriteLine("进程状态标志(procState):1：准备，2：正在运行");
        System.Console.WriteLine("===================================================================================");
        while (Ready.Count > 0 || Block.Count > 0)
        {

            if (Ready.Count > 0)
            {
                Ready[0].state = 2;
                System.Console.WriteLine("Id\t     Priority\t     ArriveTime\t       NeedTime\t    ServeTime\t    blockTime\t     State\n");
                // 输出单个时间片中全部进程的状态
                // foreach (var item in Ready)
                // {
                //     item.showState(1);
                // }
                // 仅输出单个时间片运行中的进程状态
                Ready[0].showState(1);
                Ready[0].needTime--;
                if (Ready[0].needTime == 0)
                {
                    Ready[0].state = 0;
                    System.Console.WriteLine("\t\t\t\t\t\t\t\t\tprocess {0} completed\n", Ready[0].id);
                    System.Console.WriteLine("===================================================================================");
                    Ready.RemoveAt(0);
                }
                else
                {
                    Block.Add(Ready[0]);
                    Ready.RemoveAt(0);
            }
            else
                System.Console.WriteLine("Ready list is empty!");

            Thread.Sleep(1000);
            if (Block.Count > 0)
            {

                Block[0].blockTime--;
                if (Block[0].blockTime == 0)
                {
                    Block[0].blockTime = 1;
                    Ready.Add(Block[0]);
                    Block.RemoveAt(0);
                }
            }
            System.Console.WriteLine("-----------------------------------------------------------------------------------");
            System.Console.WriteLine("time:{0}", times);
            times++;
        }
        System.Console.WriteLine("                 All processes have been completed,takes {0} times\n", times - 1);

    }
}

实验心得

操作系统这门课程并不是教如何使用操作系统的，而是讲操作系统内部机制的。操作系统的目标是为用户提供一个良好的界面，方便用户使用计算机，同时对内部各种软硬件资源能够进行有效地管理和分配，使整个系统能高效率得运行。操作系统主要有五大功能：处理机管理、存储器管理、设备管理、文件管理、用户接口。我们现在使用的大多是 PC 机，都是只有一块 CPU，而有时却要在计算机上运行多个程序，那么每道程序在什么时候使用 CPU，这需要合理得分配协调才行，操作系统关于处理机的分配有相应的调度算法，这些工作都由操作系统实现。

这次综合实验利用 C#语言对 4 种调度算法进行了设计和模拟实现，并充分考虑了进程在执行过程中可能发生的多种情况，更好的体现了进程的就绪态和执行态二者之间的关系以及相互的转换。

C#操作系统