短进程优先算法实验

实验报告

班级：10041461
姓名：任天起
学号：1004146111

实验目的：

就绪进程数大于处理机数时，按照某种策略决定哪些进程优先占用处理机。实验模拟处理机调度，加深对处理机调度的理解。

实验内容：

实验一模拟短进程优先调度
进程8 个,到达时间和服务时间(用户输入)
至少两种结果: 1 到达时间:0,1,2,….
2 到达时间:其他

实验源代码

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
//进程类
public class Process {
    String processName;     //进程名称
    int arrivalTime;        //到达时间
    int starTime;           //开始时间
    int finishTime;         //实际完成时间
    int wholeTime;          //运行所需要的的时间；
    public String getProcessName() {
        return processName;
    }
    public int getStarTime() {
        return starTime;
    }
    public int getFinishTime() {
        return finishTime;
    }
    public int getArrivalTime() {
        return arrivalTime;
    }
    public void setFinishTime(int finishTime) {
        this.finishTime = finishTime;
    }
    public void setStarTime(int starTime) {
        this.starTime = starTime;
    }
    public int getWholeTime() {
        return wholeTime;
    }
    public Process(String processName, int arrivalTime, int wholeTime) {
        this.processName = processName;
        this.arrivalTime = arrivalTime;
        this.wholeTime = wholeTime;
    }
}
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
110
111
112
113
114
115
public class Short_process {
    public static void main(String[] args) {
        ArrayList<Process> arrayList = new ArrayList<>();
        Scanner in = new Scanner(System.in);
        System.out.println("请输入有几个进程呢？");
        int numberofprocess = in.nextInt();
        for (int i = 0 ; i<numberofprocess;i++)
        {
            System.out.println("请输入进程"+(i+1)+"的进程名称");
            String name = in.next();
            System.out.println("请输入进程"+(i+1)+"的到达时间");
            int arrivalTime = in.nextInt();
            System.out.println("请输入进程"+(i+1)+"的运行所需时间");
            int wholeTime = in.nextInt();
            Process process = new Process(name,arrivalTime,wholeTime);
            arrayList.add(process);
            //System.out.println("----------------------------");
        }
        
        test(arrayList);
    }
    public static void test (ArrayList<Process> arrayList)
    {
        int nowtime =0;                     //当前时间
        int currentprocess=0;               //当前进程
        int remain = arrayList.size();      //剩余进程数
        int numofprocess =arrayList.size();
        ArrayList<Process> arrayList1 = new ArrayList<>();
        /*
        以到达时间给进程排序；
         */
        Collections.sort(arrayList, new Comparator<Process>() {
            @Override
            public int compare(Process o1, Process o2) {
                return o1.getArrivalTime()<o2.getArrivalTime()?-1:1;
            }
        });
        while (remain>0)
        {
            
            System.out.println(remain);
            int shortTestArrival = arrayList.get(0).getArrivalTime();
            if (nowtime<shortTestArrival)                               //当前时间没有进程排队
                nowtime = shortTestArrival;
            int i = 1;
            currentprocess = 0;
            /*
            寻找到达中的最短进程
             */
            while (arrayList.size()>i &&arrayList.get(i).getArrivalTime()<=nowtime)
            {
                /*
                 */
                if (arrayList.get(i).getWholeTime()<arrayList.get(currentprocess).getWholeTime())
                {
                    currentprocess = i;
                }
                if (arrayList.get(i).getWholeTime()==arrayList.get(currentprocess).getWholeTime())
                {
                   int a = (int) (Math.random()*1000);                      //模拟进程条件相同，cpu随便选取
                    if ((a&1)==0)
                    {
                        currentprocess =i;
                    }
                }
                i++;
            }
            //Process process = arrayList.get(currentprocess);
            int wholeTime = arrayList.get(currentprocess).getWholeTime();           //运行时间
            arrayList.get(currentprocess).setStarTime(nowtime);                     //设置实际开始时间
            nowtime+=wholeTime;                                                     //当前时间更新
            arrayList.get(currentprocess).setFinishTime(nowtime);                   //设置完成时间
            arrayList1.add(arrayList.get(currentprocess));                          //加入完成队列
            arrayList.remove(currentprocess);                                       //等待队列删除；
            remain--;                                                               //剩余进程--
        }
        double sumTurnaround_time=0;
        double sumTurnaround_time_withwight =0;
        for (int i = 0; i < arrayList1.size(); i++) {
            double Turnaround_time;
            double Turnaround_time_withwight;
            System.out.println("进程"+(i+1)+arrayList1.get(i).getProcessName()+"的开始时间为");
            System.out.println(arrayList1.get(i).getStarTime());
            System.out.println("进程"+(i+1)+"的完成时间为");
            System.out.println(arrayList1.get(i).getFinishTime());
            System.out.println("进程"+(i+1)+"周转时间为");
            Turnaround_time = arrayList1.get(i).getFinishTime() - arrayList1.get(i).getArrivalTime();
            sumTurnaround_time+=Turnaround_time;
            System.out.println(Turnaround_time);
            System.out.println("进程"+(i+1)+"带权周转时间为");
            Turnaround_time_withwight = Turnaround_time / (double) arrayList1.get(i).getWholeTime();
            sumTurnaround_time_withwight+=Turnaround_time_withwight;
            System.out.println(Turnaround_time_withwight);
            System.out.println("----------------------------------------------");
        }
        System.out.println("先后顺序为：");
        for (int i = 0; i < arrayList1.size(); i++) {
            System.out.print(arrayList1.get(i).getProcessName()+" ");
        }
        System.out.println();
        System.out.println("这组进程的平均周转时间为");
        System.out.println(sumTurnaround_time / numofprocess);
        System.out.println("这组进程的平均带权周转时间为");
        System.out.println(sumTurnaround_time_withwight / numofprocess);
    }
}

结果贴图，

进程

简单来说：C,D条件一样，F，G条件一样，所以会存在不同的结果；

结果一：

结果1表格

实际截图

结果1

结果1.1
结果1.2

结果二：

结果二

实际截图

结果2

结果2.1

结果2.2

实验结果分析：

算法特点，针对不同情况有什么样的优劣
优点: 短进程优先嘛，所以短进程肯定运行的更顺畅，更快结束；算法比较简单，只要在队列里找到运行时间短的就可以啦

缺点：长进程很吃亏，可能会一直等待；完全不考虑等待时间，没有优先级，也没有紧迫感；需要预先知晓进程的运行所需时间；由于事先需要知晓运行时间，那么人机交互基本就不可能啦；

实验中发现的问题：

  1. Java中关于Collections.sort的用法；
  2. 关于相同条件进程的判断；
  3. 进程太多，要输入的太多，老是输入错误；

实验二模拟时间片轮转调度

实验源代码

1
2
3
4
5
6
public class Process {            //进程部分加了运行时间的备份，另一个会在运行时减少；
           int wholeTimeBack;      //运行时间备份；
           public int getWholeTimeBack() {
           return wholeTimeBack;
    }
}
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
110
111
112
113
 public static void main(String[] args) {
        LinkedList<Process> linkedList = new LinkedList<>();
        Scanner in = new Scanner(System.in);
        System.out.println("请输入有几个进程呢？");
        int numberofprocess = in.nextInt();
        for (int i = 0 ; i<numberofprocess;i++)
        {
            System.out.println("请输入进程"+(i+1)+"的进程名称");
            String name = in.next();
            System.out.println("请输入进程"+(i+1)+"的到达时间");
            int arrivalTime = in.nextInt();
            System.out.println("请输入进程"+(i+1)+"的运行所需时间");
            int wholeTime = in.nextInt();
            Process process = new Process(name,arrivalTime,wholeTime);
            linkedList.add(process);
          //  System.out.println("----------------------------");
        }
        test(linkedList);
    }
    public static void test(LinkedList<Process> linkedList)
    {
        final  int slice = 1;                                   //时间片大小
        ArrayList<Process> arrayList = new ArrayList<>();       //存储结果的容器
        Queue<Process> queue = new LinkedList<>();              //进程队列
        int nowtime = 0 ;                                       //目前时间
        int numberOfProcess = linkedList.size();                //进程数目
        int numberOfPorcessback = numberOfProcess;
        Collections.sort(linkedList, new Comparator<Process>() {
            @Override
            public int compare(Process o1, Process o2) {
                return o1.getArrivalTime()<o2.getArrivalTime()?-1:1;
            }
        });
        while (numberOfProcess>0)
        {
            /*
            进程队列有可能为空，这时CPU空闲，我们从作业中提取一个；
             */
            if (queue==null||queue.size()==0)
            {
                queue.add(linkedList.peekFirst());
                linkedList.poll();
            }
            /*
            cpu空闲，时间就更改
             */
            if (nowtime<queue.peek().getArrivalTime()) {
                System.out.println("cpu"+nowtime+"~"+queue.peek().getArrivalTime()+"空闲");
                nowtime = queue.peek().getArrivalTime();
            }
            /*
            核心代码
             */
            while (queue.size()!=0)
            {
                boolean flag = false;                                   //进程是否做完的标志
                int currentwholetime = queue.peek().getWholeTime();     //当前所需要的运行时间
                queue.peek().setWholeTime(currentwholetime-slice);
                if (queue.peek().getWholeTime()<=0)                     //进程做完
                {
                    queue.peek().setWholeTime(0);                       //运行时间设置为0；
                    numberOfProcess--;                                  //进程数--；
                    nowtime+=currentwholetime;
                    queue.peek().setFinishTime(nowtime);
                    arrayList.add(queue.poll());
                }
                else                                            //进程没做完；
                {
                    flag = true;
                    nowtime+=slice;
                }
                while (linkedList.size()!=0&&linkedList.peek().getArrivalTime()<nowtime)
                {
                    queue.add(linkedList.pop());
                }
                /*
                这里有两种情形，一种是时间片用完的在先，一种是从作业到来的在先；
                 */
                if (flag)
                {
                    queue.add(queue.peek());
                    queue.poll();
                }
                while (linkedList.size()!=0&&linkedList.peek().getArrivalTime()==nowtime)
                {
                    queue.add(linkedList.pop());
                }
            }
        }
        double sumTurnaround_time=0;
        double sumTurnaround_time_withwight =0;
        for (int i = 0; i < arrayList.size(); i++) {
            Process process= arrayList.get(i);
            System.out.print(process.getProcessName()+"到达时间为"+process.getArrivalTime()+" ");
            System.out.print("结束时间为"+process.getFinishTime()+" ");
            System.out.print("周转时间为"+(process.getFinishTime()-process.getArrivalTime()+" "));
            double Turnaround_time=(double)(process.getFinishTime()-process.getArrivalTime());
            System.out.print("周转时间"+Turnaround_time+" ");
            sumTurnaround_time+=Turnaround_time;
            double Turnaround_time_withwight= ((double)(process.getFinishTime()-process.getArrivalTime()))/(double)process.getWholeTimeBack();
            System.out.println("带权周转时间为"+Turnaround_time_withwight+" ");
            sumTurnaround_time_withwight+=Turnaround_time_withwight;
            System.out.println();
        }
        System.out.println("--------------------------------");
        System.out.println("平均周转时间为"+sumTurnaround_time/numberOfPorcessback);
        System.out.println("平均带权周转时间为"+ sumTurnaround_time_withwight/numberOfPorcessback);
    }
}

结果贴图

时间片为1：时间片优先级>新到达的进程

结果一

运行截图：

结果1.1

时间片为5： 时间片>新到达的进程；

结果2

运行截图：

结果2.1

实验结果分析：

算法特点：
优点：比较均衡，你做一下，我做一下；比较平均，算法也比较简单实现；
缺点：时间一旦选的不好，就会造成不平衡的状态；太短的话，等于一起做，先来后来没有区别；太长的话，和依次做没有区别，所以时间片必须选择好；对紧急任务没有反应，不适合紧急的任务；而且时间片轮转，io操作怎么办，会有延迟，或者根本不让io操作吧；

实验中发现的问题

  1. 书上的例子不对
  2. 时间片用完和新进来的进程不知道选哪种；其实两种就是调换一下代码位置；
  3. 进程数量多的话，时间片短就会非常难算，所以就选择了5个；
  4. 由于代码完全没有任何参考，所以有bug也说不定；
继续跑<br><br>带着赤子的骄傲