📄 homework #2.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.cse.ucsd.edu/classes/fa02/cse120/hw/hw2.html -->
<HTML><HEAD><TITLE>CSE 120 (Fall 2002) -- Homework #2</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.2627" name=GENERATOR></HEAD>
<BODY>
<H2>CSE 120 (Fall 2002) -- Homework #2</H2><FONT color=blue size=+1><B>Out:
10/15</B></FONT><BR><FONT color=red size=+1><B>Due: 10/24</B></FONT>
<OL>
<LI>Chapter 4: 4.3
<P>4.3 A DECSYSTEM-20 computer has multiple register sets. Describe the
actions of a context switch if the new context is already loaded into one of
the register sets. What else must happen if the new context is in memory
rather in a register set, and all of the register sets are in use?
<P></P>
<LI>Chapter 5: 5.1, 5.2, 5.3
<P>5.1 Provide two programming examples of multithreading that improve
performance over a single-threaded solution.
<P>5.2 Provide two programming examples of multithreading that do
<I>not</I> improve performance over a single-threaded solution.
<P>5.3 What are the differences between user-level threads and
kernel-level threads? Under what circumstances is one type better than the
other?
<P></P>
<LI>Chapter 6: 6.8, 6.10
<P>6.8 Many CPU scheduling algorithms are parameterized. For example,
the RR algorithm requires a parameter to indicate the time slice. Multilevel
feedback queues require parameters to definte the number of queues, the
scheduling algorithms for each queue, the criteria used to move processes
between queues, etc. These algorithms are thus really sets of algorithms
(e.g., the set of RR algorithms for all time slices, etc.). One set of
algorithms may include another (in lecture, we talked about using Priority
Scheduling to implement SJF). What, if any, relation holds between the
following pair of algorithms?
<P> a. Priority and SJF. <BR> b. Multilevel feedback
queues and FCFS. <BR> c. Priority and FCFS. <BR> d.
RR and SJF.
<P>6.10 Explain the differences in the degree to which the following
scheduling algorithms discriminate in favor of short processes:
<P> a. FCFS <BR> b. RR <BR> c.
Multilevel feedback queues
<P></P>
<LI>Chapter 7: 7.8, 7.9, 7.13
<P>7.8 <B>The Sleeping-Barber Problem.</B> A barbershop consists of a
waiting room with <I>n</I> chairs and the barber room containing the barber
chair. If there are no customers to be served, the barber goes to sleep. If a
customer enters the barbershop and all chairs are occupied, then the customer
leaves the shop. If the barber is busy but chairs are available, then the
customer sits in one of the free chairs. If the barber is asleep, the customer
wakes up the barber. Write a program to coordinate the barber and the
customers.
<P>7.9 <B>The Cigarette-Smokers Problem.</B> Consider a system with
three <I>smoker</I> processes and one <I>agent</I> process. Each smoker
continuously rolls a cigarette and then smokes it. But to roll and smoke a
cigarette, the smoker needs three ingredients: tobaccor, paper, and matches.
One of the smoker processes has paper, another has tobacco, and the third has
matches. The agent has an infinite supply of all three materials. The agent
places two of the ingredients on the table. The smoker who has the remaining
ingredient then makes and smokes a cigarette, signaling the agent on
completion. The agent then puts out another two of the three ingredients, and
the cycle repeats. Write a program to synchronize the agent and the smokers.
<P>7.13 Suppose that the <TT>signal</TT> statement can appear only as
the last statement in a monitor procedure. Suggest how the implementation
described in Section 7.7 can be simplified.
<P></P>
<LI>Chapter 8: 8.4
<P>8.4 Consider the traffic deadlock depicted in Figure 8.8 (see book).
<P> a. Show that the four necessary conditions for deadlock
indeed hold in this example. <BR> b. State a simple rule that
will avoid deadlocks in this system.
<P></P>
<LI>The Intel x86 instruction set architecture provides an atomic instruction
called XCHG for implementing synchronization primitives. Semantically, XCHG
works as follows (although keep in mind it is executed atomically):
<BLOCKQUOTE><PRE>void XCHG(bool *X, bool *Y) {
bool tmp = *X;
*X = *Y;
*Y = tmp;
}
</PRE></BLOCKQUOTE>
<P>Show how XCHG can be used instead of test-and-set to implement the
acquire() and release() functions of the lock data structure described in the
"Synchronization" lecture.
<BLOCKQUOTE><PRE>struct lock {
...
}
void acquire (struct lock *) {
...
}
void release (struct lock *) {
...
}
</PRE></BLOCKQUOTE>
<LI>[Chase] This problem asks you to implement an <I>Event</I> synchronization
primitive similar to the fundamental coordination primitives used throughout
Windows NT. Initially, an <I>Event</I> object is in an <I>unsignaled</I>
state. <I>Event::Wait()</I> blocks the calling thread if the event object is
in the unsignaled state. <I>Event::Signal()</I> transitions the event to the
<I>signaled</I> state, waking up all threads waiting on the event. If
<I>Wait</I> is called on an event in the signaled state, it returns without
blocking the caller. Once an event is signaled, it remains in the signaled
state until it is destroyed.
<P>a. First implement <I>Event</I> using a monitor.
<BLOCKQUOTE><PRE>monitor Event {
<I>...</I>
}
</PRE></BLOCKQUOTE>
<P>b. Implement <I>Event</I> using an explicit mutex and conditon variable.
The mutex and condition variable have the semantics described at the end of
the "Semaphore and Monitor" lecture in the ping_pong example, and as
implemented by you in Project 1.
<BLOCKQUOTE><PRE>class Event {
<I>...private variables...</I>
void Signal () {
...
}
...
}
</PRE></BLOCKQUOTE></LI></OL><PRE>
</PRE>
<HR>
<ADDRESS><A href="mailto:voelker@cs.ucsd.edu">voelker@cs.ucsd.edu</A>
</ADDRESS></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -