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

    • Scheduling

    • Concurrency

    • 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.

Representative, but not Exhaustive

This check list is meant to be representative, rather than exhaustive (ie. there may be questions that show up on the exam that are not shown below).

Terms

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 happens during a system call?

Processes

  1. What is a process?

  2. What happens when we execute a program?

  3. What system calls can we use with processes?

  4. What states can a process be in?

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

Inter-process Communication

  1. What are some different forms of IPC and when we would we want to 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?

  2. What are different ways to implement threads?

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 build concurrent data structures?

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 synchronize threads?

Bugs

  1. What are some common concurrency bugs?

  2. What are some ways to prevent or avoid such bugs?

Sample Questions

Here are a few selected sample questions:

  1. 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.

  2. Suppose you and your friends are going slacklining. Unfortunately, the slackline can only support up to three people1 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()
    
  3. Suppose you and your friends are going to Salsa night hosted by our beloved Ramzi2. You are willing to dance, but only after at least 2 of your friends have started dancing.

    A. 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)
    

    B. 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)
    

  1. I know, you are only suppose to have one person at a time. I just needed an example withe some queuing... 

  2. Just dance...