Operating system Notes

mobiprep (6).png

Introduction of Operating System

mobiprep (6).png

PROCESS: Program to process, Lifecycle of the process, Process control block, IPC

mobiprep (6).png

Scheduling

mobiprep (6).png

Threads

mobiprep (6).png

Memory Management

mobiprep (6).png

File Management

mobiprep (6).png

Synchronization

mobiprep (6).png

Disk Management

mobiprep (6).png

IO Management

mobiprep (6).png

Protection And Security

Heading

Q

1

What are the steps to achieve synchronization?

LRM_EXPORT_207556595493866_20190724_1939

Ans

1. The problem arises when the system is not having the synchronization between the processes:
Producer Consumer Problem
Printer Spooler Daemon
Deadlock
2. The conditions to be followed to achieve synchronization is checked.
Mutual Exclusion
Progress
Bounded waiting
No assumption related to hardware and processor speed
3. Solution is checked.
Software type: Lock variables, Decker’s algo, peterson algo
Hardware type: Test and Set Lock(TSL) instruction set
Operating System Type: Counting, Binary semaphore, Reader writer, etc.
Programming language compiler support type

LRM_EXPORT_207556595493866_20190724_1939

Q

2

What is Semaphore?

LRM_EXPORT_207556595493866_20190724_1939

Ans

A semaphore is a non-negative integer variable. It is used to achieve process synchronization in a multi-programming system. It is used to solve the critical section problem.
Usage of semaphores is a simple method to manage the processes that are executed concurrently. It is a signaling mechanism rather than a blocking mechanism. It signals the other process or thread to access a resource.
Two operations can be performed on the semaphore variable. They are:
Signal()
When a process leaves the critical section, it executes the signal()/V()/release() operation. The signal() operation increments the variable value by 1.
signal(S)
{
S++;
}
Wait()
When a process enters the critical section, the wait()/P() operation is executed. It decrements the variable value by 1.
wait(S)
{
while (S<=0);
S--;
}

LRM_EXPORT_207556595493866_20190724_1939

Q

3

Explain the types of Semaphore.

LRM_EXPORT_207556595493866_20190724_1939

Ans

The two types of semaphores are:
Binary semaphore
A binary semaphore can have only two values – 0 or 1. The initial value of a binary semaphore is 1. It is also called a mutex lock. It is easier to implement than the counting semaphore.
Using a binary semphore, only one process is allowed into the critical section at a time.

Counting semaphore
A counting semaphore can take any integer value. It must not be a negative integer. The initial value of a counting semaphore is N where N is the number of units available.
Using the counting semaphore, more than one process can be allowed into the critical section.

LRM_EXPORT_207556595493866_20190724_1939

Q

4

What is Dining Philosophers problem?

LRM_EXPORT_207556595493866_20190724_1939

Ans

Input Constraints
There are five philosophers sitting around a circular table. There are five chopsticks, each between every pair of philosophers. A cup of noodles is placed at the center of the table.
If a philosopher wants to eat, he picks up two chopsticks (one from his right and one from his left). A chopstick can be used by one philosopher at a time. Hence, no two adjacent philosophers can eat simultaneously.
A philosopher can be in one of the following three states:
Eating
While eating, a philosopher holds the two chopsticks by his side.
Thinking
While a philosopher is thinking, he does not hold any chopstick.
Hungry
A hungry philosopher can eat only if the two chopsticks are available. Else, he waits for the chopsticks to be put down by the adjacent philosopher.

Problem
If each philosopher simultaneously picks up the left fork, a cycle is formed where no philosopher can eat without picking the right fork held by neighboring philosopher. Hence the condition of deadlock.

Solution
Here, the chopsticks are considered as resources, and the philosophers are considered as processes. Hence, the limited resources should be allocated efficiently to all the processes, to avoid deadlock.
We use semaphores to solve this problem.
The chopstick is represented by a semaphore. Hence, the chopstick is picked up by the philosopher by executing the wait() operation on the chopstick. Once the philosopher finishes eating, he puts down the chopstick and executes the signal() operation.

Algorithm
The structure of a philosopher is shown below:
do {
wait( chopstick[i] );
wait( chopstick[ (i+1) % 5] );
. .
. EATING THE NOODLES
.
signal( chopstick[i] );
signal( chopstick[ (i+1) % 5] );
.
. THINKING
.
} while(1);

C Code
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

#define N 5
#define THINKING 2
#define HUNGRY 1
#define EATING 0
#define LEFT (phnum + 4) % N
#define RIGHT (phnum + 1) % N

int state[N];
int phil[N] = { 0, 1, 2, 3, 4 };

sem_t mutex;
sem_t S[N];

void test(int phnum)
{
if (state[phnum] == HUNGRY
&& state[LEFT] != EATING
&& state[RIGHT] != EATING) {
// state that eating
state[phnum] = EATING;

sleep(2);

printf("Philosopher %d takes fork %d and %d\n",
phnum + 1, LEFT + 1, phnum + 1);

printf("Philosopher %d is Eating\n", phnum + 1);

// sem_post(&S[phnum]) has no effect
// during takefork
// used to wake up hungry philosophers
// during putfork
sem_post(&S[phnum]);
}
}

// take up chopsticks
void take_fork(int phnum)
{

sem_wait(&mutex);

// state that hungry
state[phnum] = HUNGRY;

printf("Philosopher %d is Hungry\n", phnum + 1);

// eat if neighbours are not eating
test(phnum);

sem_post(&mutex);

// if unable to eat wait to be signalled
sem_wait(&S[phnum]);

sleep(1);
}

void put_fork(int phnum)
{
sem_wait(&mutex);

// state that thinking
state[phnum] = THINKING;

printf("Philosopher %d putting fork %d and %d down\n",
phnum + 1, LEFT + 1, phnum + 1);
printf("Philosopher %d is thinking\n", phnum + 1);
test(LEFT);
test(RIGHT);
sem_post(&mutex);
}

void* philospher(void* num)
{
while (1) {

int* i = num;
sleep(1);
take_fork(*i);
sleep(0);
put_fork(*i);
}
}

int main()
{
int i;
pthread_t thread_id[N];

// initialize the semaphores
sem_init(&mutex, 0, 1);

for (i = 0; i < N; i++)
sem_init(&S[i], 0, 0);
for (i = 0; i < N; i++) {
// create philosopher processes
pthread_create(&thread_id[i], NULL,
philospher, &phil[i]);

printf("Philosopher %d is thinking\n", i + 1);
}
for (i = 0; i < N; i++)
pthread_join(thread_id[i], NULL);
}

LRM_EXPORT_207556595493866_20190724_1939

Q

5

Explain Bounded Buffer problem

LRM_EXPORT_207556595493866_20190724_1939

Ans

The bounded buffer problem is also called the producer consumer problem.
Input Constraints
There is a producer, consumer and a buffer. The producer produces the data and places it in the buffer. The consumer consumes the data in the buffer.
Problem
Both the producer and the consumer must not access the buffer at the same time. The buffer must be accessible to either the producer or the consumer at a time. It is a problem of process synchronization.

Solution
A mutex lock is used to lock and unlock the buffer (critical section). The variable empty is used to indicate the number of empty slots in the buffer. The variable full is used to indicate the number of slots which are not empty. The variables empty and full are initialized to N and 0 respectively. (N is the number of slots in the buffer). Empty and full are counting semaphores.
The producer waits until one of the buffer slots is empty. If any of the slots becomes empty, the producer locks the buffer and inserts data into the empty slot. Then, it decrements the empty semaphore by 1.
The consumer waits until one of the buffer slots is full. If any of the buffer slots is full, the consumer locks the critical section (buffer) and consumes the data in the non-empty slot. Then, it decrements the full semaphore by 1.

Algorithm
Producer
do
{
// wait until empty > 0 and then decrement 'empty'
// that is there must be atleast 1 empty slot
wait(empty);
// acquire the lock, so consumer can't enter
wait(mutex);
/* perform the insert operation in a slot */
// release lock
signal(mutex);
// increment 'full'
signal(full);
}
while(TRUE)

Consumer
do
{
// wait until full > 0 and then decrement 'full'
// should be atleast 1 full slot in buffer
wait(full);
// acquire the lock
wait(mutex);
/* perform the remove operation in a slot */
// release the lock
signal(mutex);
// increment 'empty'
signal(empty);
}
while(TRUE);

C Code
#include<stdio.h>
#include<stdlib.h>

int mutex=1,full=0,empty=3,x=0;

int main()
{
int n;
void producer();
void consumer();
int wait(int);
int signal(int);
printf("\n1.Producer\n2.Consumer\n3.Exit");
while(1)
{
printf("\nEnter your choice:");
scanf("%d",&n);
switch(n)
{
case 1: if((mutex==1)&&(empty!=0))
producer();
else
printf("Buffer is full!!");
break;
case 2: if((mutex==1)&&(full!=0))
consumer();
else
printf("Buffer is empty!!");
break;
case 3:
exit(0);
break;
}
}

return 0;
}

int wait(int s)
{
return (--s);
}

int signal(int s)
{
return(++s);
}

void producer()
{
mutex=wait(mutex);
full=signal(full);
empty=wait(empty);
x++;
printf("\nProducer produces the item %d",x);
mutex=signal(mutex);
}

void consumer()
{
mutex=wait(mutex);
full=wait(full);
empty=signal(empty);
printf("\nConsumer consumes item %d",x);
x--;
mutex=signal(mutex);
}

LRM_EXPORT_207556595493866_20190724_1939

Q

6

What is Reader-Writer problem? how is it resolved?

LRM_EXPORT_207556595493866_20190724_1939

Ans

Problem
If a file is shared among many people, the file should not be read and written at the same time. This causes inconsistency of data. If a person is reading the file, no other person must be allowed to edit or make changes to the file. If a person is editing the file, no readers should be permitted to read the file.
Solution
In the proposed solution, the reader has more priority than the writer.
When the reader requests access to the critical section, it is allowed access if no writer is editing the critical section. If the reader is allowed access to the critical section it increments the readcnt variable by 1. The readcnt variable represents the number of readers currently reading the file. If it is the first reader, it locks the critical section to prevent access to the writer.
When a reader requests access to the file, it is allowed access if no reader is reading the file.
Algorithm
Reader
do {
// writer requests for critical section
wait(wrt);

// performs the write

// leaves the critical section
signal(wrt);

} while(true);
Writer
do {
// Reader wants to enter the critical section
wait(mutex);
// The number of readers has now increased by 1
readcnt++;
// there is atleast one reader in the critical section
// this ensure no writer can enter if there is even one reader
// thus we give preference to readers here
if (readcnt==1)
wait(wrt);
// other readers can enter while this current reader is inside
// the critical section
signal(mutex);
// current reader performs reading here
wait(mutex); // a reader wants to leave
readcnt--;
// that is, no reader is left in the critical section,
if (readcnt == 0)
signal(wrt); // writers can enter
signal(mutex); // reader leaves
} while(true);

C Code
#include<stdio.h>
#include<pthread.h>
#include<semaphore.h>
sem_t mutex;
sem_t db;
int readercount=0;
pthread_t reader1,reader2,writer1,writer2;
void *reader(void *);
void *writer(void *);
main()
{
sem_init(&mutex,0,1);
sem_init(&db,0,1);
while(1)
{
pthread_create(&reader1,NULL,reader,"1");
pthread_create(&reader2,NULL,reader,"2");
pthread_create(&writer1,NULL,writer,"1");
pthread_create(&writer2,NULL,writer,"2");
}
}
void *reader(void *p)
{
printf("prevoius value %dn",mutex);
sem_wait(&mutex);
printf("Mutex acquired by reader %dn",mutex);
readercount++;
if(readercount==1) sem_wait(&db);
sem_post(&mutex);
printf("Mutex returned by reader %dn",mutex);
printf("Reader %s is Readingn",p);
//sleep(3);
sem_wait(&mutex);
printf("Reader %s Completed Readingn",p);
readercount--;
if(readercount==0) sem_post(&db);
sem_post(&mutex);
}
void *writer(void *p)
{
printf("Writer is Waiting n");
sem_wait(&db);
printf("Writer %s is writingn ",p);
sem_post(&db);
//sleep(2);
}

LRM_EXPORT_207556595493866_20190724_1939

Q

7

Explain Block and Wake-up system calls

LRM_EXPORT_207556595493866_20190724_1939

Ans

Blocking System Call
A blocking system call waits for an I/O operation to be completed. It causes the process to be blocked until the I/O operation is over.
EXAMPLE:
The read() system call is an example of blocking system call because it waits for the user input. If the user does not give an input, it waits indefinitely. Once the user gives an input, the value is returned to the process.
Wake-Up
The wake-up system call is used by a process when it leaves the critical section. It is used to wake-up the blocked processes which are waiting for access to the critical section.
When a process is already executing in the critical section, the other process that requests access to the critical section enters the sleep state. Once the process executing in the critical section leaves the critical section, it calls the wakeup function to schedule the waiting process to the critical section.

LRM_EXPORT_207556595493866_20190724_1939

Q

8

What are the problems with the Semaphore?

LRM_EXPORT_207556595493866_20190724_1939

Ans

The following are the disadvantages of using semaphores:
1.Implementation of semaphores is complicated. The wait() and signal() operations must be executed in the correct order to achieve process synchronization.
2.Semaphores cannot be used for large scale applications.
3.Semaphores might result in priority inversion. i.e. a process with lower priority is executed before a process with higher priority.
4.Usually, semaphores are global variables. They are distributed throughout the program. Hence, it is difficult to determine its usage.
5.Semaphores are more expensive than the mutex locks.

LRM_EXPORT_207556595493866_20190724_1939

Q

9

Explain Test and Set Synchronization Hardware

LRM_EXPORT_207556595493866_20190724_1939

Ans

Test and Set is a hardware synchronization mechanism. It uses the lock variable to synchronize the processes executing concurrently.
If lock=1, it means that the critical section is locked and no process shall enter the critical section. If lock=0, it means that the critical section is free and the process shall enter and execute the critical section.

int TestAndSet(int &lock) {
int initial = lock;
lock = 1;
return initial;
}
void enter_CS(X)
{
while test-and-set(X) ;
}
void leave_CS(X)
{
X = 0;
}
The test and set mechanism satisfies mutual exclusion and progress, but does not satisfy the Bounded wait condition.

LRM_EXPORT_207556595493866_20190724_1939

Q

10

Explain mutual exclusion with reference to Test and Set

LRM_EXPORT_207556595493866_20190724_1939

Ans

The test and set mechanism uses the lock variable. If lock=1, it means that the critical section is being used by a process. When the value of the lock variable is 1, no other process is allowed to access the critical section. A process can execute the critical section only when the value of the lock variable is 0. This shows that the critical section can be used by only one process at a time. Thus, mutual exclusion is achieved using a test and set mechanism.

LRM_EXPORT_207556595493866_20190724_1939