📄 macs 442 homework 1 solutions.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0083)http://www.mines.edu/Academic/courses/math_cs/macs442/assignments/HW1-solution.html -->
<HTML><HEAD><TITLE>MACS 442: Homework 1 Solutions</TITLE>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2900.2627" name=GENERATOR></HEAD>
<BODY>
<H3>
<CENTER><B>Solutions to Homework 1 (Chapters 1-4 and 9) </B><BR></CENTER></H3>
<BLOCKQUOTE>
<OL>
<LI><!-- from Silbershatz text -->Define these terms in one sentence:
<OL type=a>
<LI>OS: program that interfaces the user with the hardware and manages
resources
<LI>hit ratio: percent of requests that are within the storage device
<LI>degree of multiprogramming (DOM): indicates the amount of multiple
processes simultaneously sharing the system
<LI>interrupt: method to ensure the CPU takes note of some event
<LI>system call: method to request that the OS do something
<LI>non-threaded process: a program in execution
<LI>time slice: each process gets the CPU for a slice of time or until
process blocks/terminates
<LI>kernel: most frequently used functions of the OS (or the core OS)
<LI>swapping: moving ALL of a process from main memory to disk (or vice
versa)
<LI>argv: argument vector
<LI>argc: argument count
<LI>thread: a dispatchable unit of work
<LI>ready queue: linked list of all PCB's residing in main memory, waiting
to execute
<LI>preemption: to reclaim a resource before the process is finished using
it
<LI>process switch: when the OS switches from one process (or context) to
another
<LI>multiprogramming: concurrent execution of processes
<LI>preemptive CPU scheduling: policy that halts the execution of one
process, in order to run another.
<LI>CPU burst: a time interval when a process uses CPU only.
<LI>turnaround time: delay between job submission and job completion
<LI>throughput: number of processes that are completed per time unit
<LI>aging: gradual increase of the priority of a job, to prevent
"starvation."
<LI>dispatching: binding the scheduled process to a processor
<LI>CPU utilization: fraction of time the CPU is busy
<LI>CPU efficiency: fraction of time the CPU is busy doing real work
(i.e., doesn't include overhead of process switching)
<LI>starvation (in relation to a CPU scheduling algorithm): when a process
sits in a ready queue and is never allocated the CPU
<LI>time slice: blah - see g. </LI></OL>
<LI><!-- problem 1.7 from Stallings -->Chapter 1: Why is DMA access to main
memory given a higher priority than processor access to main memory?
<P>ANSWER: <BR>If a processor is held up in attempting to read or write
memory, usually no damage occurs except a slight loss of time. However, a
DMA transfer may be to or from a device that is receiving or sending data in
a stream (e.g., disk or tape), and cannot be stopped. Thus, if the DMA
module is held up (denied continuing access to main memory), data will be
lost. </P>
<LI><!-- problem 1.13 from Stallings -- changed -->Chapter 1: A computer has
a cache, main memory, and a disk used for virtual memory. An access to the
cache takes 10 ns. An access to main memory takes 100 ns. An access to the
disk takes 10,000 ns. Suppose the cache hit ratio is 0.9 and the main memory
hit ratio is 0.8. What is the effective access time (EAT) in ns required to
access a referenced word on this system?
<P>ANSWER: <BR>EAT = .9 (10) + .1 [ .8 (10 + 100) + .2 (10 + 100 + 10000) ]
<BR> = 220ns
<BR> OR <BR>EAT = 10 + .1 (100) + .02 (10000)
<BR> = 220ns </P>
<LI><!-- problem 2.2 from Stallings -->Chapter 2: Suppose a short-term
scheduling algorithm favors those processes that have used little processor
time in the recent past.
<UL>
<LI>a. Explain why this algorithm favors I/O-bound processes.
<LI>b. Explain why this algorithm does not permanently deny processor time
to CPU-bound processes. </LI></UL>
<P>ANSWER:
<UL>
<LI>a. I/O-bound processes use little processor time
<BR> thus, I/O-bound processes
will be favored by the algoritm.
<LI>b. if CPU-bound process is denied access to the processor
<BR> ==> the CPU-bound
process won't use the processor in the recent past.
<BR> ==> the CPU-bound
process won't be permanently denied access. </LI></UL>
<LI><!-- problem 2.5 from Stallings -->Chapter 2: What is the purpose of
system calls, and how do system calls relate to the OS and to the concept of
dual-mode (kernel mode and user mode) operation? <BR>
<P>ANSWER: <BR>A system call is used by an application program to invoke a
function provided by the operating system. Typically, the system call
results in transfer to a system program that runs in kernel mode. <!-- problem 3.3 from Stallings --></P>
<LI>Chapter 3: We illustrated the five state process model with a <I>queuing
diagram</I> that showed the CPU, the ready queue, and multiple event queues
(see Figure 3.7b). Extend this <I>queuing diagram</I> for the seven state
process model. (NOTE: this question is NOT asking you to draw the seven
state process model, which is shown in Figure 3.8.) <BR><IMG height=380
src="MACS 442 Homework 1 Solutions.files/hw1a.jpg">
<LI><!-- MODIFIED 9/02 problem 3.4 from Stallings -->Chapter 3: Suppose that
the OS needs to choose and dispatch another process to execute and that, at
this time, there are processes in both the ready state and the ready-suspend
state. Furthermore, suppose that at least one process in the ready-suspend
state has higher scheduling priority than any of the processes in the ready
state. Two extreme policies for deciding which process to execute are: (1)
Always dispatch a process in the ready state. (2) Always dispatch the
highest-priority process. What is a concern with each of these two policies?
Is there an intermediate policy that tries to balance these concerns?
<P>ANSWER:
<UL>
<LI>1) doesn't follow priorities
<LI>2) low performance, since CPU is idle during swap
<LI>One possible intermediate policy (there are many possibilities):
<BR>Begin swapping the highest-priority process into memory. While it is
being swapped, allocate the CPU to the highest-priority process that
exists in the ready queue. Once the process is swapped in, then preempt
the executing process in favor for this highest-priority process. </LI></UL>
<LI>Chapter 3: What is a PCB? List five items that are (usually) maintained
in a PCB and discuss the purpose of each item.
<P>ANSWER: <BR>PCB = Process control block <BR>PCB holds information
associated with each process, such as
<UL>
<LI>unique number associated with each process to identify the process
<LI>unique number associated with each process to identify the parent
<LI>process state: (new, ready, running, blocked, terminated, etc.)
<LI>program counter: address of next instruction to be executed
<LI>register information: stack pointer, data registers, etc.
<LI>CPU scheduling information: process priority, elapsed time, etc.
<LI>memory-management information: base/limit registers, page tables, etc.
<LI>accounting information: amount CPU/real time used, process numbers,
etc.
<LI>I/O status information: I/O devices allocated, list of open files,
etc. </LI></UL><!-- problem 4.2 in Silbershatz -->
<LI>Chapter 4: Describe the differences among short-term, medium-term, and
long-term scheduling. Which scheduler will execute the most often? Which
scheduler will execute the least often?
<P>ANSWER:
<UL>
<LI>Short-term (CPU scheduler): selects a job on the ready queue and
allocates it the CPU.
<LI>Medium-term (swapper): determines which process to swap in/out of disk
to/from memory.
<LI>Long-term (job scheduler): determines which jobs are admitted to the
system for processing.
<LI>Short-term will execute the most. <BR>Long-term will execute the
least. </LI></UL>
<LI><!-- problem 4.5 from Stallings, extended -->Chapter 4: Thread
questions:
<UL>
<LI>a. List three reasons for wanting to use multiple threads in a
process.
<LI>b. If a process exits and there are still threads of that process
executing, will they continue to execute? Explain.
<LI>c. What is one advantage and one disadvantage of a process using
user-level threads over a process using kernel-level threads?
<LI><!-- problem 4.1 from Stallings -->d. Suppose two processes are
executing, both of which are using multiple kernel-level threads. Is a
context switch between two threads within one processes less work than a
context switch between two threads in different processes? Explain.
<LI>e. Suppose two processes are executing, both of which are using
multiple user-level threads. Is a context switch between two threads
within one processes less work than a context switch between two threads
in different processes? Explain. </LI></UL>
<P>ANSWER:
<UL>
<LI>a. simplifies program structure <BR> improves perf.
in presence of blocking <BR> make use of multiple
processing units
<LI>b. No. When a process exits, it takes everything with it. This
includes the process structure, the memory space, etc. including threads.
<BR> (The process is the execution environment; without
it, a thread can not execute.)
<LI>c. advantage: don't need kernel to understand threads faster
switching, since kernel not involved <BR> disadvantage:
if one thread blocks, all threads blocked <BR> process
can't take advantage of multiple processors
<LI>d. PARTIAL ANSWER:
<BR>
YES! More state information needs to be switched when threads are in
different processes. <BR> FULLER ANSWER:
<BR>
context switch between two threads in the same process:
<BR>
only need to store/load the TCB information
<BR>
context switch between two threads in different processes:
<BR>
above, plus need to store/load the PCB information
<LI>e. PARTIAL ANSWER:
<BR>
YES! Process switch occurs when threads are in different processes.
<BR> FULLER ANSWER:
<BR>
context switch between two threads in the same process:
<BR>
Handled by the dispatcher within your program
<BR>
OS doesn't need to do anything
<BR>
context switch between two threads in different processes:
<BR>
must process switch between two processes </LI></UL>
<LI><!-- problem 9.1 from Stallings similar --><!-- also problems 9.2 and 9.15 could be used -->Chapter
9: Suppose the following jobs are to be executed in a uniprocessor system.
<DIV align=center>
<TABLE cellPadding=3 border=1>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -