Here is a general outline of the key concepts (arranged by topic) that you should know for the Midterm.

The exam will have the following format:

1. Definitions: Briefly define terms using one or two sentences.

2. Short Answers:

   • System Calls

   • Processes

     • Context Switch

     • Scheduling

   • Concurrency

     • Events vs Threads

     • Locks, Condition Variables

     • Semaphores

     • Bugs

The exam is completely offline. This means there will not be any need for a computer. Furthermore, the test is closed book, closed notes, but open mind.

Terms

• Virtualization
• Concurrency
• Persistence
• Microkernel
• Multiprogramming
• Timesharing
• BIOS
• Bootloader
• Kernel
• System Call
• User mode
• Trap table
• File descriptor
• Process
• Machine state
• Cooperative multitasking
• Pre-emptive multitasking
• Signal
• Sockets
• Scheduling policy
• Turnaround time
• Response time
• FIFO
• Round-Robin
• Convoy effect
• Time slice
• Starvation
• Parallelism
• Thread
• Critical Section
• Race Condition
• Mutual Exclusion
• Lock
• Condition variable
• Spin lock
• Priority inversion
• Spin waiting
• Spurious wake-up
• Semaphore
• Reader-writer locks
• Atomicity violation
• Order violation
• Deadlock
• Livelock
• Circular wait

Computer Hardware

1. What are the basic components of a computer?

Operating System

1. What is an operating system?

2. What are the three main themes in operating systems?

3. What are different types of operating systems?

4. How does a computer start the operating system?

System Calls

1. What is a system call?

2. What is a trap/interrupt?

3. What happens during a system call?

4. What are common system calls?

Processes

1. What is a process?

2. How do we coordinate multiple processes?

3. How do we switch from one process to another?

4. What system calls can we use with processes?

5. What states can a process be in?

Inter-process Communication

1. What do we want mechanisms for inter-process communication (IPC)?

2. What are some different forms of IPC and when would we use them?

Scheduling

1. What is the purpose of a scheduler?

2. When does a scheduler execute?

3. How do we evaluate a scheduling policy?

4. How would FIFO schedule a sequence of processes?

5. How would RDRN schedule a sequence of processes?

6. How would MLFQ schedule a sequence of processes?

7. What are the strengths and weaknesses of each scheduling policy?

Event-based Concurrency

1. What exactly is concurrency? parallelism?

2. How do we overlap I/O and compute within a single process?

3. What are the pros and cons of event-based concurrency versus threads?

Threads

1. What functions do we use to create a thread, wait for a thread to complete, lock a critical section, and notify another thread?

Locks

1. Why do we need locks?

2. When should we use locks?

3. How does a lock work?

4. How do we use locks to synchronize access to shared data?

Condition Variable

1. Why do we need condition variables?

2. How do we use condition variables to solve the producer / consumer problem?

Semaphores

1. What is a semaphore?

2. What operations does a semaphore provide?

3. How do we use semaphores to to solve the reader / writer problem?

Bugs

1. What are some common concurrency bugs?

2. What are some ways to prevent or avoid deadlock?

Sample Questions

Here are a few selected sample questions:

1. Recently, the Firefox web browser underwent Project Electrolysis and transitioned from their old "thread-per-tab" model to the "process-per-tab" model introduced by Chrome. The reason for this transition is:

   The two major advantages of this model are security and performance. Security improvements are accomplished through security sandboxing, performance improvements are born out of the fact that multiple processes better leverage available client computing power.

   As with anything in Computer Science, the decision to use processes over threads is a trade-off.

   • Explain the trade-offs Firefox and Chrome have made in moving away from threads and towards processes for concurrency and the relative advantages and disadvantages of both approaches.

   • As an end user, which model would you prefer and why?

2. Consider a single-CPU, a timeslice of 10 ms, and the following processes:

   Process       Arrival Time        Run Time
   A             0 ms                30 ms
   B             10 ms               20 ms
   C             20 ms               10 ms
   

   A. Sketch out exactly when each process runs, and for how long given the FIFO scheduling policy.

   B. Sketch out exactly when each process runs, and for how long given the RDRN scheduling policy.

   C. Sketch out exactly when each process runs, and for how long given the MLFQ scheduling policy. You may assume that Q0 has a timeslice of 10 ms, Q1 has a timeslice of 20 ms, and Q2 has a timeslice of 40 ms.

   Note: You should record the processes in the priority levels Q0, Q1, and Q2 in addition to sketching which process is running at the particular time step.

3. Suppose you and your friends are going slacklining. Unfortunately, the slackline can only support up to three people¹ on it at a time.

   Assuming each person performs the following procedure:

   get_on()          // Get on slackline if there is enough room
   do_slack_line()   // Attempt to walk across slackline
   get_off()         // Get off of slackline
   

   A. Solve this concurrency problem using semaphores. State any semaphores or global variables needed and write the code for each person:

   Global Variables        Code for get_on()       Code for get_off()
   

   B. Solve this concurrency problem using locks and condition variables. State any locks, condition variables, or global variables needed and write the code for each person:

   Global Variables        Code for get_on()       Code for get_off()
   

4. Suppose you and your friends are going to Salsa night hosted by our beloved Ramzi². You are willing to dance, but only after at least 2 of your friends have started dancing.

   A. Solve this concurrency problem using locks and condition variables. State any locks, condition variables, or global variables needed and write the code for you and your N friends:

   Global Variables        Code for you_dance()    Code for friend_dance(f)
   

   B. Solve this concurrency problem using semaphores. State any semaphores or global variables needed and write the code for you and your N friends:

   Global Variables        Code for you_dance()    Code for friend_dance(f)
   

5. Consider the following problem: There are multiple men and women who wish to use a public restroom. There may be multiple men in the restroom at once or multiple women at once. However, there cannot be men and women in the room at the same time. Further, no-one should be kept waiting indefinitely while a stream of the opposite gender keeps entering the restroom.

   Solve this problem using a monitor. Maximize the number of people in the restroom at once, while being careful to avoid both starvation and deadlock. Write the monitor procedures, restroom_enter() and restroom_exit(), assuming that each person is a thread like this:

   typedef enum { MALE, FEMALE } Gender;
   
   void *person_thread(void *arg) {
       Gender g = (gender)(arg);
       restroom_enter(g);
       use_restroom();
       restroom_leave(g);
   }
   
   void restroom_enter(Gender g) {
       ...
   }
   
   void restroom_leave(Gender g) {
       ...
   }
   

6. Every once in a while, someone will post the same deadlock joke to the ProgrammerHumor subreddit:

   Interviewer:    Explain us deadlock and we'll hire you.
            Me:    Hire me and I'll explain it to you.
   

   A. Explain how this joke illustrates deadlock by identifying the four common characteristics of deadlock and describing how this joke manifests these properties.

   B. Write your own humorous illustration of a concurrency bug (ie. deadlock, livelock, race condition, order violation, atomicity violation, etc.).