1. Provide two reasons why an operating system must maintain an I/O table to manage the I/O devices and channels.
  • To ensure that two processes or threads don’t simultaneously try to access the same data which might cause conflicts or data corruption
  1. Explain the concept of a deadlock and explain why a deadlock is not a livelock.

  2. Describe three elements of the process control block (i.e., elements that the operating system should keep track of per process).

  3. Explain how the following situation can occur: A process consists of two threads. Thread A is in the blocked state. Thread B is in the running state. The process itself is in the blocked state. Discuss what the process and each thread are doing to enter these states, explained the used threading model and why this situation occurs with that threading model, and list two advantages of that threading model.

  4. Name and explain three conditions that make it possible for a deadlock to appear in a system

  5. Name and explain four steps involved in a context switch (i.e., when switching from one process to another). For example, one step is “save context”. You can use this step in your answer.

  6. Name and explain three states of the Linux process model. Explain the incoming and outgoing transitions for the states.

  7. Explain two advantages (two to three sentences per advantage) of a microkernel compared to a monolithic kernel

  8. Define the term race condition and use a real-world analogy to explain it.

  9. Describe three conceptually distinct reasons why a process could be moved from the running stated into a different process state.

  10. Explain how the following situation can occur: A process consists of two threads. Thread A is in the blocked state. Thread B is in the running state. The process itself is in the ready state. Discuss what the process and each thread are doing to enter these states, explained the used threading model and why this situation occurs with that threading model, and list two advantages of that threading model

  11. Explain through pseudocode how semaphores can be used to protect a critical section. Show code for initialization, and then the critical section. Also explain whether critical sections are necessary in a multiprogramming, single-thread environment; justify your answer.

  12. Explain user-level threads (in contrast to kernel-level threads), and explain two advantages of user-level threads.

  13. Name and explain three thread states used in the Windows model for multi- threading. Explain the incoming and outgoing transitions for the states.

  14. Assume a system with virtual round-robin scheduling: • Explain the terms (1) ready queue, (2) processor, (3) I/O queue, and (4)auxiliary queue as they are used in the VRR. • Draw a diagram of how VRR uses these elements and explain at least five different transitions from one element to the other (i.e., explain the connecting line from the ready queue to the processor). • Explain the advantage of VRR over conventional round robin scheduling.

  15. The computer has three memory frames. The running program requests pages in the following order: 2,3,2,1,5,2,4,5,3,2,5, and 2. Show the allocation of pages to frames after each page using an optimal policy (optimality criterion is the number of page faults, and the lower the better)

  16. Two parents and a child are standing in front of a cookie dispenser. The parents feed the machine with coins. The machine prepares cookies and dispenses them once the deposited amount exceeds four cents. The child continuously stares at the cookie machine and whenever it sees a cookie, then it grabs the cookie and eats it.Available functions include: Parents use PrepareCoin() to prepare the next coin to be inserted. Parents use InsertCoin() to deposit the one cent in the machine.The machine uses PrepareCookie() to bake the next cookie. The machine uses DispenseCookie() to dispense the baked cookie. The kid uses GrabCookie() to take the dispensed cookie. The kid uses EatCookie() to eat the taken cookie. Assume that the usual functions mentioned in the book such as parbegin(… ) are available. Assume that PrepareCoin() takes a random amount of time, often much longer than all the other functions. Make sure that the kid takes/eats only when a cookie is available. The kid would be very unhappy otherwise. Make sure that the machine only dispenses cookies when enough funds have been deposited. Make sure that the parents never try to insert coins simultaneously. This will jam the machine and will make the kid cry, because it will get no more cookies. Furthermore it will make the parents very unhappy, because the child is crying now. Also make sure that the kid doesn’t touches the dispenser before the machine finished has dispensing the baked cookie.

  17. What is a zombie process?

  18. Consider a system with the four robots A, B, C, and D: Two robots, A and B, produce bricks and stack them in front of them. There are two stacks S1 and S2 of size 5 and 3, respectively. Obviously only one robot can operate on one stack at a time. Nonetheless, robots A and B operate on the stacks S1 and S2 in a round-robin fashion ( i.e. S1, S2, S1, S2, … ). Two robots, C and D, consume bricks from the stack. Robot C consumes only from S1 while robot D consumes only from S2. Available functions for handling bricks: produce() produces a new brick, put(stackid) puts the produced brick onto the stack stackid, consume() uses a brick, get(stackid) gets a brick from the stack stackid. Assume that the usual functions mentioned in the book such as parbegin(… ) are available. • Find the errors in the program and explain each error in your text; also suggest a fix in your text. Refer to the line numbers when explaining something. • Explain the purpose of s1, s2, s3, s4, mayaccess1, mayaccess2 in the context of this program. • Explain what type of semaphores (e.g., binary) and what mechanism of message passing (e.g., blocking) is necessary to correctly execute the example.

// Code below extern stack S1 , S2 ; mailbox mayaccess1 , mayaccess2 ; message msg ; semaphore s1 , s2 , s3 , s4 ;

Robot_AB ( ) { while ( true } { produce ( ) ; semwait ( s1 ) ; receive ( mayaccess1 , msg ) ; put ( S1 ) ; send ( mayaccess1 , NULL ) ; semsignal ( s3 ) ; produce ( ) ; semwait ( s2 ) ; receive ( mayaccess2 , msg ) ; grab ( S2 ) ; send ( mayaccess2 , NULL ) ; semsignal ( s4 ) ; } } Robot_C ( ) { while ( true ) { semwait ( s3 ) ; receive ( mayaccess1 , msg ) ; put ( S1 ) ; send ( mayaccess1 , NULL ) ; semsignal ( s1 ) ; consume ( ) ; } } Robot_D ( ) { while ( true ) { semwait ( s4 ) ; receive ( mayaccess2 , msg ) ; grab ( S2 ) ; send ( mayaccess2 , NULL ) ; semsignal ( s1 ) ; consume ( ) ; } } main ( ) { sendmessage ( mayaccess1 , NULL ) ; sendmessage ( mayaccess2 , NULL ) ; s1 = 5 ; s2 = 4 ; s3 = 1 ; s4 = 1 ; parbegin ( Robot_AB , Robot_AB , Robot_C , Robot_D ) ; }

  1. Assume a system with the processes shown in the table below with their arrival time and execution time. All processes are CPU-bound and perform no blocking calls. • Create two schedules, one using FCFS and another one Round Robin scheduling. For Round Robin use a quantum of 1 and first enqueue new processes in the ready queue before re-enqueueing the process that just ran on the processor. • Explain the difference between response time and turnaround time. • Calculate the response time and the turnaround time of the processes. • Discuss the importance of the quantum size for Round Robin scheduling. (Note: FCFS means first-come first-served) Name Arrival Execution time A 0 3 B 5 5 3 2 C D 8 4 E 4 7

  2. The computer has three memory frames. The running program requests pages in the following order: 2,3,2,1,5,2,4,5,3,2,5, and 2. Show the allocation of pages to frames after each page using an FIFO policy

  3. What a contraption! Three gnomes shoot signal flares into the air sharing one flare gun. A pizza machine watches for these signals and once it has seen three flares, it makes a pizza. Once it made the pizza, it places the pizza on the plate of a kid that will eat the pizza. Available functions include: Gnomes use PrepareFlare() to prepare the signal flare and ShootFlare() to grab the gun and shoot the prepared flare. The pizza machine uses MakePizza() to make a pizza and PutPizzaOnPlate() to put the pizza on the kid’s plate. The kid uses EatPizza() to eat the pizza from the plate. Assume thatthe usual functions mentioned in the book such as parbegin(… ) are available. Hints: Make sure that (a) the gnomes correctly share the signal gun, (b) the pizzamachine doesn’t put a new pizza on the kid’s plate unless it’s empty. There is only one kid which has only one plate

  4. Why does the best fit-policy for placing memory allocations perform worse overall than for example the next-fit policy?

  5. Two parents and their three children are standing in front of a cookie dispenser. The parents feed the machine with one cent coins. The machine uses the coins to make cookies, and dispenses them once the deposited amount exceeds three cents. The children continuously stare at the cookie machine and whenever it sees a cookie, and then they will grab and eat it. Available functions include: Parents use PrepareCoin() to prepare the next coin to be inserted and InsertCoin() to deposit a one cent coin in the machine. The machine uses PrepareCookie() to bake the next cookie and DispenseCookie() to dispense the baked cookie. The kids use GrabCookie() to take the dispensed cookie and EatCookie() to eat the taken cookie. Assume that the usual functions mentioned in the book such as parbegin(… ) are available. Assume that PrepareCoin() takes a random amount of time, often much longer than all the other functions. The cookie machine accepts new coins as it produces the cookie (i.e., parent can execute InsertCoin() while the machine executes DispenseCookie()). • Find the errors in the program and explain each error in your text; also suggest a fix in your text. Refer to the line numbers when explaining something. • Explain the purpose of m1, m2, C, R in the context of this program. • Explain what type of semaphores (e.g., binary) and what mechanism of message passing (e.g., blocking) is necessary to correctly execute the example.

  6. Assume a system which uses virtual memory with paging: • Explain in one to two sentences each of these elements: (1) Virtual address, (2) page table pointer, (3) page table, (4) physical address, and (5) main memory. • Draw a diagram of the translation mechanism. • Explain how this system achieves memory protection among processes.

  7. • Explain why this function must be implemented as atomic action in hardware instead of software. • Give an execution trace for two threads that demonstrates the problem. Refer to line numbers in the execution trace.

int compare_and_swap ( int ∗ reg , int oldval , int newval ) int old_reg_val = ∗ reg ; i f ( old_reg_val == oldval ) ∗ reg = newval ; return old_reg_val ; }

  1. The lab hosts a group of caffeine-addicted students, and a grumpy secretary whose task it is to refill the coffee pot. The students will immediately die of despair, if they try to serve coffee from an empty pot. The lab secretary, on the other hand, will die from extreme irritation, if he is called to fill a non-empty pot. Two students must not reach for the pot at the same time, otherwise a battle to the death will occur. Functions for serving coffee from the pot and to put coffee in the pot are provided. • Find and describe at least three defects dealing with concurrency. Refer to line numbers in your description.

int servings = 10 semaphore pot , fullpot mailbox emptypot

student ( ) { i f ( servings == 1 ) { sendmsg ( emptypot ) semwait ( fullpot ) } semwait ( pot ) ServeFromPot ( ) servings −= 1 sempost ( pot ) } secretary ( ) { PutCoffeeInPot ( ) recvmsg ( emptypot ) servings = 10 semsignal ( fullpot ) } main ( ) { pot = 0 emptypot = 0 parbegin ( student , student , student , student , secretary ) }

  1. Name two entries of the process control block for a system that supports multiprocessing and multithreading. Describe the entries with a single sentence

  2. Explain the circumstances in which having multiple queues for blocked processes is superior to having a single queue

  3. Define the term livelock and use a real-world analogy to explain it.

  4. Assume the given structure for semaphores listed below. Write the function semWait(semaphore *s) in C and ensure your implementation is reentrant. Explain eventual auxiliary/atomic functions you use inside your implementation of semWait() in one or two sentences. (Note for the ueber-smart kids: you can’t just call something like the real semwait() inside your code. This wouldn’t be an auxiliary function.)

struct semaphore { int count ; wait_queue_head_t q ; }

  1. There is an all-you-can-eat sushi night near the university. Three chefs prepare the food while three waiters run back and forth from the food counter to the tables to keep the guests satisfied. In expectation of a high number of guests, a literally infinite stack of plates has been made available to the chefs, but they must grab plates one at a time, otherwise the pile will topple. Similarly, plates with food are queued on the way out of the kitchen so that only one plate can be added to the counter by a chef or grabbed by a waiter at a time. Each time a chef placed a plate, he yells out to the waiters to come and get the plate. The chefs’ functions for grabbing clean plates, cooking and putting plates out are available, and so are the functions for the waiters to grab plates of food and serve. • Find and describe at least three defects dealing with concurrency. Refer to line numbers in your description.

semaphore foodcounter , dishstack mailbox food

waiter { while ( 1 ) { semwait ( foodcounter ) recvmsg ( food ) grab_plate ( ) semsignal ( foodcounter ) serve ( ) } } chef { while ( 1 ) { semsignal ( dishstack ) grab_clean_plate ( ) semwait ( dishstack ) cook ( ) semwait ( foodcounter ) put_plate_out ( ) semsignal ( foodcounter ) sendmsg ( food ) } } main ( ) { foodcounter = 1 dishstack = 1 sendmsg ( food ) parbegin ( chef , chef , chef , waiter , waiter , waiter ) }

  1. Name two entries of the thread control block for a system that supports multiprocessing and multithreading. Describe the entries with a single sentence

  2. Provide two reasons why an operating system must maintain an I/O table to manage the I/O devices and channels.

  3. Define the term race condition and use a real-world analogy to explain it