n the early days of computers, operating systems serviced users by scheduling jobs in the order in which they arrived (s
Posted: Thu May 26, 2022 9:34 am
n the early days of computers, operating systems serviced users
by scheduling jobs in the
order in which they arrived (started). This is a First-Come
First-Serve (FCFS) algorithm.
The downside of First-Come First-Serve (FCFS) is that you are at
the mercy of the order
in which jobs arrive. A large job at the beginning has everyone
waiting and becoming
irritated, particularly jobs that are important. A solution to this
is to try and help people
with important jobs get in and out quickly. This is called Priority
Scheduling. In this
algorithm as jobs arrive they are added to the run list based on
the priority of the job –
highest priority first! When the priority of multiple jobs are the
same then the arrival time
decides who goes first.
To properly implement Priority you also need pre-emption – the
concept of periodically
stopping a job to take away the CPU and decide who is the next
eligible process to run.
This is needed to prevent large jobs that acquire the CPU and start
computing to only hold
the CPU while new higher priority jobs arrive and have to wait. To
implement pre-emption,
you only execute a job for 1 period and then you add it back into
the run list.
For example if we have 1 CPU:
User Process Arrival Duration Priority
Jim A 2 5 5
Mary B 2 3 2
Sue D 5 5 6
Mary C 6 2 4
This would result in:
Time Job
2 B
3 B
4 B
5 A
6 C
7 C
8 A
9 A
10 A
11 A2
12 D
13 D
14 D
15 D
16 D
17 IDLE
Summary
Jim 12
Mary 8
Sue 17
Due to laws of physics and how fast electricity can stably travel
on a wire, CPUs have been
limited in how fast they can operate. To try and provide better
performance, manufacturers
are resorting to building CPUs today that have multiple processing
cores. For example,
Dual-core processors have 2 CPUs and Quad-core has 4 CPUs. When
considering
scheduling we need to consider how many processors we have and
which jobs the n
processors are executing at once. To make your program flexible,
provide n as a command
line argument to the program. The input/output formats are as
described in the examples.
The output header now has a column for each CPU. At any given time
you have to list what
processes are operating on each CPU (tab delimited). For example
with 3 CPUs:
Time CPU1 CPU2 CPU3
2 A B -
3 A B -
4 A B -
5 A D -
6 A C D
7 D C -
8 D - -
9 D - -
This example shows jobs A, C and D are running on CPUs 1, 2 and 3
respectively at time
6. At time 7, D and C continue to run on CPUs 1 and 2 respectively,
but CPU 3 is now idle.
Note: Be careful! You cannot start a job until it has arrived.
Also, CPUs are symmetric –
meaning it does not matter which job is on which CPU at a given
time! It is correct if at a
given time you are executing the right “set” of jobs. So, at time 6
we can have any ordering
of jobs A, D and C on CPUs 1, 2 and 3.
Write a C program that will read in job requests and print out the
corresponding job
schedule according to a Priority algorithm as above. The input
format is each line entry
contains a job separated by a tab. The first line of input is
ignored as the header. The output
format is two tables. First table is the running time and the job
currently executing (tab
separated). The second table is a summary with the user name (in
the order in which jobs
arrive) and the time when their last job is completed.
by scheduling jobs in the
order in which they arrived (started). This is a First-Come
First-Serve (FCFS) algorithm.
The downside of First-Come First-Serve (FCFS) is that you are at
the mercy of the order
in which jobs arrive. A large job at the beginning has everyone
waiting and becoming
irritated, particularly jobs that are important. A solution to this
is to try and help people
with important jobs get in and out quickly. This is called Priority
Scheduling. In this
algorithm as jobs arrive they are added to the run list based on
the priority of the job –
highest priority first! When the priority of multiple jobs are the
same then the arrival time
decides who goes first.
To properly implement Priority you also need pre-emption – the
concept of periodically
stopping a job to take away the CPU and decide who is the next
eligible process to run.
This is needed to prevent large jobs that acquire the CPU and start
computing to only hold
the CPU while new higher priority jobs arrive and have to wait. To
implement pre-emption,
you only execute a job for 1 period and then you add it back into
the run list.
For example if we have 1 CPU:
User Process Arrival Duration Priority
Jim A 2 5 5
Mary B 2 3 2
Sue D 5 5 6
Mary C 6 2 4
This would result in:
Time Job
2 B
3 B
4 B
5 A
6 C
7 C
8 A
9 A
10 A
11 A2
12 D
13 D
14 D
15 D
16 D
17 IDLE
Summary
Jim 12
Mary 8
Sue 17
Due to laws of physics and how fast electricity can stably travel
on a wire, CPUs have been
limited in how fast they can operate. To try and provide better
performance, manufacturers
are resorting to building CPUs today that have multiple processing
cores. For example,
Dual-core processors have 2 CPUs and Quad-core has 4 CPUs. When
considering
scheduling we need to consider how many processors we have and
which jobs the n
processors are executing at once. To make your program flexible,
provide n as a command
line argument to the program. The input/output formats are as
described in the examples.
The output header now has a column for each CPU. At any given time
you have to list what
processes are operating on each CPU (tab delimited). For example
with 3 CPUs:
Time CPU1 CPU2 CPU3
2 A B -
3 A B -
4 A B -
5 A D -
6 A C D
7 D C -
8 D - -
9 D - -
This example shows jobs A, C and D are running on CPUs 1, 2 and 3
respectively at time
6. At time 7, D and C continue to run on CPUs 1 and 2 respectively,
but CPU 3 is now idle.
Note: Be careful! You cannot start a job until it has arrived.
Also, CPUs are symmetric –
meaning it does not matter which job is on which CPU at a given
time! It is correct if at a
given time you are executing the right “set” of jobs. So, at time 6
we can have any ordering
of jobs A, D and C on CPUs 1, 2 and 3.
Write a C program that will read in job requests and print out the
corresponding job
schedule according to a Priority algorithm as above. The input
format is each line entry
contains a job separated by a tab. The first line of input is
ignored as the header. The output
format is two tables. First table is the running time and the job
currently executing (tab
separated). The second table is a summary with the user name (in
the order in which jobs
arrive) and the time when their last job is completed.