CS 111

Scribe Notes for 10/20/09

Scheduling (continued)

Scaling: The Bigger Picture

When viewing scheduling in the "big picture", we assume we are operating on a grid or cluster. These grids or clusters can contain medium sized nodes who all have CPU-bound jobs that need to be handled. This type of scheduling differs from FCFS, SJF, and RR in the following ways.

• Admission policy- jobs can be rejected
• Priorities- jobs are ordered in queues according to priority
• Share-based scheduling

Priority Scheduling

Usually, the lower number the priority, the higher a process is in the queue. A job with priority 1 will be run ahead of job with priority 3. However it is a good idea to verify how priority is defined in the system you are working in as this may not be the standard. There are two types of priorities:

• external priorities- these are set by the user/sysadmin,
• internal priorities- these are set by the scheduler/OS
  • a process that uses lots of disk and RAM will usually be assigned low priority
  • a process that is well behaved and system friendly will usually be assigned high priority
  • 'yield's can be strategically used by programmers to give their code higher priority

Sidebar on Priorities

In general, priority number is not equal to precedence. One workaround for this can be seen in Unix, which implements priority using "niceness". A job with niceness 1 is higher priority than a job with niceness 2, and the default for most processes is 0. The difference however is that there can be negative niceness, or very high priority.

$ nice +5 cat foo            // runs "cat foo" with a niceness 5 greater than
$ nice -5 firefox              // setting negative niceness is prohibited unless root

Realtime Scheduling

Hard Realtime Scheduling

Hard realtime schedulers involve hard deadlines, which means that all deadlines have to be met. In this instance, developers of apps and the kernel ensure that all deadlines are met. This type of scheduling is used for example in brake systems of cars, where a program response to a brake signal requires say a 10 ms response time. Repeatability is crucial and more important than speed in hard realtime schedulers. Developers can turn cache off to achieve this.

Soft Realtime Scheduling

Soft realtime schedulers allow deadlines to be missed. When it is overloaded with jobs, it skips the low-priority jobs and takes the hit in performance. For example, frame skips in media players are the result of soft realtime schedulers. If the streaming deadline of a packet is missed, it results in the frame skip (hit in performance).

Types of Schedulers

• Earliest deadline first- longer processes may starve if small jobs with early deadlines keep getting scheduled before them
• Rate-monotonic- jobs that run more frequently are assigned higher priority

Synchronization

The difficulty in synchronization is when race conditions arise. Consider the following example on pipes. (We use simplifying assumption that all I/O to pipes is 1 byte)

1    enum { N = 512 };
2    struct pipe {
3        char buf[N];
4        size_t r, w;
5    };
6

    buf             data             
         ------------------------------------------------
        |          |//////////////////|                   |
         ------------------------------------------------
	       ^r                ^w        

In this instance, the buffer wraps around. Can we say that the pipe is empty if r == w, and that the pipe is full if r == w? NO. Actual read pointer is r % N and actual write pointer is w % N. We also cannot use the same comparison to determine if it is full AND empty. Therefore we have to use the comparison r + N = w to determine if the buffer is full.

7    void write (struct pipe *p, char c){
8        p->buf[p->w++ % N] = c;
9    }
10
11
12  char readc (struct pipe *p){
13       return p->buf[p->r++ % N];
14  }

** Need to check if buffer full or empty before read/write **
busy-wait write
    while (p->w - p-> r == N) // buffer full
        continue;
    p->buf[p->w++ % N] = c;

busy-wait read
    while (p->w - p-> r == 0) 
        continue;
    return p->buf[p->r++];

Critical Sections

A critical section is a set of instructions, such that indivisibility is preserved if at most 1 thread's instruction pointer is in the set at any given time. Critical sections are implemented through mutual exclusion. Mutual exclusion means that when one guy goes in, everyone else stays out. This prevents race conditions from occuring. They are also implented using bounded wait. This means that if someone is trying to get into the critical section, there must exist an upper bound or timed wait to prevent starvation.

Mechanism

The underlying principle involves a uniprocessor, system calls and interrupts. We assume that syscalls will either fail or schedule another task and not wait indefinitely in the case of an error. What we want is read-write coherence, in other words:

1. Multiple writers cannot access the same piece of data simultaneously.
2. Data accessed by readers must be current and not revisable when being read.

The following pseudocode represents instructions we wish to execute atomically:

store byte into register
load word
change a byte in word
store word

void lock() {
	while (xchg(&locked, 1)) // xchg swaps values atomically
		continue;
	}
}

Implementing Spinlocks

Spinlocks are used when multiple threads need to run. Only a thread that has the lock may run, while other threads wait for it to be available. This is useful only when threads aren't likely to be hanging (waiting) for long durations. Implementation is as follows:

typedef int volatile mutex_t;

void lock(mutex_t *m) { // precondition: must NOT own lock
	/* 
	we need to do this atomically:
		while (*m) continue;
			*m = 1;
	*/
	
	while (xchg (*m, 1) == 1))
		continue;
}

void unlock(mutex_t *m) { // precondition: must own lock
	*m = 0;
}

Atomic instructions must be used when data needs protection from multiple threads of access. A real life analogy would be that of a bank account shared by two people. Even though both may attempt to access and change the value of whats in the account simultaneously, the account cannot cater to both at the same time and must atomically change its value so that read-write coherence is maintained. Implementation would look something like this:

struct account {	// underlying assumptions: loads and stores aren't reordered
	...
	long long balance;
	...
	mutex_t lock;
}
...
// snippet of code in action:
lock(&p->lock);
p->balance -= 8000;
unlock(&p->lock);

Coarse-grained vs. Fine-grained Locking

Coarse-grained locking

• One lock used for multiple critical sections
• Less costly to implement; simpler in general
• Not scalable; more applications mean more threads waiting on a single lock, meaning more bottleneck

Fine-grained locking

• More parallelism
• More costly
• Scalable; on bigger applications this wins out over coarse-grained locking

Minimizing Critical Sections

We don't want critical sections to be too large since locking and unlocking large sections of code halts threads, leads to contention and produces bottlenecks. Alternatively we cannot have critical sections that are too small; they must be big enough to include all necessary and delicate code so that values that can be accessed both inside and outside the critical section don't cause race conditions or contention.

How to find a minimal critical section

• look for writes to shared objects ("shared writes")
• look for reads used to compute those share writes ("dependent reads")
• put lock() and unlock() around smallest region containing these

Blocking Mutexes

Blocking mutexes avoid polling by telling the OS what lock a specific thread is looking for. Example:

typedef struct {
	mutex_t m;	// controls access to this lock
	proc_t *blocked_list;
	bool locked;	// someone has the lock
} b_mutex_t;

void acquire (bmutex_t *b) {
	for (;;) {
		lock(&b->m);
		// add self to blocked_list
		...
		if (!b->locked)
			break;
		unlock(&b->m);
		schedule();
	}
	b->locked = true;
	// remove self from p->blocked_list
	...
	unlock(&b->m);
}

void release (bmutex_t *b) {
	lock(&b->m);
	b->locked = false;
	// mark 1st process (if any) in p->blocked_list as P_RUNNABLE
	// can either notify 1st process or notify ALL processes
	...
}

Semaphores

Semaphores were the first type of blocking mutexes. Its data structure contains a lock that is an integer. Its considered unlocked when the lock is greater than zero, and locked when it is equal to zero. The lock decrements everytime it is taken by a thread. Instead of acquire and release, P and V are used, respectively.