📄 macs 442 homework 1 solutions.htm
字号:
<TBODY>
<TR>
<TD align=middle><I>Job Number</I></TD>
<TD align=middle><I>Arrival Time</I></TD>
<TD align=middle><I>Service Time</I></TD></TR>
<TR>
<TD align=middle>1</TD>
<TD align=middle>0</TD>
<TD align=middle>4</TD></TR>
<TR>
<TD align=middle>2</TD>
<TD align=middle>1 </TD>
<TD align=middle>8</TD></TR>
<TR>
<TD align=middle>3</TD>
<TD align=middle>3 </TD>
<TD align=middle>2</TD></TR>
<TR>
<TD align=middle>4</TD>
<TD align=middle>10 </TD>
<TD align=middle>6</TD></TR>
<TR>
<TD align=middle>5</TD>
<TD align=middle>12 </TD>
<TD align=middle>5</TD></TR></TBODY></TABLE></DIV>Assume the overhead of
context switching is one time unit. For each of the following scheduling
methods, give (i) a timing chart to illustrate the execution sequence, (ii)
the average job turnaround time, (iii) the normalized turnaround time for
each job, and (iv) the CPU efficiency.
<OL type=a>
<LI>FCFS
<LI>SPN
<LI>SRTN
<LI>RR, quantum = 3
<LI>Multilevel Feedback Queue with queues numbered 1-10, quantum =
2<SUP>i</SUP>, where i is the queue level number and processes are
initially placed in the first queue (i.e., level 1). In this scheduling
policy, each process executes at a particular level for one quantum and
then moves down a level; processes never move up a level. </LI></OL>
<P>ANSWERS: <BR>The following figure shows the timing charts for each
scheduling method.
<P><IMG height=737 src="MACS 442 Homework 1 Solutions.files/hw1b.jpg"
width=942>
<P>a. FCFS <BR> turnaround = [
(5-0) + (14-1) + (17-3) + (24-10) + (30-12) ] / 5 = 64 / 5 = 12.8
<BR> normalized turnaround:
<BR>
P1: 5 / 4 = 1.25
<BR>
P2: 13 / 8 = 1.625
<BR>
P3: 14 / 2 =
7
<--- FCFS can be unfair to short processes
<BR>
P4: 14 / 6 = 2.333
<BR>
P5: 18 / 5 = 3.6
<BR> CPU efficiency = 25 / 30 =
83.33%
<P>b. SPN <BR> turnaround = [
(5-0) + (17-1) + (8-3) + (30-10) + (23-12) ] / 5 = 57 / 5 = 11.4
<BR>
NOTE: SPN has the smallest
turnaround, compared to other algorithms
<BR> normalized turnaround:
<BR>
P1: 5 / 4 = 1.25
<BR>
P2: 16 / 8 = 2
<BR>
P3: 5 / 2 = 2.5
<--- SPN much more fair to short processes (compared to FCFS)
<BR>
P4: 20 / 6 = 3.333
<BR>
P5: 11 / 5 = 2.2
<BR> CPU efficiency = 25 / 30 =
83.33%
<P>c. SRTN <BR> turnaround = [
(5-0) + (31-1) + (8-3) + (17-10) + (23-12) ] / 5 = 58 / 5 = 11.6
<BR> normalized turnaround:
<BR>
P1: 5 / 4 = 1.25
<BR>
P2: 30 / 8 =
3.75 <--- largest
normalized turnaround; also largest process
<BR>
P3: 5 / 2 = 2.5
<BR>
P4: 7 / 6 = 1.166
<BR>
P5: 11 / 5 = 2.2
<BR> CPU efficiency = 25 / 31 =
80.6%
<P>d. RR quantum = 3
<BR> turnaround = [ (13-0) +
(28-1) + (11-3) + (32-10) + (35-12) ] / 5 = 93 / 5 = 18.6
<BR> normalized turnaround:
<BR>
P1: 13/ 4 = 3.25
<BR>
P2: 27 / 8 = 3.375
<BR>
P3: 8 / 2 = 4.0
<BR>
P4: 22 / 6 = 3.666
<BR>
P5: 23 / 5 = 4.6
<BR><BR> In RR, all
processes are considered equally important
<P> CPU efficiency = 25 / 35 =
71.4%
<P>e. Multilevel Feedback Queue
<BR> turnaround = [ (12-0) +
(35-1) + (9-3) + (28-10) + (32-12) ] / 5 = 90 / 5 = 18
<BR> normalized turnaround:
<BR>
P1: 12/ 4 = 3.0
<BR>
P2: 34 / 8 =
4.25 <--- largest job
<BR>
P3: 6 / 2 =
3.0
<--- smallest job
<BR>
P4: 18 / 6 = 3.0
<BR>
P5: 20 / 5 = 4.0
<BR> CPU efficiency = 25 / 35 =
71.4% </P>
<LI><!-- problem 9.13 from Stallings -->Chapter 9: What type of process is
generally favored by a multilevel feedback queueing scheduler, a CPU-bound
process or an I/O-bound process? Briefly explain why.
<P>ANSWER: I/O-bound processes are favored by a multilevel feedback queue,
in general. The priority of I/O-bound processes generally remains high,
since these processes rarely use their full time slice. </P>
<LI><!-- problem 5.5 from Silbershatx -->Chapter 9: Consider a variant of
the RR scheduling algorithm where the entries in the ready queue are
pointers to the PCBs.
<OL type=a>
<LI>What would be the effect of putting two pointers to the same process
in the ready queue?<BR>ANSWER: Since the ready queue has multiple pointers
to the same process, the system is giving that process preferential
treatment. That is, this process will get double the CPU time than a
process with only one pointer.
<LI>What would be the major advantage of this scheme?<BR>ANSWER: The
advantage is that more important jobs could be given more CPU time by just
adding an additional pointer (i.e., very little extra overhead to
implement).
<LI>How could you modify the basic RR algorithm to achieve the same effect
without the duplicate pointers?<BR>ANSWER: Want longer time slice to
processes deserving higher priority.
<BR> - add bit in PCB that says
whether a process is allowed to execute two time slices
<BR> - add integer in PCB that
indicates the number of time slices a process is allowed to execute
<BR> - have two ready queues,
one which has a longer time slice for higher priority jobs </LI></OL>
<LI>What would happen if you executed the following piece of code:
<UL>main() <BR>{
<UL>for(;;) <BR> fork();</UL>}</UL><B>Note: Don't try this
on a real machine.</B>
<P>ANSWER:
<P> ==> exponential growth of
processes occurs
<P> - only a finite number of
process ID's on systems <BR> -
only a finite amount of memory on systems
<BR>
however, since the size of
created processes is small <BR>
and since the OS has lots of swap
space available <BR>
==> above code will most
likely exhaust process table (run out of IDs) instead of run out of memory
<P> - most systems, OS will run
out of process IDs and then error "can't create a process"
<BR>
user/root can't kill the
malicious process (kill needs to create a new process)
<BR>
user/root can't ps the processes
in the system (ps needs to create a new process)
<BR>
==> only choice is to re-boot
the system
<P> - some systems, OS will
actually crash <BR> - some
systems, user has a pre-specified limit on the number of processes he/she
can create (a long-term scheduler)
<BR>
==> user process won't be
allowed to take the system down </P></LI></OL></BLOCKQUOTE></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -