Interprocess Communication (IPC)

• In many cases processes do not operate isolated on separated data
• Processes will often…

  • call each other,

  • wait for each other, or

  • coordinate with each other

• They must interact with each other
• Important questions regarding interprocess communication (IPC):
  • How can a process transmit information to other processes?
  • How can multiple processes access shared resources?

Communication vs. Cooperation

• Interprocess communication has 2 aspects:
  • Functional aspect: communication and cooperation
  • Temporal aspect: synchronization

• Communication and cooperation base on synchronization

Communication of Processes

• Types of IPC
  • Files
  • Signals/Flags
  • Shared Memory
  • Message Queues
  • Pipes
  • Sockets

Files

• A resource stored in the \(\rightarrow\) file system which can be accessed by multiple processes
• Linux
  • File descriptors represent file handles
  • Part of the POSIX API
  • Per default every process owns three file descriptors (stdin, stdout, and stderr)
  • File descriptors can be used for, e.g., reading, writing, seeking, or truncating a file
• RIOT
  • Virtual File System (VFS) may be implemented by various backends
  • Not all IoT devices provide persistent memory
  • If available, persistent memory is often realized on flash memory \(\rightarrow\) wear leveling is required

Signals and Flags

• Notify another process about the occurrence of an event
• Linux
  • POSIX signals
  • Standardized messages to trigger a certain behaviour
  • The receiver process gets interrupted
  • If a signal is unhandled by the receiver, it will terminate
• RIOT
  • Thread flags
  • The receiver needs to wait for a flag
  • Optional kernel feature
  • Notify threads of conditions in a race-free and allocation-less way

Shared Memory

• IPC via shared memory is also called memory-based communication
• Shared memory segments are memory areas which can be accessed by multiple processes
  • These memory areas are mapped in the address space of multiple processes
• Coordination (\(\rightarrow\) synchronization) between the processes accessing the shared memory is required

Shared Memory in Linux/UNIX

• Linux/UNIX operating systems contain a shared memory table, which contains information about the existing shared memory segments

  • This information includes: Start address in memory, size, owner (username and group) and privileges

• Shared memory objects are accessed similar to files

Message Queues

• Are linked lists with messages
• Operate according to the FIFO principle
• Processes can store data inside and picked them up from there
• Benefit: Even after the termination of the process which created the message queue the data inside the message queue stays available

Anonymous Pipes

Named Pipes

• Processes, which are not closely related with each other, can communicate via named pipes
  • These pipes can be accessed by using their names
    • They are created in C by: mkfifo("<pathname>",<permissions>)
  • Any process, which knows the name of a pipe, can use the name to access the pipe and communicate with other processes
• The operating system ensures mutual exclusion
  • At any time, only a single process can access a pipe
• Named pipes are not erased automatically by the operating system (unlike anonymous pipes)

Different Types of Sockets

• Connectionless sockets (= datagram sockets)
  • Use the Transport Layer protocol UDP
  • Advantage: Better data rate as with TCP
    • Reason: Lesser overhead for the protocol
  • Drawback: Segments may arrive in wrong sequence or may get lost
• Connection-oriented sockets (= stream sockets)
  • Use the Transport Layer protocol TCP
  • Advantage: Better reliability
    • Segments cannot get lost
    • Segments always arrive in the correct sequence
  • Drawback: Lower data rate as with UDP
    • Reason: More overhead for the protocol

Using Sockets

• Almost all major operating systems support sockets
  • Advantage: Better portability of applications
• Functions for communication via sockets:

  • Creating a Socket:
    socket()

  • Binding a socket to a port number and making it ready to receive data:
    bind(), listen(), accept() and connect()

  • Sending/receiving messages via the socket:
    send(), sendto(), recv() and recvfrom()

  • Closing of a socket:
    shutdown() or close()

Connection-less Sockets (UDP)

Connection-oriented Sockets (TCP)

Comparison of Communication Systems

• Advantages of message-based communication versus memory-based communication:

  • The operating system takes care about the synchronization of accesses \(\Longrightarrow\) comfortable

  • Can be used in distributed systems without a shared memory

  • Better portability of applications

Signaling

• Used to specify an execution order

• Example: Section X of process \(P_{A}\) must be executed before section Y of process \(P_{B}\)

  • The signal operation signals that process \(P_{A}\) has finished section X
  • Perhaps, process \(P_{B}\) must wait for the signal of process \(P_{A}\)

Most Simple Form of Signaling (Busy Waiting)

• The figure shows busy waiting at the signal variable s
  • The signal variable can be located in a local file, for example
  • Drawback: CPU resources are wasted, because the wait operation occupies the processor at regular intervals
• This technique is also called spinlock or polling

Locking

• In order to protect critical sections, i.e., no overlap in their execution, locking can be used

• In contrast to signaling the execution order is not specified

• The necessary operations are lock and unlock

• Example: Critical Sections X of process \(P_{A}\) and Y of process \(P_{B}\)

Problems caused by Locking

• Starvation
  • If a process does never remove a lock, the other processes need to wait infinitely long for the release
• Deadlock
  • If several processes wait for resources, locked by each other, they lock each other mutually
  • Because all processes, which are involved in the deadlock, must wait forever, no one can initiate an event that resolves the situation

Conditions for Deadlock Occurrence

• A deadlock situation can arise if these conditions are all fulfilled
  • Mutual exclusion
    • At least one resource is either occupied by exactly one process or is available \(\Longrightarrow\) non-sharable resource
  • Hold and wait
    • A process, which currently occupies at least one resource, requests additional resources which are being held by another process
  • No preemption
    • Resources occupied by a process cannot be deallocated by the OS but only be released by the holding process voluntarily
  • Circular wait
    • A cyclic chain of processes exists
    • Each process requests a resource that the next process in the chain occupies.
• Only if all of these conditions are fulfilled a deadlock occurs

Resource Graphs

• The relations of processes and resources can be visualized using directed graphs
• In this way, deadlocks can also be modeled
  • The nodes of a resource graph are:
    • Processes: Are shown as circles
    • Resources: Are shown as rectangles
  • An edge from a process to a resource means:
    • The process is blocked because it waits for the resource
  • An edge from a resource to a process means:
    • The process occupies the resource

Deadlock Detection with Matrices

• If multiple copies of a resource exist, an algorithm based on matrices can be used
• We specify two vectors
  • Existing resource vector
    • Indicates the number of existing resources of each class
  • Available resource vector
    • Indicates the number of free resources of each class
• Additionally two matrices are required
  • Current allocation matrix
    • Indicates, which resources are currently occupied by the processes
  • Request matrix
    • Indicates, which resource the processes would like to occupy

Deadlock Detection – Example

Cooperation

• Cooperation
  • Semaphor
  • Mutex

Semaphore

• In order to protect (lock) critical sections not only the already discussed locks can be used but also semaphores
• First published in 1965 by Edsger W. Dijkstra
• A semaphore is a counter lock S with operations P(S) and V(S)
  • V comes from the dutch verhogen = raise
  • P comes from the dutch proberen = try (to reduce)
• These access operations are atomic \(\Longrightarrow\) can not be interrupted
• May allow multiple processes accessing the critical section

Semaphore Access Operations (2/3)

• P operation (reduce): It checks the value of the counter variable
  • If the value is 0, the process becomes blocked
  • If the value \(>\) 0, it is reduced by 1

SEM.P() {
    // if the counter variable = 0, the process becomes blocked
    if (SEM.COUNT == 0)
    < block >
    // if the counter variable is > 0, the counter variable
    // is decremented immediately by 1
    SEM.COUNT = SEM.COUNT - 1;
} 

Semaphore Access Operations (3/3)

• V operation (raise): It first increases the counter variable by value 1
  • If processes are in the waiting room, one process gets unblocked
  • The process, which just got unblocked, continues its P operation and first reduces the counter variable

SEM.V() {
    // counter variable = counter variable + 1
    SEM.COUNT = SEM.COUNT + 1;
    // if processes are in the waiting room, one gets unblocked
    if ( < SEM waiting room is not empty > )
    < unblock a waiting process >
} 

Producer/Consumer Example

typedef int semaphore;         // semaphores are of type integer
semaphore filled = 0;          // counts the number of occupied locations in the buffer
semaphore empty  = 8;          // counts the number of empty locations in the buffer
semaphore mutex  = 1;          // controls access to the critial sections

void producer (void) {
    int data;
    while (TRUE) {               // infinite loop
        createDatapacket(data);    // create data packet
        P(empty);                  // decrement the empty locations counter
        P(mutex);                  // enter the critical section
        insertDatapacket(data);    // write data packet into the buffer
        V(mutex);                  // leave the critical section
        V(filled);                 // increment the occupied locations counter
    }
}

void consumer (void) {
    int data;
    while (TRUE) {               // infinite loop
        P(filled);                 // decrement the occupied locations counter
        P(mutex);                  // enter the critical section
        removeDatapacket(data);    // pick data packet from the buffer
        V(mutex);                  // leave the critical section
        V(empty);                  // increment the empty locations counter
        consumeDatapacket(data);   // consume data packet
    }
} 

Semaphores in Linux (System V)

• The semaphore concept of Linux differs from the Dijkstra concept
  • The counter variable can be incremented or decremented with a P or V operation by more than value 1
  • Multiple access operations on different semaphores can be carried out in an atomic way

Systems Calls for System V Semaphores

Linux/UNIX operating systems provide three system calls for working with System V semaphores

• semget(): Create new semaphore or a group of semaphores or open an existing semaphore
• semctl(): Request or modify the value of an existing semaphore or of a semaphore group or erase a semaphore
• semop(): Carry out P and V operations on semaphores
• Information about existing semaphores (System V) provides the command ipcs

Mutexes

• If the Semaphore feature of counting is not required a simplified alternative, the mutex can be used instead
  • Mutexes (derived from Mutual Exclusion) are used to protect critical sections, which are allowed to be accessed by only a single process at any given moment
    • Mutexes can only have two states: occupied and not occupied
    • Mutexes have the same functionality as binary semaphores

Monitor and erase IPC Objects

• Information about existing System V shared memory segments, System V message queues, and System V semaphores provides the command ipcs

• The easiest way to erase such shared memory segments, message queues and semaphores from the command line is the command ipcrm

        ipcrm [-m shmid] [-q msqid] [-s semid]
        [-M shmkey] [-Q msgkey] [-S semkey]

• POSIX memory segments and POSIX semaphores can be inspected and manually erased in the directory /dev/shm

• POSIX message queues can be inspected and manually erased in the directory /dev/mqueue

Summary