CS 111 Scribe notes • January 30, 2013

Contents

Interrupts & Signals

Uninterruptible power supply (UPS)Motivating Example: The computer is connected via USB to an uninterruptible power supply (UPS). How should the kernel deal with running out of power?

One solution: Take a snapshot of RAM, CPU registers and copy them to the disk. Then, shut off power. When power comes back on, reverse the process and restore everything as if the programs never noticed the power interruption.

What's wrong with this?

How to inform user processes of the situation

  1. Polling
    Use a file /dev/power. Read from it. If the file reads "!", power is low. If it reads " " (a space) power is OK.

    For every program that cares about power, and every loop that might execute for more than a few seconds, insert a check for /dev/power. This is not a satisfactory solution. It's a pain to program, and will chew up CPU time.

  2. Signals
    With signals, the kernel "magically" inserts a check into the program when the power gets low. A signal handler receives the signal from the kernel and takes the necessary steps to fix the situation.

Motivations for Signals

Example: Press ^C into a terminal to abort a process (this one takes a bunch of zeroes and throws them away).

$ cat /dev/zero > /dev/null
^C
$

The terminal driver informs the operating system of the ^C. The operating system sends SIGINT to all processes with this terminal as the controlling terminal.

Signal handling is a bit of a mess. They should only be used when other means of communication fail.

Signals vs. Other means of communication

Example: Using the kill command (kill -USR1 391) vs. sending a message with a pipe (echo x | ...) to end a process.

Signals change how our abstract machine works

When a signal arrives to a process, it acts as if it inserts an asnchronous function call between any pair of instructions.

This following is an example of a signal handler. When the process receives the SIGINT signal, it prints "ouch!" and exits. Programs don't neccessarily have to define a signal handler. The default action associated with SIGINT is to exit.

Signal handler 1:

#include <signal.h>

/* defines a new signal handler,
   returning the old one if any */
signal(SIGINT, handle_int); 

void handle_int(int signal)
{
    printf("ouch!\n");
    exit(1);
}

This signal handler has some potential issues. Internally, printf() (part of the stdio library) maintains output buffers. This means that it calls malloc() to allocate memory in the heap. If this signal arrives during a normal call to malloc() in the normal application code, there is a possibility that the signal handler's call to malloc() from printf("ouch!\n") can corrupt the heap and crash the program. Remember, signals can arrive between any pair of instructions!

To illustrate this, let us imagine that our heap is a simple array, and malloc() is implemented as follows.

char h[1000000]; // heap
char *hp; // heap pointer
char *hl; // heap limit
 ____________ ____________________
| used space |     free space     |
|____________|____________________| 
^h           ^hp                  ^hl

inline void *malloc (size_t s)
{
    char *r = hp;
        // what if SIGINT arrives here?
    hp = hp + s;
    return r;
}

Suppose we have an ordinary malloc() call in our application, and then a SIGINT signal immediately arrives after the char *r declaration within malloc(). The signal handler will issue a call to printf(), which in turn also calls malloc(). This call will allocate space at the same hp value, because the previous call to malloc() did not increment the heap pointer yet. If the signal returns, the original call to malloc() no longer has a valid heap pointer.

This means our signal handler must limit to asynchronous signal safe functions (async-signal-safe). This even excludes our call to exit(), because it flushes all output buffers before exiting the process. To account for these possible issues, we must rewrite our original handler as follows, using the write() and _exit() system calls instead.

Signal handler 2:

#include <signal.h>

signal(SIGINT, handle_int);

void handle_int(int signal)
{
    write(STD_ERR_FILENO, "ouch!\n", 6);
    _exit(1);
}
Async-signal-safe functions

The following functions are defined by POSIX.1-2004 to be async-signal safe (as described above).

_Exit()             fexecve()       poll()                sigqueue()
_exit()             fork()          posix_trace_event()   sigset()
abort()             fstat()         pselect()             sigsuspend()
accept()            fstatat()       raise()               sleep()
access()            fsync()         read()                sockatmark()
aio_error()         ftruncate()     readlink()            socket()
aio_return()        futimens()      readlinkat()          socketpair()
aio_suspend()       getegid()       recv()                stat()
alarm()             geteuid()       recvfrom()            symlink()
bind()              getgid()        recvmsg()             symlinkat()
cfgetispeed()       getgroups()     rename()              tcdrain()
cfgetospeed()       getpeername()   renameat()            tcflow()
cfsetispeed()       getpgrp()       rmdir()               tcflush()
cfsetospeed()       getpid()        select()              tcgetattr()
chdir()             getppid()       sem_post()            tcgetpgrp()
chmod()             getsockname()   send()                tcsendbreak()
chown()             getsockopt()    sendmsg()             tcsetattr()
clock_gettime()     getuid()        sendto()              tcsetpgrp()
close()             kill()          setgid()              time()
connect()           link()          setpgid()             timer_getoverrun()
creat()             linkat()        setsid()              timer_gettime()
dup()               listen()        setsockopt()          timer_settime()
dup2()              lseek()         setuid()              times()
execl()             lstat()         shutdown()            umask()
execle()            mkdir()         sigaction()           uname()
execv()             mkdirat()       sigaddset()           unlink()
execve()            mkfifo()        sigdelset()           unlinkat()
faccessat()         mkfifoat()      sigemptyset()         utime()
fchmod()            mknod()         sigfillset()          utimensat()
fchmodat()          mknodat()       sigismember()         utimes()
fchown()            open()          signal()              wait()
fchownat()          openat()        sigpause()            waitpid()
fcntl()             pause()         sigpending()          write()
fdatasync()         pipe()          sigprocmask()

Blocking signals

For some critical sections of your code (where receiving a signal can cause the program to crash), there is a built-in way to wait to receive signals until later. This is called blocking the signal.

Any code enclosed in the proper calls to sigprocmask() will be executed without any of the asynchronous function calls that signals enable and can help ensure that a code segment is executed atomically.

Blocking/unblocking

To block/pause signals, the first argument of to sigprocmask() must be SIG_BLOCK. The second argument is a sigset_t type that describes what signals to block. (Read the manual page about how to interact with sigset_ts.) And the final argument is the old set of blocked signals (i.e. the old sigset_t.)

To unblock all signals, make the function call:

sigprocmask(SIG_SETMASK, &0, 0);

Downsides

Since it's so easy to block and unblock signals, why doesn’t every program use them? Take malloc() for instance; it has very critical code that manages the heap. If it is interrupted, the program may corrupt the heap and crash. But it doesn't block signals for a few reasons…

So what's the solution? Programs can ignore signals/handlers altogether to avoid these issues but programs should have some response to signals. Perhaps the most elegant solution is to have the signal handler set a global variable (volatile bool sig_alert_set = true) then exit and have the main function/loop check periodically (when safe) for received signals. (Note the volatile keyword is important to prevent the compiler from optimizing the variable away or using a cached version.)

Threads

Compared with Processes

Important System Calls

int pthread_create (pthread_t *thread,          // Identifies the thread.
                    const pthread_attr_t *attr, // Options for making the thread.
                    void *(*fn)(void *),        // The thread executes this function...
                    void *arg);                 // ...given this argument.

This function creates a new thread. It is similar to the fork function for processes but the new thread begins in a different fuction. If successful, pthread_create returns 0. If unsucessful, it returns an error number.

int ptrhead_join (pthread_t id,    // Identifies the thread.
                  void *status);   // Stores the return value of the thread.

This function joins the calling thread with the thread given in the argument. It’s similar to the wait function for processes. If the thread is still running, then the caller waits for the thread to terminate. If successful, pthread_join returns 0 to the caller. If unsuccessful, it returns an error number.

int pthread_exit (void *status);   // Exits the thread returning ’status’
This function exits the calling thread with a status of ’status’. It is similar to the exit function for processes.

Things a Thread Can Do

  1. Perform computation

  2. Busy wait: Continually check for some condition. This consumes CPU cycles, but it continues as soon as the condition is met.

    while (device_is_busy ()) continue;

  3. Yield: Transfer control to another thread, and return here later. This consumes less CPU cycles than the busy wait, but it increases the device latency

    while (device_is_busy ()) pthread_yield ();
  4. Block: Yield and tell OS "I am waiting for device x." OS will not wake thread until device is ready.

Types of Multithreading

Cooperative Multithreading

In this model, the thread decides when to give up the CPU. In order for this method to work, threads should yield every now and again to allow other threads to continue processing. If a thread forgets to yield, then there is a bug in the program. This method is simple and avoids many data races,but it opens the door for many ”forget to yield” bugs.

Preemptive Multithreading

In this model, the scheduling of threads is handled by the operating system. Linux uses this model of multithreading. An example of this strategy would be running each thread 10 miliseconds at a time. With this method, there is no ”forget to yield” bug, but the performance is less predictable, because a thread-switch can occur anywhere.

Multithreading and Signals

When a multithreaded process receives a signal, the kernel chooses a thread which isn't blocking the signal, and sends it there. You cannot control which thread will receive the signal, but you can block certain signals on all but one thread. This single thread will then receive all signals.

Scheduling

This is the first of a two-lecture series. See the next week’s lecture notes for more discussion of scheduling.

Machines have limited resources (CPU cores, memory, bus bandwidth, etc.). When dealing with CPU cores, the operating system needs a system to decide who goes first.

Policies

Policies are the high-level algorithm used by a scheduler. Since schedulers run so often, good schedulers are fast and have desirable metrics.

Many of the metrics we use today are from automobile production. The graphic below illustrates some of the common metrics used if one factory receives an order for Model T’s and Model A’s.

Automobile Manufacturing Metrics

Since car production scheduling and thread/process scheduling are so similar, many of the terms remain unchanged. Some other common time metrics are…

Some other general metrics are…

Sometimes some metrics, especially resource/CPU utilization are kept lower than needed to save capacity for emergencies and non-characteristic system usage.

Mechanisms

Mechanisms are the low-level ways of switching a running thread. This is analagous to an operating system’s methods of switching between processes.

Each process that has threads has a thread table, a table similar to the operating system’s process table. Stored in the thread table are a thread’s ID, its registers, and more.

To implement a context switch from thread T to thread U…

  1. Control must return to the operating system. Either the thread’s time slice expires or the application directly calls an operating system interrupt: 
    int 0x80
  2. Now that the operating system is in control, it must save all of T’s registers (saved on the stack during the interrupt instruction) into the thread table.
  3. By now, T’s state is backed up in the thread table so U’s state (registers and instruction pointer) should be copied from the thread table to the appropriate place on the stack.
  4. The operating system calls reti to return the CPU to user mode and continue execution of U.
↑ Top