CS111: Lecture 7 - Signals, Threads, Intro to Scheduling

The interrupt handler that we just wrote is buggy!

Internally, printf (which is a part of standard I/O):

• buffers output
• maintains output buffers
• calls malloc which manages the heap

The problem: suppose some ordinary code contains:

printf("yay!");

Then printf will:

• buffer output
• maintain output buffers
• calls malloc

------Signal arrives!----------------

• call our interrupt handler
• handler calls printf

Problem!
printf calls malloc --> re-entering malloc!
program corrupts heap --> crashes!

The solution:

void handle_int( int sig ){
write(STDERR_FILENO, "ouch!\n", 6);
_exit(1);
}

Note that exit(1) causes problems the same reason printf does, so we use _exit(1) instead, which is a syscall

Limit ourselves to async-signal-safe functions!

Blocking Signals

Suppose heap is implemented simply as follows:

char h[1000000]; char *hp = h;

                                            
|  in use   |      free                    |
h           hp                             h

Malloc: inline void *malloc( size_t s){ char *r = hp; hp = hp + s; return r; }

Some Function:

somefn( ){ r = hp; hp = hp + s; }

- function modifies some global data structures

Problem! we want signal handlers to be able to see these structures

The solution:

somefn( ){
    sigset_t 0;
    sigprocmask(SIG_BLOCK, sigset_t s, &0);  -|
    r = hp;                                   |
    hp = hp + s;                              |----> Critical Section
    sigprocmask(SIG_SETMASK, &0, 0);         _|
}

int sigprocmask(int how, const sigset_t *set, sigset_t *oldset);

1. int how

   • SIG_BLOCK: adds set to the set of blocked signals

   • SIG_UNBLOCK: remove set from the set of blocked signals

   • SIG_SETMASK: set is the set of blocked signals

2. const sigset_t *set is the signals you want to change

3. sigset_t *oldest is the previous value of signal mask

Limitations:
- sigprocmask is a system call --> slows you down
- many applications get signals wrong:

1. program might create /tmp/foo, gets SIGINT but has no handler
       Problem!  /tmp/foo is leftover trash

2. program establishes a SIGINT handler
       signal handler does unlink("/tmp/foo")
       BUT program: - create /tmp/foo
                    - computes
                    - unlink("/tmp/foo")
                    ------Signal arrives!-------
   		 Problem!  unlink("/tmp/foo") again
   		 - exit
   		 Solution: 
                    - unlink("/tmp/foo")
                    - sigprocmask to block SIGINT
                    - exit
   		 - sigprocmask to unblock

Threads

Threads can be considered lightweight processes that perform tasks in parallel with other threads. Each thread has its own instruction pointer, registers, and stack which allow for multi-tasking. However unlike processes, threads running inside a process share memory, file descriptors, and other things such as the UID. Because of this lack of isolation, using threads creates a high risk for race conditions. If threads are implemented carefully, they have several advantages over multi-processing: threads are created more quickly than processes because utilize the current process's address space, switching between threads is quicker for similar reasons, and communicating between threads is quick because of their shared memory.

System Calls for Threads

The syntax to create a new thread is:

int pthread_create(pthread_t *threadID, const pthread_attr_t *attr, 
                     void *(*start_routine)(void *), void* arg);

This creates a thread with attributes attr and runs the function start_routine with arguments arg. Upon completion, pthread_create() stores the thread ID in *thread.
The function pthread_join() is used to prevent race conditions by suspending execution until the thread designated by threadID terminates via pthread_exit().

int pthread_join(pthread_t threadID, void *retVal);
void pthread_exit(void *retStatus);

On a sucessful join, the return value retVal is set to the value of retStatus.

Busy Wait vs Yielding

If a thread needs to wait for a device to be ready, a standard way is to insert a while loop that checks the status of the device.

while(device_is_busy)
	continue;

This example represents busy waiting (polling). The drawback polling is that the waiting thread hogs CPU that could be used for other threads. To fix this issue, threads can call the yield() function instead. This function gives up control CPU and allows another thread with high priority to run.

while(device is busy)
       yield();

Cooperative Threading

Cooperative threading is a technique that allows threads to decide when to give up its CPU for other threads. This model can simplify scheduling and reduce the amount of race conditions that occur. To implement proper cooperative threading, threads need to voluntarily give up control of the CPU every once in a while by yielding or blocking. A disadvantage to cooperative threading is that one thread can be uncooperative and keep control of the CPU if it is designed incorrectly.

Preemptive Threading ns or ms?

Preemptive threading uses a timer interrupt at the hardware level and acts like an interrupt instruction. About every 10 ms, the CPU traps and inserts a yield() into the program automatically. The kernel saves and restores contexts, including threads. This approach is much simpler than cooperative but has a more costly overhead. Since the yield() function is now automatically inserted, it can cause unpredictability in the code. Some task that we expect to run next can randomly yield() and run much later, which may result in race conditions.

Notice that cooperative threading is more structured for single-core computers because it is faster and simpler. Preemptive threading is more structured for multi-core processors because of the processor's need for more parallelism and locking.

Scheduling Issues

Threads and processes must deal with scheduling to produce the correct results. Different policies and mechanisms are used by the scheduler to help coordinate the different processes and threads.

Scheduling Policies

Scheduling policies are algorithms that are implemented to coordinate threads or processes to execute tasks correctly and efficiently. The scheduler needs to be quick in order to create the illusion of seamless executions and to maximize the efficiency of the CPU. The scheduler should also limit its use of RAM in order to keep itself invisible to the user. Because the typical user prefers speed over efficiency, the contrainst on RAM usage is larger, which limits the capabilites of the scheduler to more simple algorithms.

Scheduling Metrics

Scheduling metrics can be applied to processes in order to compare the performances of different scheduling policies.

Arrival Time: The time when a task arrives into the system.
Wait Time: How long a process needs to wait for it to begin its execution.
Response Time: How long it takes to produce an output after its initial arrival.
Turnaround Time: The total time between its arrival and its completion. This time is also refered to as the latency.
Context-Switching Time: The time it takes to switch from one task to another. Scheduling policies that rotate often, such as Round Robin, will waste lots of time in this category. This switching time applies to switches in threads and in processes.

By averaging these times, we can find the strengths and weaknesses of different scheduling policies. The goal is to find a policy that minimizes the average turnaround time. A low turnaround time represents good throughput, the amount of work a computer can do in a given period of time, and utilization, the ratio of the actual amount of CPU being used over the total CPU that can be used. Average wait time can be used to measure the fairness of the scheduler. A good scheduler will have a low average wait time.

Source: Masaki Moritani (Fall 2010)