CS 161: Operating Systems

Tuesday/Thursday 1:00-2:30

Pierce 301


Home Syllabus Assignments Resources Piazza

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!