Process Management

• Processes (Slides)
  • Process concept
    • The process (SGG Ch.4.1.1)
    • Process state (SGG Ch.4.1.2)
    • Process control block (SGG Ch.4.1.3)
    • Scheduling queues (SGG Ch.4.2.1)
    • Process creation (SGG Ch.4.3.1-10)
    • Context switch (SGG Ch.4.2.3, SGG Ch.6.1.4)
    • Process termination (SGG Ch.4.3.2)
  • System calls for process management (SGG Ch.3.3.1)
    • Students to read, while we do an example = UNIX
  • UNIX processes
    • The UNIX process hierarchy (SGG Ap.A.3.2)
    • The UNIX uarea and process table (SGG Ap.A.5.1-29)
    • Process IDs and user IDs (SGG Ap.A.3.2,4,15)
    • Process creation via fork and exec.
    • Process termination (SGG Ap.A.3.2,21.5.1,30-31,11)
    • Signals with pause, signal, kill, and alarm (SGG Ap.A.3.3,16).
  • Threads
    • Thread structure (SGG Ch.5.1)
    • Thread implementation (SGG Ch.5.1.3, 5.2)
    • Thread examples (SGG Ch.5.4-8)

• Scheduling (Slides)
  • Schedulers (SGG Ch.4.2)
  • Basic concepts
    • CPU-IO burst cycle (SGG Ch.6.1.1)
    • The CPU scheduler (SGG Ch.6.1.2)
  • Scheduling criteria (SGG Ch.6.2)
    • A top sample from hurricane
  • Scheduling algorithms (SGG Ch.5.3)
    • First come first served (SGG Ch.6.3.1)
    • Shortest next CPU burst first (SGG Ch.6.3.2)
      • Non-preemptive
      • Preemptive
      • Predicting CPU bursts
    • Priority scheduling (SGG Ch.6.3.3)
      • Non-preemptive
      • Preemptive
    • Round-robin scheduling (SGG Ch.6.3.4)
    • Multilevel scheduling
      • Multilevel queue scheduling (SGG Ch.6.3.5)
      • Multilevel feedback queue scheduling (SGG Ch.6.3.6)
    • Multi-processor scheduling (SGG Ch.6.4)
  • UNIX scheduling
    • Changing the priority with the setpriority system call

• Interprocess Communication (Slides)
  • Cooperating processes (SGG Ch.4.4)
  • Shared memory
    • The producer-consumer problem (SGG Ch.4.4)
  • Message passing
    • Basic structure (SGG Ch.4.5.1)
    • Direct and indirect IPC (SGG Ch.4.5.2)
    • Synchronization (SGG Ch.4.5.3)
    • Buffering (SGG Ch.4.5.4)
    • Exception conditions
      • Sender terminates: System notifies or terminates receiver
      • Receiver terminates
        • With buffering, no action. Sender can program for ack.
        • Without buffering, system notifies or terminates sender
      • Lost message
        • Some protocols expect unreliability
        • OS or sender detects and resends, or OS detects and notifies sender
        • Timeouts, resends, and multiple copies
      • Scrambled messages treated as lost
  • UNIX IPC
    • Shared memory
    • Message queues

• Synchronization (Slides) and deadlocks (Slides)
  • The critical section problem
    • Shared data (SGG Ch.6.1,2-3)
    • Critical sections (SGG Ch.6.2-6)
  • Solutions
    • Two process software solutions (SGG Ch.6.2.1-10)
    • Multiple process software solution (SGG Ch.6.2.2-13)
    • Hardware solutions (SGG Ch.6.3-15)
  • Semaphores
    • wait and signal (SGG Ch.6.4, Slide 6.16)
    • Uses (SGG Ch.6.4.1,20)
    • Implementation with binary semaphores (SGG Ch.6.4.4)
      • while Test-and-Set(S); implements wait for a binary semaphore, and S=FALSE implements signal.
      • Binary semaphoes and a variable can implement a general semaphore (Slide 6.23-24)
    • Implementation with blocking (SGG Ch.6.4.2)
      • Busy waiting (also called a spinlock) is wasteful of CPU, especially as application software may wait on a semaphore for a "long" time. (On the otherhand busy waiting does not require a context switch.)
      • The solution is for processes to block while waiting, by moving onto a waiting list and changing status to "waiting". When the critical section becomes available, the process can be moved back to the ready queue, and wakeup. (Slide 6.18-19)
      • The wait and signal codes are short critical sections, protected by a busy waiting lock
  • Classical problems of synchronisation
    • Bounded buffer (SGG Ch.6.5.1-28)
    • Readers and writers (SGG Ch.6.5.2-30)
    • Dining philosophers (SGG Ch.6.5.3-32, Slide Extra)
  • UNIX synchronisation (SGG Ch.21.5.2)
    • Semaphores
  • Preventing semaphore coding mistakes
    • Critical regions (SGG Ch.6.6-37)
    • Monitors (SGG Ch.6.7-43)
  • Deadlocks
    • What is it? (SGG Ch.6.4.3, Ch.7.1)
    • Deadlock characterization (SGG Ch.7.2-10)
    • Deadlock prevention (SGG Ch.7.3-13)
    • Deadlock detection (SGG Ch.7.6-31)
    • Deadlock recovery (SGG Ch.7.7)

Exam Style Questions

• Differentiate between a process and a program.
• Draw a diagram showing the five standard states of a process, showing how these are related and indicating what events cause a transition from one state to another.
• Name six items of information that are stored in a process control block.
• What are the ready queue and IO device queues used for?
• What is a context switch?
• What three steps does the dispatcher perform when swapping a new process onto the CPU?
• Define dispatch latency.
• What is "cascading process termination"?
• What are the three components of a thread? What does a thread share with other threads in the process?
• What is the main advantage of using threads over multiple processes?
• What is the difference between user level threads and kernel supported threads?

• What do the long-term and the short-term schedulers do in an OS?
• Describe what is meant by CPU-bound and IO-bound processes. What are the characteristics of their CPU bursts?
• What is the task of the CPU scheduler, and what is its primary goal?
• List the four situations when a CPU scheduling decision has to be made.
• Explain the difference between preemptive and non-preemptive CPU scheduling.
• List five criteria by which CPU scheduling may be judged, indicating in each case whether the aim should be to minimize or maximize the criterion.
• Explain what is meant by {CPU utlization,throughtput,turn around time, waiting time,response time} in the context of CPU scheduling.
• Given the following list of process arrival, process priority, and CPU burst times, draw a Gantt chart (showing which process is using the CPU at what times) for the {FCFS,SJF-preemptive,SJF-nonpreemptive,priority-preemptive, priority-nonpreemptive,round robin (quantum = N),} CPU scheduling algorithm. In each case compute the average waiting time for the processes.
  [Make up your own examples]
• Which CPU scheduling algorithm suffers from the convoy effect?
• Using exponential averaging with A% history factor (alpha) and an initial estimated CPU bust of I microseconds, to predict the CPU burst times ahead of the following sequence of observed CPU burst times.
  [Make up your own observed CPU burst times]
• What problem may priority scheduling suffer from?
• What problem may fixed priority multi-level scheduling suffer from?
• What factors parameterize multi-level feedback queue CPU scheduling?
• Differentiate between hard real-time and soft real-time CPU scheduling.

• What four advatnages may be achieved by allowing processes to cooperate?
• Provide an algorithm for the producer-consumer problem, using shared memory. You may leave one buffer position empty or use explicit synchronization.
• What are the two basic operations in message passing?
• Explain the difference between {direct and indirect, symmetric and asymmetric, buffered and unbuffered, pass by copy and pass by reference, fixed and variable message size, synchronous and asynchronous} message passing.
• Differentiate between simplex, duplex, and full-duplex IPC.
• In direct message passing IPC, how many processes can be associated with each link?
• In indirect communication, where are messages directed to and received from?
• What is the relationship between buffering and synchroneity in IPC?
• Explain how timestamps can be used to cope with lost messages in IPC.

• Describe what is meant by a "race condition", and explain how one may cause a critical section problem.
• Define the critical section problem.
• What three conditions must be met by a solution to the critical section problem?
• Explain the {mutual exclusion,progress,bounded waiting} condition for a solution to the critical section problem.
• Explain why the following algorithm, when executed concueently by processes P₁ ... P_N, does not solve the critical section problem.
  [Some half-baked algorithm]
• Give an algorithm that provides a software solution to the critical section algorithm for two processes.
• How many processes may be run concurrently using the Bakery algorithm, while meeting the conditions for a solution to the critical section problem?
• Give two reasons why disabling interrupts is an unsatisfactory hardware solution to the critical section problem.
• Give the algorithm for the Test-and-Set instruction used for solving the critical section problem.
• The following algorithm uses the Test-and-Set instruction to (attempt to) solve the critical section problem. Does the algorithm meet the requirements for a solution? If not, explain.
  [One of the algorithms using Test-and-Set]
• Give the algorithm for the Swap instruction used for solving the critical section problem.
• Define the two operations defined on a process synchronization semaphore.
• Differentiate between a binary and a counting semaphore.
• Give an algorithm using a binary semaphore, that can be executed concurrently by multiple processes, that solves the critical section problem.
• Give an algorithm showing how a counting semaphore may be used to control access to a limited number of a given resource, e.g., a limited number of printers.
• Give an algorithm showing how a semaphore may be used to synchronize two processes.
• Show how a binary semaphore can be implemented using the {Test-and-Set,Swap} instruction.
• Show how a counting semaphore may be implemented using binary semaphores and an integer variable.
• Show how a counting semaphore may be implemented using the {Test-and-Set,Swap} instruction and an integer variable. What critical weakness does such an implementation have?
• Show how a counting semaphore can be implemented using binary semaphores and an integer variable, without incurring any long busy-wait conditions.
• Briefly describe the {bounded buffer,readers and writers,dining philosophers} problem, often used to test synchronization primitives.
• What is the format of critical region statement? Under what conditions does a process successfully enter a critical region statement?
• Do critical region statement eliminate all types of synchronization errors?
• Draw a picture showing the structure of a monitor. Annotate your picture to briefly explain what each component does.
• How many processes may be active in a monitor that contains N procedures?
• What happens when a condition variable in a monitor is signalled, if there are some processes waiting on the condition variable?

• What is the deadlock problem?
• What four conditions must hold for a deadlock to occur?
• Explain the {mutual exclusion,hold and wait,no preemption,circular wait} condition for deadlock to occur.
• Given the following resource allocation graph, is there necessarily a deadlock?
  [Some resource allocation graph]
• What is the most common approach to deadlocks taken by contemporary operating systems?
• Explain two ways the hold and wait condition for deadlock can be prevented from arising.
• Explain how the circular wait condition for deadlock can be prevented from arising.
• Given the following initial resource allocation and availability, determine whether or not deadlock will necessarily occur? Show all steps of your working.
  [Some initial allocation and availability]
• What are two possible actions an OS may take when a deadlock is detected?