Linux System Programming Notes

Scheduling Algorithm

Pre-Emptive

Process can move Running Queue to Ready Queue

• SRTF (shortest remaining time first)
• LRTF (largest remaining time first)
• Round Robin
• Priority based

Non Pre-Emptive

once process in running Queue it can move to ready Queue. It will do all work and terminate.

• FCFS (first come first serve)
• SJF (shortest job first)
• LJF (largest job first)
• Multilevel Queue

Threads

• threads are mechanism that permit process an application to perform multiple task concurrently.
• Single Process can contain multiple threads. All threads independently executing. Sharing Global Data.

note: errno is a global integer variable. this doesn’t suffice for threaded program. if threaded program made function call that return errno in a global variable, then this is confuse other thread might also making function call. race condition would occur. so every thread has its own errno value.

pthread function return zero(0) on success and in failure positive value (errno)

Create thread

Thread termination

following ways of thread termination:

• thread start function performs a return specifying a return value for the thread.
• thread call pthread_exit().
• thread is canceled by pthread_cancel().
• any of thread call exit(). or main thread return which causes all thread in the process to terminate immediately.

note : main thread calls pthread_exit() instead of exit() or perform return then other threads continue to execute.

void pthread_exit(void *retval)

calling pthread_exit() is equivalent to perform a return in threads function. difference is pthread_exit() can call from any function that has been called by thread.

retval is a return value of thread. retval should not locate at thread stack. stack of thread is undefined after thread termination.

Thread IDs

each thread has its own unique id. this id is return to caller by pthead_create(), thread can obtain its own id by using pthread_self().

pthread_t pthread_self(void)

thread IDs to identify thread on which function are to act. some function include pthread_join(), pthread_detach(), pthread_cancel(), and pthread_kill(), all use argument as threadID.

int pthread_equal(pthread_t t1, pthread_t t2);

*return non-zero value if equal. otherwise 0;

to check two thread ID’s are same.

Joining with terminated thread

pthread_join() function wait for thread to terminate. this is blocking call for calling thread.

int pthread_join(pthread_t thread, void **retval);

*return 0 on success, positive errno on error.

• calling pthread_join() for already joined thread lead to unpredictable behaviour. for example if we may join for different thread that may having same thread ID. because after thread termination or joined the id of that thread can be reused.
• if we do not join thread then thread is equivalent of ZOMBIE process. wasting system resources. if enough thread zombies accumulate. we won’t be able to create additional threads.
• pthread_join() similar to that process perform waitpid(). some notable difference.

threads are peer to peer. means T1 thread can create T2 thread. and T2 thread can have T3 thread. here T3 thread can wait of T1 thread to complete vice versa. but in process hierarchical relationship. parent can only wait for its child.

Multiple thread updating Global Variable

if multiple thread updating global variable then undefined result may occur.

if thread complete its task before another thread use it than its not a problem. but if thread taking longer time to access share data. than undefined behavior happen.

Output

data = 10000

Double data =20000

Now Increase data:

data = 100000

Double data =151465

*here in case one expected result. data is double. but in case 2 unexpected result.

reason is while thread 1 is updating data same time thread 2 is updating it. so unexpected data.

assume th1 ins in loop index of 155555 at same time th2 loop index is 140000 so glb data is reduce. then again th1 increment it to 140001. so result. data is unprotected.

to reduce this. and protect the data we must use mutex (mutual exclusion).

Mutex (mutual exclusion)

• only one thread at a time can access the critical section (global data).
• mutex has two state locked and unlocked.
• when thread lock mutex. thread become owner of mutex. and mutex owner only unlock mutex.
• locked resource can not be access by other thread. they must wait.

now desirable output

Mutex Deadlock

when thread needs to simultaneously access two or more resource. each of which is govern by separate mutex. when more than one thread try to lock same set of mutex, deadlock situation can arise.

thread 1	thread 2
pthread_mutex_lock(&m1) pthread_mutex_lock(&m2)	pthread_mutex_lock(&m2) pthread_mutex_lock(&m1)

*here both threads are waiting to unlock each other mutex. so both are in wait state forever. this is deadlock situation.

to avoid this locking of mutex in order. if both thread lock mutex in order they will not enter in deadlock. another way to use “try and lock backoff”

pthread_mutex_trylock() : if mutex is currently lock it return EBUSY err.

pthread_mutex_timedlock(): caller can specify an additional argument, abstime that place a limit on the time that the thread will sleep while waiting to acquire mutex. if timeout it return ETIMEOUT err.

so best way to avoid deadlock is. thread locks the first mutex with pthread_mutex_lock() and then lock remaining mutex with pthread_mutex_trylock(). if try lock fail thread release all mutex and then try again.

Dynamic Mutex

the static initializer value PTHREAD_MUTEX_INITIALIZER can used only for initializing statically allocated mutex with default attributes.

for other case we must use dynamically initialize the mutex using pthread_mutex_init().

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr)

• mutex is dynamically allocated on the heap.
• we cant initialize statically allocated mutex other than default attributes.

when mutex no longer require we can free it with pthread_mutex_distroy() method.

int pthread_mutex_distroy(pthread_mutex_t *mutex) 

Signaling Changes of state: Conditional Variables

• conditional variable allowed thread to inform other threads about change in the stae of variable.
• Consider thread_A is waiting for flag to set. if we use loop eg while(flag == True){…} its take unnecessary CPU load to continue monitor the flag. so to overcome this we can use conditional variables.

int pthread_cond_signal(pthread_cond_t *cond);

int pthread_cond_broadcast(pthread_cond_t *cond);

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);

• principle of conditional variable is signal and wait. ( signal is indication its not UNIX signal) 
• pthread_cond_signal(), we are simply guaranteed that at least one of the blocked threads is woken up.
• pthread_cond_broadcast(), all blocked threads are woken up.
• pthread_cond_signal() is more efficient. all waiting thread are not awake. one thread shedule first check variable. perform task, unlock the variable and signal it again. so one by one execution.

so if Task of thread are associated with each other. depending on each other we must use it.

pthread_cond_broadcast() all waiting state get signal any of the thread. and any of can lock mutex and do operation and unlock mutex. if Task of threads are not related to each other and then we can use it.

Example:

int flag = 0;
 
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t con = PTHREAD_COND_INITIALIZER;
void *wait_thread(void *arg)
{
    pthread_cond_wait(&con, &mtx);
    if (flag == 1)
        printf("wait thread\n");
    pthread_exit(NULL);
}
void *while_thread(void *arg)
{
    while (flag == 0)
    {
        printf("checking flag in while thread...\n");
        sleep(1);
    }
    printf("while thread flag is set\n");
    pthread_exit(NULL);
}
void signal_to_thread()
{
    pthread_mutex_lock(&mtx);
    flag = 1;
    pthread_mutex_unlock(&mtx);
    pthread_cond_signal(&con);
}
int main()
{
    pthread_t thread_wait_id;
    pthread_t thread_while_id;
    pthread_create(&thread_wait_id, NULL, wait_thread, NULL);
    pthread_create(&thread_while_id, NULL, while_thread, NULL);
    sleep(5);
    printf("now give signal to thread \n");
    signal_to_thread();
    pthread_join(thread_wait_id, NULL);
    pthread_join(thread_while_id, NULL);
    return (0);
}

*here two thread one is demo of while thread where we always checking the status of flag.

but that tack CPU .

so wait_thread where we are only waiting for signal. if signal received then we check the status of flag.

Thread Safety

• function can be called by multiple threads at a same time. that function is called thread safe function.
• lock the mutex when function called, unlock it when mutex return.
• this is inefficient because there is a cost of locking and unlocking mutex.
• A reentrant function archive thread safety without mutexes. by avoiding the use of global variable and static variables.

One Time Initialization

• sometimes, a threaded application needs to be ensure that some of the initialization action occurs just once, regardless how many threads are created.
• if we are creating a thread in main() program than it is easy to archive the initialization before any thread start. but in library function this is not possible. because calling program may create threads before the first call of library function.

int pthread_once(pthread_once_t *once_control, void (*init)(void))

The pthread_once() function uses the stat of the argument once_control to ensure that the caller-defined function pointer by init is called just once, no matter how many times or from how many different threads the pthread_once() call is made.

Example:

pthread_once_t once_var = PTHREAD_ONCE_INIT;
void init(void)
{
/* function body */
}

Canceling Thread’s

int pthread_cancel(pthread_t thread)

The pthread_cancel() sends a cancellation request to specific thread. it is non blocking function.

to enable cancellation we need to set thread state and type parameters by pthread_setcancelstate() and pthread_setcancletype().

int pthread_setcancelstate(int stat, int *oldstate)

int pthread_setcanceltype(int type, int *oldtype)

state : PTHREAD_CANCEL_DISABLE thread is not cancelable. if request received. it remain pending until cancelability enable.

  PTHREAD_CANCEL_ENABLE Default state, thread is cancelable.

type : PTHREAD_CANCEL_ASYNCHRONOUS thread can cancel anytime.

     PTHREAD_CANCEL_DEFERRED cancel remain pending until reach cancellation point. Normally all blocking library function is cancellation points like, read(), send(), sleep(), wait()…

Cleanup Handler

when thread is cancel it need to be handle to cleanup. cause pthread object (mutexes) shared variable might be left in inconsistent state. it cause remaining thread unpredictable, deadlock or crash.

so thread can establish one or more clean_up handler. most recent handler call first.

void pthread_cleanup_push(void (*routine) (void*),void *arg)

void pthread_cleanup_pop(int execute)

Threads and Process Control

Threads and exec():

• Calling Program completely replaced.
• All Threads vanish immediately except exec() calling thread.
• no of the thread can execute destrutor or cleanup handler.
• all of the mutex, conditional variable belonging with process also vanish.
• After exec() , the Thread ID of threads are unspecified.

Threads and fork():

• only calling thread replaced with child process.
• all other threads in vanish in child process.
• no thread specific data-structure or cleanup handler call.

problem with fork():

• parent property child get duplicated. so all the global data and mutex are copy in child.
• this is very dangerous. consider thread lock mutex and fork() is updating global data. in this case thread and child not able to unlock mutex and block there.and child copy of global data in inconsistency state.
• since distructor not called memory leak can happned and may be mutex lock is not unlock.

Threads and exit():

• all thread immediately vanish.
• no thread cleanup handler or destructor can executed.

IPC (InterProcess Communication)

Three Fundamental Category

• Communication exchanging data between processes
• Synchronization Sync the process.
• Signal signal no itself is information, used for sync too.

notes:

• FIFO were developed on System V, while socket were on BSD. FIFO for same machine only but Socket communication over network( different machine).
• POSIX IPC improvement over System V.

Communication

• Data-transfer facility require data transfer between user-space to kernel space. one transfer user-memory to kernel-memory while writing, another transfer kernel memory to user memory during reading. (context switch user to kernel, and kernel to user Slow IPC)
• Shared Memory process exchanging information by placing it in an region of memory that is shared between process.(no context switch Fast IPC).

Data Transfer

• Byte Stream data exchanged via pipe, FIFO. and datagram sockets is an undelimited byte-stream.
• Message Data transfer via System V message queue, POSIX message queue. and datagram socket takes a form of delimited message.
• data-transfer facility may have multiple reader, reads are destructive. data available for only one process. 

Sync 

• require. read operation will block until some process writes data to facility.
• shared memory is fastest IPC and can be access by any process. but to ensure synchronization we must use mechanism of semaphore.

Semaphore

• A semaphore is kernel maintained integer. whose value not can not be fall below 0.
• Process can increase/decrease semaphore value.
• A process decrements a semaphore (form 1 to 0) in order to reverse exclusive action to some shared resource, and after completing work on the resource, increment semaphore so other process can use it.
• binary semaphore is value 1 and 0 is common.
• Application that deal with multiple threads and multiple shared resource in shared memory should use semaphore value equal to threads. so all thread can access shared memory resource.

File locks

• A synchronization method design to co-ordinate the actions of multiple process on same file.
• any number of process can hold a read lock on file. however when one process hold write lock on file. other process then prevented from holding write/read lock on same file.
• fcntl() system call provides record locking , allowing process to place multiple read and write locks on different region of the same file

Mutexes and Conditional variables

mutex and conditional variable technique used in Threads. for record locking and shared memory lock we semaphore is a best choice.

PIPES AND FIFOS

• pipes are oldest method of IPC, 1970s third edition of UNIX,
• pipes provide elegant solution to frequent requirement: having two process run different program( commands)
• how can shell produce by one process to use as input to another process? pipes can be used to pass data between related process
• FIFOs are variation of pipe concept. the importance difference is FIFOs can be used for communication between any process.

pipe is byte stream mean there is no concept of message or message boundaries when using pipe. pie can read blocks of data any size, regardless of size of block written by the writing process. data passes sequentially bytes are read exactly order were they were written.

pipe are unidirectional data can travel only one direction.

pipe() system call creates new pipe.

int pipe(int array[2])

*array[0] = read-end, array[1] = write-end 

*return 0 for success -1 on error 

• A successful pipe call return two file descriptor in array field. one for reading and second for writing.
• whatever data written in pipe is available to read at another end. read() can get lesser than available byte in pipe. read() will block if pipe is empty.
• Normally we use pipe to communicate to related process. related means parent and child process.
• fork() child process also get read and write file descriptor. so both can read and write in pipe.
• we should close unused file-descriptor in both child and parent process.
• Parent to Child communication Parent read and child write should close.
• Child to parent communication Chile read and parent write should close.
• cause pipe is unidirectional. for two way communication we need two pipe.
• closing unused file-descriptor for application is ensuring that process should not exhaust its limited set of file descriptor.
• reading process read() will block cause kernel knows that another write() end is open.
• writing process write() until pipe is full cause kernel knows there is read() end is open.

Example:

/* pipe half duplex communication */
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
 
int g_pipe[2];
 
int main(){
 if( pipe(g_pipe) != 0)
 {
  perror("pipe");
 }
 if(fork()==0)
 {/* child process */
  printf("child process id :%d process parend id :%d\n",getpid(),getppid());
  char data[] = "Hello World";
  write(g_pipe[1],data,strlen(data));
  exit(0);
 }
 else
 {/* parent process */
  printf("parent process id :%d process parend id :%d\n",getpid(),getppid());
  char data1[15] = {};
     read(g_pipe[0],data1,sizeof(data1));
  printf("data : %s\n",data1);   
 }
}

output:

parent process id :412 process parend id :8
child process id :413 process parend id :412
data : Hello World

Example: Full-Duplex

int g_parent_pipe[2];
int g_child_pipe[2];
int main()
{
 /* Creating Pipes */
        pipe(g_parent_pipe);
 pipe(g_child_pipe);
 
 if( fork() == 0){ /* child process */
  char data[20] = {};
  close(g_child_pipe[0]); /* closing child read in child*/
  close(g_parent_pipe[1]); /* closing parent write in child */
  write(g_child_pipe[1],"HELLO",5); 
  read(g_parent_pipe[0],data,20);
  printf("child:%s\n",data);
  exit(0);
 }
 else{ /* parent process */
  char data[20]= {};
  close(g_child_pipe[1]); /* closing child write in parent*/
  close(g_parent_pipe[0]); /* closing parent read in parent */
  read(g_child_pipe[0],data,20);
  write(g_parent_pipe[1],"hello",5);
  printf("parent:%s\n",data);
 }
}

output:

parent:HELLO
child:hello

FIFO (named pipe)

First in First Out is similar to pipe only difference is FIFO has name within file-system and open as same way as regular file.
FIFO is used to communicate unrelated process (server/client)
if all file descriptors have been close. any outstanding data discarded.

int mkfifo(const char *file_path, mode_t mode)

• FIFO for reading (open() O_RDONLY flag) blocks until another process open FIFO for writing.
• FIFO for writing(open() O_WRONLY flag) blocks until another process open FIFO for reading.
• for non blocking call apply O_NONBLOCK flag.
• Avoid use of O_RDWR flag unspecified behavior. process will never find end-of-file when reading from the resulting file descriptor. there always one file descriptor open that is unused.

Process Communication Strategy

Non-Block I/O O_NONBLOCK flag in open call has no effect if FIFO is already open

• FIFO is open for reading . and no process open for writing. then open() success.
• FIFO is open for writing and other and for reading is not open then open() fails.

operation open()	flag	open other-end	close other-end
reading	-	success	block
	O_NONBLOCK	success	success
writing	-	success	bloick
	O_NONBLOCK	success	fail (error ENXIO)

O_NONBLOCK prevent dead-lock.

fcntl() to enable /disable flags of open file descriptor.

Example: Full-Duplex

int flags;
 
flags = fcntl(fd, F_GETFL); /*Fetch the flags of open file descriptor */
 
flags |= O_NONBLOCK; /*Enable flag */
 
flags &= ~O_NONBLOCK; /* Disable flag */
 
fcntl(fd, F_SETFL,flags) /* Apply Flag */

Message Queue (System V)

• exchanging data in form of message between process.
• message queue identifier from msgget() is not same as file-descriptor.
• reader receive whole message. reader can receive multiple message at same time.
• message can retrieve with First in First policy.

Creating or Opening Message Queue

int msgget(key_t key, int msgflg)

 return message queue identifier on success and -1 on error

• IPC_CREAT if no identifier is with specified key. create a new queue.
• IPC_EXCL if already identifier is with key generate error EEXIST 

Commnads

• ipcs ipc -s show information of ipc facilities.
• ipcrm ipc -rm remove some ipc facilities.

Sending Message

int msgsnd(int msqid, const void *msqp, size_t msqsz, int msqflg)

write a message to message queue.

struct mymsg
{
	long mtype; /* message type */
	char mtext[]  /* message body */   
};

• message type of msgp structure must be greater than 0. copy desired information in program defined type mtext field. final argument is flag.
• IPC_NOWAIT perform non blocking send.
• Writing a message in queue require write permission on queue.

Receiving Message

int msgrcv(int msqid, void *msqp, size_t maxmsgz, long msgtyp, int msgflg)

• The msgrcv() system call reads (remove) message from message queue.
• if reading more than a message size , no message read fail and E2BIG error generate.
• message need not to be read in order they were sent. selection is control by msgtyp argument.
• msgtyp equals 0, first message from queue is removed and return to calling process.
• msgtyp is greater than 0, first message that msgtyp match with msgtype is removed from queue.
• msgtype is less than0, treat waiting message as priority queue. first message of the lowest msgtyp less than or equal to msgtyp is removed from queue.

Control Message

int msgctl(int msqid, int cmd, struct msqid_ds *buf)

• cmd argument specifies the operation to perform on the queue.
• IPC_RMID Immediately remove message from message queue.
• IPC_STAT copy of the message queue status to msqid_ds structure pointed by buff.
• IPC_SET update field as structure.

notes:

• message queue is limited capacity.
• message queue refer to identifier rather then file descriptor, so select(), poll() cant apply.
• complex code. require ftok() for unique key, ipcs ,ipcrm cmds.
• connection less, difficult to safe message queue to delete by an application.
• limited no of message queue available in system.
• POSIX message queue better option.

Semaphores System V

• semaphore is not used to transfer data between process. they allow process to synchronize there action.
• common use to synchronize access of shared memory.
• A semaphore is kernel maintain integer whose value >= 0.
• waiting for semaphore to equal to 0 block calling process.
• create semaphore with semget().
• initialize semaphore using semctl() SETVAL, SETALL operation.
• perform operation on semaphore with semop() use and release of semaphore.
• remove the semaphore with semctl() IPC_RMID operation.

create semaphore:

int semget(key_t key, int nsems, int semflg);

• semget() system call create a new semaphore or obtain identifier for existing set.
• key argument IPC_PRIVATE or key return by ftok().
• nsems number of semaphore in set, nsems must be greater than 0
• not possible to change number of semaphore for existing set.
• semget() return new semaphore set identifier or existing on success, -1 on error.

control semaphore:

int semctl(int semid, int semnum, int cmd, … /* union semun arg */);

• semid is identifier of semaphore on which operation to perform.
• semnum argument identifies a particular semaphore within the set.
• cmd argument specifies the operation to perform.
• semaphore creation and initialization must be perform by separate system call.
• one process must initialize semaphore before any process use it. to avoid race condition.

operation semaphore:

int semop(int semid, struct sembuf *sops, unsigned int nsops);

• one or more operation on the semaphore
• sops is a pointer to array that contain the operation to perform, nsops is size of array.

Shared Memory

two unrelated processes to access the same logical memory. Shared memory is a very efficient way of transferring data between two running

processes

• Shared memory is a special range of addresses that is created by IPC for one process and appears in the address space of that process
• If one process writes to the shared memory, the changes immediately become visible to any other process that has access to the same shared memory.
• shared memory doesn’t provide any synchronization facilities.

#include <sys/shm.h>
void *shmat(int shm_id, const void *shm_addr, int shmflg);
int shmctl(int shm_id, int cmd, struct shmid_ds *buf);
int shmdt(const void *shm_addr);
int shmget(key_t key, size_t size, int shmflg);

shmget - allocates a System V shared memory segment

• There’s a special key value, IPC_PRIVATE , that creates shared memory private to the process.
• The second parameter, size , specifies the amount of memory required in bytes.
• The third parameter, shmflg , consists of nine permission flags that are used in the same way as the mode flags for creating files. A special bit defined by IPC_CREAT must be bitwise ORed with the permissions to create a new shared memory segment.
• the shared memory is successfully created, shmget returns a nonnegative integer, the shared memory identifier. On failure, it returns –1.

shmat, shmdt - System V shared memory operations

• When you first create a shared memory segment, it’s not accessible by any process. To enable access to the shared memory, you must attach it to the address space of a process.
• The first parameter, shm_id , is the shared memory identifier returned from shmget.
• The second parameter, shm_addr should almost always be a null pointer, which allows the system to choose the address at which the memory appears.
• If the shmat call is successful, it returns a pointer to the first byte of shared memory. On failure –1 is returned.
• The shmdt function detaches the shared memory from the current process.

shmctl - System V shared memory control

• The control functions for shared memory are (thankfully) somewhat simpler than the more complex ones for semaphores

Example: Full-Duplex

struct shmid_ds {
    uid_t shm_perm.uid;
    uid_t shm_perm.gid;
    mode_t shm_perm.mode;
};

The first parameter, shm_id , is the identifier returned from shmget

• The second parameter, command , is the action to take. It can take three values
• IPC_STAT Sets the data in the shmid_ds structure to reflect the values associated with the shared memory.
• IPC_SET Sets the values associated with the shared memory to those provided in the shmid_ds data structure, if the process has permission to do so.
• IPC_RMID Deletes the shared memory segment.
• The third parameter, buf , is a pointer to the structure containing the modes and permissions for the shared memory.

Example

create common.h file

create sh1.c

create sh2.c

output