CS 161: Operating Systems
Tuesday/Thursday 1:00-2:30
Pierce 301
Web Work Answers
Below are our solutions to the web work, along with explanations as to why we
think they are correct. Note that some of the questions are ambiguous and can
be interpreted several ways, some of which yield other, equally correct
answers. If you're unsure of your understanding of the material and want to
know whether your answer was also correct, or if you feel like our solution is
incorrect, feel free to reach out to the course staff. However, the web work
is graded only on completion, not on exactly matching the solutions
below, so there's no need to argue your case if you're confident
you're also right.
2/12 -- Linking
2. A process issues a getpid system call, into what state will
the process be placed?
The following questions refer to the code below:
1. extern char *optarg;
2. extern int optind
3.
4. main(int argc, char **argv)
5. {
6. char ch;
7.
8. while ((ch = getopt(argc, argv, "ABc:C")) != EOF) {
9. /* Do something useful here. */
10. }
11.}
So, these questions had a bug -- Rdata should have been just "data." My
bad!
1 .In what segment will you find the symbol "main?"
Text: main is the symbolic name for the place where this code begins.
2. In what segment will you find the symbol "ch?"
None -- it's a local variable and would therefore be placed on the
stack.
3. In what segment will you find the string "ABc:C?"
ROdata -- it's a read only string.
4. In what segment will you find the symbol "optind?"
If optind is defined to have a value somewhere, then it will be in
data; if it is not defined, it will be in bss.
5. Which of the following symbols will appear in a relocation segment?
optarg, optind, getopt: these are all variables that are defined somewhere
else, so during linking, we'll have to resolve them; in the meantime we place
them in the relocation segment.
6. Elf files do not contain the stack; where would you find
them in an executable?
The stack is not represented in the executable (binary) file; it is
created in the address space when you construct a process from a program
(or binary or executable).
2/12 -- Architecture
1. Which type of operating system would be easier to write?
Uniprogramming -- you wouldn't have to worry much about synchronization
within the kernel -- just between the kernel and interrupt handlers.
2. Which type of operating system would be easier to use?
Undoubtedly multiprogrammed -- you can have multiple jobs running
at the same time.
3. Intel's Core™ i7-3770K Processor is a quadcore with 2-way
hyperthreading. How many threads can be executing concurrently?
quadcore = 4 cores * 2 thread per core = 8 hardware threads, so you
can have 8 threads executing concurrently.
4. It is possible to run a multiprogrammed operating system on
a uniprocessor system.
Sure (True) -- although only one thread could actually be running, you
can certainly have many programs runnable. From the notes: Multiple
programs run concurrently, even if there is only one program is
running at a given instant.
5. There is no way to run a uniprogrammed operating system on
a multiprocessor.
False -- You certainly could, but it would probably be a poor use of
resources.
6. Cores on the same chip never share a cache.
False, cores on the same chip frequently share the highest level cache.
7. If a piece of hardware supports N hardware threads, you can
never have more than N software threads present on the system.
False: you can have as many ready threads as you want, you just can't have
more than N threads actually running.
2/11 -- Process Components
1. Which of the following should be stored in an architecture
dependent structure?
Program counter, exception register: these both reference hardware
registers and therefore are architecture dependent.
2. Which of the following would you imagine are things you want
to keep track of as part of the process state?
Address space, list of open files, current working directory, amount
of CPU time consumed (for scheduling), amount of I/O this process has done
(again for scheduling).
3. Elf is:
A character from assignment 1; an executable format; a supernatural being
from German mythology. To the best of my knowledge, elf has never been
a cs161 animal.
2/11 -- Process Management
1. Imagine that a process P is blocked on a lock. When that lock
becomes available, into which state will the process be placed?
Ready -- It's certainly possible to immediately select that
process to run, but that's not required. Once the condition on which
a process is blocked goes away, the process must be in (at least) the
Ready state
2. A process issues a getpid system call, into what state will
the process be placed?
This was kind of a mean question: the process was running and there is no
reason that you need to change it to anything other than running. If you do
decide to reschedule it, then you'd have to leave it in a ready state.
3. A process issues a read system call and the data to be read
are not in memory, into what state will the process be placed?
Blocked -- this one is straight forward; the process cannot make
forward progress
4. A process with running child processes exits, into what state
will the process be placed?
This was another mean question -- all exiting processes first become
zombies and then are almost immediately reaped by their parent. So, the
correct answer is Zombie. However, it is not the case that the parent has
to stay in a Zombie state until its children exit. It only stays in the
Zombie state until it's reaped by its parent. Orphan processes (children
whose parent has exited) are inherited by the init process, which ultimately
reaps them.
5. A process with no running children exits, into what state will the process be placed?
Zombie: the answer is identical to the one above -- ALL processes first
go into the Zombie state.
6. A process forks a child process, into what state should the
child process be placed?
Probably Ready, unless you choose to run the child immediately, in which
case it could be running and the parent would be read
7. A process with no children issues a waitpid, into what state
should the process be placed?
Ready -- if there are no children, wait will return immediately.
8. The scheduler decides to run your process, in what state
does it place your process?
Running
2/10 -- Fork/Exec
1. Fork:
Creates a new process
2. Exec:
Replaces the current process with a different executable
3. Wait:
Blocks until some child process exits (or undergoes a state change
such as being stopped by a signal or restarted)
4. Waitpid:
Blocks until a particular child process exits (or changes state;
see above). Also, with pid == -1, waitpid behaves just like wait.
5. It is possible for wait to return even if no child process exited?
True -- wait and friends will return when a child process changes state,
even if it has not exited. From the man page (type 'man wait' on the
appliance): "A state change is considered to be: the child terminated;
the child was stopped by a signal; or the child was resumed by a signal."
The code snippet below is a subset of that in the fork-exec video.
In that video, we showed how to use pipes to create a communication
channel between two child processes. In this question, we wish to
have a parent process communicate with its child by writing to
standard out. The child should read from its own standard in,
receiving instructions from the master.
1. pid_t child1;
2. int pipedes[2], status;
3. assert (pipe(pipedes) == 0); /* Create the pipe. */
4. child1 = fork();
5. if (child1 == 0) {
6. /* child */
7. close(pipedes[0]); /* Close read end */
8. dup2(pipedes[1], STDOUT_FILENO);
9. execve(“foo”, argv, envp); /* Assume argp, envp are set */
10.}
11.
12. close (pipedes[0]);
13. close (pipedes[1]);
6. How should line 7 change to conform to the scenario described above?
close(pipedes[1]), which will close the writing end instead of the reading
end since we want to read from the pipe to get commands from the parent.
7. Line 8 should be changed to:
dup2(pipedes[0], STDIN_FILENO), which will dup the reading end of the
pipe to stdin.
8. Line 12 should be changed to:
None -- we want to close the reading end of the pipe in the parent
9. Line 13 should be changed to:
dup2(pipedes[1], STDOUT), so the parent's standard out will be writing
to the pipe
2/10 -- Processes, Threads, and Address Spaces
1. Address Space
Process -- threads in a proess share an address space. I can imagine
people checking "Both" because threads do, in fact, run within an
address. However, the question was supposed to get you to think about whether
two threads would necessarily have 2 different address spaces, which they
wouldn't.
2. The value of the stack pointer
Thread -- if you have multiple threads, each might have it's own
value for the stack pointer
3. Heap
The heap is simply a chunk of memory. Its contents are in the address
space, so answering "Proccess" would have been OK. However, since it's
just part of memory, had you said "Neither" that would have been OK too,
as long as you understood why you were saying that.
4. The contents of the stack.
This one is also a little tricky. Since each thread has its own
stack, my first choice would have been stack. However, you could have
also fallen back to the "hey -- it's in memory and that memory is part
of the address space, so it's process," or you could have said, "Hey,
it's just memory so neither."
5. The process ID
Process -- that "process" part was not meant to be a trick.
6. The stack pointer:Thread -- It's part of a thread's state
7. The OS ust always be involved in a thread switch
False -- it is possible to have user level threads
8. The OS will never be involved in a thread switch
False -- it would certainly be involved in switching among kernel
threads.
2/5
Why do you suppose that interrupts from faster devices get higher priority?
The faster the device, the more likely it is to generate interrupts at a
faster rate.
Thus, you want to interrupts from faster devices to either let you reply and handle
the next interrupt or queue events without overflowing resources allocated to such
queueing.
On slide 5 of the video, we showed the canonical use of SPL calls:
1. s = splhigh();
2. Do stuff
3. splx(s);
Before we call splhigh, we do not know what our existing interrupt
level is; that is what is returned from splhigh. Our goal is to
restore interrupts to their prior level, not necessarily to turn them all
off. The places this applies are a) if you have multiple priority levels,
then you might want to restore to something other than 0, and b) you have
a routine that wishes to turn interrupts off that gets called from somewhere
interrupts are already turned off. If you are in the innermost of those
routines, you don't want to turn interrupts back on, because someone above
you in the call stack may very well be depending on interrupts still being off.
Which of the following is the proper way to unlock a TAS (from slide 6)?
lock_var = 0 (Assuming that lock_var can be written atomically.)
Explain why simply turning interrupts off is insufficient for
implementing a sempahore on a multiprocessor system.
For disabling interrupts to work, you would need to disable interrupts
on all processors.
This is a bad idea (why?)
If you do not disable on all processors, then you could encounter a lost wakeup,
where a thread releasing a mutex wakes up a thread before the thread about to sleep
on it is fully enqueued.
2/3 OS Structure
1. If a processor changes mode, the memory locations to which
it has access can change.
Absolutely! The kernel will often have access to all
of physical memory, while a process will be limited to
only those memory locations in its own addrses space.
2. Intel and MIPS Processors support the same number of
protection levels.
No -- Intel has four and MIPS has only two.
3. Check all of the items that can behave differently in
different processor privilege levels.
Fortunately addition doesn't change when you change
modes, but all the reset of the items do -- user processes
can't execute the halt instruction (and therefore the
instructions executed in the two modes are different) and
user virtual addresses get mapped to the user's address
space while the kernel's virtual addresses get mapped
to the kernel's address space.
4. The operating system (kernel) is the only one who can decide
when the processor changes privilege levels.
Not exactly: a process can cause a trap (change of mode)
by issuing a system call or doing something illegal, e.g.,
dividing by 0.
5. System calls, interrupts, and exceptions are all ways to
transfer control between a user process and the operating system.
Yes! In fact, that's why we are talking about them
now.
6. Both the Intel and MIPS processors use an indirection table to
get to the code that must be executed in response to a trap.
Yes! That's how you get to the right code to handle.
2/3 Synchronization
Does the scenario below describe deadlock, starvation, a race condition,
or proper synchronization?
You and your roommate share a refrigerator...
Race condition. If you and your friend (almost) simultaneously find your
refrigerator devoid of milk, you'll probably both go out to find more.
Since you didn't synchronize your milk purchases, you'll end up with two
gallons of milk and infinite sadness.
Professor Seltzer is holding office hours...
Starvation. If Annoying Arnold, a CS 161 student shows up, and asks
questions non-stop, how will Professor Seltzer's advisees ever get their
study cards signed?
Two cats are standing on opposite sides of a cat door. Both cats
are snarling. Both cats must go through the cat door. Cats will not
go through a cat door if there is a snarling cat on the other side.
Deadlock. Neither cat can go through the door.
The same thread/process that executes a P on a semaphore must at some
point execute a corresponding V?
Nope. A semaphore is just a counter, and it doesn't care who increments or
decrements it.
If you have a semaphore implementation, you can implement any other
synchronization primitive using it.
Yup! That's actually exactly what we'll be doing in assignment 1! Well,
except for spinlocks. If you were thinking of those, then the semaphore
doesn't quite cut it, because the semaphore blocks, rather than simply
spinning.
Complex data structures must be implemented by monitors.
No way! While monitors are certainly useful to control access to complex
data structures, there's no reason you are required to use any particular
locking technique over any of the others.
1. | struct cv *CV;
2. | struct lock *L;
3. | int readers, writers;
4. |
5. | CV = cv_create("sample");
6. | L = lock_create("sample");
7. |
8. | lock_acquire(L);
9. | while (writers > 0 || readers > 10) {
10. | cv_wait(CV, L);
11. | }
12. |
Based on the code sample above, is the programmer assuming Mesa or Hoare
semantics?
Mesa. The call to cv_wait is within a while loop that checks for a
certain condition. If this were a Hoare condition variable, the loop would
be unnecessary, since the thread knows that the condition must be true when
it awakens.
If we changed the semantics of the CV implementation (e.g., from Mesa to
Hoare or Hoare to Mesa), which lines of code would need to be changed or
removed?
Line 9. We'd just replace the while with an if. See
above for an explanation.
At line 12, this thread holds the lock L.
Yup. When you wait on a CV with an associated lock, you are guaranteed to be
holding the lock when you wake.
1/29
There weren't any real questions here -- we just wanted you to get your
virtual machine ready to go!