Concurrency issues

Mode and context

Context: execution of the kernel on behalf of user or for management (system)

                       process context
                              |
                              |
            application       |     system calls
            code              |     exceptions
  user                        |                        supervisor
  mode    --------------------+----------------------  mode
                              |
                              |     interrupts
             not allowed      |     system tasks
                              |
                              |
                       system context

int turn = 0;

void enterCriticalSection(int pid) {
     while (turn == 1-pid);
     turn = pid;
}

void exitCriticalSection(int pid) {
     turn = 1-pid;
}

int turn = 0;

int main(void) {
     if (0 == fork()) { /* child */
          enterCriticalSection(1);
          /* access the shared variable */
          exitCriticalSection(1);
     }

/* parent */

     enterCriticalSection(0);
     /* access the shared variable */
     exitCriticalSection(0);
}

The address spaces of processes are independent. Any shared access should be mediated by the kernel.

Universal IPC

Signals

Pipes

FIFOs

Pipes

The pipe system call returns two pipe descriptors: one for reading and the other for writing.

    int pipefd[2];

    pipe(pipefd);

// write to pipefd[1]
// read from pipefd[0]
// can be passed to child proceses

A FIFO is a named pipe. Use mkfifo to create fifos. Arbitrary processes can communicate using FIFOs.

Redirection and pipes

To implement a.out < foo, the shell

1. opens the file foo
2. makes descriptor 1 point to the descriptor of foo.

1. creates a pipe
2. makes descriptor 1 of a.out point to the read end of the pipe.
3. makes descriptor 0 of sort point to the write end of the pipe.

System V IPC

Semaphores

Message queues

Shared memory

System V IPC

Key

a user supplied integer that identifies the resource instance globally.

Creator

Owner

Permissions

rwx permissions

System V IPC Programming interface

creation

int semget(key_t key, int nsems, int semflg);
int shmget(key_t key, size_t size, int shmflg);
int msgget(key_t key, int msgflg);

The flags are IPC_CREAT, IPC_EXCL. The flags also include access permissions. The flags can be OR'ed as in IPC_CREAT|IPC_EXCL|0600.

control

int semctl(int semid, int semnum, int cmd, ...);
int shmctl(int shmid, int cmd, shmid_ds *buf);
int msgctl(int msgid, int cmd, struct msqid_ds *buf);

The commands are IPC_STAT, IPC_SET, IPC_RMID. The IPC_RMID is used for deleting the resource.

Global persistence

The IPC resource used by one set of processes can become visible to a totally unrelated process it it happens to use the appropriate key and if the protection is lax.

IPC resources remain allocated till they are explicitly deallocated. For example, one process can allocate a shared memory, store some data in it, and exit. Another process can start and read the data.

The kernel maintains only a fixed number of these resources. So it is possible for the kernel to run out of IPC resources if process fail to delate them after use.

Shared memory example

int *turn;

int main(void) {
    shmid = shmget(IPC_PRIVATE, sizeof(int), IPC_CREAT|0600); // create
    turn = (int *) shmat(shmid, NULL, 0); // attach
    if (!fork()) child();
/*  do something with turn */
    shmdt(turn);  // detach
    shmctl(shmid, IPC_RMID, NULL); // delete
}

void child(void) {
  /* use turn */
}

Semaphore example

static struct sembuf semDown[1] = {0, -1, 0}; // number, increment, flag
static struct sembuf semUp[1] = {0, 1, 0};
semid = semget(IPC_PRIVATE, 1, IPC_CREAT|IPC_EXCL|0600)

void enterCS() {
    semop(semid, semDown, 1);
}

void exitCS() {
    semop(semid, semUp, 1);
}

Naming

The system call ftok converts a file name to a key value. If the processes agree on a file name, then they can use this call to arrive at the same key and hence the same id.

Programming pointers

You should now make sure that this routine is executed when the program exits normally. You can register this routine with atexit so that it is executed when the program exits normally.

How do you take care of abnormal exits? You can register a signal handler for all possible signals which an cause the program to terminate. So the final code looks like this.

void releaseIPC(void) {
        /* release IPC resources */
}

void sigHand(int sig) { // signal handler
    exit(1);
}

int main(void) {
    /* declarations */

    atexit(releaseIPC);
    signal(SIGBUS, sigHand);
    signal(SIGSEGV, sigHand);
    signal(SIGQUIT, sigHand);
    signal(SIGINT, sigHand);

    /* real stuff */
}

Process overheads

creation

copying address space

communication

should be mediated by kernel

Some implementations use copy-on-write to optimize creation overhead.

Threads

         per thread resources             per process resources
           program counter                  address space
           stack                            global variables
           register set                     open files
           child threads                    child processes
           state                            timers
                                            signals
                                            semaphores
                                            accounting information

Threads scheduling is independent of process scheduling by the kernel.

Thread synchronization

mutex

binary semaphores

conditional variables

for event signaling

Reader/writer example

int full=0, empty=1;
pthread_mutex_t mutex;
pthread_cond_t cvFull, cvEmpty;

/* initialize mutex and condvar before use */

void producer() {
    pthread_mutex_lock(&mutex);
    while (full) pthread_cond_wait(&cvFull, &mutex);
    /*  enter item */
    pthread_cond_broadcast(&cvEmpty);
    pthread_mutex_unlock(&mutex);
}

/* destroy mutex and condvar after use */

Copy only the forking thread (fork1 system call).

Copy all the threads.

Signals and threads

1. Send the signal to each thread.
2. Appoint a master thread in each process to receive all signals.
3. Send the signal to any arbitrarily chosen thread.
4. Use heuristics to determine the thread to which the signal applies.
5. Create a new thread to handle each signal.

Stack growth problems. Each thread has its own stack.

Thread scheduling is done at the application level.

If any thread issues a system call, all the threads of the process block.

Thread implementations

Solaris

Cthreads

Classification

Thread: application level, not visible to the kernel

Lightweight processes: threads at the kernel level