Inter Process Communication

October 29, 2016
Categorised in: Operating System Design
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
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
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
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)
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
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.
- Kernel cannot preempt a process and switch context to another process while executing in kernel mode.
- 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.
Pratik Kataria is currently learning Springboot and Hibernate.
Technologies known and worked on: C/C++, Java, Python, JavaScript, HTML, CSS, WordPress, Angular, Ionic, MongoDB, SQL and Android.
Softwares known and worked on: Adobe Photoshop, Adobe Illustrator and Adobe After Effects.