DEV Community: Anna

Scheduling Algorithms in Operating Systems - Part 5 - Highest Response Ratio next

Anna — Tue, 07 Dec 2021 12:41:37 +0000

You can skip the intro if you have been through the Part - 1 or Part - 2 or Part - 3 or Part - 4 of the series

Like humans, the operating system needs to plan its activities. These activities are the various processes that need to be executed by the OS. The OS needs to schedule all its processes properly to ensure that they get executed without any problems and in minimal time.

For this purpose, there are many scheduling algorithms like the First Come First Serve (FCFS) algorithm, Shortest Job First (SJF) algorithm, etc. We will be discussing these algorithms in detail but before that, we need to understand some terms.

Arrival Time: The time at which the process arrives in the processor for execution.
Waiting Time: The time for which a process has to wait before it starts executing. A process may have to wait if some other process is being executed (in a uniprocessor environment) or when the resources required by the process are not available, etc. It is calculated as :

Waiting time = Completion Time- Arrival Time- Service Time
1. Service Time/ Burst time: The time required by the process to complete its execution.
2. Turnaround Time: The interval between the time at which the process starts executing and the arrival time of the process. It is calculated using the formula: > Turnaround Time = Service Time + Waiting Time

Now, let us have a look at the Highest Response Ratio Next algorithm :

Highest Response Ratio Next Algorithm:

In this, for execution, we select the process that has the highest response ratio.

Response Ratio =( Waiting Time + Service Time ) / Service time

Let us understand this using an example:

Here, process A is the only process to enter the processor and hence it starts executing. Meanwhile, B enters the queue.

Now, since B is the only process to enter the queue, it starts executing next.

Now comes the trickier part.

There are three processes — C, D, E in the queue. How do we decide which one to select out of these?

It's very easy! We calculate the response ratio for each of them using the formula mentioned earlier.

As you can see, C has the highest response ratio. Hence it will be executed next.

Now we have to choose between process D and E. Let us calculate the response ratio for these processes.

Since E has the highest response ratio, it is executed next.

Now the only process left is D. Hence, it will be executed finally.

Let us now calculate the average waiting time and turnaround time for this example:

This is how processes are scheduled using the Highest Response Ratio algorithm.

Here, the disadvantage is that extra calculation is required. Also, the service time has to be known and the waiting time has to be tracked.

Hope this helps you!

Have a nice day 😊!!

PS : This was the last part of the scheduling algorithms series. Hope all your questions were answered. Still if there's anything you need to ask or add to what I've posted please let me know in the comments.
Thanks!

Scheduling Algorithms in Operating Systems - Part 4 - Priority Scheduling Algorithm

Anna — Tue, 07 Dec 2021 12:29:43 +0000

You can skip the intro if you have been through the Part - 1 or Part - 2 or Part - 3 of the series

Arrival Time: The time at which the process arrives in the processor for execution.
Waiting Time: The time for which a process has to wait before it starts executing. A process may have to wait if some other process is being executed (in a uniprocessor environment) or when the resources required by the process are not available, etc. It is calculated as :

Waiting time = Completion Time- Arrival Time- Service Time
1. Service Time/ Burst time: The time required by the process to complete its execution.
2. Turnaround Time: The interval between the time at which the process starts executing and the arrival time of the process. It is calculated using the formula: > Turnaround Time = Service Time + Waiting Time

Now, let us have a look at the Priority Scheduling algorithm :

Priority Scheduling Algorithm:

In this algorithm, every process has a specific priority and is executed according to the given priority.

Non-Preemptive Priority Scheduling Algorithm:

In this algorithm, the process of highest priority is completely executed first and then the process with the next highest priority is executed.

Let's take an example:

In the above example, we have 5 processes A, B,C, D,E

Processes A and B enter the processor first. Out of those two processes, process B has a higher priority and hence, process B will be executed first.

Meanwhile, the other processes are added to the waiting queue.

Now, after B completes its execution, the waiting queue is checked. Process D is the process in the waiting queue with the highest priority. Hence, it is executed next.

Similarly, now from the queue, process E has the highest priority and is therefore executed.

Again, considering the priority, process C is executed….

followed by the process A.

Now, let us calculate the average waiting time and turnaround time.

Advantages:

The processes of higher priority get preference and are made to execute earlier.

Disadvantages:

The processes with lower priority may suffer starvation.

Preemptive Scheduling Algorithm:

In this algorithm, if a process with a priority higher than that of the process being executed enters, the processor is preempted and that process starts executing.

For example,

Here at 0ms processes A and B enter the system. B being the process with the highest priority starts executing first….

..but as process D enters the processor since D has a higher priority, it starts executing next and B is added to the queue.

Now after D completes executing, (D gets completely executed as no other process with higher priority enters in between) B being the process with the highest priority starts executing next.

Next, the process E starts executing

Then, process C starts executing

And finally, process A starts executing

Now, let us calculate the average waiting time and turnaround time

The advantage of this algorithm is that the processes with higher priority do not have to wait, hence they are not starved.

In the next post, let us have a look at the Highest Response Ratio Next Algorithm.

Hope this helps you!

Have a nice day 😊!!

Scheduling Algorithms in Operating Systems - Part 3 - Round Robin Algorithm

Anna — Tue, 07 Dec 2021 12:22:46 +0000

You can skip the intro if you have been through the Part - 1 or Part - 2 of the series

Arrival Time: The time at which the process arrives in the processor for execution.
Waiting Time: The time for which a process has to wait before it starts executing. A process may have to wait if some other process is being executed (in a uniprocessor environment) or when the resources required by the process are not available, etc. It is calculated as :

Waiting time = Completion Time- Arrival Time- Service Time
1. Service Time/ Burst time: The time required by the process to complete its execution.
2. Turnaround Time: The interval between the time at which the process starts executing and the arrival time of the process. It is calculated using the formula: > Turnaround Time = Service Time + Waiting Time

Now, let us have a look at the Round Robin algorithm :

Round robin algorithm :

In this method, every process is executed for a specific interval or time quantum and after the interval is over the next process to arrive starts executing for the same amount of time.

Let's take an example.

Consider a time quantum of 4ms

A being the first process to arrive starts executing first.

Though the time quantum is 4ms, A needs 3ms, 1ms less than the time quantum. Hence, it gets completely executed 1ms earlier.

Now since B is the next process, it starts executing.

It executes for 4ms and then the execution stops. The next process i.e. C starts executing and B is put back into the waiting queue.

C process executes for 4ms and executes completely. Meanwhile, process E enters the queue.

Next, process D starts executing.

Process D executes for 4ms whereas its required time was 5ms. Hence, it is added back into the queue and the next process to be executed is process B which will execute for 2ms.

Next, process E will be executed for 2ms.

Now, the only process left in the queue is process D. Hence, it will get executed next for 1ms.

In this way, all processes are executed using the round-robin method.

Now let's have a look at the average waiting time and turnaround time.

Advantages :

An effective approach in time sharing or transaction processing time.

Disadvantages :

Relative treatment of processor bound and I/O bound processes can cause poor performance.
Inefficient use of I/O devices.
Increase in variance of response time.

In the next post, let us have a look at the Priority Scheduling algorithm.

Hope this helps you!

Have a nice day 😊!!

Scheduling Algorithms in Operating Systems - Part 2 - Shortest Job First (SJF)

Anna — Tue, 07 Dec 2021 12:16:38 +0000

You can skip the intro if you've gone through the Part - 1

Arrival Time: The time at which the process arrives in the processor for execution.
Waiting Time: The time for which a process has to wait before it starts executing. A process may have to wait if some other process is being executed (in a uniprocessor environment) or when the resources required by the process are not available, etc. It is calculated as :

Waiting time = Completion Time- Arrival Time- Service Time
1. Service Time/ Burst time: The time required by the process to complete its execution.
2. Turnaround Time: The interval between the time at which the process starts executing and the arrival time of the process. It is calculated using the formula: > Turnaround Time = Service Time + Waiting Time

Shortest Job First/ Shortest Process Next :

In this algorithm, the processes that require the least time for execution are executed first.

Let us first consider

Non-Preemptive Shortest Job First Algorithm :

Let's consider this example:

Process A is the first process to enter the processor. So it starts executing.

B is the only process in the queue now, so, it starts executing. As and when the processes arrive, they are added to the waiting queue.

Now, in the waiting queue, as we can see process E is the process that will require the least time for execution. Hence, process E starts executing.

C being the process requiring the least time starts executing next.

Finally, D starts executing

This is how the SJF algorithm works.

Now, let's calculate the waiting and turnaround time.

Advantages :

No bias for longer processes.
Improved response time.

Disadvantages :

Increased variability hence reduced predictability.
The processing time of the process needs to be known.
Possibility of starvation for longer processes.

This waiting and turnaround time can be further improved using the below method:

Preemptive Shortest Job First Algorithm (Shortest remaining time first):

In this method, while a process is executing, if a process requiring lesser service time enters, that process is executed first.

Consider the example:

A being the process to arrive first starts executing first.

Here, process B arrives at 2ms. Already executing process i.e. process A requires 1ms to complete and B needs 6ms which is greater. Hence, A continues execution.

Then B starts executing.

But at 4ms, C enters the queue. B requires 5ms to complete its execution whereas C requires 4ms. Hence, C starts executing and B is added to the queue.

While C was executing, the D process entered the queue but since the time required for D to execute was greater than that of process C, processes were not switched.

Now all the processes are either executed or are in the queue. So now the process requiring minimum time for execution will be executed first. i.e. process E.

Now, the queue has processes B and D both requiring 5ms. So any process can be executed next.

B entered the queue first hence, we will execute B first.

Now, D is the only process left. Hence, it will get executed next.

Ok, so let us now calculate the average waiting and turnaround time.

Advantages :

Improved turnaround time and waiting time than preemptive SJF.
No bias towards longer processes.

Disadvantages :

The scheduler must have an estimate of processing time.
Risk of starvation of longer processes.
Elapsed service time must be recorded which increases overhead.

In the next part, we'll see the Round Robin Algorithm.

Hope this helps you!

Have a nice day!!

IPv4 Classful Addressing

Anna — Mon, 06 Dec 2021 22:48:26 +0000

Internet protocol is a set of rules for the transfer of data/communication on the internet.IPv4 is the 4th version of the Internet Protocol.

The IPv4 uses 32-bit addresses and has 4.3 billion addresses. It uses the dotted-decimal representation, for e.g: 192.168.0.2.

The IPv4 address format is: *8bit.8bit.8bit.8bit *(adds up to 32bit)

Now, there are two types of IPv4 addresses — Classful and Classless.

We will see the classful addressing method here.

Classful Addressing:

Basically, there are 5 classes of addresses — A, B, C, D, E.

Let us now have a look at each of them one by one:

Class A:-

In Class A, as you can see above, the 32-bit address, which is divided into four sections of 8 bits each, out of those, the leading 8 bits are used to represent the network and the trailing 24 bits are used to represent the network host.

For example: 125.16.32.64 is a class A address

Now, the 1st bit of a class A address is always zero.

Since 1 bit is fixed out of the 32 bits, there are 31 bits left to represent the address. So, in total, there can be 2³¹ addresses in class A and 2⁷ network ID.

The class A addresses constitute a total of 50% of the possible addresses.

And the range for the network address is 0 to 127 (How? → If we put all zeroes in the first octet i.e. 00000000 = 0 and if we consider the last address i.e. put all ones except for the 1st bit which is 0 by default, we get 01111111 = 127).

The first and the last address i.e 0.0.0.0 and 127.255.255.255 are never used since the former is the host address/identifier and the latter is the broadcast address.

Due to this, even though 128 network addresses are available, only 126 out of them can be used.

The default subnet mask for Class A is *255.0.0.0 *(i.e. to find the network ID, we just need to logically AND our address with this subnet mask…How interesting :-) ).

Class B:-

In Class B, the leading 16 bits are used to represent the network and the trailing 16 bits are used to represent the network host.

For example: 136.192.168.64 is a class B address

Now, the 1st two bits in the first octet of a class B address are always 10.

Since 2 bits are fixed out of the 32 bits, there are 30 bits left to represent the address. So, in total, there can be 2³⁰ addresses in class B and 2¹⁴ network ID.

The class B addresses constitute a total of 25% of the possible addresses.

And the range for the network address is 128 to 191 (How? → If we put all zeroes except for the 1st 2 bits which are 10 by default, in the first octet, we get 10000000 = 128, and if we consider the last address i.e. put all ones we get 10111111 = 191).

The first and the last address i.e 128.0.0.0 and 191.255.255.255 are never used since the former is the host address/identifier and the latter is the broadcast address.

Due to this, even though 2¹⁴ network addresses are available, only 2¹⁴-2 out of them can be used.

The default subnet mask for class B is 255.255.0.0.

Class C:-

In Class C, the leading 24 bits are used to represent the network and the trailing 8 bits are used to represent the network host.

For example: 193.201.198.23 is a class C address

Now, the 1st three bits in the first octet of a class C address are always 110.

Since 3 bits are fixed out of the 32 bits, there are 29 bits left to represent the address. So, in total, there can be 2²⁹ addresses in class C and 2²¹ network ID.

The class C addresses constitute a total of 12.5% of the possible addresses.

And the range for the network address is 192 to 223 (How? → If we put all zeroes except for the 1st 3 bits which are 110 by default, in the first octet, we get 11000000 = 192, and if we consider the last address i.e. put all ones we get 11011111 = 223).

The first and the last address i.e 192.0.0.0 and 223.255.255.255 are never used .

Due to this, even though 2²⁹ network addresses are available, only 2²⁹-2 out of them can be used.

The default subnet mask for class C is 255.255.255.0.

Class D:-

In Class D, there are no hosts or networks.

For example: 225.108.162.1 is a class D address

Now, the 1st four bits in the first octet of a class D address are always 1110.

Since 4 bits are fixed out of the 32 bits, there are 28 bits left to represent the address. So, in total, there can be 2²⁸ addresses in class D.

The class D addresses constitute a total of 6.25% of the possible addresses.

And the range for the network address is 224 to 239 (How? → If we put all zeroes except for the 1st 4 bits which are 1110 by default, in the first octet, we get 111000000 = 224, and if we consider the last address i.e. put all ones we get 11101111 = 239).

These addresses are reserved for multicasting group email/broadcast.

Class E:-

Class E addresses are very similar to class D addresses.

The 1st four bits in the first octet of a Class E address are always 1111.

Since 4 bits are fixed out of the 32 bits, there are 28 bits left to represent the address. So, in total, there can be 2²⁸ addresses in class E.

The class E addresses also constitute a total of 6.25% of the possible addresses.

And the range for the network address is 240 to 255 (How? → If we put all zeroes except for the 1st 4 bits which are 1111 by default, in the first octet, we get 111100000 = 240 and if we consider the last address i.e. put all ones we get 11111111 = 255).

These addresses are reserved for military purposes.

To summarize,

So, that was all about classful addressing in IPv4.

Feel free to leave a feedback in the comments.

Have a nice day 😊

Scheduling Algorithms in Operating Systems - Part 1 - First Come First Serve (FCFS)

Anna — Mon, 06 Dec 2021 22:37:38 +0000

Arrival Time: The time at which the process arrives in the processor for execution.
Waiting Time: The time for which a process has to wait before it starts executing. A process may have to wait if some other process is being executed (in a uniprocessor environment) or when the resources required by the process are not available, etc. It is calculated as :

Waiting time = Completion Time- Arrival Time- Service Time
1. Service Time/ Burst time: The time required by the process to complete its execution.
2. Turnaround Time: The interval between the time at which the process starts executing and the arrival time of the process. It is calculated using the formula: > Turnaround Time = Service Time + Waiting Time

Now, let us have a look at the First Come First serve scheduling algorithm :

First Come First Serve (Also called FCFS or FIFO or non-preemptive) algorithm :

In this algorithm, the processes are executed in the order they enter the processor.

Consider the example,

Here, there are 5 processes A, B, C, D, E with their arrival time and service time.

From the given arrival times, we can see that process A is the first one to arrive at 0ms (milliseconds). So that process starts executing.

This is the execution queue. Process A starts executing at 0 and continues till 3 i.e. executes completely. Meanwhile, process B arrives at 2ms and is added to the waiting queue. Note: The value in the brackets ‘()’ denotes the service time/burst time required by the process.

Next, process B is removed from the waiting queue and starts executing:

Process B executes till 9ms. Meanwhile processes C, D, E arrive and are added to the waiting queue.

C being first in the queue starts executing next.

It executes for 4ms. No new process is added to the waiting queue. The next process to be executed is D.

D executes for 5ms from 13 through 18. After that E is the only process left to be executed. So, E executes next.

As you can see all the processes are successfully executed. Now let us calculate the waiting time and the turnaround time using the formulae mentioned above.

These are the results obtained:

So, this is the FCFS algorithm.

Advantages :

It is very simple.

Disadvantages :

Favors CPU bound processes over I/O bound processes.
If a longer process starts executing, the shorter processes have to wait for long which leads to the starvation of the shorter processes.

To overcome this disadvantage, we have the Shortest Job First algorithm.

Hope this helps you!

Have a nice day!!

The Deterministic Finite Automata

Anna — Mon, 06 Dec 2021 22:32:06 +0000

What is DFA?

Does DFA stand for Dog Food Association?

😂Nope, not at all. DFA has nothing to do with any dog or association. In fact, it is a very sophisticated machine.

DFA in fact is the acronym for — Deterministic Finite Automata.

What is Deterministic Finite Automata?

Firstly, automata is a mathematical model or abstract model which is used to determine if a string is accepted by a language or not.

The DFA is an automata that has finite states and accepts or rejects a given string by running through several states.

Oof! That’s too much of bookish language.

To make things simpler, let's take an example.

Consider a machine that accepts strings over the alphabets a and **b *which contain at least one *a.**

This machine can be diagrammatically represented as:

Here, the state q0 is the state we are starting from and qf is the final state of the machine i.e. the state where we understand if the string is accepted or not.

Let's say we have a string ‘ba’.

‘b’ is the first alphabet that goes into the system first.

As we can see from the above diagram, when b enters the system i.e. the initial state q0, it is accepted by q0 and stays there. Now when we give the symbol a to the machine, as we can see that when q0 accepts a, it goes to **qf **which is the final state. (The double circles indicate the final state).

With **a **being accepted by the machine and since the string is over, we can conclude that the string is accepted by the DFA.

Now let's consider the string “bbb”.

The first **b *is accepted by the string *q0.**

Then comes the second b. We are at q0 currently and the second b is again accepted by q0, thanks to the self-loop that we have shown.

So, by the end of the string, we stay on the state **q0 *and do not reach the final state. Hence the string *“bbb”** is not accepted by the machine. Also, the condition we had laid was that the string should contain a minimum of one “a”.

So, obviously, the string **“bbb” **should not be accepted.

This was a very easy example where one could easily predict if the string would be accepted or not without the DFA. But in some cases, it is really difficult for a person to determine that.

Formally, the DFA is defined using 5 tuples:

(**Q, Σ , 𝛿, q0 , F **)

where:

Q : Set of finite states (for eg: {q0,q1,q2,……,qf})

Σ: Set of symbols (for eg: a,b....1,0…..)

𝛿: Transition Function (function applied/ condition applied onto the string)

q0: Initial/start state

F: Set of final states (here, qf but there can be multiple final states)

For every state, each input symbol has to have one transition

Let’s solve some examples now:

Example 1:

Design a DFA over the input alphabets {a,b} which accepts all strings that end with a

— Consider the strings {a,aa,ba,aba,bba………}

All these ends with a, so all of them should be accepted by the DFA.

From the example above, we can infer that there can be any number of alphabets before a.

Considering that, we can design the DFA as:

As you can see, according to the given question we need a machine to accept strings ending with a. Since our condition involves only one symbol, we have only one necessary transition and hence we take two states. Here, the string can start with any symbol but should end in a. Hence, any occurrence of b is directed towards q0 but a’s are directed towards the final state qf.

Test it out with other strings ending with a.

Example 2:

Design a DFA over the input alphabets {a,b} which accepts all strings that start with a and end with b

If you have understood the concept, why not give your brain a little exercise?

Try this one on your own and then scroll down to check your answer.

I hope you could solve it. If you couldn’t no worries, you could check out my solution:

Consider strings such as:{ab ,aabb ,aab ,abb ,abab,…… }

These strings should be accepted by the DFA. Hence, the DFA can be designed as:

D is the dead state that accepts all the strings not suitable for our machine.

Here, if the string starts with*** b***, it will get into a dead state and will never reach the final state.

Did you get it right? Do let me know in the comments.

Another one,

Example 3:

Design a DFA over the input alphabets {a,b} which accepts all strings that do not start with a or d not end with b.

Try this on your own!

Hope you got this one!

Here's a little trick to solve this one. Take the complement of the problem statement. The complement would be:

……………..which accepts all strings that **start with a and end with b.**

Design a DFA for the compliment. That would be:

Now, take the complement of this DFA. i.e. make the final states non-final and the non-final states final. This would give us:

This is the solution to our problem statement.

Consider the examples: {ε, a ,b ,ba , bbaa, aaa, aba,…..}

ε is a null/empty string

These are a few strings that do not start with a or do not end in b.

These are accepted by the above DFA.

On the other hand if you try the strings like {ab ,aabb ,aab ,abb ,abab,…. }, they won’t be accepted.

Example 4:

Design a DFA over the input alphabets {0,1} where the 2nd symbol should 0 and 4th should be 1.

Got the answer?…..Check it with the one I got:

Consider input strings : {0011, 0001, 1001 ,1011,…}

Wasn’t it easy?

Now let’s take a look at the last but very very interesting example.

Example 5:

Design a DFA over the input alphabets {0,1} which should accept all numbers divisible by 3.

This is a bit tricky question, but let’s solve it step by step.

Firstly, if a number is divided by 3, the possible remainders are 0,1 and 2.

Hence, our DFA will have 3 states.

Now binary equivalents of these remainders are:

0 -> 0

1->01

2->10

These combinations, when occur, should lead to the respective state.

Also, we want to target strings divisible by 3, so the expected remainder is 0 and hence, the final state is q0.

So, until now we have this.

Now, the next step is to consider other strings like:

3->011

4 ->100

5-> 101

6-> 110

7 ->111

From these, 3 and 6 give a remainder of 0;

4 and 7 give 1; 5 give 2.

If we handle all these conditions and complete our DFA this is what we get:

This is the complete solution to our problem.

For example, consider 15 (1111), which is divisible by 3. Hence we should get 0 as output. Let’s verify:

When we give 1111 to this DFA, the path followed is q0->q1->q0->q1->q0 which brings us back to q0 which is our final state. Hence, 15 is accepted as expected.

Similarly, for 21(10101), the path is: q0->q1->q2->q2->q1->q0.

Hence,21 is also accepted.

Consider 14(1110), which is not divisible by 3 and leaves a remainder of 2 i.e. should end up at q2.

Let's verify.

The path obtained is q0->q1->q0->q1->q2.

Hence verified.

I hope things are much clearer now. I have tried my best to explain the concept and tried to take as many examples as possible.

Let me know if it helped you and also you can post your questions in the comments below.

Have a nice day!

The Dining Philosophers Problem Solution in C

Anna — Mon, 06 Dec 2021 22:26:37 +0000

The dining philosophers problem is a very famous and interesting problem used to demonstrate the concept of deadlock.

To understand what the dining philosophers problem actually is, you can refer this blog:
The Dining Philosopher’s problem

Here, I am going to explain the solution to this problem using the concept of semaphores in C. Here’s the program:

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<semaphore.h>
#include<unistd.h>

sem_t room;
sem_t chopstick[5];

void * philosopher(void *);
void eat(int);
int main()
{
    int i,a[5];
    pthread_t tid[5];

    sem_init(&room,0,4);

    for(i=0;i<5;i++)
        sem_init(&chopstick[i],0,1);

    for(i=0;i<5;i++){
        a[i]=i;
        pthread_create(&tid[i],NULL,philosopher,(void *)&a[i]);
    }
    for(i=0;i<5;i++)
        pthread_join(tid[i],NULL);
}

void * philosopher(void * num)
{
    int phil=*(int *)num;

    sem_wait(&room);
    printf("\nPhilosopher %d has entered room",phil);
    sem_wait(&chopstick[phil]);
    sem_wait(&chopstick[(phil+1)%5]);

    eat(phil);
    sleep(2);
    printf("\nPhilosopher %d has finished eating",phil);

    sem_post(&chopstick[(phil+1)%5]);
    sem_post(&chopstick[phil]);
    sem_post(&room);
}

void eat(int phil)
{
    printf("\nPhilosopher %d is eating",phil);
}

/* BY - ANUSHKA DESHPANDE */

Let us first understand what is a semaphore and why it is used.

Basically, semaphore is a special type of variable used to control the access to a shared resource.

The definition of semaphore is in the library **semaphore.h **.

There are many functions related to semaphores like sem_inti(), sem_wait(), sem_post(), etc. *These functions are also defined under the *semaphore.h** library.

The data type of the semaphores is sem_t

There are two types of semaphores-:

Binary semaphore
Counting semaphore

The binary semaphore is used when there is only one instance of the resource whereas the counting semaphore is used when there are multiple instances of the resources.

In our program, we have used both types of semaphores.

sem_t room;
sem_t chopstick[5];

Here, the semaphore room is a counting semaphore since there is one dining room which can accommodate 4 philosophers. (i.e. Consider there are 4 chairs in the room and that is the resource. Hence there are multiple instances of the resource in the room. Therefore, room is a counting semaphore.)

sem_init(&room,0,4);

The function *sem_init() *is used to initialize the semaphore.

int sem_init(sem_t **sem*, int *pshared*, unsigned int *value*);

The first parameter is the pointer to the declared semaphore.
The second parameter is pshared. If it is zero, the semaphore is shared between threads; else it is shared between processes. In our case it is zero meaning it is shared between threads.
The third parameter value is the value with which the semaphore is initialized.

Here, the semaphore room is initialized as 4 meaning it will vary between 0–3 and have 4 values.

Now, since there are 5 chopsticks, we have created 5 binary semaphores referring to the five chopsticks C0-C4.

for(i=0;i<5;i++)
        sem_init(&chopstick[i],0,1);

For the chopsticks, we have used binary semaphores since for every chopstick, C0-C4 we have only one instance of it.

So, according to our program, we have a scenario like:-

An empty room with 5 chopsticks and places for four philosophers.

In the program above, we have created threads.

pthread_t tid[5];

These threads refer to the 5 philosophers sitting around the table.

We have them as threads since we want these to execute simultaneously (i.e. we want multiple philosophers to eat at a time).

Now there can be a situation where all 5 threads start executing i.e. all 5 philosophers enter the room and cause deadlock. Hence, we are allowing 4 philosophers to enter the room first so that at least one of them can finish eating.

for(i=0;i<5;i++){
        a[i]=i;
        pthread_create(&tid[i],NULL,philosopher,(void *)&a[i]);
    }

We are calling the function philosopher() from pthread_create and passing it the address of an integer variable which refers to the philosopher number.

In the philosopher function,

void * philosopher(void * num)
{
    int phil=*(int *)num;

    sem_wait(&room);
    printf("\nPhilosopher %d has entered room",phil);
    sem_wait(&chopstick[phil]);
    sem_wait(&chopstick[(phil+1)%5]);

    eat(phil);
    sleep(2);
    printf("\nPhilosopher %d has finished eating",phil);

    sem_post(&chopstick[(phil+1)%5]);
    sem_post(&chopstick[phil]);
    sem_post(&room);
}

we are first converting the number passed as a void * into integer.

Then we have called the sem_wait function which first checks if the resource is available and if it is available, the resource is allocated to the philosopher i.e. the semaphore is locked.

sem_wait(&room);

This being a counting semaphore, the prototype of sem_wait is:

struct semaphore {
      int count;
      queueType queue;
};

void sem_wait(semaphore s)
{
      s.count--;
      if(s.count<0)
      {
            /*place this process in s.queue */;
            /*block this process*/;      
      }
}

So here, the number of semaphores is decremented, meaning one of the semaphores is allocated. If all of the resources are allocated, the thread is placed on waiting queue.

Now, we apply sem_wait on chopsticks which are binary semaphores.

sem_wait(&chopstick[phil]);
sem_wait(&chopstick[(phil+1)%5]);

The definition of sem_wait for binary semaphores is:

struct binary_semaphore {
      enum {zero,one} value;
      queueType queue;
}

void sem_wait(binary_semaphore s)
{
      if(s.value == one)
           s.value = zero;
      else
      {
              /* place this process in s.queue */
              /* block this process */
      }
}

Here, according to the prototype, if the value of semaphore is one, it is changed to zero indicating that the semaphore is blocked.

In our case we are blocking the chopsticks towards the left and the right of the philosopher.

For example, for philosopher P0, we are blocking chopstick C0 and C4.

Then, we are allowing the philosophers to eat.

Finally, we are freeing the semaphores by calling the sem_post() function so that the other threads that are placed on the queue can use the resources.

The prototype for the sem_post() function is:

int sem_post(sem_t **sem*);

If it returns a positive value, the semaphore is unlocked successfully.

For a binary semaphore, the sem_post() function works as:

void sem_post(semaphore s)
{
      if(s.queue is empty)
            s.value=one;
      else
      {
            /* remove a process P from s.queue */
            /* place process P on ready list */
      }
}

and for a counting semaphore, the sem_post() function is:

void sem_post(semaphore s)
{
      s.count++;
      if(s.count <= 0)
      {
            /* remove a process P from s.queue */
            /* place process P on ready list */
      }
}

Using the above functions, we free all the semaphores so that they can be used by other threads.

sem_post(&chopstick[(phil+1)%5]);
sem_post(&chopstick[phil]);
sem_post(&room);

The same thing happens for all 5 philosophers.

After all the 5 are done, we join the threads back to the main process.

for(i=0;i<5;i++)
        pthread_join(tid[i],NULL);

So, this is how we can implement the solution to the dining philosophers problem using semaphores.

At the end, you should get an output which looks like this:

Philosopher 4 has entered room
Philosopher 4 is eating
Philosopher 2 has entered room
Philosopher 2 is eating
Philosopher 3 has entered room
Philosopher 1 has entered room
Philosopher 2 has finished eating
Philosopher 4 has finished eating
Philosopher 3 is eating
Philosopher 1 is eating
Philosopher 0 has entered room
Philosopher 3 has finished eating
Philosopher 1 has finished eating
Philosopher 0 is eating
Philosopher 0 has finished eating

The sequence does not matter. It can be different on different machines.

The only thing is to make sure that all philosophers are entering the room, performing the eating operation and leaving the room and also that no two philosophers are using the same chopstick at the same time.

Do let me know if you face any problems and feel free to leave a feedback.

Hope this helps you!

The Dining Philosopher's Problem

Anna — Mon, 06 Dec 2021 22:22:44 +0000

The dining philosopher’s problem is a very well known resource sharing problem in the world of computers.

The problem says:

There are 5 philosophers sitting around a round table eating spaghetti and each of them has one chopstick between them. All 5 of them sit around the table and pick up the chopstick placed towards their right. But, here’s the problem. To eat the spaghetti they need both the chopsticks and since everyone picked up the chopstick to their right, nobody gets the left chopstick and hence, nobody can eat.

Logically thinking, this problem isn’t really a problem in real life scenario. The philosophers could have asked for a few extra pairs of chopsticks, or they could have eaten using their hands 😂 .

Jokes apart, but the dining philosophers problem is an excellent example to explain the concept of deadlock while resource sharing in OS.

Consider the philosophers to be processes and the chopsticks to be a shared resource. Every process needs two resources out of which one it has already acquired and the other is acquired by some other process. Till the other process does not free the resource, this process cannot proceed. Similarly, the other process is dependent on another process for its resource. Since every process is dependent on each other, it forms a circular-wait and the system goes into a deadlock condition.

Here, when each philosopher picks up the chopstick to their right, they also end up picking the left chopstick of the person sitting next to them which leaves every philosopher with just one chopstick and nobody can start eating.

To solve this problem, we can use this strategy:

Consider five philosophers: P0,P1,P2,P3,P4 &

five chopsticks: C0,C1,C2,C3,C4

Initially we let P0 enter into the dining room.

Since nobody else is present there all the chopsticks are free and P0 acquires chopsticks C0 and C1 and starts eating.

Now, P1 enters the room. Since P0 is already eating, chopstick C1 is not available for P1 and hence P1 cannot eat and is kept waiting.

PS : Since P1 does not get C1, it doesn’t claim C2.

Next, P2 enters the room. Since C2 and C3 both are available, P2 starts eating.

Next, P3 enters and is blocked and added to the waiting queue because C3 is not available.

Similarly P4 is blocked and is added to the waiting queue as C0 is not available

Now, consider P0 has finished eating and the resources claimed by it i.e. C0 and C1 are released. P1 cannot start eating since C2 is still not released and hence P4 starts eating since C4 and C0 both are released. Hence,

If now P2 releases the chopsticks C2 and C3, philosopher P1 can start eating

P3 has to stay in the waiting queue since chopstick C4 is not available.

Finally, consider that philosopher P4 has finished eating and has freed chopsticks C0 and C4, P3 can start eating.

This is the strategy using which we have ensured that all the philosophers have been served and avoided the circular wait situation.

This is the logic behind the solution of the dining philosophers problem.

Here is the C program designed to solve the problem:-

(I’ve used semaphores to solve this problem. For more information on semaphores, refer this website-)
Semaphores

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<semaphore.h>
#include<unistd.h>

sem_t room;
sem_t chopstick[5];

void * philosopher(void *);
void eat(int);
int main()
{
    int i,a[5];
    pthread_t tid[5];

    sem_init(&room,0,4);

    for(i=0;i<5;i++)
        sem_init(&chopstick[i],0,1);

    for(i=0;i<5;i++){
        a[i]=i;
        pthread_create(&tid[i],NULL,philosopher,(void *)&a[i]);
    }
    for(i=0;i<5;i++)
        pthread_join(tid[i],NULL);
}

void * philosopher(void * num)
{
    int phil=*(int *)num;

    sem_wait(&room);
    printf("\nPhilosopher %d has entered room",phil);
    sem_wait(&chopstick[phil]);
    sem_wait(&chopstick[(phil+1)%5]);

    eat(phil);
    sleep(2);
    printf("\nPhilosopher %d has finished eating",phil);

    sem_post(&chopstick[(phil+1)%5]);
    sem_post(&chopstick[phil]);
    sem_post(&room);
}

void eat(int phil)
{
    printf("\nPhilosopher %d is eating",phil);
}

/* BY - ANUSHKA DESHPANDE */

To understand this program, refer my blog
The dining philosophers problem solution in C

Do let me know in the comments if this helps you.

Have a nice day!