.png)
Mobiprep has created last-minute notes for all topics of operating system to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Operating System (OS).
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Synchronization
Question- 1) What are the steps to achieve synchronization?
Answer: 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
Question- 2) What is Semaphore?
Answer: 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:
1) 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++;
}2) 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--;
}Question- 3) Explain the types of Semaphore.
Answer: The two types of semaphores are:
1) 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 semaphore, only one process is allowed into the critical section at a time.
2) 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.
Question- 4) What is Dining Philosophers problem?
Answer: 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);
}
Question- 5) Explain Bounded Buffer problem.
Answer: 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);
}
Question- 6) What is Reader-Writer problem? how is it resolved?
Answer:
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);
}
Question- 7) Explain Block and Wake-up system calls.
Answer:
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.
Question- 8) What are the problems with the Semaphore?
Answer: The following are the disadvantages of using semaphores:
Implementation of semaphores is complicated. The wait() and signal() operations must be executed in the correct order to achieve process synchronization.
Semaphores cannot be used for large scale applications.
Semaphores might result in priority inversion. i.e. a process with lower priority is executed before a process with higher priority.
Usually, semaphores are global variables. They are distributed throughout the program. Hence, it is difficult to determine its usage.
Semaphores are more expensive than the mutex locks.
Question- 9) Explain Test and Set Synchronization Hardware.
Answer: 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.
Question- 10) Explain mutual exclusion with reference to Test and Set.
Answer: 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.
Question- 11) What is mutual exclusion in swap synchronization hardware?
Answer: Mutual exclusion with the swap synchronization hardware is shown below:
The swap function is given below:
void Swap(boolean *a, boolean *b)
{
boolean temp = *a;
*a = *b;
*b = temp;
}Here, lock is a global Boolean variable and key is a local Boolean variable. The lock variable is initialized to 0 (False). Each process has a key variable. When the critical section is occupied by a process, the lock variable is set to 1 (True) and the key value becomes 0 (the old value of the lock variable is swapped to the key variable). If the lock variable is set to 1, no other process can access the critical section. Thus, mutual exclusion is achieved using the swap synchronization hardware.
Question- 12) What do you mean by critical selection?
Answer: The code segment which is accessed by multiple processes concurrently is called critical section. For maintaining data consistency in the critical section, the processes must be synchronized. Else, race condition occurs and leads to the loss of data consistency.
The entry section is used to request access to the critical section. After execution in the critical section, the process enters the remainder section.
Question- 13) Define progress for process synchronization.
Answer: If there is no process executing in the critical section, then the other processes which are not executing in the remainder section only can decide which process should access the critical section next. This decision should not be delayed indefinitely.
Question- 14) What do you mean by bounded waiting?
Answer: The bounded waiting condition is used to prevent a process from waiting for a resource for an infinite amount of time. The waiting time refers to the time between the resource request and the resource allocation.
The bounded waiting condition imposes a limit on the number of the other processes that can access the critical section after a process has requested for the critical section. Hence, this prevents indefinite waiting.
Question- 15) Define race condition.
Answer: The race condition occurs when many processes or threads operate on the same data at the same time. When multiple processes attempt to change the data at the same time, output depends on the order in which the critical section is accessed. So, the processes must access the critical section in a specified order. Else, race condition will occur and cause inconsistency in the output. Hence, the output will become unpredictable.
To avoid the race condition, the processes must be synchronized.
Question- 16) Define Peterson’s Solution.
Answer: Peterson’s Solution provides a good algorithmic software based solution to the critical section problem.
There are two processes.
Shared variables used:
boolean flag[i] :Initialized to FALSE, which tells if anyone is interested in entering the critical section
int turn : Tells which process’s turn is to enter the critical section.
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
/* critical section */
flag[i] = false;
/* remainder section */
}
while (true);
Peterson’s Solution preserves all three conditions :
Mutual Exclusion is assured as only one process can access the critical section at any time.
Progress is also assured.
Bounded Waiting is preserved.
Disadvantages of Peterson’s Solution
It involves Busy waiting
It is limited to 2 processes.
Comments