Difficulties inside the Operating System (concurrent programming, mutual exclusion, critical section and Deadlock)

_{Image from : Pixabay}

---

Introduction

---

Ever wondered how tedious life was before the implementation of concurrent programming in the operating system, in which one process has to wait for another process to finish its execution, even when both can run concurrently without disrupting each other, gone are those days, when a process needs to wait for a computer to finish compiling a program before sending a file to a printer or open a file for reading and playing a digital video clip concurrently.

Human natures have always had the ability to walk and chew a gum at the same time. i.e. multi-functioning in nature, in a simpler way, human beings perform many actions concurrently, although, no camera is attached to this post, but am sure as you are reading this post with your own personal eyes, you are also breathing, listening, thinking or even eating at the same time.

Concurrent programming stems from the fact that human beings are multi-tasking in nature and so computer must also be programmed to perform such properties. In fact, many advancements in computing world today stem from incorporating the properties of human beings into the computer system, be it Artificial Intelligence, Machine Learning. e.t.c.

---

Diving into Subject Matter

---

The early operating systems gave room to run multiple processes concurrently but programming languages used then did not allow to explicitly specify concurrency primitives and that led to the creation of ADA in 1970's. Process in this context simply refers to a program in execution.

Each time a user gives more than one instructions to a system to execute, these processes form a long waiting queue because processes are always much more than the processors and as such process control block maintains the information of all the processes and arrange them in order in which they will be executed by the central processing unit at runtime.

The Process Control Block stores the following information about the process:

1. Name of the Process.
2. State of the Process(Ready, Active, Wait)
3. Memory which is provided to the Process.
4. Resources allocated to the Process.
5. Scheduling information.
6. Input and Output Devices used by the Process.
7. Process ID which is given by the CPU when a Process Request for a Service.

---

_{Image from : Wikipedia}

Each time a user runs a program, a process is automatically created and enter the waiting/ready list where it will stay till a processor is through with the process on the running state. Once a processor is available, the next process on the ready list will undergo dispatching by making a quick state transition from the ready state to running state.

The operating system must be programmed in such a way to manage such transition in order to avoid monopoly of a process over the entire system. Each process has a specific time interval which it must run and once a process fails to release the processor before the allocated time interval comes to an end, there will be an interrupt by the interrupt clock giving control back to the operating system and change the operating system from running state to ready state, thereby dispatching the first process on the ready list to the running state.

---

Application of concurrent programming

---

In order to increase throughput, resource utilization and reduced the waiting time of processes on a ready state queue, the idea of multiprogramming was put in place so that many processes that are not in need of the same resources could be processed at the same time.

To be able to do this, one must find a suitable solution to the problem of shared resources, which is the only thing that might disrupt the running of two processes concurrently, for instance if one process is making use of input and output I/O resources and there is another process that does not in need of I/O resources, then both can run concurrently otherwise if they both need I/O resources at the same time, definitely there will be problem during the runtime and that led to the concept of mutual exclusion.

---

Mutual Exclusion

---

In order to understand the concept of mutual exclusion in operating system, consider steemit as a server that monitors the number of article a user post in a day, assuming that one process is to issue a receipt out each time a user post an article, the process increments a shared resource, postCount by 1, now consider what happens when two processes make an attempt to increase postCount concurrently by running the below code in assembly language

LOAD postCount
ADD 1
STORE postCount

Assuming a user posts an article, the code LOAD postCount will execute by loading the current value of postCount from the memory to the register, the ADD 1 code will then add 1 to the value of postCount in the register and the STORE instruction will copy the value from register back to memory.

suppose a process executes the first two instruction. i.e LOAD and ADD instruction but not yet execute the third instruction(STORE postCount). i.e. updating the memory with the current value of postCount before the allocated interrupt time, the control will automatically be shifted to the second process that wants to get access to the shared resource postCount which might execute all the three instruction before context switching back to the first process which will directly execute its third missing instruction without rechecking the value of postCount in the memory for an update and as such a wrong value will be stored in the memory, this is a critical error which might lead to loss of lives, especially in a critical mission applications.

In order to solve this problem in the operating system, an operating system must be designed in such a way that no more than one process must gain access to share resources at a time and this is the concept of mutual exclusion.

---

Critical Section

---

_{By Zaya gd CC BY-SA 3.0 via Wikimedia Commons}

To allow concurrent programming in an operating system, the mutual exclusion must be enforced, especially when processes need to access shared resources, when they are not sharing any share resources, there is no confliction and as such, they can run concurrently without enforcing mutual exclusion.

Each time a process is accessing share resources, it is said to be in its critical section and that will prevent the earlier problem by making sure that only one process can be in the critical section at a time. others processes that want to use critical section must wait till critical section is free.

---

Implementation of Mutual Exclusion

---

Many Algorithms have been proposed and used in the past, starting from Dekker’s Algorithm in 1960 to Peterson’s Algorithm and Lamport Bakery's Algorithm. e.t.c. In order not to bore us with unnecessary codes, the basic idea behind their implementation is the functions enterMutualExclusion() and exitMutualExclusion() which allow the first process to acquire lock and sets flag[self] = 1, once it is in the critical section and then allow the other process to acquire the lock once it is done.

---

Conclusion

---

Concurrent programming in operating system has many benefits such as improved throughput, resource utilization and reduced the waiting time of processes, however, it is without a problem. As discussed above, resource sharing is the main thing that is common to processes and as such, each process must have a total control of its resources, but in a situation where a process fails to complete its execution, this will lead to Deadlock because many processes will be waiting for the resources such process is holding and this will later affect the throughput and leads to failure of the operating system.

---

Thanks for reading through, your thoughts are important.
Until my next post,
keep on sending zeroes and ones.

---

References

1. _{OPERATING SYSTEMS PROCESSES}
2. _{What is Concurrent Programming?)}
3. _{Implementing Mutual Exclusion}
4. _{critical section Mutual Exclusion}
5. _{Operating System - Processes}
6. _{Concurrency and Mutual Exclusion}

---

_{All images are from free source websites (Pixabay, Wikipedia and Wikimedia)}

---

_{If you write STEM (Science, Technology, Engineering, and Mathematics) related posts, consider joining #steemSTEM on discord here. If you are from Nigeria, you may want to include the #stemng tag in your post. You can visit this blog by @stemng for more details. You can also check this blog post by @steemstem here and this guideline here for help on how to be a member of @steemstem. Please also check this blog post from @steemstem on the proper use of images devoid of copyright issues here.}