Operating System Learning 1: NetCore—Implementing Simple Processor Scheduling that Simulates Multiprogramming

Introduction

In multiprogramming, several processes are often in the ready state at the same time. To ensure that all processes in the system run in an orderly manner, a scheduling strategy must be chosen to select a process to occupy the processor. This experiment designs an algorithm that simulates single-processor scheduling, in order to deepen understanding of processor scheduling algorithms.

Requirements

1. Design a simulated scheduler according to the time-slice round-robin algorithm.
2. Output the process scheduling procedure.

Approach Analysis

Because this experiment implements processor scheduling by simulation according to a processor scheduling algorithm, it is not entirely the same as the real processor scheduling process; for example, interrupts are not implemented (the time slice is set to 1), and process execution is not real execution either, but rather printing its running time and so on on the screen. Therefore process information is provided in the form of a file; the file contents may look as follows:

进程ID  到达时间     估计运行时间     优先级
0        0             3               2
1        2             6               4
2        4             4               0
3        6             5               3
4        8             2               1  

The following is a rough outline of the experiment:

1. Create three queues: the PCB queue, the ready queue, and the completion queue. PCB queue: stores processes that will enter the system. (Because interrupts are not implemented, processes that will enter the system to run must be provided before the program runs.) Ready queue: when the time at which a process enters the system is reached, put that process into the ready queue to wait for scheduling. Completion queue: put processes that have finished “running” into the completion queue.

2. The process execution procedure consists of printing related information on the screen. The information that should be printed for processes scheduled using the round-robin algorithm includes: the sequence of processes occupying the processor, and the start time and end time of each occupancy of the processor by that process.

3. Compute the processes’ turnaround time T and weighted turnaround time W.

Flowchart

Implementation Code

1. ProcessControlBlock.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace OperatingSystemExperiment.Exp1 {
    enum ProcessStatus {
        Ready,
        Run,
        Finish
    }

    /// <summary>
    /// 进程控制块 PCB
    /// </summary>
    class ProcessControlBlock {
        /// <summary>
        /// 进程号
        /// </summary>
        public int ID;

        /// <summary>
        /// 进程状态
        /// </summary>
        public ProcessStatus Status;

        /// <summary>
        /// 进程到达时间
        /// </summary>
        public int ArriveTime;

        /// <summary>
        /// 估计运行时间
        /// </summary>
        public int Time;

        /// <summary>
        /// 已运行时间
        /// </summary>
        public int RunTime = 0;

        /// <summary>
        /// 等待时间
        /// </summary>
        public int WaitTime;

        /// <summary>
        /// 优先级
        /// </summary>
        public int Priority;

        /// <summary>
        /// 链接指针
        /// </summary>
        public ProcessControlBlock Next;

        /// <summary>
        /// 开始时间
        /// </summary>
        public int StartTime;

        /// <summary>
        /// 结束时间
        /// </summary>
        public int FinishTime;

        public void Run()
        {
            this.Status = ProcessStatus.Run;

            if (RunTime >= Time) {
                this.Status = ProcessStatus.Finish;
                return;
            }

            this.RunTime++;
        }

        public void Wait()
        {
            this.WaitTime++;
        }

        public override string ToString() => String.Format("{0} {1} {2}", ID, StartTime, FinishTime);
    }
}

2. CentralProcessUnit.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace OperatingSystemExperiment.Exp1 {
    class CentralProcessUnit {
        private List<ProcessControlBlock> PCBList = new List<ProcessControlBlock>();
        private Queue<ProcessControlBlock> FinishQueue = new Queue<ProcessControlBlock>();
        private Queue<ProcessControlBlock> ReadyQueue = new Queue<ProcessControlBlock>();

        public CentralProcessUnit()
        {
            LoadPcbList();
        } 

        /// <summary>
        /// 生成进程列表
        /// </summary>
        /// <param name="count">进程数量</param>
        public static void GenerateProcessList(int count)
        {
            var processListFile = Path.Combine(Environment.CurrentDirectory, "process_list.txt");
            var writer = new StreamWriter(processListFile);
            var rnd = new Random(DateTime.Now.Millisecond);
            for (var i = 0; i < count; i++) {
                var runTime = rnd.Next(1, 10);
                writer.WriteLine("{0} {1} {2} {3}", i, Math.Pow(2, i), runTime, rnd.Next(0, 4));
            }

            writer.Close();
        }

        /// <summary>
        /// 加载PCB列表
        /// </summary>
        private void LoadPcbList()
        {
            var processListFile = Path.Combine(Environment.CurrentDirectory, "process_list.txt");
            var reader = new StreamReader(processListFile);
            while (!reader.EndOfStream) {
                var line = reader.ReadLine();
                var procInfo = line.Split(' ');
                PCBList.Add(new ProcessControlBlock {
                    ID = int.Parse(procInfo[0]),
                    ArriveTime = int.Parse(procInfo[1]),
                    Time = int.Parse(procInfo[2]),
                    Priority = int.Parse(procInfo[3])
                });
            }
        }

        /// <summary>
        /// CPU运行
        /// </summary>
        public void Run()
        {
            var times = 0;
            while (true) {
                // 如果所有进程运行完，则退出循环
                if (FinishQueue.Count == PCBList.Count) {
                    break;
                }

                // 遍历所有进程列表
                foreach (var p in PCBList) {
                    // 根据进程到达时间判定是否有新进程加入，然后将进程状态设置为就绪
                    if (p.ArriveTime == times++) {
                        Console.WriteLine("时间：{0},进程 {1} 到达", times, p.ID);
                        p.Status = ProcessStatus.Ready;
                    }

                    // 讲就绪状态进程加入就绪列表
                    if (p.Status == ProcessStatus.Ready) {
//                        Console.WriteLine("时间：{0}，进程 {1} 加入就绪列表", times, p.ID);
                        ReadyQueue.Enqueue(p);
                    }

                    // 如果就绪队列为空则进入下一次循环
                    if (ReadyQueue.Count == 0) {
//                        Console.WriteLine("时间：{0}，没有就绪进程，进入下一个循环", times);
                        continue;
                    }

                    // 从就绪队列中取出一个进程运行
                    var currentProcess = ReadyQueue.Dequeue();
                    Console.WriteLine("时间：{0}，运行进程 {1}", times, p.ID);
                    currentProcess.Run();

                    // 将运行完毕进程加入完成列表
                    if (currentProcess.Status == ProcessStatus.Finish) {
                        Console.WriteLine("时间：{0}，进程 {1} 运行完毕，总运行时间：{2}", times, p.ID, p.RunTime);
                        FinishQueue.Enqueue(currentProcess);
                    }
                    else
                        currentProcess.Status = ProcessStatus.Ready;
                }
            }
        }
    }
}

3. Main.cs

namespace OperatingSystemExperiment.Exp1
{
    public class Main
    {
        public static void Run()
        {
            CentralProcessUnit.GenerateProcessList(5);
            new CentralProcessUnit().Run();
        }
    }
}

Results

• Contents of the generated process_list.txt:

0 1 8 3
1 2 3 1
2 4 8 0
3 8 6 3
4 16 4 1

• Console output Time: 1, running process 0 Time: 2, running process 1 Time: 3, running process 2 Time: 4, running process 3 Time: 5, running process 4 Time: 6, running process 0 Time: 7, running process 1 Time: 8, running process 2 Time: 9, process 3 arrived Time: 9, running process 3 Time: 10, running process 4 Time: 11, running process 0 Time: 12, running process 1 Time: 13, running process 2 Time: 14, running process 3 Time: 15, running process 4 Time: 16, running process 0 Time: 17, running process 1 Time: 17, process 1 finished running, total running time: 3 Time: 18, running process 2 Time: 19, running process 3 Time: 20, running process 4 Time: 21, running process 0 Time: 23, running process 2 Time: 24, running process 3 Time: 25, running process 4 Time: 25, process 4 finished running, total running time: 4 Time: 26, running process 0 Time: 28, running process 2 Time: 29, running process 3 Time: 31, running process 0 Time: 33, running process 2 Time: 34, running process 3 Time: 34, process 3 finished running, total running time: 6 Time: 36, running process 0 Time: 38, running process 2 Time: 41, running process 0 Time: 41, process 0 finished running, total running time: 8 Time: 43, running process 2 Time: 43, process 2 finished running, total running time: 8

Welcome to communicate with me

• Live coding room: https://live.bilibili.com/11883038
• WeChat Official Account: DealiAxy
• Zhihu: https://www.zhihu.com/people/dealiaxy
• Blog: https://blog.deali.cn
• Jianshu: https://www.jianshu.com/u/965b95853b9f