Starting from:
$25
CS526 Homework Assignment 4 Solved
The goal of this assignment is to give students an opportunity to implement an application that uses a priority queue. The application to be implemented is a simulation of a process scheduler of a computer system. This simulated scheduler is a small, simplified version, which reflects some of the basic operations of a typical scheduler.
Name the file with the main method as ProcessScheduling.java.
The following describes the scheduling system that is simulated.
Processes arrive at a computer system and the computer system executes the processes one at a time based on a priority criterion. Each process has a process id, priority, arrival time, and duration. The duration of a process is the amount of time it takes to completely execute the process. The system keeps a priority queue to keep arriving processes and prioritize the execution of processes. When a process arrives, it is inserted into the priority queue. Then, each time the system is ready to execute a process, the system removes a process with the smallest priority from the priority queue and executes it for the duration of the process.
For the purpose of this simulation, we assume the followings:
We use the priority queue implemented in the java. This class implements a priority queue that uses a heap data structure.
Each entry in the priority queue keeps (K, V) pair, which represents a process.K is the priority of the process and it is of Integer type. The value of priority is between 1 and 10, inclusively. A process with a smaller priority is executed before a process with a larger priority.
V is the reference to the process.
Each process must have, at the minimum, the following attributes:
pr: Integer // priority of the process
id: integer // process id
arrivalTime: integer // the time when the process arrives at the system duration: integer // execution of the process takes this amount of time
The simulation program uses a logical time to keep track of the simulation process and the same logical time is used to represent the arrivalTime and duration. The simulation goes through a series of iterations and each iteration represents the passage of one logical time unit (in what follows we will use time unit to refer to logical time unit). At the beginning, the current time is set to time 0. Each iteration implements what occurs during one time unit and, at the end of each iteration, the current time is incremented.
The following describes the simulation program:
All processes are stored in a certain data structure D, which is supposed to be external to the computer system.
In each iteration, the following occurs:
We compare the current time with the arrival time of a process with the earliest arrival time in D. If the arrival time of that process is equal to or smaller than the current time, we remove the process from D and insert it into the priority queue Q (this represents the arrival of a process at the system).
If no process is being executed at this time and there is at least one process in Q, then a process with the smallest priority is removed from Q and executed.
Note: When there is more than one process with the same smallest priority, it would be reasonable that the one with the earliest arrivalTime is removed from Q and executed. However, for this assignment, you don’t need to implement this and you just need to remove an entry with the smallest priority as determined by the code within java.
The current time is increased by one time unit.
The above is repeated until D is empty. At this time, all processes have arrived at the system. Some of them may have been completed and removed from Q and some may still wait in Q.
If there are any remaining processes in Q, these processes are removed and executed one at a time. Again, a process with the smallest priority is removed and executed first.
A pseudocode of the simulation is given below. You must consider this pseudocode as a highlevel description and you need to figure out details and convert the pseudocode to a Java program. In the pseudocode, Q is a priority queue, which stores <priority, process pairs. There is a Boolean variable running in the pseudocode. It is used to indicate whether the system is currently executing a process or not. It is true if the system is currently executing a process and false otherwise.
Read all processes from the input file and store them in an appropriate data structure, D currentTime = 0 running = false
create an empty priority queue Q
While D is not empty // while loop runs once for every time unit until D is empty
Get (don’t remove) a process p from D that has the earliest arrival time
If the arrival time of p <= currentTime Remove p from D and insert it into Q
If Q is not empty and the flag running is false
Remove a process with the smallest priority from Q
Set a flag running to true currentTime = currentTime + 1 If currently running process has finished
Set a flag running to false
End of While loop
// At this time all processes in D have been moved to Q.
While there is a process waiting in Q
Remove a process with the smallest priority from Q and execute it
As mentioned in the first line of the pseudocode, an input file stores information about all processes. The name of the input file is process_scheduling_in.txt. A sample input file is shown below (this sample input is posted on Blackboard):
10 25 10
3 15 17
1 17 26
9 17 30
10 9 40
6 14 47
7 18 52
5 18 70
2 16 93
8 20 125
Each line in the input file represents a process and it has four integers separated by a space(s). The four integers are the process id, priority, duration, and arrival time, respectively, of a process. Your program must read all processes from the input file and store them in an appropriate data structure. You can use any data structure that you think is appropriate.
However, for the priority queue, you must use the priority queue implemented in HeapPriorityQueue.java. The HeapPriorityQueue class inherits from or implements a few superclasses and interfaces. You may want to study some or all of these superclasses and interfaces to better understand the HeapPriorityQueue class. On Blackboard, I will post only the HeapPriorityQueue.java file. You can obtain other files from the textbook’s source code collection.
While your program is performing the simulation, whenever a process is removed from the priority queue (to be executed), your program must display information about the removed process. Your program also needs to print other information as shown in the sample output below. After your program finishes the simulation of the execution of all processes in the input file, it must display the average waiting time of all processes. A sample output is shown below, which is the expected output for the above sample input.
Id = 1, priority = 10, duration = 25, arrival time = 10
Id = 2, priority = 3, duration = 15, arrival time = 17
Id = 3, priority = 1, duration = 17, arrival time = 26
Id = 4, priority = 9, duration = 17, arrival time = 30 Id = 5, priority = 10, duration = 9, arrival time = 40 Id = 6, priority = 6, duration = 14, arrival time = 47
Id = 7, priority = 7, duration = 18, arrival time = 52
Id = 8, priority = 5, duration = 18, arrival time = 70
Id = 9, priority = 2, duration = 16, arrival time = 93
Id = 10, priority = 8, duration = 20, arrival time = 125
Process removed from queue is: id = 1, at time 10, wait time = 0 Total wait time = 0.0
Process id = 1
Priority = 10
Arrival = 10
Duration = 25
Process 1 finished at time 35
Process removed from queue is: id = 3, at time 35, wait time = 9 Total wait time = 9.0
Process id = 3
Priority = 1
Arrival = 26
Duration = 17
Process 3 finished at time 52
Process removed from queue is: id = 2, at time 52, wait time = 35 Total wait time = 44.0 Process id = 2
Priority = 3
Arrival = 17
Duration = 15
Process 2 finished at time 67
Process removed from queue is: id = 6, at time 67, wait time = 20 Total wait time = 64.0 Process id = 6
Priority = 6
Arrival = 47
Duration = 14
Process 6 finished at time 81
Process removed from queue is: id = 8, at time 81, wait time = 11 Total wait time = 75.0 Process id = 8
Priority = 5
Arrival = 70
Duration = 18
Process 8 finished at time 99
Process removed from queue is: id = 9, at time 99, wait time = 6 Total wait time = 81.0
Process id = 9
Priority = 2
Arrival = 93
Duration = 16
Process 9 finished at time 115
Process removed from queue is: id = 7, at time 115, wait time = 63 Total wait time = 144.0 Process id = 7
Priority = 7
Arrival = 52
Duration = 18
D becomes empty at time 125
Process 7 finished at time 133
Process removed from queue is: id = 10, at time 133, wait time = 8 Total wait time = 152.0 Process id = 10
Priority = 8
Arrival = 125
Duration = 20
Process 10 finished at time 153
Process removed from queue is: id = 4, at time 153, wait time = 123 Total wait time = 275.0 Process id = 4
Priority = 9
Arrival = 30
Duration = 17
Process 4 finished at time 170
Process removed from queue is: id = 5, at time 170, wait time = 130 Total wait time = 405.0 Process id = 5
Priority = 10
Arrival = 40
Duration = 9
Process 5 finished at time 179
Total wait time = 405.0
Average wait time = 40.5
Your program must write the output to an output file named process_scheduling_out.txt.
Name the file with the main method as ProcessScheduling.java.
The following describes the scheduling system that is simulated.
Processes arrive at a computer system and the computer system executes the processes one at a time based on a priority criterion. Each process has a process id, priority, arrival time, and duration. The duration of a process is the amount of time it takes to completely execute the process. The system keeps a priority queue to keep arriving processes and prioritize the execution of processes. When a process arrives, it is inserted into the priority queue. Then, each time the system is ready to execute a process, the system removes a process with the smallest priority from the priority queue and executes it for the duration of the process.
For the purpose of this simulation, we assume the followings:
We use the priority queue implemented in the java. This class implements a priority queue that uses a heap data structure.
Each entry in the priority queue keeps (K, V) pair, which represents a process.K is the priority of the process and it is of Integer type. The value of priority is between 1 and 10, inclusively. A process with a smaller priority is executed before a process with a larger priority.
V is the reference to the process.
Each process must have, at the minimum, the following attributes:
pr: Integer // priority of the process
id: integer // process id
arrivalTime: integer // the time when the process arrives at the system duration: integer // execution of the process takes this amount of time
The simulation program uses a logical time to keep track of the simulation process and the same logical time is used to represent the arrivalTime and duration. The simulation goes through a series of iterations and each iteration represents the passage of one logical time unit (in what follows we will use time unit to refer to logical time unit). At the beginning, the current time is set to time 0. Each iteration implements what occurs during one time unit and, at the end of each iteration, the current time is incremented.
The following describes the simulation program:
All processes are stored in a certain data structure D, which is supposed to be external to the computer system.
In each iteration, the following occurs:
We compare the current time with the arrival time of a process with the earliest arrival time in D. If the arrival time of that process is equal to or smaller than the current time, we remove the process from D and insert it into the priority queue Q (this represents the arrival of a process at the system).
If no process is being executed at this time and there is at least one process in Q, then a process with the smallest priority is removed from Q and executed.
Note: When there is more than one process with the same smallest priority, it would be reasonable that the one with the earliest arrivalTime is removed from Q and executed. However, for this assignment, you don’t need to implement this and you just need to remove an entry with the smallest priority as determined by the code within java.
The current time is increased by one time unit.
The above is repeated until D is empty. At this time, all processes have arrived at the system. Some of them may have been completed and removed from Q and some may still wait in Q.
If there are any remaining processes in Q, these processes are removed and executed one at a time. Again, a process with the smallest priority is removed and executed first.
A pseudocode of the simulation is given below. You must consider this pseudocode as a highlevel description and you need to figure out details and convert the pseudocode to a Java program. In the pseudocode, Q is a priority queue, which stores <priority, process pairs. There is a Boolean variable running in the pseudocode. It is used to indicate whether the system is currently executing a process or not. It is true if the system is currently executing a process and false otherwise.
Read all processes from the input file and store them in an appropriate data structure, D currentTime = 0 running = false
create an empty priority queue Q
While D is not empty // while loop runs once for every time unit until D is empty
Get (don’t remove) a process p from D that has the earliest arrival time
If the arrival time of p <= currentTime Remove p from D and insert it into Q
If Q is not empty and the flag running is false
Remove a process with the smallest priority from Q
Set a flag running to true currentTime = currentTime + 1 If currently running process has finished
Set a flag running to false
End of While loop
// At this time all processes in D have been moved to Q.
While there is a process waiting in Q
Remove a process with the smallest priority from Q and execute it
As mentioned in the first line of the pseudocode, an input file stores information about all processes. The name of the input file is process_scheduling_in.txt. A sample input file is shown below (this sample input is posted on Blackboard):
10 25 10
3 15 17
1 17 26
9 17 30
10 9 40
6 14 47
7 18 52
5 18 70
2 16 93
8 20 125
Each line in the input file represents a process and it has four integers separated by a space(s). The four integers are the process id, priority, duration, and arrival time, respectively, of a process. Your program must read all processes from the input file and store them in an appropriate data structure. You can use any data structure that you think is appropriate.
However, for the priority queue, you must use the priority queue implemented in HeapPriorityQueue.java. The HeapPriorityQueue class inherits from or implements a few superclasses and interfaces. You may want to study some or all of these superclasses and interfaces to better understand the HeapPriorityQueue class. On Blackboard, I will post only the HeapPriorityQueue.java file. You can obtain other files from the textbook’s source code collection.
While your program is performing the simulation, whenever a process is removed from the priority queue (to be executed), your program must display information about the removed process. Your program also needs to print other information as shown in the sample output below. After your program finishes the simulation of the execution of all processes in the input file, it must display the average waiting time of all processes. A sample output is shown below, which is the expected output for the above sample input.
Id = 1, priority = 10, duration = 25, arrival time = 10
Id = 2, priority = 3, duration = 15, arrival time = 17
Id = 3, priority = 1, duration = 17, arrival time = 26
Id = 4, priority = 9, duration = 17, arrival time = 30 Id = 5, priority = 10, duration = 9, arrival time = 40 Id = 6, priority = 6, duration = 14, arrival time = 47
Id = 7, priority = 7, duration = 18, arrival time = 52
Id = 8, priority = 5, duration = 18, arrival time = 70
Id = 9, priority = 2, duration = 16, arrival time = 93
Id = 10, priority = 8, duration = 20, arrival time = 125
Process removed from queue is: id = 1, at time 10, wait time = 0 Total wait time = 0.0
Process id = 1
Priority = 10
Arrival = 10
Duration = 25
Process 1 finished at time 35
Process removed from queue is: id = 3, at time 35, wait time = 9 Total wait time = 9.0
Process id = 3
Priority = 1
Arrival = 26
Duration = 17
Process 3 finished at time 52
Process removed from queue is: id = 2, at time 52, wait time = 35 Total wait time = 44.0 Process id = 2
Priority = 3
Arrival = 17
Duration = 15
Process 2 finished at time 67
Process removed from queue is: id = 6, at time 67, wait time = 20 Total wait time = 64.0 Process id = 6
Priority = 6
Arrival = 47
Duration = 14
Process 6 finished at time 81
Process removed from queue is: id = 8, at time 81, wait time = 11 Total wait time = 75.0 Process id = 8
Priority = 5
Arrival = 70
Duration = 18
Process 8 finished at time 99
Process removed from queue is: id = 9, at time 99, wait time = 6 Total wait time = 81.0
Process id = 9
Priority = 2
Arrival = 93
Duration = 16
Process 9 finished at time 115
Process removed from queue is: id = 7, at time 115, wait time = 63 Total wait time = 144.0 Process id = 7
Priority = 7
Arrival = 52
Duration = 18
D becomes empty at time 125
Process 7 finished at time 133
Process removed from queue is: id = 10, at time 133, wait time = 8 Total wait time = 152.0 Process id = 10
Priority = 8
Arrival = 125
Duration = 20
Process 10 finished at time 153
Process removed from queue is: id = 4, at time 153, wait time = 123 Total wait time = 275.0 Process id = 4
Priority = 9
Arrival = 30
Duration = 17
Process 4 finished at time 170
Process removed from queue is: id = 5, at time 170, wait time = 130 Total wait time = 405.0 Process id = 5
Priority = 10
Arrival = 40
Duration = 9
Process 5 finished at time 179
Total wait time = 405.0
Average wait time = 40.5
Your program must write the output to an output file named process_scheduling_out.txt.
1 file (21.3KB)
