Operating Systems, Spring 2015

Programming Assignment 3 - An Example Solution

Table of Contents

Introduction

This page presents a solution to the third programming assignment, which involves implementing the critical-section system calls csin, and csout.

Only additions to and significant changes of the previous assignment are shown here. Portions of the operating system that are largely unchanged from the previous assignment are omitted.

Critical Section Scheduling

One way to solve this problem is to have the operating system define a critical-section scheduler class to handle critical sections defined by processes. 
〈The critical-section scheduler〉=
Defines CriticalSectionScheduler (links are to index).


private class
CriticalSectionScheduler

  〈critical-section scheduler methods〉

  〈critical-section scheduler instance variables〉
The operating system can then create an instance of the critical-section scheduler class 
〈Operating system instance variables〉=
Defines criticalSectionScheduler (links are to index).

private final CriticalSectionScheduler criticalSectionScheduler =
  new CriticalSectionScheduler()
and use the instance to handle critical-section system calls 
〈critical section system calls〉=

case OperatingSystem.SystemCall.csin
  criticalSectionScheduler.enter(hw.fetch(1))
  break

case OperatingSystem.SystemCall.csout
  criticalSectionScheduler.exit(hw.fetch(1))
  break
The only thing left to do is figure out what goes in the critical-section scheduler. The critical-section system-call handlers assumed the methods enter() and exit(), so that seems like a sensible place to start.

Before getting to the methods, a small amount of thought about representing critical sections is needed. The tricky thing about critical sections as defined for this assignment is that they're dynamic: the calling process defines the critical section with a tag in the csin system call. But dynamic critical sections aren't that tricky: use a map from tags to a process queue.

The process queue associated with each critical section is the queue of clients for the critical section. In particular, the head of the queue, if it exists, is the process executing in the critical section. The processes behind the head of the queue, if any, are processes waiting to enter the critical section. 
〈critical-section scheduler instance variables〉= (←U)
Defines criticalSections(links are to index).
 
private final Map<Integer, Queue<ProcessDescriptor>> criticalSections =
  new HashMap<Integer, Queue<ProcessDescriptor>>()
The enter() critical-section scheduler method accepts a single parameter, which is the tag of the critical section the calling process is trying to enter. 
〈critical-section scheduler methods〉= (←U) [D→]
Defines enter (links are to index).

void
enter(int tag)

  // If this is the first time the tagged critical section is being entered,
  // create a representation for it.

     if !criticalSections.containsKey(tag)
       criticalSections.put(tag, new ArrayDeque<ProcessDescriptor>())

  // Hang the calling process on the critical section's client queue.

     final Queue<ProcessDescriptor> clients = criticalSections.get(tag)
     clients.add(runningProcess)

  // The csin system call always succeeds.

     hw.store(0, Hardware.Status.ok)

  // If the calling process is not at the head of the tagged critical section's
  // client queue, then some other process is in the critical section and the
  // calling process has to wait.

     if clients.size() > 1
       SystemSim.dmsg.print("criticalSection",
         "Process %d waits on critical section %d.%n",
         runningProcess.processID, tag)
       suspendRunningProcess()
     else
       SystemSim.dmsg.print("criticalSection",
         "Process %d enters critical section %d.%n",
         runningProcess.processID, tag)
The exit() method can fail, which makes is slightly more involved to implement than is the enter() method. 
〈critical-section scheduler methods〉+= (←U) [←D→]
Defines exit (links are to index).

void
exit(int tag)

  if !criticalSections.containsKey(tag)

    // If the tagged critical section doesn't exist, the calling process is
    // sadly mistaken.  The process should probably be terminated, but that's
    // not what the documentation wants.

       hw.store(0, Hardware.Status.noResource)

  else
    // Give the calling process its ok and clear the critical section for the 
    // next process, if any.

       hw.store(0, Hardware.Status.ok)
       remove(criticalSections.get(tag), runningProcess, tag)
And finally, if a process dies in a critical section, the critical section should be recovered so the next waiting process, if any, can gain the critical section. This is probably not an intelligent thing to do, because the dead process probably left the critical section in some undefined state. A process entering the critical section will probably find it a mess. However, dealing with this problem in general is impossible, and dealing with it in particular is hard, so taking the easy way out seems advisable. 
〈critical-section scheduler methods〉+= (←U) [←D→]
Defines clear (links are to index).

void
clear(ProcessDescriptor p)

  for Integer tag : criticalSections.keySet()
    final Queue<ProcessDescriptor> clients = criticalSections.get(tag)
    if ¬clients.isEmpty() ∧ (clients.element() ≡ p)
      remove(clients, p, tag)

When a process exits the system, make sure it releases any critical sections it may be holding.

〈Operating system methods〉=

private void
exitRunningProcess()

  criticalSectionScheduler.clear(runningProcess)

  storageBlocks.deallocate(
    runningProcess.startAddress(), 
    programBlockCount[runningProcess.programIndex])
  processQueue.remove(runningProcess)
  clearQuantum()

  if processQueue.processCount() ≡ 0
    hw.store(Hardware.Address.haltRegister, 0)
  else
    runProcess(processQueue.readyProcess())
Defines exitRunningProcess (links are to index).

Remove the critical-section queue head and let in the next process, if any. 

〈critical-section scheduler methods〉+= (←U) [←D]

private void
remove(Queue<ProcessDescriptor> clients, ProcessDescriptor p, int tag)

  SystemSim.dmsg.print("criticalSection",
    "Process %d exits critical section %d.%n", p.processID, tag)

  // Sanity checks.  The exiting process should be at the head of the client
  // queue.

     assert ¬clients.isEmpty() : "critical-section clients queue is empty"
     assert clients.element() ≡ p 
       : "running process isn't at head of critical-section clients queue"

  clients.remove()

  // If there's another process waiting for this critical section, get it
  // ready.

     if ¬clients.isEmpty()
       final ProcessDescriptor nextP = clients.element()
       SystemSim.dmsg.print("criticalSection",
         "Process %d enters critical section %d.%n", nextP.processID, tag)
       processQueue.resumeProcess(nextP)
Defines remove (links are to index).

Index

This page last modified on 2012 March 17.