current position:Home>Tit operating system experiment 5 simulated time slice scheduling (process scheduling algorithm) (first come first service, short job priority, time slice rotation, highest priority priority scheduling)

Tit operating system experiment 5 simulated time slice scheduling (process scheduling algorithm) (first come first service, short job priority, time slice rotation, highest priority priority scheduling)

2022-01-26 22:52:21 Zhang Shier

Experiment five Simulation scheduling time slice ( Process scheduling algorithm )

Preface

Related knowledge

First come, first serve (FCFS): Schedule according to the order in which the process is submitted to the system

Short job preferred (SJF/SPF): Measured by the running time required by the process

Time slice rotation : Sort by first come, first served , In a time slice , Execute different processes in turn

Highest priority first scheduling algorithm (HRRN): Set a priority for each job ( Response ratio ), Calculate the priority of each job before scheduling , The higher the priority number, the better the scheduling RP( Response ratio )= Operation turnover time / Job run time =1+ Job waiting time / Job run time

Calculation

Turnaround time = When the homework is finished - Homework arrival time

Turnaround time with rights = Turnaround time / Service time

Average turnaround time = Total operation turnaround time / Number of assignments

Average weighted turnaround time = Total weighted turnaround time / Number of assignments

The experiment purpose

Write and debug the simulation program of process scheduling in high-level language , To deepen the understanding of process scheduling algorithm

Experimental content

1、 Customize the data structure related to the process

2、 Implement the first come first serve algorithm 、 Time slice rotation algorithm 、 Highest priority first scheduling algorithm 、 Shortest process first scheduling algorithm

3、 Test the turnaround time of the above process scheduling strategy 、 Turnaround time with rights 、 Average turnaround time and average weighted turnaround time , And qualitatively evaluate their performance

The experimental steps

menu

public static void runattribute(attribute[] ab) {
    //  Run the call 
    System.out.println(" Please select sort by ");
    Scanner in = new Scanner(System.in);
    int n = -1;
    while (n != 0) {
    
        System.out.println("1. First come, first serve  2. The shortest process takes precedence  3. Time slice wheel  4. Preemptive high priority  0 sign out ");
        n = in.nextInt();
        switch (n) {
    
            case 1:
                ab = InputTimesort(ab);
                OutputAttribute(ab);
                break;
            case 2:
                ab = Short_jobs_take_precedence(ab, 0, 0);
                OutputAttribute(ab);
                break;
            case 3:
                System.out.println(" Please enter the time slice time ");
                n = in.nextInt();
                Time_slice_rotation(ab, n);
                break;
            case 4:
                ab = priorityTimesort(ab, 0, 0);
                OutputAttribute(ab);
                break;
        }
    }
    return;
}

Define an object for the process

class attribute {
    
	static int runname = -1;//  Name the current progress 
	int Run_time;//  Need service time 
	int input_time;//  Input time 
	int name = -1;//  Process number 

	public int getName() {
    
		return name;
	}

	public void setName(int name) {
    
		this.name = name;
	}

	public attribute() {
    
	}

	public attribute(int input_time, int run_time) {
    
		this.Run_time = run_time;
		this.input_time = input_time;
		runname++;
		this.name = runname + 0;

	}

	public int getRun_time() {
    
		return Run_time;
	}

	public void setRun_time(int run_time) {
    
		Run_time = run_time;
	}

	public int getInput_time() {
    
		return input_time;
	}

	public void setInput_time(int input_time) {
    
		this.input_time = input_time;
	}
}

First come, first served

//  First come, first serve , Sort the input time ( Bubble sort )
	private static attribute[] InputTimesort(attribute[] ab) {
    
		for (int i = 0; i < ab.length; i++) {
    
			int min = i;
			for (int J = i; J < ab.length; J++) {
    
				if (ab[J].getInput_time() < ab[i].getInput_time()) {
    
					min = J;
				}
			}
			swat(ab, i, min);
		}
		return ab;
	}

The shortest process takes precedence

// The shortest process takes precedence 
private static attribute[] Short_jobs_take_precedence(attribute[] ab, int i, int Begin) {
    
    int min_Run_time = -1;
    int min_input_time = i;
    int index = -1;
    //  Get the shortest running time before the running time 
    for (int j = Begin; j < ab.length; j++) {
    
        if (ab[j].input_time <= i) {
    
            if (min_Run_time == -1) {
    
                index = j;
                min_Run_time = ab[j].Run_time;
            } else {
    
                if (min_Run_time > ab[j].Run_time) {
    
                    index = j;
                    min_Run_time = ab[j].Run_time;
                }
            }
        }
    }
    if (index == -1) {
    
        min_Run_time = ab[Begin].Run_time;
        min_input_time = ab[Begin].input_time;
        index = Begin;
        for (int j = Begin; j < ab.length; j++) {
    
            if (ab[j].input_time < min_input_time) {
    
                min_input_time = ab[j].input_time;
                index = j;
                min_Run_time = ab[j].Run_time;
            } else {
    
                if (ab[j].input_time == min_input_time) {
    
                    if (min_Run_time < ab[j].Run_time) {
    
                        min_input_time = ab[j].input_time;
                        index = j;
                        min_Run_time = ab[j].Run_time;
                    }
                }
            }
        }
    }
    swat(ab, Begin, index);
    if (Begin + 1 == ab.length) {
    
        return ab;
    }
    Short_jobs_take_precedence(ab, (min_input_time > i ? min_input_time : i) + min_Run_time, Begin + 1);
    return ab;
}

Time slice rotation

// Time slice wheel 
private static attribute[] Time_slice_rotation(attribute[] ab, int n) {
    
    int[] Alltime = new int[ab.length];//  It takes time to complete 
    for (int j = 0; j < ab.length; j++) {
    
        Alltime[j] = ab[j].Run_time;
    }
    int[] complete_Alltime = new int[ab.length];//  Time completed 
    int min_input_time = -1;
    int index;
    int complete = 0;//  Number of completed 
    int N = 1;
    while (complete < ab.length) {
    
        index = -1;
        for (int i = 0; i < ab.length; i++) {
    
            if (ab[i].input_time >= N * n) {
    
                continue;
            }
            if (Alltime[i] <= complete_Alltime[i]) {
    
                continue;
            }
            if (index == -1) {
    
                index = i;
                min_input_time = ab[i].input_time;
            }
            if (ab[i].input_time < min_input_time) {
    
                index = i;
            }
        }
        if (index != -1) {
    
            if (ab[index].input_time > N * n - n) {
    
                complete_Alltime[index] = N * n - ab[index].input_time;
            } else {
    
                complete_Alltime[index] += n;
            }

            if (Alltime[index] <= complete_Alltime[index]) {
    
                complete++;
                complete_Alltime[index] = Alltime[index];
            }
            System.out.println(" The first " + N + " Time slice   Run the process " + ab[index].name + " Progress is  " + complete_Alltime[index] + "/"
                               + Alltime[index]);
        } else {
    
            System.out.println(" The first " + N + " Time slice   No process has entered ");

        }
        N++;
    }
    return null;
}

Preemptive high priority

//  Preemptive high priority 
private static attribute[] priorityTimesort(attribute[] ab, int i, int Begin) {
    
    int min_Run_time = -1;
    int min_input_time = i;
    int min_priority = 0;
    int index = -1;
    //  Gets the highest priority before runtime 
    for (int j = Begin; j < ab.length; j++) {
    
        if (ab[j].input_time <= min_input_time) {
    
            if (min_Run_time == -1) {
    
                index = j;
                min_Run_time = ab[j].Run_time;
                min_priority = (ab[j].input_time - i) / ab[j].Run_time;
            } else {
    
                if (min_priority > (ab[j].input_time - i) / ab[j].Run_time) {
    //  Priority is higher than me 
                    index = j;
                    min_Run_time = ab[j].Run_time;
                    min_priority = (ab[j].input_time - i) / ab[j].Run_time;
                }
            }
        }
    }
    if (index == -1) {
    
        min_Run_time = ab[Begin].Run_time;
        min_input_time = ab[Begin].input_time;
        index = Begin;
        for (int j = Begin; j < ab.length; j++) {
    
            if (ab[j].input_time < min_input_time) {
    //  The running time is changed directly before me 
                min_input_time = ab[j].input_time;
                index = j;
                min_Run_time = ab[j].Run_time;
            } else {
    
                if (ab[j].input_time == min_input_time) {
    
                    if (min_input_time < ab[j].Run_time) {
    //  The running time is small, so you can change it directly 
                        min_input_time = ab[j].input_time;
                        index = j;
                        min_Run_time = ab[j].Run_time;
                    }
                }
            }
        }
    }
    swat(ab, Begin, index);
    if (Begin + 1 == ab.length) {
    
        return ab;
    }
    priorityTimesort(ab, (min_input_time > i ? min_input_time : i) + min_Run_time, Begin + 1);
    return ab;
}

Displacement array position

//  Swap places 
public static void swat(attribute[] ab, int i, int index) {
    
    attribute a = ab[i];
    ab[i] = ab[index];
    ab[index] = a;
}

Results output

public static void OutputAttribute(attribute[] ab) {
    
    int time = ab[0].input_time;
    int TimeSum[] = new int[ab.length];//  Total operation turnaround time 
    double DTimeSum[] = new double[ab.length];//  Total weighted turnaround time 
    System.out.print(" process ID ");
    System.out.print(" Arrival time  ");
    System.out.print(" Service time  ");
    System.out.print(" Completion time  ");
    System.out.print(" Turnaround time  ");
    System.out.print(" Turnaround time with rights  \n");
    for (int i = 0; i < ab.length; i++) {
    
        if (ab[i].input_time > time) {
    
            time = ab[i].input_time;
        }

        System.out.print(ab[i].name + "\t ");//  process ID
        System.out.print(ab[i].input_time + "\t ");//  Arrival time 
        time += ab[i].Run_time;
        System.out.print(ab[i].Run_time + "\t ");//  Service time 
        System.out.print(time + "\t ");//  Completion time 
        TimeSum[i] = (time - ab[i].input_time);
        System.out.print(TimeSum[i] + "\t ");//  Turnaround time 
        DTimeSum[i] = (double)(TimeSum[i] / ab[i].Run_time);

        System.out.print(DTimeSum[i]);//  Turnaround time with rights 
        System.out.println();
    }
    System.out.println(" Total turnaround time :" + Arrays.stream(TimeSum).sum());
    System.out.println(" Average turnaround time :" + (double)Arrays.stream(TimeSum).sum()/ab.length);
    System.out.println(" Total weighted turnaround time :" + Arrays.stream(DTimeSum).sum());
    System.out.println(" Average weighted turnaround time :" + Arrays.stream(DTimeSum).sum()/ab.length);
}

The main function

public class  Simulation scheduling time slice  {
    
    public static void main(String[] args) {
    
        //  Define five processes ,attribure Indicates the time of arrival , Service time 
        attribute[] ab = {
     
            new attribute(1, 5),
            new attribute(8, 5),
            new attribute(10, 5),
            new attribute(16, 15),
            new attribute(14, 25) };
        utils.runattribute(ab);//  Select sorting method 
    }
}

Complete code

package  Operating system experiments ;

import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;

/* *  Simulation scheduling time slice  * @author  Zhang Shier  * @data 2021 year 12 month 16 Japan  */
public class  Simulation scheduling time slice  {
    
    public static void main(String[] args) {
    
        //  Define five processes ,attribure Indicates the time of arrival , Service time 
        attribute[] ab = {
     
            new attribute(1, 5),
            new attribute(8, 5),
            new attribute(10, 5),
            new attribute(16, 15),
            new attribute(14, 25) };
        utils.runattribute(ab);//  Select sorting method 
    }
}

// Define an object for the process 
class attribute {
    
    static int runname = -1;//  Name the current progress 
    int Run_time;//  Need service time 
    int input_time;//  Input time 
    int name = -1;//  Process number 

    public int getName() {
    
        return name;
    }

    public void setName(int name) {
    
        this.name = name;
    }

    public attribute() {
    
    }

    public attribute(int input_time, int run_time) {
    
        this.Run_time = run_time;
        this.input_time = input_time;
        runname++;
        this.name = runname + 0;

    }

    public int getRun_time() {
    
        return Run_time;
    }

    public void setRun_time(int run_time) {
    
        Run_time = run_time;
    }

    public int getInput_time() {
    
        return input_time;
    }

    public void setInput_time(int input_time) {
    
        this.input_time = input_time;
    }
}

class utils {
    
    //  Output results OutputAttribute
    public static void OutputAttribute(attribute[] ab) {
    
        int time = ab[0].input_time;
        int TimeSum[] = new int[ab.length];//  Total operation turnaround time 
        double DTimeSum[] = new double[ab.length];//  Total weighted turnaround time 
        System.out.print(" process ID ");
        System.out.print(" Arrival time  ");
        System.out.print(" Service time  ");
        System.out.print(" Completion time  ");
        System.out.print(" Turnaround time  ");
        System.out.print(" Turnaround time with rights  \n");
        for (int i = 0; i < ab.length; i++) {
    
            if (ab[i].input_time > time) {
    
                time = ab[i].input_time;
            }

            System.out.print(ab[i].name + "\t ");//  process ID
            System.out.print(ab[i].input_time + "\t ");//  Arrival time 
            time += ab[i].Run_time;
            System.out.print(ab[i].Run_time + "\t ");//  Service time 
            System.out.print(time + "\t ");//  Completion time 
            TimeSum[i] = (time - ab[i].input_time);
            System.out.print(TimeSum[i] + "\t ");//  Turnaround time 
            DTimeSum[i] = (double)(TimeSum[i] / ab[i].Run_time);

            System.out.print(DTimeSum[i]);//  Turnaround time with rights 
            System.out.println();
        }
        System.out.println(" Total turnaround time :" + Arrays.stream(TimeSum).sum());
        System.out.println(" Average turnaround time :" + (double)Arrays.stream(TimeSum).sum()/ab.length);
        System.out.println(" Total weighted turnaround time :" + Arrays.stream(DTimeSum).sum());
        System.out.println(" Average weighted turnaround time :" + Arrays.stream(DTimeSum).sum()/ab.length);
    }

    public static void runattribute(attribute[] ab) {
    //  Run the call 
        System.out.println(" Please select sort by ");
        Scanner in = new Scanner(System.in);
        int n = -1;
        while (n != 0) {
    
            System.out.println("1. First come, first serve  2. The shortest process takes precedence  3. Time slice wheel  4. Preemptive high priority  0 sign out ");
            n = in.nextInt();
            switch (n) {
    
                case 1:
                    ab = InputTimesort(ab);
                    OutputAttribute(ab);
                    break;
                case 2:
                    ab = Short_jobs_take_precedence(ab, 0, 0);
                    OutputAttribute(ab);
                    break;
                case 3:
                    System.out.println(" Please enter the time slice time ");
                    n = in.nextInt();
                    Time_slice_rotation(ab, n);
                    break;
                case 4:
                    ab = priorityTimesort(ab, 0, 0);
                    OutputAttribute(ab);
                    break;
            }
        }
        return;
    }

    //  First come, first serve , Sort the input time ( Bubble sort )
    private static attribute[] InputTimesort(attribute[] ab) {
    
        for (int i = 0; i < ab.length; i++) {
    
            int min = i;
            for (int J = i; J < ab.length; J++) {
    
                if (ab[J].getInput_time() < ab[i].getInput_time()) {
    
                    min = J;
                }
            }
            swat(ab, i, min);
        }
        return ab;
    }

    // The shortest process takes precedence 
    private static attribute[] Short_jobs_take_precedence(attribute[] ab, int i, int Begin) {
    
        int min_Run_time = -1;
        int min_input_time = i;
        int index = -1;
        //  Get the shortest running time before the running time 
        for (int j = Begin; j < ab.length; j++) {
    
            if (ab[j].input_time <= i) {
    
                if (min_Run_time == -1) {
    
                    index = j;
                    min_Run_time = ab[j].Run_time;
                } else {
    
                    if (min_Run_time > ab[j].Run_time) {
    
                        index = j;
                        min_Run_time = ab[j].Run_time;
                    }
                }
            }
        }
        if (index == -1) {
    
            min_Run_time = ab[Begin].Run_time;
            min_input_time = ab[Begin].input_time;
            index = Begin;
            for (int j = Begin; j < ab.length; j++) {
    
                if (ab[j].input_time < min_input_time) {
    
                    min_input_time = ab[j].input_time;
                    index = j;
                    min_Run_time = ab[j].Run_time;
                } else {
    
                    if (ab[j].input_time == min_input_time) {
    
                        if (min_Run_time < ab[j].Run_time) {
    
                            min_input_time = ab[j].input_time;
                            index = j;
                            min_Run_time = ab[j].Run_time;
                        }
                    }
                }
            }
        }
        swat(ab, Begin, index);
        if (Begin + 1 == ab.length) {
    
            return ab;
        }
        Short_jobs_take_precedence(ab, (min_input_time > i ? min_input_time : i) + min_Run_time, Begin + 1);
        return ab;
    }
    //  Swap places 
    public static void swat(attribute[] ab, int i, int index) {
    
        attribute a = ab[i];
        ab[i] = ab[index];
        ab[index] = a;
    }

    // Time slice wheel 
    private static attribute[] Time_slice_rotation(attribute[] ab, int n) {
    
        int[] Alltime = new int[ab.length];//  It takes time to complete 
        for (int j = 0; j < ab.length; j++) {
    
            Alltime[j] = ab[j].Run_time;
        }
        int[] complete_Alltime = new int[ab.length];//  Time completed 
        int min_input_time = -1;
        int index;
        int complete = 0;//  Number of completed 
        int N = 1;
        while (complete < ab.length) {
    
            index = -1;
            for (int i = 0; i < ab.length; i++) {
    
                if (ab[i].input_time >= N * n) {
    
                    continue;
                }
                if (Alltime[i] <= complete_Alltime[i]) {
    
                    continue;
                }
                if (index == -1) {
    
                    index = i;
                    min_input_time = ab[i].input_time;
                }
                if (ab[i].input_time < min_input_time) {
    
                    index = i;
                }
            }
            if (index != -1) {
    
                if (ab[index].input_time > N * n - n) {
    
                    complete_Alltime[index] = N * n - ab[index].input_time;
                } else {
    
                    complete_Alltime[index] += n;
                }

                if (Alltime[index] <= complete_Alltime[index]) {
    
                    complete++;
                    complete_Alltime[index] = Alltime[index];
                }
                System.out.println(" The first " + N + " Time slice   Run the process " + ab[index].name + " Progress is  " + complete_Alltime[index] + "/"
                                   + Alltime[index]);
            } else {
    
                System.out.println(" The first " + N + " Time slice   No process has entered ");

            }
            N++;
        }
        return null;
    }

    //  Preemptive high priority 
    private static attribute[] priorityTimesort(attribute[] ab, int i, int Begin) {
    
        int min_Run_time = -1;
        int min_input_time = i;
        int min_priority = 0;
        int index = -1;
        //  Gets the highest priority before runtime 
        for (int j = Begin; j < ab.length; j++) {
    
            if (ab[j].input_time <= min_input_time) {
    
                if (min_Run_time == -1) {
    
                    index = j;
                    min_Run_time = ab[j].Run_time;
                    min_priority = (ab[j].input_time - i) / ab[j].Run_time;
                } else {
    
                    if (min_priority > (ab[j].input_time - i) / ab[j].Run_time) {
    //  Priority is higher than me 
                        index = j;
                        min_Run_time = ab[j].Run_time;
                        min_priority = (ab[j].input_time - i) / ab[j].Run_time;
                    }
                }
            }
        }
        if (index == -1) {
    
            min_Run_time = ab[Begin].Run_time;
            min_input_time = ab[Begin].input_time;
            index = Begin;
            for (int j = Begin; j < ab.length; j++) {
    
                if (ab[j].input_time < min_input_time) {
    //  The running time is changed directly before me 
                    min_input_time = ab[j].input_time;
                    index = j;
                    min_Run_time = ab[j].Run_time;
                } else {
    
                    if (ab[j].input_time == min_input_time) {
    
                        if (min_input_time < ab[j].Run_time) {
    //  The running time is small, so you can change it directly 
                            min_input_time = ab[j].input_time;
                            index = j;
                            min_Run_time = ab[j].Run_time;
                        }
                    }
                }
            }
        }
        swat(ab, Begin, index);
        if (Begin + 1 == ab.length) {
    
            return ab;
        }
        priorityTimesort(ab, (min_input_time > i ? min_input_time : i) + min_Run_time, Begin + 1);
        return ab;
    }
}

Running results

First come, first served

image-20211216173712589

The shortest process takes precedence

image-20211216173725983

Time slice rotation

image-20211216173758581

Preemptive high priority

image-20211216173737421

New things learned

Experiment 3 learned how to output arrays , Value passing of array , Today I found out how to call API Do some calculations of the array

int[] arr1 = {
    1, 5, 3, 6, 7};
int sum = Arrays.stream(arr1).sum(); //  Sum up 
OptionalDouble avg = Arrays.stream(arr1).average(); //  averaging 
double average = avg.getAsDouble();
int min = Arrays.stream(arr1).min().getAsInt(); //  minimum value 
int max = Arrays.stream(arr1).max().getAsInt(); //  Maximum 
System.out.println("arr1  and  = " + sum + ",  Average  = " + average
        + ",  minimum value  = " + min + ",  Maximum  = " + max);

image-20211216165046003

summary

First come first serve algorithm : The idea of the algorithm is to allocate processors according to the order of entering the ready queue . Adopt non deprivation scheduling mode , That is, once a process occupies the processor , Just keep running , The processor is not released until the process completes its work or cannot continue due to waiting for an event

① The principle of the algorithm is simple , Easy to implement

② All processes compete equally

③ Because the execution time of each process is different , This leads to relative unfairness

④ The algorithm is conducive to long process , It is not conducive to short process

⑤ This algorithm is rarely used as the main modulation strategy , It is often used as an auxiliary scheduling algorithm

Short job preferred : Measured by the running time required by the process . But it's bad for long-term operation , May cause hunger , It is difficult to achieve real short homework priority

Highest priority first scheduling algorithm : Set a priority for each job ( Response ratio ), Calculate the priority of each job before scheduling . The trade-off between the above two algorithms , Considering the waiting time and running time .

Time slice rotation : Sort by first come, first served , In a time slice , Execute different processes in turn . fair , For time-sharing systems , But frequent switching has overhead , Don't prioritize

Attached is the summary of knowledge points of Wangdao postgraduate entrance examination

image-20211216174525839 image-20211216174542619

copyright notice
author[Zhang Shier],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201262252173753.html

Random recommended