$24
Lab : Queues Solution
Information
In-class labs are meant to introduce you to a new topic and provide some practice with that new topic.
Topics: Queues, Scheduling schemes
Solo work: Labs should be worked on by each individual student, though asking others for help is permitted. Do not copy code from other sources, and do not give your code to other students. Students who commit or aid in plagiarism will receive a 0% on the assignment and be reported.
Building and running: If you are using Visual Studio, make sure to run with debugging. Do not run without debugging!
Using the debugger will help you nd errors.
To prevent a program exit, use this before return 0;
cin.ignore(); cin.get();
Turn in: Once you're ready to turn in your code, prepare the les by
doing the following: (1) Make a copy of your project folder and name it
LASTNAME-FIRSTNAME-LABNAME. (Example: HOPPER-GRACE-LAB-UNIT-TESTS)
Make sure that all source les (.cpp, .hpp, and/or .h les) and the Makefile les are all present. (3) Remove all Visual Studio les - I only want the source les and Make les. (4) Zip your project folder as LASTNAME-FIRSTNAME-LABNAME.zip
Never turn in Visual Studio les!
Starter les: Download from GitHub.
Grading: Grading is based on completion, if the program functions as intended, and absense of errors. Programs that don't build will receive 0%. Besides build errors, runtime errors, logic errors, memory leaks, and ugly code will reduce your score.
Contents
1.1
About . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.1
Queues . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2
Scheduling . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2
Lab speci cations . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2.1
Queue . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2.2
The Job struct . . . . . . . . . . . . . . . . . . . . . .
7
1.2.3
The Processor . . . . . . . . . . . . . . . . . . . . . . .
8
1.3
Example output . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.3.1
Running the program . . . . . . . . . . . . . . . . . . .
11
1.3.2
result-fcfs.txt . . . . . . . . . . . . . . . . . . . . . . .
12
1.3.3
result-rr.txt . . . . . . . . . . . . . . . . . . . . . . . .
14
1.1 About
1.1.1 Queues
A queue is a restricted-access data type that is \FIFO" (First-in, First-out). Like with a line at Micro Center, new nodes in the queue enter from the back of the \line", and the node at the front of the queue will leave it next once Pop() is called.
front
0 1 2
back
1. Empty queue
front
0 1 2
A
back
2. Pushed \A" into queue
front
0 1 2
B
back
3. Pushed \B" into queue
front
0 1 2
B
back
4. Pop removes \A"
1.1.2 Scheduling
First come, rst served: The rst processors were simple and only al-lowed one program to run at a time, and everything else had to wait for it to complete before getting a chance to run. This can be considered \First Come, First Served" scheduling. This is also known as FIFO, since it is basically a vanilla queue.
Round Robin: Another way to handle scheduling, so that multiple pro-cesses can run is with \Round Robin". In this manner, you choose some timeout. Once the timer hits the value you selected, it moves the item cur-rently being worked on to the back of the processing queue and spends time on the next thing.
Let's say that we have a job queue, and ever 5 time units (you can think of seconds, but it would be much, much faster than that)
A job queue, with interval = 5 units
front
0
1
2
back
JobA
JobB
JobC
15 units
17 units
11 units
Time 0...1...2...3...4...
The processor would work for 5 units of time, then move JobA to the back of the queue. JobA's remaining time is now 10 units.
front
0
1
2
back
JobB
JobC
JobA
17 units
11 units
10 units
Time 5...6...7...8...9...
The process continues...
front
0
1
2
C
A
B
11
10
12
Time 10...11...12...13...14...
front
0
1
2
B
C
A
12
6
5
Time 20...21...22...23...24...
front
0
1
2
A
B
C
5
7
1
Time 30...31...32...33...34...
back
back
back
front
0
1
2
A
B
C
10
12
6
Time 15...16...17...18...19...
front
0
1
2
C
A
B
6
5
7
Time 25...26...27...28...29...
front
0
1
2
B
C
7
1
Time 35...36...37...38...39...
back
back
back
Once a process is done being processed, it is removed from the queue, and processing can continue with the remaining items.
front
0 1 2
B
12
back
front
0
1
2
B
2
back
Time 40...41...42...43...44...
Time 45...46...47...48...49...
More info: You can learn more about scheduling algorithms at Wikipedia:
https://en.wikipedia.org/wiki/Scheduling (computing)
1.2 Lab specifications
In this lab, you will have a list of Jobs to process. You will have a FCFS (First Come, First Served) Queue and a RR (Round Robin) Queue. Each of these will go through the job and \process" it.
1.2.1 Queue
Here we are going to implement the Queue using the LinkedList class in-cluded. Instead of doing it as inheritance (is-a relationship), we are going to use composition (has-a relationship).
First, give the Queue a private templated LinkedList item:
LinkedList<T m list;
Then each of the Queue's functions should do the following:
Push
Call m
list.PushBack( data );
Pop
Call m
list.PopFront();
Front
return m
list.GetFirst();
Size
return m
list.Size();
1.2.2 The Job struct
The Job struct looks like this:
struct Job
2
{
3
Job () ;
void Work ( JobType type ) ;
5
void
S e t F i n i s h T i m e ( int time , JobType type ) ;
6
7
int
id ;
8
9
int
f c f s _ t i m e R e m a i n i n g ;
int f c f s _ f i n i s h T i m e ;
11
bool fc fs _d on e ;
12
13
int
r r _ t i m e R e m a i n i n g ;
14
int
r r _ f i n i s h T i m e ;
bool rr_done ;
16
int r r _ t i m e s I n t e r r u p t e d ;
17
};
The Work function just counts down on the timeRemaining (either the fcfs or
version, depending on what you pass in.) For example, you would process the next item in the FCFS queue like this:
jobQueue.Front()-Work( FCFS );
Once the time remaining hits 0, the Job will have its done boolean set to true, which can be used from the processor side to decide to remove it from the job queue.
jobQueue.Front()-SetFinishTime( cycles, FCFS );
jobQueue.Pop();
For the Round Robin processor, any time the job runs out of time and focus is given to a new job, you'll also want to keep track of how many times the job gets interrupted.
jobQueue.Front()-rr timesInterrupted += 1;
1.2.3 The Processor
The processor is just a wrapper for two functions...
class Pr oc es so r
2
{
3
public :
4
5
void F i r s t C o m e F i r s t S e r v e (
vector < Job & allJobs ,
6
Queue < Job * &
jobQueue ,
const string & logFile ) ;
7
8
void R o u n d R o b i n (
vector < Job & allJobs ,
9
Queue < Job * &
jobQueue , int timePerProcess ,
10
const string & logFile ) ;
11
};
You will implement these two functions. The parameters are...
vector<Job& allJobs The list of all jobs being used; can be used within the function to display a list of all jobs and their info.
Queue<Job*& jobQueue The queue of jobs waiting to be pro-cessed. You will be working with this structure, calling the Work() function on the front-most Job to process.
int timePerProcess (Round Robin) This is the time increment for the Round Robin scheduler. After n units of time have passed, the current item is put at the back of the queue so a di erent job can have a chance to process.
const string& logFile A string lename where the output le should be written to. You can display output with cout, but you should also be writing a report to an output text le.
Opening and writing to an output le
ofstream output ( logFile ) ;
2
output
<< " First Come First Served ( FCFS ) " << endl ;
3
// ...
4
output . close () ;
Processor::FirstComeFirstServe
While the jobQueue is not empty...
Process the front-most item.
If the front-most item's done variable (for this type - fcfs done or
done), then...
{ Set the front-most item's nished time via the SetFinishTime function.
{ Pop the item o the queue. Increment the cycle counter.
You will want to keep track of cycles, as a simple int counter. Each cycle is a unit of time. Increment the cycle counter after each iteration of the loop. Also display the following information to the output text le (not the cout): The current cycle, The current job's ID, and the amount of time the job has remaining.
Once the queue is empty, you will also display some result statistics about the processing. You can still access all the nished jobs via the allJobs vector. Display each job's ID and time to complete the job. As a summary, display the average time to complete all the jobs, and the total processing time.
See the Example Output for more.
Processor::RoundRobin
For this one, you'll keep a separate cycles counter, as well as a timer, which will keep track of the round time.
While the jobQueue is not empty...
If the timer has hit the timePerProcess value...
{ Increment the front-most job's r timesInterrupted by 1. { Push the front-most job to the back of the queue.
{ Pop the job o the front of the queue. { Reset your timer to 0.
Process the front-most item.
If the front-most item's done variable (for this type - fcfs done or
done), then...
{ Set the front-most item's nished time via the SetFinishTime function.
{ Pop the item o the queue.
Increment the cycle counter and the timer counter.
Once again you'll need to write the current cycle, the job's ID, the remaining time, and the amount of times the job has been interrupted so far to the text le.
Once the job queue is empty, you will output a summary. You can still access all the nished jobs via the allJobs vector. Display each job's ID, time to complete the job, and amount of times it was interrupted. As a sum-mary, display the average time to complete all the jobs, the total processing time, and the round robin interval.
1.3 Example output
1.3.1 Running the program
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
| Job Pr oc es so r |
- - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
How many jobs ? ( More than 10)
20
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Round Robin time interval ?
5
Creating jobs ...
Job 0 , fcfs : 122 , rr : 122
Job 1 , fcfs : 93 , rr : 93
Job 2 , fcfs : 135 , rr : 135
( etc )
Job 18 , fcfs : 113 , rr : 113
Job 19 , fcfs : 102 , rr : 102
Filling queues ...
P r o c e s s i n g with FCFS ...
P r o c e s s i n g with RR ...
DONE
1.3.2 result-fcfs.txt
First Come
First
Served ( FCFS )
P r o c e s s i n g job #0...
CYCLE
0
RE MA I NI NG :
94
...
CYCLE
1
RE MA I NI NG :
93
...
CYCLE
2
RE MA I NI NG :
92
...
CYCLE
3
RE MA I NI NG :
91
...
CYCLE
4
RE MA I NI NG :
90
...
CYCLE
5
RE MA I NI NG :
89
...
CYCLE
6
RE MA I NI NG :
88
...
CYCLE
7
RE MA I NI NG :
87
...
CYCLE
8
RE MA I NI NG :
86
...
CYCLE
9
RE MA I NI NG :
85
...
CYCLE
10
RE MA I NI NG :
84
...
CYCLE
11
RE MA I NI NG :
83
...
CYCLE
12
RE MA I NI NG :
82
...
CYCLE
13
RE MA I NI NG :
81
...
CYCLE
14
RE MA I NI NG :
80
...
CYCLE
15
RE MA I NI NG :
79
...
CYCLE
16
RE MA I NI NG :
78
...
CYCLE
17
RE MA I NI NG :
77
...
CYCLE
18
RE MA I NI NG :
76
...
( etc )
CYCLE
93
RE MA I NI NG :
1
...
CYCLE
94
RE MA I NI NG :
0
...
Done
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
P r o c e s s i n g job #1...
CYCLE
95
RE MA I NI NG :
101 ...
CYCLE
96
RE MA I NI NG :
100 ...
CYCLE
97
RE MA I NI NG :
99
...
CYCLE
98
RE MA I NI NG :
98
...
CYCLE
99
RE MA I NI NG :
97
...
CYCLE
100
RE M AI NI NG :
96
...
CYCLE
101
RE M AI NI NG :
95
...
CYCLE
102
RE M AI NI NG :
94
...
CYCLE
103
RE M AI NI NG :
93
...
( etc )
CYCLE
2026
RE MA I NI NG :
5
...
CYCLE
2027
RE MA I NI NG :
4
...
CYCLE
2028
RE MA I NI NG :
3
...
CYCLE
2029
RE MA I NI NG :
2
...
CYCLE
2030
RE MA I NI NG :
1
...
CYCLE
2031
RE MA I NI NG :
0
...
Done
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
First come , first serve results :
JOB ID
TIME TO COMPLETE
0
94
1
196
2
308
3
400
4
500
569
6
623
7
677
8
824
9
889
10
980
11
1088
12
1213
13
1287
14
1421
15
1524
16
1671
17
1756
18
1899
19
2031
Total time : . . . . . . . . . . .
. . 2032
( Time for all jobs to complete p r o c e s s i n g )
Average
time : . . . . . . . . .
. . 997.5
( The average time to complete , i nc lu di ng the wait time
while
items
are
ahead of it in
the queue .)
1.3.3 result-rr.txt
Round Robin ( RR )
P r o c e s s i n g job #0...
CYCLE
0
RE MA I NI NG :
94
...
CYCLE
1
RE MA I NI NG :
93
...
CYCLE
2
RE MA I NI NG :
92
...
CYCLE
3
RE MA I NI NG :
91
...
CYCLE
4
RE MA I NI NG :
90
...
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - P r o c e s s i n g job #1...
CYCLE
5
RE MA I NI NG :
101 ...
CYCLE
6
RE MA I NI NG :
100 ...
CYCLE
7
RE MA I NI NG :
99
...
CYCLE
8
RE MA I NI NG :
98
...
CYCLE
9
RE MA I NI NG :
97
...
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - P r o c e s s i n g job #2...
CYCLE
10
RE MA I NI NG :
111 ...
CYCLE
11
RE MA I NI NG :
110 ...
CYCLE
12
RE MA I NI NG :
109 ...
CYCLE
13
RE MA I NI NG :
108 ...
CYCLE
14
RE MA I NI NG :
107 ...
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - P r o c e s s i n g job #3...
CYCLE
15
RE MA I NI NG :
91
...
CYCLE
16
RE MA I NI NG :
90
...
CYCLE
17
RE MA I NI NG :
89
...
CYCLE
18
RE MA I NI NG :
88
...
CYCLE
19
RE MA I NI NG :
87
...
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
P r o c e s s i n g job #4...
CYCLE
20
RE MA I NI NG :
99
...
CYCLE
21
RE MA I NI NG :
98
...
CYCLE
22
RE MA I NI NG :
97
...
CYCLE
23
RE MA I NI NG :
96
...
CYCLE
24
RE MA I NI NG :
95
...
( etc )
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
P r o c e s s i n g job #8...
CYCLE
2025
RE MA I NI NG :
6
...
CYCLE
2026
RE MA I NI NG :
5
...
CYCLE
2027
RE MA I NI NG :
4
...
CYCLE
2028
RE MA I NI NG :
3
...
CS 250,
Lab : Queues
CYCLE
2029
RE MA I NI NG :
2
...
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
P r o c e s s i n g job #8...
CYCLE
2030
RE MA I NI NG :
1
...
CYCLE
2031
RE MA I NI NG :
0
...
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Round Robin results :
JOB ID
TIME
TO
COMPLETE
TIMES I N T E R R U P T E D
0
1644
18
1
1801
21
2
1838
22
3
1651
18
4
1766
20
5
1298
13
6
1033
10
7
1127
11
8
2031
33
9
1224
12
10
1720
19
11
1813
21
12
1933
25
13
1398
14
14
1996
28
15
1787
20
16
2021
30
17
1564
16
18
2017
29
19
1971
26
Total time : . . . . . . . . . . . . . 2032
( Time
for
all
jobs to
complete p r o c e s s i n g )
Average time : . . . . . . . . . . . 1681.65
( The average time to complete , i nc lu di ng the wait time
while items
are ahead of it in the queue .)
Round robin interval : ... 5
( Every n units of time , move the current item being
pr o ce ss ed
to the back of the queue and start working on the next
item )
