Solutions to Hw
#2
Q1) A user level
thread library, can communicate between similar ULTs on other processors, while
KLTs of different systems do not communicate.
KLTs cannot take advantage of the other CPUs. So load balancing is not possible and hence no performance
enhancement can be gained despite other free CPUs may be available. Hence ULTs are more useful than KLTs. ULT blocking problem only partially exists,
since threads can be divided into groups which run on different CPUs, in which
case only threads within a single CPU is subject to blocking problem.
Q2a) PCB and
other related data structures need to be maintained as a part of the OS because
of protective reasons. Some of these
reasons are the following.
·
Protection
of 1 user from other user. User should
not be able to modify the PCB in their favor or others detriment. (X could send
wrong signal to Y, decrease Y’s priority etc…).
·
Protection
of the OS from the user. Certain parts
of the operating system need to be protected from the user. OS processes, daemons, device drivers, etc
should be interfered by the users.
·
Protection
against accidental errors. Users
programs could run into infinite loops, accidentally write into restricted
memory area etc…
Q2b) Several protection mechanisms such as reference
monitors (check validity of each memory access), protection domains (kernel
processes, User’s processes), and other constraints (process preemption), etc…
are not needed since the users are totally dependable and co-operative.
However, many operating
system services such as file systems, virtual memory, IO system etc still needs
to exist although users might have unprotected and unrestricted access to
these.
Q3a) Under the
assumptions that there exits a schedule such that all jobs can be completed
within the deadline, the ‘earliest deadline first’ scheduling algorithm
provides an optimal schedule. According
to this scheduling algorithm, of all the processes available for scheduling
presently, one with the earliest deadline is selected to be executed if it can
finish within the deadline.
For example, consider the 4 jobs A with
deadline 10 and running time 4, B with deadline 4 and running time 2, C with
deadline 6 and running time 3, and D with deadline 12 and running time 2. Assume that all the jobs arrive at the
start. In this case, the earliest
deadline scheduling, schedules job B first, C next, A next and D next. As you can clearly see, in this schedule all
processes finish within their deadline.
Consider another example, where
job A has deadline 5, running time 1, job B has deadline 6, running time 2, job
C has deadline 7, running time 3, and job 4 has deadline 4 and running time
4. Clearly, in this case the eaeliest
deadline first algorithm will schedule jobs in the order D, A, B, C, in which
case only 2 job finish within their deadline.
However, scheduling A, B, C, D makes 3 jobs (A, B, C) finish within
their deadline. Thus this algorithm
will not be optimal if we relax the assumption that there is a possible
schedule accommodating all processes.
Q3b) As
illustrated above, we need to specify both the estimated running time, and the
deadline to this algorithm. Knowing the
running time prevents the algorithm from scheduling a job that cannot possibly
terminate within its deadline.
3c) Prove that
earliest deadline scheduling is the most optimal:
Assumptions:
-
All jobs
start at the same time 0.
-
The running
time of each job is known.
-
The
scheduling is non-preemptive scheduling.
-
There is a
schedule such that all processes can finish within the deadline.
-
Let there be n
jobs with running times r1, r2, …, rn and deadline d1, d2, …, dn.
Non-preemptive
Earliest Deadline Scheduling:
At each time t, when a job is
finished, choose a job with the minimum value of d such that t+r < d, i.e.,
choose a job with the minimum deadline that can finish within the deadline.
Lemma: Let S = i1, i2,
…,in be a schedule of jobs. If there is a 1<=j<=n such that dij
> dij+1, then the schedule S’ = i1, i2, …, ij-1, ij+1,
ij, ij+2, …, in has at least the same number of jobs that complete before
deadline.
Proof:
A job ik in schedule S completes within the deadline iff ri1 + ri2 + … +
rik < dik. Thus all jobs i1, i2, …,
ij-1 finish within the deadline in S’ iff they do so in S. The same also holds for jobs ij+2, …,
in. This is because the above sum is
unaltered by interchanging jobs ij and ij+1.
Now consider the job ij and ij+1. Since ij+1 completes within deadline,
r1 + … + rj-1 + rj + rj+1 < dj+1.
Since di > dj, we know r1 + … + rj-1 + rj+1 + rj < dj. Also
trivially, r1 + … + rj-1 + rj+1 < dj+1.
Thus both jobs j and j+1 finish within the deadline in schedule S’. Thus S’ has at least the same number of jobs
finishing within the deadline.
Theorem: EDS is a scheduling algorithm, which
gives optimal scheduling.
Proof:
Any optimal schedule can be converted into an EDS schedule by switching
jobs with smaller deadline with that with greater deadline several number of
times (bubble sort) as shown in lemma 2. Thus EDS must have the same number of
jobs finishing within deadline as the optimal algorithm.
4a) First of
all, note that under pre-emptive scheduling, the non-preemptive strategy of
shortest job first, SJF does not suffice.
For example, consider a two job example where job A has run time 10, starting
at 0 and job B has run time 4 starting at time 2. SJF would give a (A, B) schedule with average completion time =
(10 + 14)/2 = 12. What we need here is
to pre-empt the job A when the job B arrives and start running Job B instead,
in this case, we get a completion time = (14 + 6)/2 = 10. Thus SJF no longer works.
The strategy we need is called
the ‘shortest remaining time first’ algorithm.
According to this algorithm, at the end of every time quantum, the
process, which will finish the earliest, will be chosen from the ready
processes and executed in the next quantum.
From the above example, you can see why this strategy actually minimizes
the average completion time.
4b) In this
case, we need to minimize the average response time. Where the response time is the time between start of job and the
first response of the job to the user (response may be something written on the
screen, some input taken from key board, something written to a file,
etc…). Thus once a process has given a
response, is no longer valuable to keep executing the same process. We need the round robin scheme of
scheduling, where each process executes until it gives a response and then a
new process is scheduled instead.