# 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

# Experiment five Simulation scheduling time slice ( Process scheduling algorithm )

## 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

``````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.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.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 The shortest process takes precedence Time slice rotation Preemptive high priority ## 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);
`````` ## 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  