Please disable adblock to view this page.

← Go home

Inter Process Communication

data-structure-messages

October 29, 2016
Published By : Pratik Kataria
Categorised in:

IPC

Independent processes & co-operating processes
Communicating two processes related or unrelated.
Purposes for IPC

  • Information Sharing
  • Data Transfer
  • Synchronization
  • Event Notification

IPC mechanism:

  • Signal
  • Message Passing
  • Pipes
  • Sockets
  • Shared memory

SYSTEM V IPC

Messages: allow processes to send formatted data streams to arbitrary process
Shared memory: allows processes to share parts of virtual address space
Semaphores: allows processes to synchronize execution

COMMON PROPERTIES

Each Mechanism contains:
A table whose entries describes all instances of mechanism
A get system call

  • to create a new entry or
  • to retrieve existing entry

Includes a key and flags
Set IPC_CREAT bit in flag: create new entry with given key
IPC_CREAT and IPC_EXCL bit in flag: error if entry for given key is present
Returns a kernel-chosen descriptor
A control system call

  • to query status of an entry or
  • to set status information or
  • to remove entry from the system

Each IPC entry contains:
A numeric key, i.e. user chosen name
Permission structure:

  • User ID and Group ID of the process that created the entry

Status information:

  • PID of the last process to update the entry
  • Time of last access/modification

MESSAGES

Four system calls:

  • msgget: returns/creates a message descriptor which corresponds to a message queue i.e. create a message queue
  • msgctl:
    • Set and return parameters associated with a message queue
    • Remove descriptors
  • msgsnd: send a message
  • msgrcv: receive a message
  • msgqid=msgget(key,flag)
  • Messages are stored on a linked list(queue)
  • Fields of queue structure
    • ptr to 1st and last msg on linked list
    • no of msg & total no of data byte on linked list
    • max no of bytes of data byte on linked list
    • process IDs of last processes to send and receive messages
    • timestamp of last msgsnd, msgrcv and msgctl calls

data-structure-messages

msgqid=msgget(key,flag)

When msgget called

search msg queue to find id with given key

if no entry

allocate new queue  struct

initialize it

return identifier

else

check permission & return

msgsnd(msgqid,msg,count,flag)

Msgqid-descriptor of msg queue returned by msgget
Msg- ptr to data structure of a user-chosen int type and char array i.e. pointer to data structure where actually message to be sent is stored
Count- size of data array
Flag-action taken if it runs of internal buffer space

 

count=msgrcv(id,msg,maxcount,type,flag)

id- msg descriptor
Msg-address of user structure to contain received msg
Maxcount-size of data array in msg
Type-msg type user wants to read
Flag- what kernel should do if no msg are on the queue
count- no of bytes returned to user

 

msgctl(id,cmd,mstatbuf)

Id-msg descriptor
Cmd- type of command
Mstatbuf- address of user data structure that will contain control parameters or result of query

SHARED MEMORY

Processes can communicate directly by

  • sharing parts of their virtual address space
  • and then reading and writing data stored in shared memory
  • IPC happens through shared memory

Four System Calls:

  • shmget()
    • creates a new region of shared memory or
    • returns an existing one
  • shmat()
    • logically attaches a shared region to virtual address space of the process
  • shmdt()
    • logically detaches a shared region to virtual address apace of the process
  • shmctl()
    • manipulates parameters related to shared memory i.e. controls the shared memory

data-structure-shared-memory

shmid=shmget(key,size,flag)

Size-no of bytes in region

Search for given key in shared memory table

if entry present & permission

return descriptor for entry

if no entry & IPC_CREAT flag is set

verify size  & allocate region using allocreg

shared memory table saves:

permission modes, size, ptr to region table

entry

flag is set to indicate no memory is associated with

the region

Allocating a region

allocreg – allocate a region data structure

Region table entries can be on:

  • free linked list or
  • an active linked list

While allocating a region table entry, kernel:

  • removes first available region from free list
  • put it on active list
  • locks the region
  • marks its type (private or shared)

shmat – attach a shared memory

Attaching a shared memory

Kernel

  • Verifies permissions to access the region
  • Attaches region using algorithm attachreg.
  • Update shared memory table entry
  • Returns virtual address at which the region is attached

attachreg – attach a region to a process

Attaching a region

Kernel

  • Allocates a free pregion entry
  • Sets its type field (text,data, shared memory or stack)
  • Records virtual address where the region will exist in the process address space

     

  • Returns pointer to the pregion entry for the newly attached region

     

  • i.e. create pregion table entry

Shared Memory detach

shmdt(addr)

  • addr- address returned by shmat

Kernel

  • Searches for the process region attached at addr
  • Detaches it from process address space, using detachreg
  • Adjust time in shared memory table

Detaching a Region

detachreg – detach a region from a process

Kernel

  • Updates the pregion entry
  • Decrements region reference count and size field in the process table entry

SEMAPHORES

data-structure-semaphores

TYPES OF SEMAPHORES

Counting semaphore

wait(Semaphore s){

while (s==0);    /* wait until s>0 */

s=s-1;

//Resource is accessed

}

signal(Semaphore s){

//Resource is released

s=s+1;

}

Init(Semaphore s , Int v){

s=v;

}

Binary semaphore

//Value 0: busy

//Value 1: free

do

{

wait(s);

// critical section

signal(s);

// remainder section

} while(1);

Semaphore Operations:

  • Wait/P (try): when a process wants access to a resource
    decrements value of a semaphore if its value is greater
    than 0
  • Signal/V (increment): called when a process is done using a resource
    increments value of semaphore

Semaphore elements:

  • Semaphore value
  • Last process’s ID which manipulated the semaphore
  • Number of processes waiting for semaphore value to increase
  • Number of processes waiting for semaphore value to become 0

Change in Semaphore value according to operation value

If Positive:

  • Increment semaphore
  • Wake up processes waiting for sem value to increase

If 0:

  • If sem value=0 :- continue with other operation with array
  • Else put process to sleep (process waiting for sem value to be 0)

If Negative:

  • Decrements semaphore by op value
  • If semaphore = 0
    • Wakeup all processes waiting for sem to be 0
  • Else
    • process goes to sleep (process waiting for sem value to increase)

undo-structure-semaphores

FLAG BITS

  • IPC_CREAT
  • IPC_EXCL
  • IPC_NOWAIT
  • IPC_RMID
  • IPC_PRIVATE

     

  • MSG_NOERROR

     

  • SEM_UNDO

PROCESS TRACING

Process tracing means one process traces and controls the execution of another process
Primitive form of inter-process communication for tracing processes
Useful for debugging
Two processes:

  • Trace – A Traced process
  • Debug – A Tracing process

Process tracing consists of:

  • Synchronization of the debugger process and the traced process
  • Controlling the execution of the traced process

Debugger process creates a process to be traced and controls its execution with the ptrace system call

ptrace(cmd, pid, addr, data)

  • cmd: commands such as reading data, writing data, resume the execution etc.
  • Pid: process Id of traced process
  • Addr: virtual address to be read or written in the child process
  • Data: integer value to be written

Used by debuggers sdb or dbx
Global trace data structure

Drawbacks and limitations

  • child must allow tracing explicitly by invoking ptrace
  • parent can control the execution of its direct children only
  • extremely inefficient (requires several context switches)
  • cannot control a process already running
  • security problems when tracing a setuid programs (user can obtain super user privileges)
  • to avoid this UNIX disables tracing such programs

Debugging Process Structure

if ((pid = fork() ) == 0)

{

/*child – traced process */

ptrace(0, 0, 0, 0) ;             // sets Trace bit in child process table entry

exec(“name of traced process here”) ;  //e.g. a.out

}

/* debugger process continues here */

for (;;)

{

wait( (int *) 0) ;

read (input for tracing instructions)

ptrace(cmd,pid,addr,data) ;

if (quitting trace)

break;

}

PIPES

A unidirectional, FIFO, unstructured data stream of fixed maximum size.
int pipe (int * filedes)
filedes[0] for read, filedes[1] for write

Applications: in shell – passing output of one program to another program – e.g. cat fil1 file2 | sort
Limitations: cannot be used for broadcasting;
Data in pipe is a byte stream
No way to distinguish between several readers or writers

Named Pipes:

  • Use mknod(),mkfifo()

SOCKETS

A socket is defined as an endpoint for communication
Concatenation of IP address and port
Communication needs a pair of sockets

SOCKET FUNCTIONS

sd = socket (format, type, protocol)
Estabilshes end point of a communication link

  • format: communication domain (Unix system domain/Internet domain)
  • type: type of communication(virtual circuit/datagram)
  • protocol: protocol to control the communication

bind (sd, address, length)
Associates a name with the socket descriptor

  • sd: socket descriptor
  • address: structure specifying an ID specific to communications domain and protocol
  • length: length of address structure

connect (sd, address, length) ;
Requests that the kernel make a connection to an existing socket

  • sd: socket descriptor
  • address: address of target socket
  • Length:length of address structure

listen (sd, qlength);
Specifies maximum queue length

  • sd: socket descriptor
  • qlength: maximum number of outstanding requests

nsd = accept (sd, address, addrlen) ;
Receives incoming requests for a connection to a server process

  • sd: socket descriptor
  • address: points to user data array with return address of the connecting client
  • addrlen: size of user array

count = send (sd, msg, length, flags) ;
count = recv (sd, buf, length, flags) ;
Transmits data over a connected socket

shutdown (sd, mode);
Closes a socket connection

getsockname(sd, name, length) ;
Gets the name of a socket bound by a previous bind call

MULTIPROCESSOR CONFIGURATION

multiprocessor-configuration

Greater throughput as processes run concurrently.
Each CPU executes independently but all of them execute one copy of kernel.
Semantics for system call are same.
Drawback: Several process execute simultaneously in kernel mode causes integrity problems.

PROBLEM OF MULTIPROCESSOR SYSTEM

In uniprocessor Unix system, integrity of kernel data structure is maintained by two policies.

  1. Kernel cannot preempt a process and switch context to another process while executing in kernel mode.
  2. Kernel masks out interrupts when executing a critical region of code .

On a multiprocessor, if two or more processes execute simultaneously in the kernel on separate processors, the kernel could become corrupt, even if above two policies are applied

METHODS OF PREVENTION

Execute all critical activity on one processor
Serialize access to critical regions of code with locking primitives.
Redesign algorithms to avoid contention of data structures.

Solution with master and slave processors

One processor called master can execute in kernel mode and other called slave execute only in user mode.
Master processor- handle all system calls and interrupt.
Slave processor-execute process in user mode and inform master when makes system calls.

DRAWBACK

Corruption of kernel data structure possible in scheduler algorithm because it does not protect against having a process selected for execution on two processor.

Master can specify the slave processor on which the process should execute (more than one process can be assign –load balancing problem).
Kernel can allow only one processor to execute the scheduling loop at a time.

Solutions with semaphore

  • Mechanism for setting lock:
    while(lock is set) //test operation
    sleep(condition until lock is free);
    set lock;
  • Mechanism for unlocking the lock:
    free lock;
    wake up all processes sleeping on condition lock set;

IMPLEMENTATION OF SEMAPHORE

Dijkstra- possible to implement semaphore without sp. m/c instruction.

Pprim locks semaphore by checking value of array val.

When lock sem. It checks to see if processor already locked(val=2) or if processor with lower ID trying to lock(val=1).

If either cond true, resets entry =1 & tries again

Algorithms implemented with semaphore

  • Buffer allocation
  • Wait
  • Driver-locking scheme
  • Dummy process

BUFFER ALLOCATION

Data structure for buffer allocation

  • Buffer Header
  • HQ of buffer
  • Free List Buffers

In multiprocessor two process could manipulate the linked list of hash queue, the semaphore for the hash queue permits only one processor at a time to manipulate the linked list.

Free list requires a semaphore as several process could corrupt it.

Wait

Parent should miss a zombie child as it executes the wait algorithm.
Parent must not sleep waiting forever.

Drivers

Avoided inserting semaphore into driver code.
P & V operations at the driver entry points.

P(driver_semaphore);

Open(driver);

V(driver_semaphore):

Same semaphore for all entry points.
Different semaphore for each driver.

Dummy Process

In uniprocessor, if no process are ready to run, kernel idles in the context of the process that last run.
In multi processor, Kernel can not idle in context of the process executed most recently on the processor.
Create a dummy process per processor.
When processor has no work to do context switch is done to the dummy process & it idles the context of dummy process .
It consists of kernel stack only and can not be scheduled.

The Tunis system

User interface compatible to Unix.
Written in Concurrent Euclid.
Solves the mutual exclusion problem.
Kernel process are activated by queuing messages for input.
Concurrent Euclid implements monitor to prevent corruption of queues.

Performance limitation

Methods to implement multiprocessor configuration.

  • Master – slave
  • Semaphore

The implementation of multiprocessor Unix system generalizes to any no of processor but throughput will not increase at linear rate with no of processors.

  • Increased memory contention in h/w .
  • Wait longer period of time to gain semaphore.
  • Master processor becomes bottleneck.