CS471/571 - Operating Systems

Lesson 8

copy-on-write pages

Normally when a fork() is performed, the pages of the new process are shared with the parent in a copy-on-write manner. When either the parent or child attempts to write to a page of memory, it is duplicated then made private in both processes. This is done to optimize the memory usage in the child process as often a fork() is quickly followed by an exec*() system call which will replace all the pages of the child process with the image of the new program.

Prior to the invention of copy-on-write pages, fork() needed to copy all pages of the parent to the child, which was an expensive operation which was wasteful in the event of a exec*() being called shortly after the fork(). To prevent this expense, Unix systems featured a vfork() system call (and still do though it is deprecated,) which shares the parents pages as shared memory while blocking the parent process until the exec*() call is performed. In Linux vfork() is special instance of a call to clone().

clone()

The clone() system call allows the parent process to control the aspects of the child process that will be shared with the parent or private to the child. It's probably not recommended to use clone() directly, however it is the means by which Linux implements the POSIX threads (pthreads) library.

The clone call allows the creation of threads that share the data and heap segments of the parent process (and many other aspects of the parent process) while still having their own private stack segment, allowing threads to work on the same global data as a singular program all the while operating as individual processes. Threads are one of the primary means of marshaling multiple CPUs in a system towards a singular task.

Shared memory pages

A memory page is shared between two or more processes (for our purposes a thread is a process, which are scheduled by the kernel in much the same way as any other process,) when the TLB entry for the processes' page points to the same real memory area. Memory can be shared via clone() or mmap() or via other means such as pipe(), socketpair() or other InterProcess Communications (IPC) mechanisms which use shared memory pages to communicate between processes.

pthreads

Reading: POSIX Threads Programming

In the pthreads library a single process will launch threads that share the same data and heap segments of the main process, but not the stack, which is private to each thread. Each thread will also share with its parent the following attributes:

Process ID and parent process ID
Process group ID and session ID
The controlling terminal
User and group IDs
Open file descriptors
Record locks (see fcntl(2))
Signal dispositions (this can make signal handling problematic, thus each thread maintains its own signal mask.)
File mode creation mask (umask(2))
Current directory (chdir(2)) and root directory (chroot(2))
Interval timers (setitimer(2)) and POSIX timers (timer_create(2))
Nice value (setpriority(2))
Resource limits (setrlimit(2))
Measurements of the consumption of CPU time (times(2)) and resources (getrusage(2))

In addition to the stack, the distinct attributes of a thread include:

A thread ID (the pthread_t data type)
Signal mask (pthread_sigmask(3)) (this allows threads to control which thread(s) receives signals)
The errno variable
An alternate signal stack (sigaltstack(2))
Real-time scheduling policy and priority (sched(7))

The following Linux-specific features are also per-thread:

Capabilities (see capabilities(7))
CPU affinity (sched_setaffinity(2))

Compiling with the pthreads library:

To use the pthreads library, include the pthread.h header file and link the library with the -lpthread command line switch:

gcc -o prog prog.c -lpthread

pthread_create()

#include <pthread.h>

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

Pthread create is the fork() equivalent for starting a thread. The start_routine is a C function that is entry point for the new thread. The arg parameter is passed to the start_routine function as its only parameter. Usually the arg parameter is a pointer to either an integer or structure that may contain the thread ID and/or some data for the thread to work on.

The thread parameter is filled in by the pthread_create() routine and is like a resource handle that represents the created thread. The attr parameter is for altering the default behavior of the thread and is created, but for now can be left as NULL to use the defaults.

A return value of less than 0 indicates failure to create the thread. Each thread counts as a full process against your process limit, thus attempting to spawn many threads could exceed that limit on the CS server.

Example:

void *run(void *tid)
{
  printf("Thread ID = %d\n", *(int *)tid);
}

int main(void)
{
  pthread_t th;
  int tid = 1;

  // Creates and starts the thread:
  pthread_create(&th, NULL, (void *)run, &tid);

  // waits for the thread to terminate:
  pthread_join(th, NULL);

  return 0;
}

Example of launching and joining multiple threads:

#define NT    4

int main(void)
{
  pthread_t th[NT];
  int i, tid[NT];

  for(i=0; i < NT; i++) {
    // The memory that contains the thread ID should be unique to each thread
    // thus we place the thread ids into an array.
    tid[i] = i;
    pthread_create(&th[i], NULL, (void *)run, &tid[i]);
  }

  for(i=0; i < NT; i++)
    pthread_join(th[i], NULL);

  return 0;
}

pthread_join()

int pthread_join(pthread_t thread, void **retval);

The pthread_join() function is the wait() function for threads, it blocks the controlling thread until the thread given by the thread resource handle exits. A thread can optionally return a pointer to a return value in retval, and if no return value is required, a NULL can be specified. There are limitations on the memory location of said return value, discussed below.

pthread_exit()

void pthread_exit(void *retval);

Causes a thread to exit immediately. The retval pointer must point to a memory area in the heap or BSS/data sections as the stack for a thread is local to the thread and becomes invalid on exit.

Mutual Exclusion - Mutexes

Reading: Mutex Variables

In a multi-threaded application data sections are shared between threads and so it becomes possible for one thread to modify a data-structure while another thread may be attempting to access it. In pthreads one of the ways we can "protect" data sections from being modified by other threads via the use of a mutex.

Mutual Exclusion is the notion of ensuring that only one thread at any given time may have access to a particular region of code, this does not necessarily protect a particular region of data, but by restricting access to the regions of code that modify that data, we might "serialize" access to the data, preventing multiple threads from attempting to modify the data at the same time.

To protect a data section a mutex is created (and initialized), then a lock is obtained on the mutex by one (and only one) of the threads, which then can then enter into the code region to read/modify the data, then unlock the mutex allowing another thread to obtain the lock, thus a mutex is used to protect the data section in an area of code called a critical section.

Mutex variables should obviously be available in a global data section available to the threads that will use it, so should not be in the threads local stack.

Mutex init:

int pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrict attr);

or

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

The pthread_mutex_init() function takes the address of the mutex variable to initialize and an optional attr which may modify the behavior of the mutex, for now however we will use the defaults which can be specified by using NULL for the attr.

Example:

pthread_mutex_t m1;

pthread_init_mutex(&m1, NULL);
// Mutex variable 'm1' is ready to be used.

// Alternatively, you can define and initialize it in one statement:
pthread_mutex_t m2 = PTHREAD_MUTEX_INITIALIZER;

Mutex locking:

int pthread_mutex_lock(pthread_mutex_t *mutex);

This function will block the thread until a lock is obtained on the mutex variable. Once a lock is obtained it must be unlocked by the locker to allow other threads to obtain the lock themselves.

int pthread_mutex_trylock(pthread_mutex_t *mutex);

This function attempts to obtain a lock and if successful, returns success (return value of 0), if unsuccessful, returns failure (< 0 return), but never blocks the thread.

int pthread_mutex_unlock(pthread_mutex_t *mutex);

This function releases the lock, it should only be called by the thread that obtained the lock and only after it is done working in the critical section.

Example:

// The mutex variable is global, i.e. available to all threads:
pthread_mutex_t lock;

void *run(int *tid)
{
  // Non-critical section code...

  pthread_mutex_lock(&lock);

  // Critical section code...
  // Only one thread is allowed into this code region at any given time by
  // the mutex lock obtained above.  The lock is like closing the door to
  // this code area.

  pthread_mutex_unlock(&lock);

  // The unlock above is like opening the door to the critical section
  // allowing the next thread to enter.
  // Non-critical section code...
}

int main(void)
{
  pthread_t th[NT];
  int tid[NT];

  // Initialize the mutex variable before launching threads that will use it:
  pthread_mutex_init(&lock, NULL);

  for(int i=0; i < NT; i++) {
    tid[i] = i;
    pthread_create(&th[i], NULL, (void *)run, &tid[i]);
  }
  for(int i=0; i < NT; i++)
    pthread_join(th[i], NULL);

  return 0;
}