CS 111: Operating Systems Principles

Scribe Notes for 2/5/13

Scheduling Policies

Overview

Scheduling policies are the methods that your operating system uses to choose what processes to run at a given time. There are many different approaches to this problem. We'll be looking at a few and comparing their benefits and drawbacks...

One key aspect of scheduling policies is fairness. A scheduling policy is defined as fair if every process that requests to be run will eventually be run.

First Come First Served

The first policy we will examine is "first come first served" or FCFS. This is where processes are scheduled solely on arrival time. The first process scheduled will be the first to run. This policy is fair if every process terminates. If not, the non-terminating process will be run forever, leaving any processes that arrived after it to wait forever. Below is an example of how one CPU would divide its clock cycles for this scheduling policy. Each column represents a separate clock cycle and A, B, C, and D each represent an individual process. A has a runtime of 5, B has a runtime of 2, C has a runtime of 9, and D has a runtime of 4.

The table below shows the timing characteristics of this scheduling example:

Shortest Job First

The FCFS scheduling policy also favors longer jobs, giving them a disproportionate amount of clock cycles compared to shorter jobs. "Shortest job first" or SJF is a policy that avoids this issue. After they arrive, processes are arranged to run in order of least required clock cycles to greatest. This fixes the problem of short jobs waiting a disproportionately long time compared to longer jobs, but introduces a new issue; it isn't a fair scheduling policy. If a long job is waiting to be run and shorter jobs continuously arrive, the longer job could wait indefinitely. The tables below show how the CPU will divide its clock cycles amongst the different processes and the timing characteristic of each of these process. The runtimes are the same as the previous example.

The table below details the timing characteristics of this scheduling example:

We'd like to create a system that is fair, but has an average wait time less than that of FCFS. We can sum the arrival time and the runtime of each process, inserting fairness into the SJF scheme. However, this has a longer average wait time than SJF, which minimizes wait time.

Round Robin

We make a large assumption that runtimes are known in advance in the case of the SJF scheduling policy. This will not always be the case. We can demonstrate two other scheduling policies that don't require this prior knowledge if we make a different assumption: preemption. Preemption is the ability for operating systems to interrupt processes before they terminate. Round robin scheduling is a policy that takes advantage of this ability, triggering an interrupt trap at a regular interval and switching to another runnable process. This policy can be described as a combination of FCFS and preemption, scheduling processes as they arrive and preempting to another process at regular intervals. The tables below illustrate the details of this process.

Below is a table showing the timing aspects of this scheduling example:

As you can see, this dramatically reduced the wait time of every process, eliminating it completely. However, the average turnaround time was made much worse.

Priorities

These scheduling policies follow different priority schemes: earliest, shortest, a combination of the two, and preemption. Priorities are characteristics used to determine the scheduling of jobs. These can be divided into two categories: external priorities and internal priorities. External priorities can be set arbitrarily, independent of inherent qualities of processes being run. For example, on a server used by the computer science department at a college, processes may have different scheduling priorities, dependent on who is running them. Sysadmins with the highest priority, faculty below them, and students with the lowest priority. Internal priorities are those dependent on characteristics of the jobs being run. The SJF and FCFS policies mentioned earlier rely on internal priorities (arrival time and runtime).

The "nice" Command

Linux features a command that can modify the priority of any runnable process: nice. Each process has a niceness integer associated with it, ranging from -19 to 19. This represents an external priority, where the greater the number is, the less aggressively scheduled the process is. Here are a few examples of usage:

$ nice make        # Adds 5 to the niceness of the command being run
$ nice -10 make    # Adds 10 to the niceness of the command being run
$ nice --10 make   # Subtracts 10 from the niceness of the command being run 
                   # This last command can only be done by the root

All the solutions for scheduling policies we demonstrated so far are significantly less than ideal. There are a few reasons for this inadequacy. First is that lack of information that schedulers must deal with. As mentioned before, the SJF policy cannot be enacted without prior knowledge of the runtime of the processes to be scheduled. Because schedulers are always running in the background of an operating system, they must execute rapidly and use a minimal amount of resources.

Why do schedulers really matter?

Schedulers are crucial in the case of real time scheduling. This is scheduling that interfaces with the real world, where processes must be run to coincide with events that occur in real life. Real time scheduling can be divided into two categories, hard and soft:

Hard

This is the less common of the two categories. It is used in circumstances where deadlines can never be missed, such as controlling the brakes in a vehicle or controlling critical functions in a nuclear power plant. In these circumstances, predictability is favored over performance. Systems that use hard scheduling will take measures to ensure predictability such as disabling the use of the cache and disabling the use of interrupts.

Soft

In soft scheduling, the more common of the two categories, the timing of processes is less critical and some deadlines can be missed. No extreme measures need be taken to ensure correct timing of execution. Earliest deadline first scheduling is one example a soft scheduling policy. In this scheme, the scheduler considers the time by which a process needs to be completed. If this time has passed, or if the process's runtime is long enough to prevent the system from making this deadline, the processes is ignored. Otherwise, the system chooses to run the process which needs to finish first. One might ask why we want systems to simply ignore processes whose deadlines have passed. In some applications, a late process is useless. Consider streaming an online video. Missing a frame will hardly disrupt the user experience, and sending the missed frame later on would not make much sense. Another example of soft scheduling is rate-monotonic scheduling. This is where higher priorities are assigned to more frequently run tasks.

In all the cases we've examined thus far, we have been dealing with one CPU. Scheduling policies become much more complicated when run on multiprocessors and in the case of cloud computing. These are complex problems for which ideal solutions are still being sought today.

Thread Synchronization

Motivation

It was mentioned in a previous lecture that one of the fundamental differences between threads and processes is that threads share a memory space while processes each have their own. This poses a potential problem: race conditions can occur when multiple threads are accessing and/or changing the same data elements. In order to solve this issue, we need to guarantee that threads are synchronized so that each thread is accessing the most up-to-date data.

Example

Consider the scenario: you've just graduated from UCLA with a degree in computer science and you were hired by Big Bank, LLC to write the code necessary for maintaining clients' accounts. Before you got there, someone else (who coincidentally went to USC) wrote the following code:

1   // Thread 1 
2   // Making a deposit         
3   long balance;
4   void deposit (long p) {
5     balance += p; 
6   }
7
8   // Thread 2
9   // Making a withdrawl 
10  void withdraw (long p) {
11    if (p <= balance) {
12      balance -= p;       
13      return 1; 
14    }
15    else
16     return 0;     
17  }

When running, the assembly of this C code may look something like:

  # Thread 1
  movl balance, %eax   # Load balance into %eax
  addl $10, %eax       # Add 10 cents to %eax
  movl %eax, balance   # Load %eax into balance

  # Thread 2
  movl balance, %eax   # Load balance into %eax
  subl $10, %eax       # Subtract 10 cents from %eax
  movl %eax, balance   # Load %eax into balance

Order Enforcement

When working with multiple threads, we have an observability requirement: as long as the user cannot tell a difference when multiple threads are being run and the execution has consistent behavior, the internal operation is left to the system. Consider a system running two threads: Thread 1 and Thread 2. Thread 1 is responsible for running arbitrary actions A1, B1, C1 , and D1 while Thread 2 is responsible for the actions A2, B2, C2, and D2. The time at which each action completes is random and unpredictable. Specifically, under our current system, we cannot know in advance whether A1 will finish before C2, or whether B2 will finish before D1. What we do know is that the threads themselves enforce the order in which their actions are implemented:

where t_Xk is the time at which thread k finishes action X. So long as these inequalities are satisfied, the system make execute any of the actions in parallel or wait for other actions to complete. That is, actions A1 and B2 may happen in parallel, or C2 may finish before D1. If the observed behavior is that of some sequence of operations that is consistent with what the threads themselves enforce, then the behavior is okay. For example, if the system schedules the threads such that

Cases 1 and 2 are okay, since the thread inequalities from Equation 1 are satisfied, but in Case 3, B2 finishes before A2, D1 finishes before B1, and C2 finishes before D2, each of which violates our observability requirement.

Atomicity vs. Isolation

If we want to guarantee that these conditions are met, we have a few options in how to run our threads. The simplest way to do this is atomicity, where everything involving shared memory is serialized, and thus we make sure that only one thread at a time has access to this shared memory. The second approach is isolation, where each thread runs in its own memory. Each method has its drawbacks, since atomicity is slow and isolation is inefficient. To have a secure approach, one must do both, with isolation being the default behavior and atomicity used if needed.

Critical sections can be used to enforce isolation. Only one critical section can have an instruction pointer pointing to it, which ensures that threads execute serially. But we also must watch out for compiler optimizations. Compilers often cache memory into registers. If signal_arrived is stored in the register, then we will never see the signal arrive. Thus, we use the keyword volatile to avoid compiler optimizations.

Our approach to atomicity varies depending on the characteristics of the machine on which it is implemented. First, we will consider a case where the machine has only one CPU and does not support interrupts or signals. Then, we consider a one-CPU system that allows for interrupts and signals to function. Finally, we consider the generic case of multiple CPUs with interrupts and signals.

Case 0: One CPU, No Interrupts or Signals

This is the easiest case to support, since we are only running one process at a time. When we run the command balance += p; no interrupts or signals can disrupt the process from running.

Case 1: One CPU, Allowing Interrupts and Signals

By introducing signals and interrupts into the system, we now could have a scenario where the handlers could interfere with the expected operation. For example, in the bank account management code, suppose the balance is loaded into register %eax, but before it is returned, a signal handler modifies register %eax and thus an unexpected or incorrect value is returned. Clearly, we want to guarantee that a program's behavior is predictable, so this issue needs to be resolved.

A potential fix would be to implement isolation by giving signal handlers their own memory space. Then, they would not be allowed to access or modify anything in the running process, only influence its operation, if desired. One way to do this is to have a signal handler modify a global variable and have the process check if the value changes.

1   // Global Variable that spontaneously changes from time to time
2   int signal_arrived; 
3 
4   // Signal handler that modifies global variable upon signal
5   void handle_sig(int sig){
6     signal_arrived = -1;
7   }
8
9   // Main process that checks global variable for any change
10  for ( i = 0, i < 1000000, i++) {
11    // Unless a signal arrives, continue running as normal
12    if (signal_arrived)
13      break;
14    // Maintain bank account  
15    compute(int);
16  }
17  // Do something special to acknowledge signal, then reset signal_arrived
18  signal_arrived = 0;

Note that the handler doesn't directly modify any of the 'important' data, like the balance. Instead, the main process checks to see if the signal was triggered, and alters its operation accordingly, if it chooses to do so.

While this is all very exciting, the reader may note that a race condition could exist. The compiler will optimize this code by storing signal_arrived in a register because it is frequently accessed. This means that the signal_arrived variable might be changed by the signal handler while the signal_arrived value stored in the register is being checked, effectively making the program miss the arrival of a signal. To avoid this race condition, signal_arrived can be declared as volatile. This tells the compiler to load the value from memory every time it is checked.

Case 2: Multiple CPUs

When we introduce multiple CPUs into the system, processes no longer need to interrupt one another. However, multiple threads can now be running simultaneously, meaning one thread can alter the data in another without interrupting that thread's execution. To ensure well-defined behavior, we must enforce that only one thread writes to a shared piece of memory at a given time, while no others access it. For this reason, it may be advantageous to create a way to freeze all the other CPUs and follow the same approach we developed for a one-CPU system.

This concept is referred to as locking, since we are reserving data elements to be used only by certain threads. Our data structure for implementing locking is known as the mutex, short for mutual exclusion. Using these, we can 'lock' and 'unlock' critical sections so that only one critical section can run at a time.

  lock(mutex_t*);
  unlock(mutex_t*);

Thus, for synchronized operation, we need to make sure that for an object o, we put a mutex around every critical section for that object. Before the critical section, the mutex must be locked, and after the critical section, the mutex should be unlocked. The implementation of these two functions is as follows:

1   typedef int mutex_t;
2   void lock (mutex*t m){
3     while (*m)
4       continue;
5     *m = 1;
6   }
7
8   void unlock(mutex_t* m){
9     *m = 0;
10  }

While we have good intentions for using mutexes to enforce synchronization, there are a few problems that can occur when locking:

1. Since there is only one lock, it would be impossible to obtain another. Therefore, the owner of a lock will spin forever if it attempts to acquire the lock again.
2. A thread may ignore a lock and continue execution anyway. Because it left to the thread to confirm it has the lock, it could irresponsibly ignore the mutex altogether and still execute a critical section.
3. A thread holds a lock indefinitely. If the thread does not unlock the mutex, no other threads may access critical sections. Thus, other threads would wait forever. More commonly, a thread may wait too long to unlock the mutex, leading to a bottleneck. Larger bottlenecks occur when a thread locks unnecessary code.
4. A race condition can occur when multiple threads try to get the same lock.

Because of these issues, we need to have a few rules for when we work with locking.

1. An owner of a lock must not lock again.
2. Only the owner of the lock may unlock it.
3. Owners of locks must unlock as soon as possible to avoid bottlenecks
4. We need a single atomic instruction to handle the race condition

Luckily there is an atomic x86 instruction, lock, designed for this purpose. One implementation is as follows:

L1: movl $1, %eax
    xchgl %eax, (%ebx)
    tstl %eax            # If zero, the thread has the lock. If nonzero, it doesn't
    jnz L1

The downside is that this instruction is slow, since the CPU needs to broadcast a signal saying it would like to be the only one to communicate with memory, thus blocking all other CPUs from doing so. That being said, the implementation also allows for unlock to work as long as the stores to memory are atomic and integers are aligned to a multiple of 4, which the compiler guarantees.