Introduction to Systems Programming with examples in POSIX
Process
¨ A process can be thought of as a program whose execution has started and not yet terminated.
¨ A process can be in three states:
§ Running: The process is using a processor to execute instructions.
§ Ready: The process is executable, but other processes are executing and all processors are currently in use.
§ Blocked: The process is waiting for an event to occur.
¨ Each process uses a Process Control Block (PCB) data structure to store complete information about the process. PCB contains the following information:
§ Process name and id, processor state (program counter, register contents, interrupt masks, etc.), process state, priority, privileges, virtual memory address translation maps, information about other resources owned by the process, etc.
Concurrent Processes
¨ Two processes are concurrent if their execution can overlap in time.
§ In multiprocessor systems, concurrent processes can use different CPUs at the same time.
§ In single processing systems, concurrent processing can be thought of as one process using the CPU while another process uses system I/O, etc. If a CPU interleaves the execution of several processes, logical concurrency is obtained.
§ Processes are serial if the execution of one must be complete before the execution of the other can start.
¨ Concurrent processes interact through the following mechanisms:
§ Shared variables.
§ Message passing.
Threads
¨ Threads are mini processes within a process and therefore share the address space with the processes.
¨ Every process has at least one thread.
¨ A thread executes a portion of the program and cooperates with other threads concurrently executing within the same process and address space.
¨ Because threads share the same address space, it is more efficient to perform a context switch between two threads of the same process than it is to perform a context switch between two separate processes.
¨ Each thread has it’s own program counter and control block.
Critical Sections
¨ In multiprocessing systems, processes or threads may compete with each other for system resources that can only be used exclusively.
§ CPU is a good example of this type of resource as only one process or thread can execute instructions on a single CPU at a time.
¨ Processes may also cooperate with each other by using shared memory or message passing.
¨ For both of these cases, mutual exclusion is necessary to insure that only one process or thread at one time holds a resource or modify shared memory.
¨ A critical section is a code segment in a process in which some shared resource is accessed.
Mutual Exclusion
¨ A solution to the mutual exclusion problem must satisfy the following requirements:
§ Only one process can execute its critical section at any one time.
§ When no process is executing in its critical section, any process that requests entry to its critical section must be permitted to enter without delay.
§ When two or more processes compete to enter their respective critical sections, the selection cannot be postponed indefinitely (Deadlock).
§ No process can prevent any other process from entering its critical section indefinitely (Starvation).
Some Mechanisms for Insuring Mutual Exclusion
¨ Polling or Busy waiting
¨ Disabling interrupts
¨ Semaphores
Semaphores
¨ A semaphore is an integer variable S and an associated group of waiting processes for which only two operations may be performed:
Wait state P(S): if S ³ 1 then S := S – 1
else the executing process waiting for the semaphore S joins the wait queue for S and forfeits the resource;
endif
Signal state V(S): if wait queue for S is not empty then remove a process from the queue and give it the resource
else S := S + 1
endif
Semaphores (cont.)
¨ A semaphore can be used for synchronization and mutual exclusion.
§ Synchronization: Coordination of various tasks or processes.
§ Mutual exclusion: Protection of one or more resources or implementation of critical sections among several competing processes sharing the critical section.
¨ There are three types of semaphores:
§ Binary semaphores
§ Mutual exclusion semaphores (mutex)
§ Counting semaphores
¨ Binary Semaphores
§ Simplest form of the semaphore.
§ Primarily used for synchronization. Can also be used for mutual exclusion.
§ Using a binary semaphore, a process can wait (block or pend) on an event which triggers the release of a semaphore.
§ Should be used in place of polling.
- Polling is an inefficient way of synchronization or event waiting because of the use of processor resources.
- Using semaphores, the process is in a blocked or pended state while other processes use the processor.
- Upon the occurrence of the event, the pended process becomes ready to execute.
¨ Mutual Exclusion Semaphores
§ Used to provide resource consistency in a system for resources shared simultaneously by multiple tasks.
- Shared resources can be such as shared data, files, hardware, devices, etc.
§ To protect against inconsistency in a multi-tasking system, each task must obtain exclusive access right to a shared resource.
§ One common problem that can occur without designing proper mutual exclusion in a multi-tasking system sharing resources simultaneously is known as the “Racing condition”.
- Based on which task gets to the resource first the system behavior is different.
- Racing conditions can go on undetected for a very long time in a system and can be a very difficult problem to detect and fix.
§ When using mutual exclusion semaphores, be aware of the racing condition; deadlock.
- Use only one mutual exclusion semaphore to protect resources that are used together.
§ When using mutual exclusion semaphores, avoid starvation situations.
- Do not include unnecessary sections in the critical section.
§ Mutual exclusion semaphores can not be used in interrupt service routines.
¨ Counting Semaphores
§ Yet another mean to implement task synchronization and mutual exclusion.
§ Counting semaphore is just like the binary semaphore with the exception that it keeps track of the number of times a semaphore has been given or taken.
- Counting semaphores use a counter to keep track of the semaphores and hence the name, counting semaphore!
- The semaphore is created with a fixed number of semaphores available.
- Every time that a semaphore is taken, the semaphores count is decremented.
- When a semaphore is given back, if a task is blocked on the semaphore, it takes the semaphore. Otherwise, the semaphores count is incremented.
§ Counting semaphores are generally used to guard resources with multiple instances.
Classical Synchronization Problems
¨ The dining philosophers problem
¨ The producer-consumer problem
¨ The readers-writes problem
§ Reader’s priority
- Weak reader’s priority
§ Writer’s priority
- Weak writer’s priority
POSIX Semaphores
§ There are two types of POSIX Semaphores, named and unnamed semaphores.
Both types of POSIX semaphores have exactly the same properties and behave in exactly the same manor.
The two different types, have different API’s and interfaces when creating/opening/destroying the semaphores.
§ For named semaphores, a symbolic name is assigned to a semaphore and all references to that semaphore are made using the symbolic name.
¨ POSIX Semaphores routines:
§ sem_init() Initialize an unnamed semaphore.
The API:
int sem_init ( sem_t * sem, int pshared, unsigned int value );
sem: Semaphore descriptor of the unnamed semaphore to be initialized.
pshared: Whether semaphore can be usable between multiple processes, or merely within the calling process. Unless you have a system with threads, you will always set this to 1. If set to 0, then multiple processes may not be able to use the resulting semaphore.
value: Value of the initialized semaphore. The initial value can not be negative.
Returns: OK (0), ERROR (-1).
§ sem_destroy() Destroy an unnamed semaphore.
Must be careful when dealing with this call especially when semaphore is used for mutual exclusion.
A good design will assure that no other task has locked the semaphore, before destroying the semaphore.
One way of assuring this is to adopt the protocol of only deleting semaphores that the deleting task has successfully locked.
The API:
int sem_destroy ( sem_t * sem );
sem: Semaphore descriptor.
Returns: OK (0), ERROR (-1).
¨ POSIX Semaphores routines (continued):
§ sem_open() Initialize/open a named semaphore.
The API:
sem_t sem_open (const char* name, int oflag, mode_t mode, unsigned int value);
name: Semaphore name.
oflag: O_CREAT (required the following 3rd and 4th calling parameters)
mode_t mode: Three triplets of permissions are set for semaphores: read, write for creator, group, and others (refer to sys/stat.h for portable symbols).
unsigned int value: Initial semaphore value. Must be £ SEM_VALUE_MAX.
O_EXCL used in conjunction with O_CREAT. When O_EXCL | O_CREAT is used, call will fail if semaphore name exists.
Returns: A pointer to sem_t, ERROR (-1).
§ sem_close() Close a named semaphore.
Deallocates system resources allocated by the system for use by the task for the named semaphore.
Semaphore must have been removed using the call sem_unlink () for sem_close () to have an effect.
The API:
int sem_close ( sem_t * sem );
sem: Semaphore descriptor.
Returns: OK (0), ERROR (-1).
¨ POSIX Semaphores routines (continued):
§ sem_unlink() Remove a named semaphore.
Removes the string name from the semaphore name table, and marks the corresponding semaphore for destruction.
Semaphore is destroyed when the last task closes it with sem_close ().
The API:
int sem_unlink ( const char * name );
name: Semaphore name.
Returns: OK (0), ERROR (-1).
¨ POSIX Semaphores routines (continued):
§ sem_wait() Locks (takes) a semaphore, causing the calling task to block if unavailable.
Deadlock detection is not implemented.
The API:
int sem_wait ( sem_t * sem );
sem: Semaphore descriptor.
Returns: OK (0), ERROR (-1).
§ sem_trywait() Locks (takes) a semaphore, returning error if unavailable.
Deadlock detection is not implemented.
The API:
int sem_trywait ( sem_t * sem );
sem: Semaphore descriptor.
Returns: OK (0), ERROR (-1).
§ sem_post() Unlocks (gives) a semaphore.
The API:
int sem_post ( sem_t * sem );
sem: Semaphore descriptor.
Returns: OK (0), ERROR (-1).
¨ POSIX Semaphores routines (continued):
§ sem_getvalue() get the value of a semaphore.
The API:
int sem_getvalue ( sem_t * sem, int * sval );
sem: Semaphore descriptor.
sval: Buffer for which the semaphore value is returned.
Returns: OK (0), ERROR (-1).
Message Queues
§ Used for inter-task (inter-process) communication (IPC)
§ Not as fast as semaphores but allows cooperating tasks to communicate with each other.
§ Allows messages to be queued and sent/received to/from tasks/interrupt service routines.
§ Multiple tasks can send/receive to/from a common message queue.
¨ POSIX Message queues
§ POSIX message queues provide named queues.
§ POSIX message queues provide a range or message priorities (0 the lowest to 31 the highest priority).
§ POSIX message queues allow a routine to request notification when a message for it arrives at an empty queue, therefore avoiding task block or polling to wait for a message. POSIX signals are used to achieve this.
¨ POSIX Message queue routines:
§ mq_open() open a message queue.
The API:
mqd_t mq_open ( const char * mqName, int oflag, mode_t mode, struct mq_attr * pAttr );
mqName: Message queue name. Must begin with “/” and contain full path.
oflag: O_CREAT (requires the following 3rd and 4th calling parameters)
mode_t mode: Mode.
mq_attr *pAttr: NULL, mq_maxmsg, mq_msgsize.
O_EXCL (used in conjunction with O_CREAT. When O_EXCL | O_CREAT is used, call will fail if message queue name exists.)
O_RDONLY (open the message queue for read only.)
O_WRONLY (open the message queue for write only.)
O_RDWR (open the message queue for read and write.)
O_NONBLOCK (opened message queue can be used in a blocking or non blocking mode.)
When message queue is used in non-blocking mode, upon send, it will not block with a full message queue. Upon receive, it will not block with an empty message queue.
Returns: A pointer to message queue descriptor, mqd_t, ERROR (-1).
¨ POSIX Message queue routines:
§ mq_close() Close a message queue.
Deallocates system resources allocated by the system for use by the task for the message queue.
Message queue must have been removed using the call mq_unlink () for mq_close () to have an effect.
The API:
int mq_close ( mqd_t * mq );
mq: Message queue descriptor.
Returns: OK (0), ERROR (-1).
¨ POSIX Message queue routines (continued):
§ mq_unlink() Remove a message queue.
Removes the string name from the message queue name table, and marks the corresponding message queue for destruction.
Message queue is destroyed when the last task closes it with mq_close ().
The API:
int mq_unlink ( const char * name );
name: Message queue name.
Returns: OK (0), ERROR (-1).
¨ POSIX Message queue routines (continued):
§ mq_send() Sends a message to the message queue.
The API:
int mq_send ( mqd_t * mqdes, const void *pMsg, size_t msgLen, int msgPrio );
mqdes: Message queue descriptor.
pMsg: Pointer to the message.
msgLen: Size of message in bytes. Value must be less than or equal to the mq_msgsize attribute of mq_attr.
msgPrio: Message priority. Message with a higher priority value is inserted before message with lower value. The value of msgPrio must be less than or equal to MQ_PRIO_MAX.
Returns: OK (0), ERROR (-1).
§ mq_receive() Receives the oldest of the highest priority message from a message queue.
The API:
ssize_t mq_receive ( mqd_t * mqdes, void *pMsg, size_t msgLen, int *pMsgPrio );
mqdes: Message queue descriptor.
pMsg: Pointer to buffer to receive the message.
msgLen: Size of buffer in bytes. Value must be less than or equal to the mq_msgsize attribute of mq_attr.
msgPrio: Received message priority if not NULL.
Returns: OK (0), ERROR (-1).
¨ POSIX Message queue routines (continued):
§ mq_notify() Notify a task that a message is available on a queue.
The API:
int mq_notify ( mqd_t mqdes, const struct sigevent * pNotification );
mqdes: Message queue descriptor.
pNotification: real-time signal.
Returns: OK (0), ERROR (-1).
¨ POSIX Message queue routines (continued):
§ mq_setattr() can be used to set the message queue attribute:
mq_flags O_NONBLOCK
§ mq_getattr() can be used to get the message queue attribute:
mq_flags O_NONBLOCK
mq_maxmsg
mq_msgsize
mq_curmsgs
¨ POSIX Message queue routines (continued):
§ mq_setattr() Set message queue attributes.
The API:
int mq_setattr ( mqd_t mqdes, const struct mq_attr * pMqStat,
struct mq_attr * pOldMqStat );
mqdes: Message queue descriptor.
pMqStat: New attribute.
pMqStat: Old attribute.
Returns: OK (0), ERROR (-1).
§ mq_getattr() Get message queue attributes.
The API:
int mq_getattr ( mqd_t mqdes, const struct mq_attr * pMqStat );
mqdes: Message queue descriptor.
pMqStat: Buffer in which to return attributes.
Returns: OK (0), ERROR (-1).
POSIX Pipes
§ An alternative interface to the message queue facility.