الگوریتم HRRN – آموزش و توضیح به زبان ساده

1// C++ program for Highest Response Ratio Next (HRRN)
2// Scheduling
3#include <bits/stdc++.h>
4using namespace std;
5// Defining process details
6struct process {
7	char name;
8	int at, bt, ct, wt, tt;
9	int completed;
10	float ntt;
11} p[10];
12
13int n;
14
15// Sorting Processes by Arrival Time
16void sortByArrival()
17{
18	struct process temp;
19	int i, j;
20
21	// Selection Sort applied
22	for (i = 0; i < n - 1; i++) {
23		for (j = i + 1; j < n; j++) {
24
25			// Check for lesser arrival time
26			if (p[i].at > p[j].at) {
27
28				// Swap earlier process to front
29				temp = p[i];
30				p[i] = p[j];
31				p[j] = temp;
32			}
33		}
34	}
35}
36
37int main()
38{
39	int i, j, sum_bt = 0;
40	char c;
41	float t, avgwt = 0, avgtt = 0;
42	n = 5;
43
44	// predefined arrival times
45	int arriv[] = { 0, 2, 4, 6, 8 };
46
47	// predefined burst times
48	int burst[] = { 3, 6, 4, 5, 2 };
49
50	// Initializing the structure variables
51	for (i = 0, c = 'A'; i < n; i++, c++) {
52		p[i].name = c;
53		p[i].at = arriv[i];
54		p[i].bt = burst[i];
55
56		// Variable for Completion status
57		// Pending = 0
58		// Completed = 1
59		p[i].completed = 0;
60
61		// Variable for sum of all Burst Times
62		sum_bt += p[i].bt;
63	}
64
65	// Sorting the structure by arrival times
66	sortByArrival();
67	cout << "PN\tAT\tBT\tWT\tTAT\tNTT";
68	for (t = p[0].at; t < sum_bt;) {
69
70		// Set lower limit to response ratio
71		float hrr = -9999;
72
73		// Response Ratio Variable
74		float temp;
75
76		// Variable to store next process selected
77		int loc;
78		for (i = 0; i < n; i++) {
79
80			// Checking if process has arrived and is
81			// Incomplete
82			if (p[i].at <= t && p[i].completed != 1) {
83
84				// Calculating Response Ratio
85				temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
86
87				// Checking for Highest Response Ratio
88				if (hrr < temp) {
89
90					// Storing Response Ratio
91					hrr = temp;
92
93					// Storing Location
94					loc = i;
95				}
96			}
97		}
98
99		// Updating time value
100		t += p[loc].bt;
101
102		// Calculation of waiting time
103		p[loc].wt = t - p[loc].at - p[loc].bt;
104
105		// Calculation of Turn Around Time
106		p[loc].tt = t - p[loc].at;
107
108		// Sum Turn Around Time for average
109		avgtt += p[loc].tt;
110
111		// Calculation of Normalized Turn Around Time
112		p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
113
114		// Updating Completion Status
115		p[loc].completed = 1;
116
117		// Sum Waiting Time for average
118		avgwt += p[loc].wt;
119		cout << "\n" << p[loc].name << "\t" << p[loc].at;
120		cout << "\t" << p[loc].bt << "\t" << p[loc].wt;
121		cout << "\t" << p[loc].tt << "\t" << p[loc].ntt;
122	}
123	cout << "\nAverage waiting time: " << avgwt / n << endl;
124	cout << "Average Turn Around time:" << avgtt / n;
125}

1// C program for Highest Response Ratio Next (HRRN) Scheduling
2#include <stdio.h>
3
4// Defining process details
5struct process {
6	char name;
7	int at, bt, ct, wt, tt;
8	int completed;
9	float ntt;
10} p[10];
11
12int n;
13
14// Sorting Processes by Arrival Time
15void sortByArrival()
16{
17	struct process temp;
18	int i, j;
19
20	// Selection Sort applied
21	for (i = 0; i < n - 1; i++) {
22		for (j = i + 1; j < n; j++) {
23
24			// Check for lesser arrival time
25			if (p[i].at > p[j].at) {
26
27				// Swap earlier process to front
28				temp = p[i];
29				p[i] = p[j];
30				p[j] = temp;
31			}
32		}
33	}
34}
35
36void main()
37{
38	int i, j, t, sum_bt = 0;
39	char c;
40	float avgwt = 0, avgtt = 0;
41	n = 5;
42
43	// predefined arrival times
44	int arriv[] = { 0, 2, 4, 6, 8 };
45
46	// predefined burst times
47	int burst[] = { 3, 6, 4, 5, 2 };
48
49	// Initializing the structure variables
50	for (i = 0, c = 'A'; i < n; i++, c++) {
51		p[i].name = c;
52		p[i].at = arriv[i];
53		p[i].bt = burst[i];
54
55		// Variable for Completion status
56		// Pending = 0
57		// Completed = 1
58		p[i].completed = 0;
59
60		// Variable for sum of all Burst Times
61		sum_bt += p[i].bt;
62	}
63
64	// Sorting the structure by arrival times
65	sortByArrival();
66	printf("\nName\tArrival Time\tBurst Time\tWaiting Time");
67	printf("\tTurnAround Time\t Normalized TT");
68	for (t = p[0].at; t < sum_bt;) {
69
70		// Set lower limit to response ratio
71		float hrr = -9999;
72
73		// Response Ratio Variable
74		float temp;
75
76		// Variable to store next process selected
77		int loc;
78		for (i = 0; i < n; i++) {
79
80			// Checking if process has arrived and is Incomplete
81			if (p[i].at <= t && p[i].completed != 1) {
82
83				// Calculating Response Ratio
84				temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
85
86				// Checking for Highest Response Ratio
87				if (hrr < temp) {
88
89					// Storing Response Ratio
90					hrr = temp;
91
92					// Storing Location
93					loc = i;
94				}
95			}
96		}
97
98		// Updating time value
99		t += p[loc].bt;
100
101		// Calculation of waiting time
102		p[loc].wt = t - p[loc].at - p[loc].bt;
103
104		// Calculation of Turn Around Time
105		p[loc].tt = t - p[loc].at;
106
107		// Sum Turn Around Time for average
108		avgtt += p[loc].tt;
109
110		// Calculation of Normalized Turn Around Time
111		p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
112
113		// Updating Completion Status
114		p[loc].completed = 1;
115
116		// Sum Waiting Time for average
117		avgwt += p[loc].wt;
118		printf("\n%c\t\t%d\t\t", p[loc].name, p[loc].at);
119		printf("%d\t\t%d\t\t", p[loc].bt, p[loc].wt);
120		printf("%d\t\t%f", p[loc].tt, p[loc].ntt);
121	}
122	printf("\nAverage waiting time:%f\n", avgwt / n);
123	printf("Average Turn Around time:%f\n", avgtt / n);
124}

1// Java equivalent 
2import java.util.Arrays; 
3
4// Defining process details 
5class Process { 
6	char name; 
7	int at, bt, ct, wt, tt; 
8	int completed; 
9	float ntt; 
10} 
11
12public class HRRN { 
13
14	// Sorting Processes by Arrival Time 
15	static void sortByArrival(Process p[], int n) 
16	{ 
17		Process temp; 
18		int i, j; 
19
20		// Selection Sort applied 
21		for (i = 0; i < n - 1; i++) { 
22			for (j = i + 1; j < n; j++) { 
23
24				// Check for lesser arrival time 
25				if (p[i].at > p[j].at) { 
26
27					// Swap earlier process to front 
28					temp = p[i]; 
29					p[i] = p[j]; 
30					p[j] = temp; 
31				} 
32			} 
33		} 
34	} 
35
36	public static void main(String[] args) 
37	{ 
38		int i, j, sum_bt = 0; 
39		char c; 
40		float t, avgwt = 0, avgtt = 0; 
41		int n = 5; 
42
43		// predefined arrival times 
44		int arriv[] = { 0, 2, 4, 6, 8 }; 
45
46		// predefined burst times 
47		int burst[] = { 3, 6, 4, 5, 2 }; 
48
49		Process[] p = new Process[n]; 
50
51		// Initializing the structure variables 
52		for (i = 0, c = 'A'; i < n; i++, c++) { 
53			p[i] = new Process(); 
54			p[i].name = c; 
55			p[i].at = arriv[i]; 
56			p[i].bt = burst[i]; 
57
58			// Variable for Completion status 
59			// Pending = 0 
60			// Completed = 1 
61			p[i].completed = 0; 
62
63			// Variable for sum of all Burst Times 
64			sum_bt += p[i].bt; 
65		} 
66
67		// Sorting the structure by arrival times 
68		sortByArrival(p, n); 
69		System.out.println("PN\tAT\tBT\tWT\tTAT\tNTT"); 
70		for (t = p[0].at; t < sum_bt;) { 
71
72			// Set lower limit to response ratio 
73			float hrr = -9999; 
74
75			// Response Ratio Variable 
76			float temp; 
77
78			// Variable to store next process selected 
79			int loc = -1; 
80			for (i = 0; i < n; i++) { 
81
82				// Checking if process has arrived and is 
83				// Incomplete 
84				if (p[i].at <= t && p[i].completed != 1) { 
85
86					// Calculating Response Ratio 
87					temp = (p[i].bt + (t - p[i].at)) / p[i].bt; 
88
89					// Checking for Highest Response Ratio 
90					if (hrr < temp) { 
91
92						// Storing Response Ratio 
93						hrr = temp; 
94
95						// Storing Location 
96						loc = i; 
97					} 
98				} 
99			} 
100
101			// Updating time value 
102			t += p[loc].bt; 
103
104			// Calculation of waiting time 
105			p[loc].wt = (int)(t - p[loc].at - p[loc].bt); 
106
107			// Calculation of Turn Around Time 
108			p[loc].tt = (int)(t - p[loc].at); 
109
110			// Sum Turn Around Time for average 
111			avgtt += p[loc].tt; 
112
113			// Calculation of Normalized Turn Around Time 
114			p[loc].ntt = ((float)p[loc].tt / p[loc].bt); 
115
116			// Updating Completion Status 
117			p[loc].completed = 1; 
118
119			// Sum Waiting Time for average 
120			avgwt += p[loc].wt; 
121			System.out.println(p[loc].name + "\t" + p[loc].at + "\t" + p[loc].bt 
122							+ "\t" + p[loc].wt + "\t" + p[loc].tt 
123							+ "\t" + p[loc].ntt); 
124		} 
125		System.out.println("Average waiting time: " + (avgwt / n)); 
126		System.out.println("Average Turn Around time:" + (avgtt / n)); 
127	} 
128}

1# Python3 program for Highest Response Ratio
2# Next (HRRN) Scheduling
3
4# Function to sort process by arrival time
5def sortByArrival(at, n):
6	
7	# Selection Sort applied 
8	for i in range(0, n - 1):
9		for j in range(i + 1, n):
10			
11			# Check for lesser arrival time 
12			if at[i] > at[j]:
13				
14				# Swap earlier process to front
15				at[i], at[j] = at[j], at[i]
16
17# Driver code
18if __name__ == '__main__':
19	
20	sum_bt = 0
21	avgwt = 0
22	avgTT = 0
23	n = 5
24	
25	completed =[0] * n
26	waiting_time = [0] * n
27	turnaround_time = [0] * n
28	normalised_TT = [0] * n
29	
30	# Predefined arrival times 
31	arrival_time = [ 0, 2, 4, 6, 8 ]
32	
33	# Predefined burst times 
34	burst_time = [ 3, 6, 4, 5, 2 ]
35	process = []
36	
37	# Initializing the structure variables 
38	for i in range(0, n):
39		process.append(chr(65 + i))
40		sum_bt += burst_time[i]
41		
42	# Sorting the structure by arrival times 
43	sortByArrival(arrival_time, n)
44	print("Name", "Arrival time", 
45		"Burst time", "Waiting Time", 
46		"Turnaround ", "Normalized TT")
47	t = arrival_time[0]
48	
49	while(t < sum_bt):
50		
51		# Set lower limit to response ratio 
52		hrr = -9999
53		temp, loc = 0, 0
54		
55		for i in range(0, n):
56			
57			# Checking if process has arrived 
58			# and is Incomplete 
59			if arrival_time[i] <= t and completed[i] != 1:
60				
61				# Calculating Response Ratio 
62				temp = ((burst_time[i] +
63						(t - arrival_time[i])) /
64						burst_time[i])
65						
66				# Checking for Highest Response Ratio 
67				if hrr < temp:
68					
69					# Storing Response Ratio 
70					hrr = temp
71					
72					# Storing Location 
73					loc = i
74					
75		# Updating time value 
76		t += burst_time[loc]
77		
78		# Calculation of waiting time 
79		waiting_time[loc] = (t - arrival_time[loc] -
80								burst_time[loc])
81		
82		# Calculation of Turn Around Time 
83		turnaround_time[loc] = t - arrival_time[loc]
84		
85		# Sum Turn Around Time for average 
86		avgTT += turnaround_time[loc]
87		
88		# Calculation of Normalized Turn Around Time 
89		normalised_TT = float(turnaround_time[loc] /
90							burst_time[loc])
91		
92		# Updating Completion Status 
93		completed[loc] = 1
94		
95		# Sum Waiting Time for average 
96		avgwt += waiting_time[loc]
97		
98		print(process[loc], "\t\t", arrival_time[loc],
99			"\t\t", burst_time[loc], "\t\t", 
100			waiting_time[loc], "\t\t", 
101			turnaround_time[loc], "\t\t", 
102			"{0:.6f}".format(normalised_TT))
103
104	print("Average waiting time: {0:.6f}".format(avgwt / n))
105	print("Average Turn Around time: {0:.6f}".format(avgTT / n))

1using System;
2using System.Collections;
3using System.Collections.Generic;
4using System.Linq;
5
6// C# equivalent 
7
8// Defining process details 
9class Process { 
10	public char name; 
11	public int at, bt, ct, wt, tt; 
12	public int completed; 
13	public float ntt; 
14} 
15
16class HelloWorld {
17	
18	// Sorting Processes by Arrival Time 
19	public static void sortByArrival(Process[] p, int n) 
20	{ 
21		Process temp; 
22		int i, j; 
23
24		// Selection Sort applied 
25		for (i = 0; i < n - 1; i++) { 
26			for (j = i + 1; j < n; j++) { 
27
28				// Check for lesser arrival time 
29				if (p[i].at > p[j].at) { 
30
31					// Swap earlier process to front 
32					temp = p[i]; 
33					p[i] = p[j]; 
34					p[j] = temp; 
35				} 
36			} 
37		} 
38	} 
39	
40	static void Main() {
41		int i, j, sum_bt = 0; 
42		char c; 
43		float t, avgwt = 0, avgtt = 0; 
44		int n = 5; 
45
46		// predefined arrival times 
47		int[] arriv = { 0, 2, 4, 6, 8 }; 
48
49		// predefined burst times 
50		int[] burst = { 3, 6, 4, 5, 2 }; 
51
52		Process[] p = new Process[n]; 
53
54		// Initializing the structure variables 
55		for (i = 0, c = 'A'; i < n; i++, c++) { 
56			p[i] = new Process(); 
57			p[i].name = c; 
58			p[i].at = arriv[i]; 
59			p[i].bt = burst[i]; 
60
61			// Variable for Completion status 
62			// Pending = 0 
63			// Completed = 1 
64			p[i].completed = 0; 
65
66			// Variable for sum of all Burst Times 
67			sum_bt += p[i].bt; 
68		} 
69
70		// Sorting the structure by arrival times 
71		sortByArrival(p, n); 
72		Console.WriteLine("PN\tAT\tBT\tWT\tTAT\tNTT"); 
73		for (t = p[0].at; t < sum_bt;) { 
74
75			// Set lower limit to response ratio 
76			float hrr = -9999; 
77
78			// Response Ratio Variable 
79			float temp; 
80
81			// Variable to store next process selected 
82			int loc = -1; 
83			for (i = 0; i < n; i++) { 
84
85				// Checking if process has arrived and is 
86				// Incomplete 
87				if (p[i].at <= t && p[i].completed != 1) { 
88
89					// Calculating Response Ratio 
90					temp = (p[i].bt + (t - p[i].at)) / p[i].bt; 
91
92					// Checking for Highest Response Ratio 
93					if (hrr < temp) { 
94
95						// Storing Response Ratio 
96						hrr = temp; 
97
98						// Storing Location 
99						loc = i; 
100					} 
101				} 
102			} 
103
104			// Updating time value 
105			t += p[loc].bt; 
106
107			// Calculation of waiting time 
108			p[loc].wt = (int)(t - p[loc].at - p[loc].bt); 
109
110			// Calculation of Turn Around Time 
111			p[loc].tt = (int)(t - p[loc].at); 
112
113			// Sum Turn Around Time for average 
114			avgtt += p[loc].tt; 
115
116			// Calculation of Normalized Turn Around Time 
117			p[loc].ntt = ((float)p[loc].tt / p[loc].bt); 
118
119			// Updating Completion Status 
120			p[loc].completed = 1; 
121
122			// Sum Waiting Time for average 
123			avgwt += p[loc].wt; 
124			Console.WriteLine(p[loc].name + "\t" + p[loc].at + "\t" + p[loc].bt 
125							+ "\t" + p[loc].wt + "\t" + p[loc].tt 
126							+ "\t" + p[loc].ntt); 
127		} 
128		Console.WriteLine("Average waiting time: " + (avgwt / n)); 
129		Console.WriteLine("Average Turn Around time:" + (avgtt / n)); 
130	}
131}

1// javascript program for Highest Response Ratio Next (HRRN)
2// Scheduling
3
4// Defining process details
5class process {
6	
7	constructor(){
8		this.name = '#';
9		this.at = 0;
10		this.bt = 0;
11		this.ct = 0;
12		this.wt = 0;
13		this.tt = 0;
14		this.completed= 0;
15		this.ntt = 0;
16	}
17
18} 
19let p = new Array(10);
20for(let i = 0; i < 10; i++){
21	p[i] = new process();
22}
23
24let n;
25
26// Sorting Processes by Arrival Time
27function sortByArrival()
28{
29	let temp;
30	let i, j;
31
32	// Selection Sort applied
33	for (i = 0; i < n - 1; i++) {
34		for (j = i + 1; j < n; j++) {
35
36			// Check for lesser arrival time
37			if (p[i].at > p[j].at) {
38
39				// Swap earlier process to front
40				temp = p[i];
41				p[i] = p[j];
42				p[j] = temp;
43			}
44		}
45	}
46}
47
48
49let i, j, sum_bt = 0;
50let c;
51let t, avgwt = 0, avgtt = 0;
52n = 5;
53
54// predefined arrival times
55let arriv = [0, 2, 4, 6, 8];
56
57// predefined burst times
58let burst = [3, 6, 4, 5, 2];
59
60// Initializing the structure variables
61for (i = 0, c = 'A'; i < n; i++) {
62	p[i].name = c;
63	p[i].at = arriv[i];
64	p[i].bt = burst[i];
65
66	// Variable for Completion status
67	// Pending = 0
68	// Completed = 1
69	p[i].completed = 0;
70
71	// Variable for sum of all Burst Times
72	sum_bt += p[i].bt;
73	c = String.fromCharCode(c.charCodeAt(0) + 1);
74}
75
76// Sorting the structure by arrival times
77sortByArrival();
78console.log("PN\tAT\tBT\tWT\tTAT\tNTT");
79
80for (t = p[0].at; t < sum_bt;) {
81
82	// Set lower limit to response ratio
83	let hrr = -9999;
84
85	// Response Ratio Variable
86	let temp;
87
88	// Variable to store next process selected
89	let loc;
90	for (i = 0; i < n; i++) {
91
92		// Checking if process has arrived and is
93		// Incomplete
94		if (p[i].at <= t && p[i].completed != 1) {
95
96			// Calculating Response Ratio
97			temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
98
99			// Checking for Highest Response Ratio
100			if (hrr < temp) {
101
102				// Storing Response Ratio
103				hrr = temp;
104
105				// Storing Location
106				loc = i;
107			}
108		}
109	}
110
111	// Updating time value
112	t += p[loc].bt;
113
114	// Calculation of waiting time
115	p[loc].wt = t - p[loc].at - p[loc].bt;
116
117	// Calculation of Turn Around Time
118	p[loc].tt = t - p[loc].at;
119
120	// Sum Turn Around Time for average
121	avgtt += p[loc].tt;
122
123	// Calculation of Normalized Turn Around Time
124	p[loc].ntt = (p[loc].tt / p[loc].bt);
125
126	// Updating Completion Status
127	p[loc].completed = 1;
128
129	// Sum Waiting Time for average
130	avgwt += p[loc].wt;
131	console.log(p[loc].name + "\t" + p[loc].at + "\t" + p[loc].bt + "\t" + p[loc].wt + "\t" + p[loc].tt + "\t" + p[loc].ntt);
132}
133console.log("\nAverage waiting time: " + avgwt / n);
134console.log("Average Turn Around time:" + avgtt / n);