W7 - Inter-Process Communication (IPC)

Class: CSCE-410-02159

Notes:

Interprocess Communication

• How do different threads communicate?
  • Threads of different processes (inter-process)
  • Threads within the same process (intra-process)

Ways to Communicate

• Shared Memory
  • Global variables, heap memory (threads only)
  • Shared memory in the kernel
  • Files
• Messages and Data Streams
  • Signals
  • Pipes
  • Sockets (UDP, TCP, UNIX)

Notes:

• UNIX sockets are essentially sockets that can only be used within the same machine (locally?) but they are a bit obsolete because we can always use TCP sockets

Communication through Files

• The bank account example
  • Your bank account balance is saved on a file
  • A periodic process withdraws an amount
  • Another periodic process deposits an amount
• What is happening here

1-account.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>


#define AMOUNT 10000

void withdraw(int amount){

  int balance;
  FILE *f = fopen("bank_account.txt","r"); // Open Bank Account
  fscanf(f, "%d\n", &balance);             // Read Balance
  fclose(f);                               // Close Bank Account

  balance = balance - amount;              // Withdraw Amount

  f = fopen("bank_account.txt","w");       // Open Bank Account
  fprintf(f, "%d\n", balance);             // Write Balance
  fclose(f);                               // Close Account
  exit(0);
}

void deposit(int amount){

  int balance;
  FILE *f = fopen("bank_account.txt","r"); // Open Bank Account
  fscanf(f, "%d\n", &balance);             // Read Balance
  fclose(f);                               // Close Bank Account

  balance = balance + amount;              // Deposit Amount

  f = fopen("bank_account.txt","w");       // Open Bank Account
  fprintf(f, "%d\n", balance);             // Write Balance
  fclose(f);                               // Close Account
  exit(0);
}

int main(void){
  int balance;
  pid_t pid1, pid2;
  FILE *f;

  pid1 = fork(); // fork a child process
  if (pid1 == 0) {
    deposit(AMOUNT); // Child deposits amount
  }

  pid2 = fork(); // fork a child process
  if (pid2 == 0) {
    withdraw(AMOUNT); // Child withdraws amount
  }

  waitpid(-1,NULL,0);
  waitpid(-1,NULL,0);

  f = fopen("bank_account.txt","r");
  fscanf(f, "%d\n", &balance);
  fclose(f);

  printf("Balance: %d\n", balance);

  return 0;
}

Notes:

• The parent simply creates 2 child processes, each makes a transaction to the account
• They both take an amount integer argument
• They open the bank account, read the balance, updates the balance, and writes back to the account
• Deposit is basically identical to withdrawal except for a + sign instead of a - sign.
• In this case if balance is not 0, there is a bug
• These transactions happen in parallel, and this is realistic because transactions in the real world can happen actually in parallel (at the same time)
• The outcome is that sometimes this works as intended and sometimes it does not, it is a bit unpredictable
• Notice this is implemented with files, which are quite slow
• What is happening?
  • Guess: race condition between the two children processes?

The same problem can also apply with threads: 2-threads_plain.c:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define AMOUNT 1
#define REPEAT 100000

int balance = 0;
pthread_t thread_id[2];

void* withdraw(void *input) {
  int i;
  for (i=0;i<REPEAT;i++)
    balance = balance - AMOUNT;
  pthread_exit(NULL); // Thread's job is done
}

void* deposit(void *input) {
  int i;
  for (i=0;i<REPEAT;i++)
    balance = balance + AMOUNT;
  pthread_exit(NULL); // Thread's job is done
}

int main(void) {
  pthread_create(&thread_id[0], NULL, withdraw, NULL); // create a thread
  pthread_create(&thread_id[1], NULL, deposit, NULL); // create a thread

  pthread_join(thread_id[0], NULL);
  pthread_join(thread_id[1], NULL);

  printf("Balance: %d \n", balance);
  return 0;
}

Notes:

• Performing transactions one by one with a for loop.
• We expect the same thing to happen here
  • The intended behavior is that if we withdraw/deposit the same amount and it starts from 0, it keeps being 0.
• Real behavior: Every execution gives you a different number!
• It is statistically very difficult to get the right answers
• Why this happens?
  • balance = balance - AMOUNT
  • This is not one step, but it is multiple steps
    • Read balance, perform subtraction, then update the balance variable
  • The problem is that the CPU can be given to another process by the scheduler at any point in time, if this happens between these 3 steps, then we end up in a situation where my local register has already updated the variable but maybe not yet written to memory and so on.
• In reality, these types of bugs are very difficult to find
  • They can escape testing very easily because it might be the case that the execution order you intended actually happens some times.

Murphy's Law

• A and B want to print a file
• A adds the file in the printing queue and increments the in counter
• B adds the file in the printing queue and increments the in counter
• Imagine the following happens:
  • A reads in and stores the value in a register
  • Scheduler stops A and starts B
  • B reads in and stores the value in a register
  • B enters file in position 7 and increments the counter
  • Scheduler stops B and starts A
  • A thinks the next available slot is 7
  • A enters file in position 7 and increments the counter
  • A overwrites the file of B
  • A prints the file
  • B is still waiting

Race Condition

• Race Condition is the situation where the outcome depends on the timing of process/thread execution (scheduling)

• Scheduling is effectively random (unpredictable and uncontrollable) from the perspective of process/thread

• A race condition leads to unexpected non-deterministic behaviour

  • Bugs that appear rarely and are hard to explain
  • Plain testing is not sufficient

Notes:

• Scheduling is so complex to predict that you can consider it being completely random
• = non-deterministic behavior
• The problem appears only when you write to the same resource

How do we avoid Race Conditions?

• Critical Regions
  • The parts of the programme where the shared memory, shared file, or other shared resource is accessed
• We avoid race conditions with mutual exclusion
  • Ensuring that when one process/thread is in the critical region, no other process/thread can enter the critical region
  • Locking (or acquiring) and unlocking (or releasing) the resource
• Example: A public toilet
  • Goal: Up to one person can use the toilet at any given time
  • Solution: Mutual exclusion with a lock
    • A person can enter the toilet only when it is unlocked
    • When inside the toilet, the person locks it before using it
    • Others cannot enter a locked toilet, they must wait
    • The person unlocks the toilet when exiting making it available to the others

Notes:

• We need to ensure that the process locking the resource unlocks it at the end so that other processes can use it after

Mutual Exclusion using Critical Regions

Notes:

• B waits for the common resource to be released
• Access to critical region happens sequentially because of the lock
• It is efficient to our code to keep the critical region as small as necessary
  • If I decide to lock the resource before I actually need to use it, or if I finish using the same resource and instead of unlocking it immediately we make something else and then unlock it later, this makes our code slower, you are creating a bottleneck.

Lock Variables

• Imagine process A and process B execute the following code

  • lock is a shared variable

• Is this safe from race conditions?

while(1) {
	if (lock == 0){
		lock = 1;
		critical_region();
		lock = 0;
		break;
	}
}

Notes:

• If other process tries to execute this block of code in parallel, it will keep looping there until the resource is release
• Did we fix the problem of race conditions?
  • No, the lock itself requires operations to be run, therefore it would need to be part of a critical region
    • For example imagine we check the lock (lock == 0) but don't get to actually lock it (lock = 1) when the scheduler changes to another process.
  • "A process might be stopped between the if statement and the lock = 1; statement."

3-threads_lock.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define AMOUNT 1
#define REPEAT 100000

#define UNLOCKED 0
#define LOCKED   1
int lock = UNLOCKED;

int balance = 0;
pthread_t thread_id[2];

void* withdraw(void *input) {
  int i;
  for (i=0;i<REPEAT;i++){
    while(lock == LOCKED);       // Block until is unlocked...
    lock = LOCKED;               // Lock
    balance = balance - AMOUNT;  // Access critical region
    lock = UNLOCKED;             // Unlock
  }
  pthread_exit(NULL); // Thread's job is done
}

void* deposit(void *input) {
  int i;
  for (i=0;i<REPEAT;i++){
    while(lock == LOCKED);       // Block until is unlocked...
    lock = LOCKED;               // Lock
    balance = balance + AMOUNT;  // Access critical region
    lock = UNLOCKED;             // Unlock
  }
  pthread_exit(NULL); // Thread's job is done
}

int main(void) {
  pthread_create(&thread_id[0], NULL, withdraw, NULL); // create a thread
  pthread_create(&thread_id[1], NULL, deposit, NULL); // create a thread

  pthread_join(thread_id[0], NULL);
  pthread_join(thread_id[1], NULL);

  printf("Balance: %d \n", balance);
  return 0;
}

Strict Alternation

• Process A and Process B take turns
  • When A exits the critical region gives the turn to B and vice versa
• Is this safe from race conditions?

while (TRUE) {
    while (turn != 0) /* loop */ ;
    critical_region();
    turn = 1;
    noncritical_region();
}

while (TRUE) {
    while (turn != 1) /* loop */ ;
    critical_region();
    turn = 0;
    noncritical_region();
}

Notes:

• Yes it is technically safe, it works well if the implementation has this logic of taking turns
  • But at this point you might have 10 withdraws/deposits back to back in the same account
• "Yes, but it has a problem. A process cannot enter the critical region twice in a row, thus a slow process would slow down a fast process. Also, a process may be stopped from entering the critical region with no reason!"

Hardware-based Solutions

• The source of the problem is that the process can be preempted between the instruction that checks the lock variable and the instruction that sets the lock variable
• If checking and setting were indivisible or atomic, all would be fine!
• Can the Hardware help?

Notes:

• In practice we use the hardware to solve this
• Checking the status of the locks are the problems, they are two steps.
• Ideally, if we have a way that we cannot be stop in between these 2 steps, then we can solve our problem.
• How can the hardware help?
• For a preemptive scheduler to work, we need to have interrupts
  • It gives the CPU to a process for some amount of time, before it gives it, it sets up a timer. If this timer ends, it takes the CPU back. This means the OS cannot take the CPU back from the processor.

Disabling Interrupts

• Disabling Interrupts
  • No clock interrupts, no preemption, no race conditions
  • Allowing the user to disable interrupts can be catastrophic
    • We can however implement locks at the kernel
    • See Contiki-NG OS
  • Works only in single-processor systems

while(1) {
	disable_interrupts();
	critical_region();
	enable_interrupts();
}

Notes:

• Interrupts are essentially a hardware triggered interruptions
• They schedule an interruption to the normal execution
• "Take the power away from the OS to schedule these interruptions"
• Note this doesn't work if we have multiple systems (for true parallelism)

Atomic Instructions

• Atomic Instructions
  • Lock variable do not work because the process/thread might be stopped in between testing and setting the lock
  • The TSL (Test and Set Lock) instruction ensures that testing and setting the lock is indivisible or atomic
  • The CPU executing the TSL instruction locks the memory bus to prevent other CPUs from accessing the memo

enter_region:
	TSL REGISTER,LOCK    | copy lock to register and set lock to 1
	CMP REGISTER,#0      | was lock zero?
	JNE enter_region     | if it was not zero, lock was set, so loop
	RET                  | return to caller; critical region entered

leave_region:
	MOVE LOCK,#0         | store a 0 in lock
	RET                  | return to caller

• This solves the problem of mutual exclusion
• But it still has one problem:
  • A performance problem
  • The processor that is waiting is in an infinite loop rechecking if the lock has been released every time
  • Every time we try and we fail, we are consuming energy and efficiency that other process could have better used

Spinlock and Busy Waiting

• Busy waiting is when a process/thread continuously tests a lock until it is unlocked
  • Continuously try to open the locked door of a public toilet
  • Problems?
    • Not very polite (in case of a public toilet)
    • Wasting CPU resources (in case of processes/threads)
• A lock that uses busy waiting is called a spinlock
  • Spinlocks are useful in multi-processor systems in cases of very short waiting time

Mutex

• Mutexes are safe locks provided by the Operating System
  • They are based on atomic instructions
  • Mutexes are safe locks provided by the Operating System
• They are based on atomic instructions
• No busy waiting

mutex_lock:
	TSL REGISTER,MUTEX    | copy mutex to register and set mutex to 1
	CMP REGISTER,#0       | was mutex zero?
	JZE ok                | if it was zero, mutex was unlocked, so return
	CALL thread_yield     | mutex is busy; schedule another thread
	JMP mutex_lock        | try again
	RET                   | return to caller; critical region entered

mutex_unlock:
	MOVE MUTEX,#0         | store 0 in a mutex
	RET                   | return to caller

Avoiding Race Conditions with Mutexes

while(1) {
	mutex_lock();
	critical_region();
	mutex_unlock();
}

Mutexes in Pthreads

• Mutexes can protect shared variables (global, heap) among threads within a process
• Mutexes can also protect shared variables (shared memory) and files among threads in different processes (the mutex must be allocated in the shared memory

4-threads_mutex.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define AMOUNT 1
#define REPEAT 100000

pthread_mutex_t lock;

int balance = 0;
pthread_t thread_id[2];

void* withdraw(void *input) {
  int i;
  for (i=0;i<REPEAT;i++){
    pthread_mutex_lock(&lock);   // Lock
    balance = balance - AMOUNT;  // Access critical region
    pthread_mutex_unlock(&lock); // Unlock
  }
  pthread_exit(NULL); // Thread's job is done
}

void* deposit(void *input) {
  int i;
  for (i=0;i<REPEAT;i++){
    pthread_mutex_lock(&lock);   // Lock
    balance = balance + AMOUNT;  // Access critical region
    pthread_mutex_unlock(&lock); // Unlock
  }
  pthread_exit(NULL); // Thread's job is done
}

int main(void) {
  pthread_mutex_init(&lock, NULL); // init mutex

  pthread_create(&thread_id[0], NULL, withdraw, NULL); // create a thread
  pthread_create(&thread_id[1], NULL, deposit, NULL); // create a thread

  pthread_join(thread_id[0], NULL);
  pthread_join(thread_id[1], NULL);

  printf("Balance: %d \n", balance);
  return 0;
}

Notes:

• We create the mutex
• Every time we do withdraw or deposit, we lock and unlock when finished

File Locks

• Mutual exclusion can also be ensured with lock files
  • The OS can ensure that only one process can open a file

while(1) {
	lockf(LOCK);
	critical_region();
	lockf(UNLOCK);
}

Notes:

• Files that only one process can open at a time

5-account_filelock.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

#define AMOUNT 10000

FILE *lock;

void withdraw(int amount){

  int balance;
  lockf(fileno(lock), F_LOCK, 0);          // Lock
  FILE *f = fopen("bank_account.txt","r"); // Open Bank Account
  fscanf(f, "%d\n", &balance);             // Read Balance
  fclose(f);                               // Close Bank Account

  balance = balance - amount;              // Withdraw Amount

  f = fopen("bank_account.txt","w");       // Open Bank Account
  fprintf(f, "%d\n", balance);             // Write Balance
  fclose(f);                               // Close Account
  lockf(fileno(lock), F_ULOCK, 0);         // Unlock
  exit(0);
}

void deposit(int amount){

  int balance;
  lockf(fileno(lock), F_LOCK, 0);          // Lock
  FILE *f = fopen("bank_account.txt","r"); // Open Bank Account
  fscanf(f, "%d\n", &balance);             // Read Balance
  fclose(f);                               // Close Bank Account

  balance = balance + amount;              // Deposit Amount

  f = fopen("bank_account.txt","w");       // Open Bank Account
  fprintf(f, "%d\n", balance);             // Write Balance
  fclose(f);                               // Close Account
  lockf(fileno(lock), F_ULOCK, 0);         // Unlock
  exit(0);
}

int main(void){
  int balance;
  pid_t pid1, pid2;
  FILE *f;

  lock = fopen("lock","w+");

  pid1 = fork(); // fork a child process
  if (pid1 == 0) {
    deposit(AMOUNT); // Child deposits amount
  }

  pid2 = fork(); // fork a child process
  if (pid2 == 0) {
    withdraw(AMOUNT); // Child withdraws amount
  }

  waitpid(-1,NULL,0);
  waitpid(-1,NULL,0);

  f = fopen("bank_account.txt","r");
  fscanf(f, "%d\n", &balance);
  fclose(f);

  printf("Balance: %d\n", balance);

  return 0;
}

Notes:

• Note we are suing system call lockf to lock the file

Back to the Bank Account Example

• We want to implement a function that sends money (e.g. MobilePay)

send_money(int a, int b, int amount) {
	mutex_lock(&mutex[a]);
	mutex_lock(&mutex[b]);
	account[a] = account[a] - amount;
	account[b] = account[b] + amount;
	mutex_unlock(&mutex[b]);
	mutex_unlock(&mutex[a]);
}

• Instead of having a big lock across all accounts, we have an individual lock for each account
  • Logic: lock the account of the sender, then lock the account of the receiver -> perform transaction -> unlock the two individual account locks
• Is this safe?
  • No, it still has a problem:
    • When we have two mutex locks one after the other, this becomes not atomic, which means the scheduler could take over the CPU between these two instructions
  • What if alex sends money to bob and in parallel bob sends money to alex?
    • First instruction locks the account of alex, now imagine the other transaction starts, locks the account of bob, then tries to lock the account of alex but it was already locked by the first transaction so it waits!
  • We call this a deadlock, because it is a situation where the program is dead, everybody is waiting for the other forever
• There is a risk for deadlock (A waits for B, while B waits for A)
• send_money(0,1,100) in parallel with send_money(1,0,200)
• To avoid deadlocks, we must lock resources always in the same order
  • For example if you always block the smaller integer account first then this problem does not appear

The Producer-Consumer Problem

• Two processes share a fixed-size buffer
  • The producer puts items in the buffer
  • The consumer takes items out of the buffer
• If the buffer is full, the producer must wait for an item to be removed
• If the buffer is empty, the consumer must wait for an item to appear
• We want to avoid inefficient busy waiting
• The processes synchronise by signaling each other
  • If the buffer is full, the producer goes to sleep
  • The consumer wakes up the producer when an empty slot appears
  • If the buffer is empty, the consumer goes to sleep
  • The producer wakes up the consumer when an item appears

Notes:

• Now the action of the other processes can be implemented with signals
• We can have one process send signals when the status of the buffer changes

#define N 100  /* number of slots in the buffer */
int count = 0; /* number of items in the buffer */

void producer(void)
{
    int item;
    while (TRUE) {               /* repeat forever */
        item = produce_item();   /* generate next item */
        if (count == N) sleep(); /* if buffer is full, go to sleep */
        insert_item(item);       /* put item in buffer */
		count = count + 1;       /* increment count of items in buffer */
        if (count == 1) wakeup(consumer); /* was buffer empty? */
    }
}

void consumer(void)
{
    int item;
    while (TRUE) {               /* repeat forever */
        if (count == 0) sleep(); /* if buffer is empty, got to sleep */
        item = remove_item();    /* take item out of buffer */
        count = count - 1;       /* decrement count of items in buffer */
        if (count == N - 1) wakeup(producer); /* was buffer full? */
        consume_item(item);      /* print item */
    }
}

Two Race Conditions

• The previous solution to the Producer-Consumer problem has two race conditions
• We need mutual exclusion in the shared resources (buffer, count)
• There is a race condition in the sleep-wakeup signaling
  • Buffer is empty, counter is 0
  • Consumer checks that the counter is 0, so the if statement is true
  • Scheduler stops consumer and starts producer
  • Producer adds an item, updates counter to 1, and sends wakeup
  • Consumer is awake, receives the wakeup signal and ignores it
  • Consumer continues execution and goes to sleep
  • Eventually Producer fills up the buffer and goes to sleep
  • Both sleep forever

Notes:

• The if statement looks like 1 line of code but it is divisible
  • The problem can happen if you have done your check but you haven't done the sleep yet!
  • So the consumer can be interrupted between the checking and the sleeping
  • But the consumer thinks that it has waking up, and it will generate more items without ever receiving an interrupt from the consumer
  • When the buffer gets full the producer will go to sleep and then you will have a deadlock because both are waiting for each other sleeping

Semaphores

• Invented by Dijkstra in 1965

• A semaphore is an integer (greater or equal to 0)

• Two atomic operations: down and up

  • If > 0, down decrements the semaphore and continues
  • If == 0, down blocks
  • up increments the value of the semaphore

• Managing a pool of N resources

  • down reserves a resource or blocks if no resource available
  • up releases a resource, making it available
  • A semaphore tracks only how many resources are free; it does not keep track of which of the resources are free.
  • A binary semaphore is when N1

Solving The Producer-Consumer Problem (semaphores)

#define N 100 /* number of slots in the buffer */
typedef int semaphore; /* semaphores are a special kind of int */
semaphore mutex = 1; /* controls access to critical region */
semaphore empty = N; /* counts empty buffer slots */
semaphore full = 0; /* counts full buffer slots */

void producer(void)
{
    int item;
    while (TRUE) { /* TRUE is the constant 1 */
        item = produce_item(); /* generate something to put in buffer */
        down(&empty); /* decrement empty count */
        down(&mutex); /* enter critical region */
        insert_item(item); /* put new item in buffer */
        up(&mutex); /* leave critical region */
        up(&full); /* increment count of full slots */
    }
}

void consumer(void)
{
    int item;
    while (TRUE) { /* infinite loop */
        down(&full); /* decrement full count */
        down(&mutex); /* enter critical region */
        item = remove_item(); /* take item from buffer */
        up(&mutex); /* leave critical region */
        up(&empty); /* increment count of empty slots */
        consume_item(item); /* do something with the item */
    }
}

Notes:

• We start with N free slots in the buffer thanks to the semaphore
• The semaphore will keep track of these

Semaphore and Mutexes

• Semaphores and Mutexes are similar but different
  • Do not confuse them!
• Mutex
  • It solves the problem of mutual exclusion
    • Use a mutex when you execute code that no other process/thread should execute at the same time
  • A mutex has an owner, only the owner can up the mutex
    • Lock (down) and unlock (up) are coupled
• Semaphore
  • It solves the problem of signaling
    • Use a semaphore when you want to sleep until some other process/thread wakes you up
  • A semaphore does not have an owner, typically another process/thread is going to up the semaphore
    • Sleep (down) and wake-up (up) are decoupled

Notes:

• Semaphore handle coordination between different processes, not necessarily mutual exclusion
• Typically what happens with semaphores: One locks by going down and it is waken up by another thread

Message Passing

• Processes can also communicate by exchanging messages
  • Applies to processes within the same computer
  • It also applies to processes the run in different computers
    • Computer Networking
• Based on two communication primitives
  • send(destination, &message);
    • Sends messages to an address
  • receive(source, &message);
    • Blocks until it receive message
• No race conditions, but networking introduces new problems
  • What if a messages do not arrive?
  • What if messages arrive out of order

Notes:

• Networking introduces other problems: making sure that the message is complete, tracking sequence numbers to rebuild message, etc.
• It is like seding an envelope, and you fill it up with something

Solving The Producer-Consumer Problem (messages)

#define N 100 /* number of slots in the buffer */

void producer(void)
{
    int item;
    message m; /* message buffer */
    while (TRUE) {
        item = produce_item(); /* generate something to put in buffer */
        receive(consumer, &m); /* wait for an empty to arrive */
        build_message(&m, item); /* construct a message to send */
        send(consumer, &m); /* send item to consumer */
    }
}

void consumer(void)
{
    int item, i;
    message m;
    for (i = 0; i < N; i++) send(producer, &m); /* send N empties */
    while (TRUE) {
        receive(producer, &m); /* get message containing item */
        item = extract_item(&m); /* extract item from message */
        send(producer, &m); /* send back empty reply */
        consume_item(item); /* do something with the item */
    }
}