Understanding Process Synchronization in Operating Systems

So, welcome to module 8 and we will be talking about process synchronization. What do you mean by synchronization? Synchronization is that when two processes want to access say a resource, a shared resource, should be certain discipline that needs to be enforced while accessing that resource and what is that discipline becomes the subject matter of synchronization. And if that discipline is not adhered to then the process is basically can access that resource in. in such a way that there could be some inconsistency in the entire operation. When you look at the entire operating system, there are lot of shared resources. For example, there is something called buffer cache, there is something called the super block in the file system. There are many shared resources and these resources are shared by multiple processes at a given point of time. And so process synchronization becomes the bread and butter. of how to maintain consistency of access of these shared resources among these processes whenever they try to access them. So that becomes the subject matter. So we will introduce process synchronization not from a file system point of, not from examples derived from file system but using some simple concepts like you know sharing a buffer etcetera and then we will introduce the concepts and understanding this concept is also very important from a security perspective because. A lot of leaks of information do come, race conditions could be exploited to basically hack into your system and these are very important concepts that need to be understood specifically for the security community too. So the objective of this particular module is about getting processes to coordinate with each other, about how processes work with resources that must be shared between them and about how we go about acquiring blocks to protect regions of memory. Why do you need to protect? Because if I do not protect, 2 processes can access at the same time and basically go and make the content of that memory inconsistent with what the program is actually doing. We will see some examples and how synchronization is really used and it is really implemented. So that is, these are all the objectives of this particular module. So but why should we synchronize? This is because I am sharing the resources. When I am sharing the resources, I am not just sharing the data. resources, I need to adhere to some discipline. If I do not have that discipline, then what will happen is that the state of your resource will become inconsistent, the data actually becomes inconsistent. We will give you some examples of that as we progress. And there is, we have to share resources because we are looking at a cooperating environment where multiple processes try to work together to basically solve a particular problem. We have already seen why more than one process can work together and we can do scheduling we have seen in the previous module. In the context of scheduling we found that if two processes are working together then I can basically merge the CPU time of one process with the I O time of another essentially giving you lot more computation speed up and lot more hardware utilization etcetera. In addition I could have certain things like modularity and convenience. For example if I have a particular functionality, I would like to keep that functionality with respect to a particular module so that tomorrow when I upgrade a software, so software has 5 different functionalities, I would like to realize it as 5 different modules because tomorrow when the software is actually upgraded and say functionality 3 changes, the modules corresponding functionality 1, 2, 4 and 5 can be retained and only the third module need to be changed and this becomes. very easy for me to release the next version. So modularity is also very important for creating this type of large scale software and that basically comes by isolating different loosely related modularities as separate threads or processes and building up a system. And if that needs to be executed then basically what happens is that each module becomes a thread and or a process and these processes. work in a cooperating way to solve the problem and then hence we will end up with a cooperating process environment. So, what may happen when process cooperate? So, we will take up a very simple problem called buffer sharing problem. So, when one and there is a producer who produces. into that buffer, there is a consumer who consumes from the buffer and so let me say that there is a bounded buffer, so I have n locations. Now, a producer should not produce into a buffer that is already full. because he will not have location to store it. And the consumer should not consume from a empty buffer. He will basically land up with a null. So this is the access rule, right? So if I have one buffer that I am going to share, there is a consume. consumer who consumes from the buffer, there is a producer who produces into that buffer, the producer should not produce into a buffer that is full and a consumer should not try and consume or remove data from that buffer when the buffer is empty. This is a rule that we need to implement. So this is where I need synchronization. So when the buffer is full, I should not allow the producer to add an entry there. When the buffer is empty, I should not allow the consumer to consume. from it. So, this rule has to be implemented and this is what we call as a synchronization. So, the producer is a process, the consumer is another process, both of them are working together in a cooperative way and there is, they are trying to share a resource in this case a buffer and there is a discipline that I am basically enforcing in this context where you know the producer produces. and the consumer consumes, the producer should not produce into a full buffer, the consumer should not consume from an empty buffer. So this is what we are trying to achieve here. So this is the entire diagram for this. So what will the producer do? So if you look at the extreme left, the producer will wait for the buffer to be not full. If the buffer is not full, he goes across the orange block. Then he will go and lock the buffer. Then he will deposit some. something, then he will unlock the buffer and if the buffer is not empty he will go and trigger something and then he goes back. So that two green cross lines we will just discuss it a little later, but what does the producer do? It just two orange boxes, it will wait, the first orange box will wait till the buffer is not full. So, if the buffer is full it will wait till the buffer is not full. full. So, if the buffer is full it will keep waiting there. And if the buffer is full it will be waiting and who will go and say that you can proceed? It is waiting there meaning that process is in a suspended state. Now, who is going to go and say you can proceed? The consumer is going to go and say. So, when the consumer consumes something from the buffer, certainly there will be one location which will be. not full because it has consumed one fellow from there so that at least one location will be there. So, that is the fellow who triggers an event to the producer saying hey the buffer is not full for sure. So, that is the green line that goes from the consumer to the producer. So, when the producer comes it finds that the buffer is full, it waits on the first orange box till the green signal comes from the consumer saying hey the buffer is not full now you can go and produce. Immediately it will go and lock the buffer and it will deposit and then unlock the buffer and then it will come back to, it will now go and say to the consumer buffer is not empty because it has produced something. So, now it will go and tell the consumer buffer is not empty and it will go back. For the consumer it will wait till the buffer is not empty. Because, if the buffer is empty it has to wait, so it will wait till the buffer becomes not empty. So, if the buffer is empty it will wait there and there is a green signal coming from the producer which says A no F produce one thing certainly the buffer is not empty. So, then it will go, it will lock the buffer, it will retrieve that data and then it will unlock the buffer. Again it comes back and it says now I have at least one location is empty there. So, it will say buffer is not full that signal it will send to the producer. So, the 2 signals that pass from the consumer to the producer and from the producer to the consumer, these are the synchronizing action. By having these 2 signals here, we basically see to it that the producer does not produce into a full buffer and the consumer does not consume from an empty buffer. Both will land up in an inconsistent state. Now also note that whenever I am depositing, whenever the producer is depositing something into the… to the buffer or when the consumer is retrieving something from the buffer, it basically It locks the buffer because when I am producing into the buffer, I do not want the consumers to start consuming. I want to finish that deposition, I want to deposit the entire thing and then only allow the consumer to consume. So, there is a lock and a unlock. So, when there is a buffer. When the buffer is locked what will happen? The consumer cannot cross that lock buffer. When the producer has crossed the lock buffer, the consumer cannot cross the lock buffer. It will wait till the producer unlocks. blocks, then only the consumer can go and start retrieving. So at the same point of time the producer and the consumer cannot be inside the yellow blocks meaning deposit and retrieve. When the producer is depositing the consumer cannot retrieve, when the consumer is retrieving the producer cannot deposit. So that is also taken care. Otherwise half the way he is depositing this fellow will start retrieving it then there could be an inconsistent state. So, what you see on the right hand side is basically an implementation of this entire shared infrastructure. So, there is one buffer that is shared by the producer and consumer and this is how the access to this is basically synchronized. So, the two green lines basically tell you how we synchronize these two actions of not producing into a full buffer and not consuming from an empty buffer. The solution essentially is the producer goes to sleep or discard data. of the buffer is full. Actually in this case it goes to sleep. So when that is the first rectangle on the producer side, the orange rectangle, the body mean by weight it goes to sleep. When consumer removes an item from the buffer, it notifies the producer who starts to fill the buffer again and that notification goes through this green line from the consumer to the producer. Similarly, the consumer goes to sleep if it finds the buffer to be empty which is the first red rectangle on the consumer side. And whenever the producer puts data into the buffer, it wakes up the sleeping consumer. Now, let us go and make it much more interesting. So, let us say there are two programs P1 and P2, right? This is a C program. There is a both this program P1 and P2 share one integer called C. Like they share a buffer, this shares an integer called C. The program P1 increments C, the program P2 decrements C. Assuming that P1 executes immediately followed by P2, the value of C should remain the same. Let us say. say before execution of P1 the value of C is 4 or in this case let us say the value of C is 42, when P1 executes and then P2 executes the answer should again remain 42. But what we will show now is that when P1 executes followed by P2 in some interlaced fashion the answer can become 43. That is what we are going to show now. Now what do you mean by incrementing C++? Please note. Note that that c++ that you see there in red on your left hand side essentially is 3 assembly instruction that is incrementing an integer is 3 assembly instructions. The 3 assembly instructions that you see here load the content of c into register 1, increment register 1, store the content of register 1 back to c. This is the syntax let us keep this as the syntax. Similarly for c minus minus load the content of c on to register 1. register 2, decrement register 2 and store the content of register 2 back to C, correct. So this is how increment works, this is how recruitment works. Now these are 3 assembly instructions. Now what will happen when I am going to execute this course? Let us say the P1, the first 2 instructions of this is executed, say load ampersand C register 1 that means register 1 gets the value 42 because C is initialized to 42. Now see how the program works. I am executing at the bottom of your screen here. First I will load C into register 1, so 42 gets into register 1. I will increment, so register 1 becomes 43. Before I could store, please note that the P2 starts executing. Because let us say it is a round robin algorithm, so there is a context switch. So before, so the time quantum allotted to P1 is over, now I go to P2. Now P2's load C res 2 happens, so res 2 again gets 42 because C is not up. C is still 42, so res 2 will get 42 and now decrement res 2, so res 2 gets 41. Then I store the value of res 2 on to C, so C gets 41. Now the counter switch happens. When the corner switch happens back to P1, what happens it will now It is in the third instruction. The first two instructions are already done. The third instruction is store edge 1 ampersand C. So, C will get 43. So C++, C++ executed one after another should maintain the value of C as 42 but when I compile that code C++ and C++ I get 3 assembly instructions for C++ and 3 assembly instructions for C++ and when I am started executing this program and if they get interleaved in between then what happens I get an inconsistent value for C. Do you follow? This is the problem of sharing data and this is a race condition because who wants to finish first? Two fellows are racing, P1 and P2 are racing with each other and because of that this entire problem has happened. Now, what is the solution to this? When P1 is executing these 3 instructions, P2 should not be allowed to execute those 3 instructions. When P2 is executing those 3 instructions, P1 should not be allowed. out to execute these three instructions. If you had done C++ completely and then C minus minus or if you had done C minus minus completely and then C++ then this problem should not have happened. The point is to ensure that what should I do? I should execute P1 first, the 3 assembly instructions corresponding to P1 first, I have to finish that. Then I have to start the assembly instructions with respect to P2 or I should finish off the assembly instructions with respect to P1. P2 first and then start assembly instructions with respect to P1. That means these 3 instructions and these 3 instructions of P1 and P2 they form the critical section for P1 and P2. So if you look at some of the modern books, critical section means one single code which is executed by multiple programs. That is the feel you get in some of the operating system books. That is not the case, right? There is a critical section. for every program and they are different, but they are all bound by one level. So, for the purpose of executing this multi-threaded program which essentially has two threads namely P 1 and P 2. is one critical section spawning between those program. The critical section of P1 is these three instructions that you see on the left, the critical section for P2 are the three instructions you see on the right and these two critical sections are linked in the sense that when P1 is executing its critical section, P2 should not go into the corresponding associated critical section. executing its critical section, P1 should not go into its associated critical section. You are getting this point. So when you look at all these modern books, there will be one block called critical section and almost every student I have interviewed so far in the last 16 years have shown that there is one critical section which two fellows will share. No. The code is different. Again I repeat P1's critical section has the code on your left hand side, P2's critical section has the code on the right hand side. When P1 is executing its code which is different from the code of P2. should not go and execute its associated code and vice versa. And if that is ensued then this type of an inconsistency or race condition should not will not happen right and that is what we meant by locking. locking and unlocking. So imagine that very simply that before coming into this P1 these 3 instructions it will go and lock and the end of this it will go and unlock. Similarly P2 will also put a lock and unlock before and after this C code. So when I lock, so P1 locks and then when P2 also tries to lock it will say somebody else has locked and it will ask to wait. And when I unlock then I. I go and release the lock, so P1 can now lock and go in. But when I unlock, what has happened? I have completely finished executing those 3 instructions. I unlock only after I finish the 3 instructions. By this only one fellow will be allowed to go into the critical section while the other fellow will be waiting on its critical section. Please note. And when it comes and executes its critical section, this fellow should be out of that critical section. enter here again yes So, the notion of allowing only one process to execute on its critical section while the other process has to wait and vice versa and it extends to n processes. If all n processes share one resource. source, each one will have its own critical section and exactly one can be in its critical section, the others have to be out of their respective critical section. This property is called mutual exclusion. And so So, the entire process synchronization revolves around how do we achieve this mutual exclusion. So, one immediately we have seen how we achieve this mutual exclusion, we have seen the notion of lock in the previous one but one slide. So, I lock the buffer and I unlock, I get this mutual exclusion, right. But it is not so easy. Now we will see how to achieve this mutual exclusion but the need for a mutual exclusion crucial exclusion is that I need to have a synchronization mechanism to avoid raise conditions by ensuring exclusive execution of critical section. That is the motive of mutual exclusion and this exclusive execution of critical section wherein only one fellow can enter and the other fellow should not enter, this is among n cooperating processes. I need to get a method for that. From the OS point of view. This is achieved using something called semaphores or monitors. What is a semaphore? Semaphore is a shared entity, it has an integer value and it can be decremented, it can be incremented. When I decrement a semaphore and its value becomes 0, I sleep. When I increment it is just to go and increase its value. I said there is an integer value, right? It is an increase its value by 1, right? And when I am incrementing, before I increment I sleep. I check if it is 0, if it is 0 then I go and wake up all the processes that are waiting for this semaphore. So let us understand a semaphore has 2 operations, it has an integer value and it has 2 operations P and V, P means decrement, V means increment. Decrement what I do? I decrement reduce the integer value I reduce it by 1 and if that value becomes 0 I put that process which is trying to decrement to sleep. Ready? When increment means I go and increment that integer value and before incrementing I check if it is 0, if it is 0 then there will be some processes that are sleeping I wake all of them and then I go and increment. So these are the 3 operations and semaphores can be used extensively for achieving this synchronization that we have done in the past. There are also binary semaphores which basically does not have a value but it is basically the integer values in the range 0 and 1. an integer value, it has a bit as that value. So, it basically uses 0 and 1 and these binary semaphores are also called as mutual exclusion locks. A lock is something like you have locked or unlocked, there is no value for it. Now, as we see that a critical section as in 3 parts as we saw in the program also in the previous thing, a critical section whatever we see as 3 instructions is the critical section for the. p 1 and also on the left for p 2, but there is something before it and then there is an entry into the critical section, then there is exit from the critical section and then there can be reminder. So in a huge code there will be some part which is the critical section, there will be entry criteria for the critical section, there will be some exit criteria for the critical section and then there will be remaining portion of the code. So that is what we have seen here. So there will be an entry section for a critical section, then the critical section itself, then an entry. an exit section for the critical section and there will be something called remainder section which is the remainder of all the code. The entire code minus the critical section is the remainder section. Now we will explain the synchronization through what we call as the readers-writers problem which is very interesting. So there is a shared data and multiple readers can read from that data. At the same point of time multiple readers can read from the data, but only one fellow can write into the data at any point of time. And when somebody is writing into that, nobody can read. So the three conditions are at any point of time multiple readers can be reading, no one can be writing, should write. And at any point one fellow can write, more than one cannot write, only one fellow can write and when that fellow is writing nobody else can read. So, these are the three types of criteria. ...material that we want to put and let us see how synchronization, how do we achieve this. So, this is called a reader's writer's problem. So, what are there? There is a data which people will read and write, may be one integer variable or whatever and then we will... be using 3 semaphores, one is called mutex initialized to 1, WRT which is initialized to 1 and then we will have an integer called read count which is initialized to 0. So, these are all the shard data. So, I have a data set which people will read and write from, the processes will read and write from. There is a semaphore called mutex which is initialized to 1, there is a semaphore called wrt which is initialized to 1 and there is an integer which is called read count which is initialized to 0. The read count actually tells how many readers are currently reading the shared data. Read count essentially says how many readers are currently reading the shared data. Now let us do this. The code for writer is note that. there could be multiple readers and multiple writers. There will be n readers and n writers, not one reader and one writer. There could be n readers and n writers. So, one example for that is a file is to be shared among several processes. Many processes can read at the same time. Many processes will try to write, but when it is writing only one fellow should be allowed. After that other fellow can be allowed, but one point of time only one fellow can be allowed to write, but many fellows can be allowed to read the file. There is a direct translation of the reader status problem to a practical problem. Now, this is the code. I have WRT as a semaphore. So what I do is when I want to write. I just say wait wrt, wrt is a semaphore, so when I say wait wrt it is initialized 1. So when I say wait it becomes 0. Now if somebody wants to write he will also execute wait wrt, when wrt is 0 he will go to sleep. So, I will perform writing and then I will do signal WRT. When I do signal WRT, what will happen? That will be incremented from 0 to 1. Since it is incremented from 0 to 1, if somebody is waiting, those fellows will also be woken up. So, wait WRT and signal WRT will ensure that only one fellow can write at any point of time. So, whoever executes wait WRT first will execute that fellow. He will see that WRT is 1 and he will reduce it to 0 and that fellow will come and start performing the writing. The other fellows who are going to execute the wait WRT later, they will all wait. After this fellow finishes, he signals WRT then those fellows will start executing. By this what, just by putting wait WRT and signal WRT, I have ensured that only one process can write, more than one process cannot write at the same time. Now, this wait wrt and signal wrt are atomic instructions. Atomic instruction is that when I am executing wait, it will be completely executed before something else can get executed. So, when I start executing wait, I will finish the execution of wait before anybody else can do anything. So, by this two processes want to write into the shard data. cannot execute wait at the same time and get access into the perform writing part. So, only one fellow, so if two fellows want to execute write, the first fellow the moment he says wait write, he will finish of wait write then only he will give the control to the next fellow. So, I will do wait write, the other fellow wants to do wait write, when I get hold of wait write, I will start executing wait write. finish that wait write then only I will give the control to the other fellow because wait is an atomic instruction. That is what we mean by atomic instructions. So, when I say wait, so essentially I do that wait and if write is 0, wrt is 1, I make it 0 and I start performing the writing while other fellow executes wait after me and he will find that wrt is 0. So, essentially he will go and sleep. Now, when I finish writing. Then I say signal, then I allow him to go and continue. So, this is how. So, I have ensured that no two fellows can write at the same time. Now, the other thing that we need to ensure is when I am writing, no fellow should read When somebody is reading, no fellow should be allowed to write. When I am writing, the writer alone will be there. No other fellow will write, no other fellow will read also. And when I am reading, no other fellow will be allowed to write. Correct? You are getting this? So, now how do I achieve this? The reader problem that is shown below. We will go ahead and go to the next slide and see how it is achieved. First foremost, if you look at the reader code down, there is something called read count. What will read count tell you? Read count basically tells that the number of readers that are currently reading. And please note that when I want to read, first I increment read count, then I perform the reading, then I decrement read count and go off. So, that is what I am doing. Say read count equal to read count plus 1, perform reading, read count equal to read count minus 1, get away. Since multiple fellows can read at the same time, please note that when one fellow is doing read count equal to read count plus 1, another fellow can do read count equal to read count minus 1. One fellow does read count plus plus, at the same time another fellow can do read count minus minus. if a same variable is incremented by one process and it is decremented by another process, already we have seen that there is a raise condition. So, whenever I am incrementing read count or whenever I am decrementing read count, I want to protect it. So, that only one. fellow can increment read count and only one fellow can decrement read count. So, what I do there? So, I use that semaphore called mutex. So, I say weight mutex, read count equal to read count plus 1, signal mutex. Perform reading. Wait mutex read count equal to read count minus 1 signal mutex. So, there are multiple readers. If any of the reader is in either incrementing or decrementing, he would have made mutex to 0. Then only you can read. can enter. So, when I want to enter either read count equal to read count plus 1 or read count equal to read count minus 1, one of those two sections either on the top before reading or on the bottom after reading, if I want to enter my mutex value should be be 1 and the moment I enter I will make the mutex to 0. So, all the fellows who want to enter either of these sections, they may all the readers can be in either one of these 3 sections, it can be either on the entry part where it is incrementing read count or it can be actually reading or it can be on the exit part where it is decrementing read count. So, if any of the process wants to enter any of these 2 mutual execution sections, they cannot enter unless I finish my. operation. If I get hold of mutex, no other process can increment or decrement read count until I finish the incrementing or decrementing of the read count. By this read count, there is a serialization of the way by which I keep on increasing or decreasing the read count. If I do not put that mutex before and after signal, wait and signal mutex before read count equal to read count plus 1 and after read count equal to read count plus 1. 1 or again if I do not put weight and signal before in between and read count equal to read count minus 1. If I do not put that weight and signal there, then what will happen? There will be a raise condition on the way read count is managed. So the read count will become inconsistent. Read count should tell me how many fellows are reading, but if I do not put that weight and signal mutex on both ends, then read count can become inconsistent. an inconsistent value as we had demonstrated earlier. You are following this? So what happens here is that there is, so when 2 readers are there, so reader 1 wants to do reading, it first gets weight mutex and then it increments read count. Just forget the next statement, if read count equal to 1, we will explain it a little later. Then it will signal mutex. It has incremented read count and now it is doing reading. After it signals mutex, reader 2 can now go and increment read count and he can also do signal mutex and he can also do reading. So, at the same time, 2 fellows can do the reading, but 2 fellows cannot increment read count at the same time. If they are allowed to, then we will land up with the inconsistency we have already seen in this lecture. And again when they finish the reading, they want to decrement read count, again there there will be a serialization. Reader 1 will finish, then reader 2 or reader 2 will finish and then reader 1. So, please note that if I put a wait mutex in the beginning and signal mutex in the last and I do not have any signal and wait in between, then which property is violated? The property that multiple readers can read. read at the same time that property gets violated. So I have to put a wait and signal before and after read count equal to read count plus 1 and again a wait and signal before read count equal to read count minus 1 before and after. So then what happens is multiple readers readers can read at the same time, but they cannot increment or decrement read count at the same time. So, that is the basic thing. Please understand this is how it works. So, this is about readers. So what are the two properties that we have ensured? Now let us go here. I have ensured that two writers cannot write at the same time. So, only one writer can enter. Multiple readers can read at the same time and read count is consistently incremented and decremented. These two I have. ensured, but what I have not ensured is that when a writer is writing no reader can read and when a reader is reading no writer can write and that is basically achieved by those two statements if read count equal to 1 then wait WRT. So, when will read count be equal to 1? When I am the first reader, correct? Because I have just incremented read count equal to read count plus 1 and then immediately I am executing if read count equal to 1. count equal to 1, then wait WRT. Please note the reader code. Now, when read count equal to 1 means I am the first reader, then I will go and say wait WRT. If already somebody has entered and they are doing the writing, then what will happen? I have to wait. If there is a writer already in, I have to wait. If no fellow is writing there, then WRT will be 1. I would have made it 0 and I will start reading. Correct? So, if another writer wants to enter, he will start waiting because if I am the first reader and I go and wait on WRT, what will happen? I will I will and nobody is writing, then I will get that WRT as 1, I will make WRT to 0 and since WRT is 0, no other writer also can enter into it. So, the first reader who gets WRT as 1, he will make WRT 0 and till WRT becomes 1, no writer can enter. So, when a reader has entered, no writer can enter. When a writer has entered, no reader can enter. So, that we have taken care of. We will perform reading. So similarly, please note that When a writer is writing, the first reader goes and tries to read. He would have incremented read count and now read count is 1, then he will go and wait in WRT. So he has to wait till the writer finishes. Now please also note that the mutex is also with him. The mutex is also with the reader. He has not still released the mutex. So any other reader who wants to execute on read. from this, they will come and wait where? They will wait on mutex itself. So, please note that writer 1 is writing, so it has WRT, reader 1, reader A is the first one to start reading. Now he will find that read count is 1, he will go and wait on WRT. So, reader A has mutex and he is waiting on WRT. Now reader B wants to or reader C wants to read here, now he will go and wait on mutex itself because mutex is currently held by writer A. So, writer B is writing, so WRT is with the writer B, reader A wants to read, he gets mutex, wait mutex, he will make mutex 0, he will get mutex, he will enter that code, he will make read count equal to read count plus 1 and now he will find out read count is 1 because he is the only reader. Now, he will go and wait on WRT, the WRT is held by writer B. Now, reader C wants to read, he will go and wait on WRT, the WRT is held by writer B. to read, he will now wait in mutex itself because it is there. So now what happens when one writer is writing and any number of readers want to read, everybody will start waiting in mutex. You are getting this? Everybody will start waiting in mutex. So when one writer is writing, everybody will start waiting in mutex. When the writer is writing, no other reader can enter the corresponding critical section. Now when the writer finishes signal write, then it will, when it signals, what will happen? The reader A will get that signal. Now he will go and signal mutex. So, reader C will now do read count equal to read count plus 1 and then he will now wait on write. Now, read count becomes 2. So, when read count is 1 only you go and wait on write. You will not execute the second statement there. The reader C will not execute the second statement there, he will signal mutex and then correspondingly every reader can enter. So when the writer finishes, then all the readers who are waiting will start entering into it. So multiple readers can enter. So the Only the first reader will check if there is a writer. If there is a writer inside, he will stop everybody else, he will hold mutex and he will stop everybody else from entering and when the writer finishes, immediately he will enter and once he enters, he will allow everybody else to enter because he will release mutex. So, the first reader alone will check whether there is a writer and the other readers will not check. read count equal to 1 then wait for read. After we perform the reading then what happens? Again when I do read count equal to read count minus 1, if read count equal to 0 that means I am the last reader then I will go and say signal WRT. So, the moment I start reading the first reader will hold WRT and then he will enable second reader, third reader, fourth reader. Now the fourth reader. is the one who is going to finish, let us say they are doing it in, you know, it takes that same amount of time. So, the second reader will finish, first reader, second reader, third reader, fourth reader is the fellow who finish, that fellow will be responsible for returning the WRT. So, that is why we say if read count equal to 0, then signal WRT. So, by just using two semaphores, we are now in a position to see that two semaphores are Two things, one semaphore mutex is basically used to increment and decrement read count. In addition, mutex is also used to stop readers from entering when there is a writer as I explained. And then there is a WRT which ensures that exactly one writer enters and when that writer is inside, no reader will be there and many readers can enter and when there is a reader, no writer can enter. So, that is the first thing. So, these two are basically achieved. So, this is an interesting example of how we can use weight and signal to basically do this synchronization. So, this is called the code section. So, perform writing, perform writing, perform reading, this is called the code section and that code section is a critical section. So, for a writer process perform writing is a critical section, for a reader process perform reading is a critical section. Now I could have reader area. reader c, two readers, they need not do the same reading, they can do different reading, but that reading port is a associated critical section. Similarly, writer b and writer d as you see they can perform different writing, they need not do the same code as you see in contemporary test books. So it can be different code. So I have writer a, reader b, reader a, writer b, reader c, writer d, four fellows here, each will do different writing and different reading respectively, that code can be different. be different, but all these four sections which I have marked as ellipses here, they are associated and they need to follow this access principle that at any point of time exactly one writer can be there and no reader can be there, multiple readers can be there, but then no writer can be there and this is what we need to achieve here. So, the thing is that there are multiple things that we need to achieve in this critical sections or critical session or whatever you call here. So, one thing is mutual exclusion that we have seen that exactly one fellow should be there or multiple depending on the access rule. The second thing is progress. What do you mean by progress? That when nobody is there in the critical section and I want to enter, I should be allowed to enter. That is called progress. And the third important thing about here is bounded weighting. want to access that critical section, I should access it within a bounded amount of time. I should not infinitely wait for that. So, these three aspects are very important while we implement this critical section. One thing is mutual exclusion. Another is progress. Mutual exclusion we have seen. Progress is that when nobody is there in the critical section and I want to access it, I should be allowed to access. That is called progress. Bounded waiting. When I want to access a critical section, I express a wish to access a critical section at time t within some time t plus delta. That delta should be quantified. I should be allowed to access. There should be a guarantee that I should access. These three are very very important. These three conditions, one is called deadlock where the processes can permanently be blocked, livelock where execution is done but no progress or starvation where one or more threads or process are denied the resources. One of these three conditions can basically occur. So when we do process synchronization, whenever we talk of mutual exclusion as we have described here, we need to take care of progress and bounded waiting. So, who will ensure this progress and bounded weighting? The way weight and signal is implemented that will ensure that we will have progress and bounded weighting. We will have all the three mutual excursion, progress and bounded weighting. While we will not go into the exact implementation of these three, but we know that there are modern processes which can help us by having these atomic processes. instructions. So, there are lot of atomic instructions for example, something called a test instruction, there is something called swap instructions where you can swap the values of 2 bits, test instruction, test and set instructions it is called. So, I can test the value of bit and set it immediately as a single operation. So, there are implementations of this weight and signal of a semaphore that basically uses this swap. and test and set instructions which are atomic. If you look at the instruction set of many of the contemporary microprocessors that have come in the last two decades, you will find these type of atomic instructions that are uninterruptible and which can be used to implement this weight and signal operations. And once I could do that, I can basically ensure there will be mutual execution and I can ensure there will be progress and bounded weight. So, one has to be extremely careful about... Deadlocks. First thing is that when there is mutual exclusion, we need mutual exclusion because we need to share resources. Along with mutual exclusion, if I have hold and wait, that is a process is holding a semaphore or a resource by which it is blocking another process from entering and there is no preemption, that is the operating system cannot take a resource back from a process that has it. I have given that resource, I cannot take it back. And then Then you land up with a circular wait. A is holding a resource and it is waiting for B to release. B is holding a resource which A wants but it is waiting for C. C is holding a resource which A wants and so A is waiting for B, B is waiting for C, C is waiting for A. If that type of a circular wait comes, then if all these 4 conditions are true, then deadlock can occur. So, when we do process synchronization, one of the thing is that we implement such that These three conditions are satisfied, mutual execution, progress and bounded weighting. In addition, we also see that a circular weight does not happen and that is very, very important. So, when you look at a complex system like the file system, a lot of synchronization needs to be done because many processes share many files. Now, to basically handle deadlock and ensure that a deadlock free envelope comes, that becomes a big challenge. Deadlock can also be a denial of service. And so... So, there is also some sort of security implications for this. So synchronization in Linux prior to kernel version 2.6, the synchronization happens like this. I want to have an atomic instruction that means it is uninterruptible. So, how do I relay an uninterruptible instruction? Go and disable interrupt when it starts executing, enable interrupt after it completes execution. But that is a very trivial naive way of doing it. In version 2.6 and later, it has become fully preemptive. And, Linux actually provides semaphores and spin locks. Okay. So, this is all that I wanted to talk about process synchronization, some depth about race conditions and how do you implement mutual exclusion, etc. Right. So, this will form some basis for you to appreciate operating systems security and administration at a later point of time. So, I also guide you to some of the test books, the standard test books like Galvin to basically the Look into this chapters in detail. The objective of this course is to actually teach you administration of operating systems and administration of network security, networks basically from a security perspective. Nevertheless, these are some title. which need to be understood in great detail and that is why we gave a glimpse of it. It is not a complete education on process synchronization, but whatever is necessary is given an initial, but there are also MOOC courses on. on operating systems plus standard test books and other NPTEL lectures which you are welcome to read to understand more about process synchronization. So, we will meet in the next module. Thank you.

And if that discipline is not adhered to then the process is basically can access that resource in. in such a way that there could be some inconsistency in the entire operation. When you look at the entire operating system, there are lot of shared resources. For example, there is something called buffer cache, there is something called the super block in the file system. There are many shared resources and these resources are shared by multiple processes at a given point of time.

And so process synchronization becomes the bread and butter. of how to maintain consistency of access of these shared resources among these processes whenever they try to access them. So that becomes the subject matter.

So we will introduce process synchronization not from a file system point of, not from examples derived from file system but using some simple concepts like you know sharing a buffer etcetera and then we will introduce the concepts and understanding this concept is also very important from a security perspective because. A lot of leaks of information do come, race conditions could be exploited to basically hack into your system and these are very important concepts that need to be understood specifically for the security community too. So the objective of this particular module is about getting processes to coordinate with each other, about how processes work with resources that must be shared between them and about how we go about acquiring blocks to protect regions of memory.

Why do you need to protect? Because if I do not protect, 2 processes can access at the same time and basically go and make the content of that memory inconsistent with what the program is actually doing. We will see some examples and how synchronization is really used and it is really implemented.

So that is, these are all the objectives of this particular module. So but why should we synchronize? This is because I am sharing the resources. When I am sharing the resources, I am not just sharing the data. resources, I need to adhere to some discipline.

If I do not have that discipline, then what will happen is that the state of your resource will become inconsistent, the data actually becomes inconsistent. We will give you some examples of that as we progress. And there is, we have to share resources because we are looking at a cooperating environment where multiple processes try to work together to basically solve a particular problem.

We have already seen why more than one process can work together and we can do scheduling we have seen in the previous module. In the context of scheduling we found that if two processes are working together then I can basically merge the CPU time of one process with the I O time of another essentially giving you lot more computation speed up and lot more hardware utilization etcetera. In addition I could have certain things like modularity and convenience. For example if I have a particular functionality, I would like to keep that functionality with respect to a particular module so that tomorrow when I upgrade a software, so software has 5 different functionalities, I would like to realize it as 5 different modules because tomorrow when the software is actually upgraded and say functionality 3 changes, the modules corresponding functionality 1, 2, 4 and 5 can be retained and only the third module need to be changed and this becomes.

very easy for me to release the next version. So modularity is also very important for creating this type of large scale software and that basically comes by isolating different loosely related modularities as separate threads or processes and building up a system. And if that needs to be executed then basically what happens is that each module becomes a thread and or a process and these processes.

work in a cooperating way to solve the problem and then hence we will end up with a cooperating process environment. So, what may happen when process cooperate? So, we will take up a very simple problem called buffer sharing problem.

So, when one and there is a producer who produces. into that buffer, there is a consumer who consumes from the buffer and so let me say that there is a bounded buffer, so I have n locations. Now, a producer should not produce into a buffer that is already full. because he will not have location to store it.

And the consumer should not consume from a empty buffer. He will basically land up with a null. So this is the access rule, right? So if I have one buffer that I am going to share, there is a consume. consumer who consumes from the buffer, there is a producer who produces into that buffer, the producer should not produce into a buffer that is full and a consumer should not try and consume or remove data from that buffer when the buffer is empty.

This is a rule that we need to implement. So this is where I need synchronization. So when the buffer is full, I should not allow the producer to add an entry there.

When the buffer is empty, I should not allow the consumer to consume. from it. So, this rule has to be implemented and this is what we call as a synchronization.

So, the producer is a process, the consumer is another process, both of them are working together in a cooperative way and there is, they are trying to share a resource in this case a buffer and there is a discipline that I am basically enforcing in this context where you know the producer produces. and the consumer consumes, the producer should not produce into a full buffer, the consumer should not consume from an empty buffer. So this is what we are trying to achieve here.

So this is the entire diagram for this. So what will the producer do? So if you look at the extreme left, the producer will wait for the buffer to be not full.

If the buffer is not full, he goes across the orange block. Then he will go and lock the buffer. Then he will deposit some.

something, then he will unlock the buffer and if the buffer is not empty he will go and trigger something and then he goes back. So that two green cross lines we will just discuss it a little later, but what does the producer do? It just two orange boxes, it will wait, the first orange box will wait till the buffer is not full.

So, if the buffer is full it will wait till the buffer is not full. full. So, if the buffer is full it will keep waiting there.

And if the buffer is full it will be waiting and who will go and say that you can proceed? It is waiting there meaning that process is in a suspended state. Now, who is going to go and say you can proceed? The consumer is going to go and say. So, when the consumer consumes something from the buffer, certainly there will be one location which will be.

not full because it has consumed one fellow from there so that at least one location will be there. So, that is the fellow who triggers an event to the producer saying hey the buffer is not full for sure. So, that is the green line that goes from the consumer to the producer. So, when the producer comes it finds that the buffer is full, it waits on the first orange box till the green signal comes from the consumer saying hey the buffer is not full now you can go and produce.

Immediately it will go and lock the buffer and it will deposit and then unlock the buffer and then it will come back to, it will now go and say to the consumer buffer is not empty because it has produced something. So, now it will go and tell the consumer buffer is not empty and it will go back. For the consumer it will wait till the buffer is not empty.

Because, if the buffer is empty it has to wait, so it will wait till the buffer becomes not empty. So, if the buffer is empty it will wait there and there is a green signal coming from the producer which says A no F produce one thing certainly the buffer is not empty. So, then it will go, it will lock the buffer, it will retrieve that data and then it will unlock the buffer.

Again it comes back and it says now I have at least one location is empty there. So, it will say buffer is not full that signal it will send to the producer. So, the 2 signals that pass from the consumer to the producer and from the producer to the consumer, these are the synchronizing action. By having these 2 signals here, we basically see to it that the producer does not produce into a full buffer and the consumer does not consume from an empty buffer.

Both will land up in an inconsistent state. Now also note that whenever I am depositing, whenever the producer is depositing something into the… to the buffer or when the consumer is retrieving something from the buffer, it basically It locks the buffer because when I am producing into the buffer, I do not want the consumers to start consuming. I want to finish that deposition, I want to deposit the entire thing and then only allow the consumer to consume. So, there is a lock and a unlock. So, when there is a buffer.

When the buffer is locked what will happen? The consumer cannot cross that lock buffer. When the producer has crossed the lock buffer, the consumer cannot cross the lock buffer.

It will wait till the producer unlocks. blocks, then only the consumer can go and start retrieving. So at the same point of time the producer and the consumer cannot be inside the yellow blocks meaning deposit and retrieve. When the producer is depositing the consumer cannot retrieve, when the consumer is retrieving the producer cannot deposit.

So that is also taken care. Otherwise half the way he is depositing this fellow will start retrieving it then there could be an inconsistent state. So, what you see on the right hand side is basically an implementation of this entire shared infrastructure.

So, there is one buffer that is shared by the producer and consumer and this is how the access to this is basically synchronized. So, the two green lines basically tell you how we synchronize these two actions of not producing into a full buffer and not consuming from an empty buffer. The solution essentially is the producer goes to sleep or discard data. of the buffer is full.

Actually in this case it goes to sleep. So when that is the first rectangle on the producer side, the orange rectangle, the body mean by weight it goes to sleep. When consumer removes an item from the buffer, it notifies the producer who starts to fill the buffer again and that notification goes through this green line from the consumer to the producer. Similarly, the consumer goes to sleep if it finds the buffer to be empty which is the first red rectangle on the consumer side.

And whenever the producer puts data into the buffer, it wakes up the sleeping consumer. Now, let us go and make it much more interesting. So, let us say there are two programs P1 and P2, right?

This is a C program. There is a both this program P1 and P2 share one integer called C. Like they share a buffer, this shares an integer called C.

The program P1 increments C, the program P2 decrements C. Assuming that P1 executes immediately followed by P2, the value of C should remain the same. Let us say. say before execution of P1 the value of C is 4 or in this case let us say the value of C is 42, when P1 executes and then P2 executes the answer should again remain 42. But what we will show now is that when P1 executes followed by P2 in some interlaced fashion the answer can become 43. That is what we are going to show now. Now what do you mean by incrementing C++?

Please note. Note that that c++ that you see there in red on your left hand side essentially is 3 assembly instruction that is incrementing an integer is 3 assembly instructions. The 3 assembly instructions that you see here load the content of c into register 1, increment register 1, store the content of register 1 back to c. This is the syntax let us keep this as the syntax. Similarly for c minus minus load the content of c on to register 1. register 2, decrement register 2 and store the content of register 2 back to C, correct.

So this is how increment works, this is how recruitment works. Now these are 3 assembly instructions. Now what will happen when I am going to execute this course?

Let us say the P1, the first 2 instructions of this is executed, say load ampersand C register 1 that means register 1 gets the value 42 because C is initialized to 42. Now see how the program works. I am executing at the bottom of your screen here. First I will load C into register 1, so 42 gets into register 1. I will increment, so register 1 becomes 43. Before I could store, please note that the P2 starts executing. Because let us say it is a round robin algorithm, so there is a context switch. So before, so the time quantum allotted to P1 is over, now I go to P2.

Now P2's load C res 2 happens, so res 2 again gets 42 because C is not up. C is still 42, so res 2 will get 42 and now decrement res 2, so res 2 gets 41. Then I store the value of res 2 on to C, so C gets 41. Now the counter switch happens. When the corner switch happens back to P1, what happens it will now It is in the third instruction. The first two instructions are already done.

The third instruction is store edge 1 ampersand C. So, C will get 43. So C++, C++ executed one after another should maintain the value of C as 42 but when I compile that code C++ and C++ I get 3 assembly instructions for C++ and 3 assembly instructions for C++ and when I am started executing this program and if they get interleaved in between then what happens I get an inconsistent value for C. Do you follow? This is the problem of sharing data and this is a race condition because who wants to finish first?

Two fellows are racing, P1 and P2 are racing with each other and because of that this entire problem has happened. Now, what is the solution to this? When P1 is executing these 3 instructions, P2 should not be allowed to execute those 3 instructions. When P2 is executing those 3 instructions, P1 should not be allowed.

out to execute these three instructions. If you had done C++ completely and then C minus minus or if you had done C minus minus completely and then C++ then this problem should not have happened. The point is to ensure that what should I do? I should execute P1 first, the 3 assembly instructions corresponding to P1 first, I have to finish that.

Then I have to start the assembly instructions with respect to P2 or I should finish off the assembly instructions with respect to P1. P2 first and then start assembly instructions with respect to P1. That means these 3 instructions and these 3 instructions of P1 and P2 they form the critical section for P1 and P2. So if you look at some of the modern books, critical section means one single code which is executed by multiple programs. That is the feel you get in some of the operating system books.

That is not the case, right? There is a critical section. for every program and they are different, but they are all bound by one level. So, for the purpose of executing this multi-threaded program which essentially has two threads namely P 1 and P 2. is one critical section spawning between those program. The critical section of P1 is these three instructions that you see on the left, the critical section for P2 are the three instructions you see on the right and these two critical sections are linked in the sense that when P1 is executing its critical section, P2 should not go into the corresponding associated critical section.

executing its critical section, P1 should not go into its associated critical section. You are getting this point. So when you look at all these modern books, there will be one block called critical section and almost every student I have interviewed so far in the last 16 years have shown that there is one critical section which two fellows will share.

No. The code is different. Again I repeat P1's critical section has the code on your left hand side, P2's critical section has the code on the right hand side. When P1 is executing its code which is different from the code of P2. should not go and execute its associated code and vice versa.

And if that is ensued then this type of an inconsistency or race condition should not will not happen right and that is what we meant by locking. locking and unlocking. So imagine that very simply that before coming into this P1 these 3 instructions it will go and lock and the end of this it will go and unlock.

Similarly P2 will also put a lock and unlock before and after this C code. So when I lock, so P1 locks and then when P2 also tries to lock it will say somebody else has locked and it will ask to wait. And when I unlock then I. I go and release the lock, so P1 can now lock and go in.

But when I unlock, what has happened? I have completely finished executing those 3 instructions. I unlock only after I finish the 3 instructions. By this only one fellow will be allowed to go into the critical section while the other fellow will be waiting on its critical section. Please note.

And when it comes and executes its critical section, this fellow should be out of that critical section. enter here again yes So, the notion of allowing only one process to execute on its critical section while the other process has to wait and vice versa and it extends to n processes. If all n processes share one resource. source, each one will have its own critical section and exactly one can be in its critical section, the others have to be out of their respective critical section. This property is called mutual exclusion.

And so So, the entire process synchronization revolves around how do we achieve this mutual exclusion. So, one immediately we have seen how we achieve this mutual exclusion, we have seen the notion of lock in the previous one but one slide. So, I lock the buffer and I unlock, I get this mutual exclusion, right.

But it is not so easy. Now we will see how to achieve this mutual exclusion but the need for a mutual exclusion crucial exclusion is that I need to have a synchronization mechanism to avoid raise conditions by ensuring exclusive execution of critical section. That is the motive of mutual exclusion and this exclusive execution of critical section wherein only one fellow can enter and the other fellow should not enter, this is among n cooperating processes. I need to get a method for that.

From the OS point of view. This is achieved using something called semaphores or monitors. What is a semaphore?

Semaphore is a shared entity, it has an integer value and it can be decremented, it can be incremented. When I decrement a semaphore and its value becomes 0, I sleep. When I increment it is just to go and increase its value.

I said there is an integer value, right? It is an increase its value by 1, right? And when I am incrementing, before I increment I sleep.

I check if it is 0, if it is 0 then I go and wake up all the processes that are waiting for this semaphore. So let us understand a semaphore has 2 operations, it has an integer value and it has 2 operations P and V, P means decrement, V means increment. Decrement what I do?

I decrement reduce the integer value I reduce it by 1 and if that value becomes 0 I put that process which is trying to decrement to sleep. Ready? When increment means I go and increment that integer value and before incrementing I check if it is 0, if it is 0 then there will be some processes that are sleeping I wake all of them and then I go and increment. So these are the 3 operations and semaphores can be used extensively for achieving this synchronization that we have done in the past. There are also binary semaphores which basically does not have a value but it is basically the integer values in the range 0 and 1. an integer value, it has a bit as that value.

So, it basically uses 0 and 1 and these binary semaphores are also called as mutual exclusion locks. A lock is something like you have locked or unlocked, there is no value for it. Now, as we see that a critical section as in 3 parts as we saw in the program also in the previous thing, a critical section whatever we see as 3 instructions is the critical section for the. p 1 and also on the left for p 2, but there is something before it and then there is an entry into the critical section, then there is exit from the critical section and then there can be reminder. So in a huge code there will be some part which is the critical section, there will be entry criteria for the critical section, there will be some exit criteria for the critical section and then there will be remaining portion of the code.

So that is what we have seen here. So there will be an entry section for a critical section, then the critical section itself, then an entry. an exit section for the critical section and there will be something called remainder section which is the remainder of all the code.

The entire code minus the critical section is the remainder section. Now we will explain the synchronization through what we call as the readers-writers problem which is very interesting. So there is a shared data and multiple readers can read from that data.

At the same point of time multiple readers can read from the data, but only one fellow can write into the data at any point of time. And when somebody is writing into that, nobody can read. So the three conditions are at any point of time multiple readers can be reading, no one can be writing, should write.

And at any point one fellow can write, more than one cannot write, only one fellow can write and when that fellow is writing nobody else can read. So, these are the three types of criteria. ...material that we want to put and let us see how synchronization, how do we achieve this.

So, this is called a reader's writer's problem. So, what are there? There is a data which people will read and write, may be one integer variable or whatever and then we will... be using 3 semaphores, one is called mutex initialized to 1, WRT which is initialized to 1 and then we will have an integer called read count which is initialized to 0. So, these are all the shard data. So, I have a data set which people will read and write from, the processes will read and write from.

There is a semaphore called mutex which is initialized to 1, there is a semaphore called wrt which is initialized to 1 and there is an integer which is called read count which is initialized to 0. The read count actually tells how many readers are currently reading the shared data. Read count essentially says how many readers are currently reading the shared data. Now let us do this.

The code for writer is note that. there could be multiple readers and multiple writers. There will be n readers and n writers, not one reader and one writer.

There could be n readers and n writers. So, one example for that is a file is to be shared among several processes. Many processes can read at the same time. Many processes will try to write, but when it is writing only one fellow should be allowed. After that other fellow can be allowed, but one point of time only one fellow can be allowed to write, but many fellows can be allowed to read the file.

There is a direct translation of the reader status problem to a practical problem. Now, this is the code. I have WRT as a semaphore. So what I do is when I want to write. I just say wait wrt, wrt is a semaphore, so when I say wait wrt it is initialized 1. So when I say wait it becomes 0. Now if somebody wants to write he will also execute wait wrt, when wrt is 0 he will go to sleep.

So, I will perform writing and then I will do signal WRT. When I do signal WRT, what will happen? That will be incremented from 0 to 1. Since it is incremented from 0 to 1, if somebody is waiting, those fellows will also be woken up.

So, wait WRT and signal WRT will ensure that only one fellow can write at any point of time. So, whoever executes wait WRT first will execute that fellow. He will see that WRT is 1 and he will reduce it to 0 and that fellow will come and start performing the writing. The other fellows who are going to execute the wait WRT later, they will all wait.

After this fellow finishes, he signals WRT then those fellows will start executing. By this what, just by putting wait WRT and signal WRT, I have ensured that only one process can write, more than one process cannot write at the same time. Now, this wait wrt and signal wrt are atomic instructions.

Atomic instruction is that when I am executing wait, it will be completely executed before something else can get executed. So, when I start executing wait, I will finish the execution of wait before anybody else can do anything. So, by this two processes want to write into the shard data.

cannot execute wait at the same time and get access into the perform writing part. So, only one fellow, so if two fellows want to execute write, the first fellow the moment he says wait write, he will finish of wait write then only he will give the control to the next fellow. So, I will do wait write, the other fellow wants to do wait write, when I get hold of wait write, I will start executing wait write.

finish that wait write then only I will give the control to the other fellow because wait is an atomic instruction. That is what we mean by atomic instructions. So, when I say wait, so essentially I do that wait and if write is 0, wrt is 1, I make it 0 and I start performing the writing while other fellow executes wait after me and he will find that wrt is 0. So, essentially he will go and sleep. Now, when I finish writing.

Then I say signal, then I allow him to go and continue. So, this is how. So, I have ensured that no two fellows can write at the same time. Now, the other thing that we need to ensure is when I am writing, no fellow should read When somebody is reading, no fellow should be allowed to write. When I am writing, the writer alone will be there.

No other fellow will write, no other fellow will read also. And when I am reading, no other fellow will be allowed to write. Correct?

You are getting this? So, now how do I achieve this? The reader problem that is shown below.

We will go ahead and go to the next slide and see how it is achieved. First foremost, if you look at the reader code down, there is something called read count. What will read count tell you?

Read count basically tells that the number of readers that are currently reading. And please note that when I want to read, first I increment read count, then I perform the reading, then I decrement read count and go off. So, that is what I am doing. Say read count equal to read count plus 1, perform reading, read count equal to read count minus 1, get away.

Since multiple fellows can read at the same time, please note that when one fellow is doing read count equal to read count plus 1, another fellow can do read count equal to read count minus 1. One fellow does read count plus plus, at the same time another fellow can do read count minus minus. if a same variable is incremented by one process and it is decremented by another process, already we have seen that there is a raise condition. So, whenever I am incrementing read count or whenever I am decrementing read count, I want to protect it.

So, that only one. fellow can increment read count and only one fellow can decrement read count. So, what I do there?

So, I use that semaphore called mutex. So, I say weight mutex, read count equal to read count plus 1, signal mutex. Perform reading. Wait mutex read count equal to read count minus 1 signal mutex.

So, there are multiple readers. If any of the reader is in either incrementing or decrementing, he would have made mutex to 0. Then only you can read. can enter.

So, when I want to enter either read count equal to read count plus 1 or read count equal to read count minus 1, one of those two sections either on the top before reading or on the bottom after reading, if I want to enter my mutex value should be be 1 and the moment I enter I will make the mutex to 0. So, all the fellows who want to enter either of these sections, they may all the readers can be in either one of these 3 sections, it can be either on the entry part where it is incrementing read count or it can be actually reading or it can be on the exit part where it is decrementing read count. So, if any of the process wants to enter any of these 2 mutual execution sections, they cannot enter unless I finish my. operation. If I get hold of mutex, no other process can increment or decrement read count until I finish the incrementing or decrementing of the read count.

By this read count, there is a serialization of the way by which I keep on increasing or decreasing the read count. If I do not put that mutex before and after signal, wait and signal mutex before read count equal to read count plus 1 and after read count equal to read count plus 1. 1 or again if I do not put weight and signal before in between and read count equal to read count minus 1. If I do not put that weight and signal there, then what will happen? There will be a raise condition on the way read count is managed. So the read count will become inconsistent. Read count should tell me how many fellows are reading, but if I do not put that weight and signal mutex on both ends, then read count can become inconsistent.

an inconsistent value as we had demonstrated earlier. You are following this? So what happens here is that there is, so when 2 readers are there, so reader 1 wants to do reading, it first gets weight mutex and then it increments read count. Just forget the next statement, if read count equal to 1, we will explain it a little later.

Then it will signal mutex. It has incremented read count and now it is doing reading. After it signals mutex, reader 2 can now go and increment read count and he can also do signal mutex and he can also do reading. So, at the same time, 2 fellows can do the reading, but 2 fellows cannot increment read count at the same time.

If they are allowed to, then we will land up with the inconsistency we have already seen in this lecture. And again when they finish the reading, they want to decrement read count, again there there will be a serialization. Reader 1 will finish, then reader 2 or reader 2 will finish and then reader 1. So, please note that if I put a wait mutex in the beginning and signal mutex in the last and I do not have any signal and wait in between, then which property is violated? The property that multiple readers can read.

read at the same time that property gets violated. So I have to put a wait and signal before and after read count equal to read count plus 1 and again a wait and signal before read count equal to read count minus 1 before and after. So then what happens is multiple readers readers can read at the same time, but they cannot increment or decrement read count at the same time. So, that is the basic thing. Please understand this is how it works.

So, this is about readers. So what are the two properties that we have ensured? Now let us go here. I have ensured that two writers cannot write at the same time. So, only one writer can enter.

Multiple readers can read at the same time and read count is consistently incremented and decremented. These two I have. ensured, but what I have not ensured is that when a writer is writing no reader can read and when a reader is reading no writer can write and that is basically achieved by those two statements if read count equal to 1 then wait WRT. So, when will read count be equal to 1?

When I am the first reader, correct? Because I have just incremented read count equal to read count plus 1 and then immediately I am executing if read count equal to 1. count equal to 1, then wait WRT. Please note the reader code. Now, when read count equal to 1 means I am the first reader, then I will go and say wait WRT. If already somebody has entered and they are doing the writing, then what will happen?

I have to wait. If there is a writer already in, I have to wait. If no fellow is writing there, then WRT will be 1. I would have made it 0 and I will start reading. Correct?

So, if another writer wants to enter, he will start waiting because if I am the first reader and I go and wait on WRT, what will happen? I will I will and nobody is writing, then I will get that WRT as 1, I will make WRT to 0 and since WRT is 0, no other writer also can enter into it. So, the first reader who gets WRT as 1, he will make WRT 0 and till WRT becomes 1, no writer can enter. So, when a reader has entered, no writer can enter. When a writer has entered, no reader can enter.

So, that we have taken care of. We will perform reading. So similarly, please note that When a writer is writing, the first reader goes and tries to read.

He would have incremented read count and now read count is 1, then he will go and wait in WRT. So he has to wait till the writer finishes. Now please also note that the mutex is also with him. The mutex is also with the reader.

He has not still released the mutex. So any other reader who wants to execute on read. from this, they will come and wait where? They will wait on mutex itself. So, please note that writer 1 is writing, so it has WRT, reader 1, reader A is the first one to start reading.

Now he will find that read count is 1, he will go and wait on WRT. So, reader A has mutex and he is waiting on WRT. Now reader B wants to or reader C wants to read here, now he will go and wait on mutex itself because mutex is currently held by writer A.

So, writer B is writing, so WRT is with the writer B, reader A wants to read, he gets mutex, wait mutex, he will make mutex 0, he will get mutex, he will enter that code, he will make read count equal to read count plus 1 and now he will find out read count is 1 because he is the only reader. Now, he will go and wait on WRT, the WRT is held by writer B. Now, reader C wants to read, he will go and wait on WRT, the WRT is held by writer B. to read, he will now wait in mutex itself because it is there.

So now what happens when one writer is writing and any number of readers want to read, everybody will start waiting in mutex. You are getting this? Everybody will start waiting in mutex. So when one writer is writing, everybody will start waiting in mutex. When the writer is writing, no other reader can enter the corresponding critical section.

Now when the writer finishes signal write, then it will, when it signals, what will happen? The reader A will get that signal. Now he will go and signal mutex. So, reader C will now do read count equal to read count plus 1 and then he will now wait on write. Now, read count becomes 2. So, when read count is 1 only you go and wait on write.

You will not execute the second statement there. The reader C will not execute the second statement there, he will signal mutex and then correspondingly every reader can enter. So when the writer finishes, then all the readers who are waiting will start entering into it. So multiple readers can enter. So the Only the first reader will check if there is a writer.

If there is a writer inside, he will stop everybody else, he will hold mutex and he will stop everybody else from entering and when the writer finishes, immediately he will enter and once he enters, he will allow everybody else to enter because he will release mutex. So, the first reader alone will check whether there is a writer and the other readers will not check. read count equal to 1 then wait for read. After we perform the reading then what happens?

Again when I do read count equal to read count minus 1, if read count equal to 0 that means I am the last reader then I will go and say signal WRT. So, the moment I start reading the first reader will hold WRT and then he will enable second reader, third reader, fourth reader. Now the fourth reader.

is the one who is going to finish, let us say they are doing it in, you know, it takes that same amount of time. So, the second reader will finish, first reader, second reader, third reader, fourth reader is the fellow who finish, that fellow will be responsible for returning the WRT. So, that is why we say if read count equal to 0, then signal WRT.

So, by just using two semaphores, we are now in a position to see that two semaphores are Two things, one semaphore mutex is basically used to increment and decrement read count. In addition, mutex is also used to stop readers from entering when there is a writer as I explained. And then there is a WRT which ensures that exactly one writer enters and when that writer is inside, no reader will be there and many readers can enter and when there is a reader, no writer can enter. So, that is the first thing. So, these two are basically achieved.

So, this is an interesting example of how we can use weight and signal to basically do this synchronization. So, this is called the code section. So, perform writing, perform writing, perform reading, this is called the code section and that code section is a critical section.

So, for a writer process perform writing is a critical section, for a reader process perform reading is a critical section. Now I could have reader area. reader c, two readers, they need not do the same reading, they can do different reading, but that reading port is a associated critical section.

Similarly, writer b and writer d as you see they can perform different writing, they need not do the same code as you see in contemporary test books. So it can be different code. So I have writer a, reader b, reader a, writer b, reader c, writer d, four fellows here, each will do different writing and different reading respectively, that code can be different.

be different, but all these four sections which I have marked as ellipses here, they are associated and they need to follow this access principle that at any point of time exactly one writer can be there and no reader can be there, multiple readers can be there, but then no writer can be there and this is what we need to achieve here. So, the thing is that there are multiple things that we need to achieve in this critical sections or critical session or whatever you call here. So, one thing is mutual exclusion that we have seen that exactly one fellow should be there or multiple depending on the access rule.

The second thing is progress. What do you mean by progress? That when nobody is there in the critical section and I want to enter, I should be allowed to enter. That is called progress.

And the third important thing about here is bounded weighting. want to access that critical section, I should access it within a bounded amount of time. I should not infinitely wait for that. So, these three aspects are very important while we implement this critical section.

One thing is mutual exclusion. Another is progress. Mutual exclusion we have seen.

Progress is that when nobody is there in the critical section and I want to access it, I should be allowed to access. That is called progress. Bounded waiting.

When I want to access a critical section, I express a wish to access a critical section at time t within some time t plus delta. That delta should be quantified. I should be allowed to access. There should be a guarantee that I should access. These three are very very important.

These three conditions, one is called deadlock where the processes can permanently be blocked, livelock where execution is done but no progress or starvation where one or more threads or process are denied the resources. One of these three conditions can basically occur. So when we do process synchronization, whenever we talk of mutual exclusion as we have described here, we need to take care of progress and bounded waiting. So, who will ensure this progress and bounded weighting? The way weight and signal is implemented that will ensure that we will have progress and bounded weighting.

We will have all the three mutual excursion, progress and bounded weighting. While we will not go into the exact implementation of these three, but we know that there are modern processes which can help us by having these atomic processes. instructions.

So, there are lot of atomic instructions for example, something called a test instruction, there is something called swap instructions where you can swap the values of 2 bits, test instruction, test and set instructions it is called. So, I can test the value of bit and set it immediately as a single operation. So, there are implementations of this weight and signal of a semaphore that basically uses this swap. and test and set instructions which are atomic. If you look at the instruction set of many of the contemporary microprocessors that have come in the last two decades, you will find these type of atomic instructions that are uninterruptible and which can be used to implement this weight and signal operations.

And once I could do that, I can basically ensure there will be mutual execution and I can ensure there will be progress and bounded weight. So, one has to be extremely careful about... Deadlocks.

First thing is that when there is mutual exclusion, we need mutual exclusion because we need to share resources. Along with mutual exclusion, if I have hold and wait, that is a process is holding a semaphore or a resource by which it is blocking another process from entering and there is no preemption, that is the operating system cannot take a resource back from a process that has it. I have given that resource, I cannot take it back.

And then Then you land up with a circular wait. A is holding a resource and it is waiting for B to release. B is holding a resource which A wants but it is waiting for C.

C is holding a resource which A wants and so A is waiting for B, B is waiting for C, C is waiting for A. If that type of a circular wait comes, then if all these 4 conditions are true, then deadlock can occur. So, when we do process synchronization, one of the thing is that we implement such that These three conditions are satisfied, mutual execution, progress and bounded weighting. In addition, we also see that a circular weight does not happen and that is very, very important. So, when you look at a complex system like the file system, a lot of synchronization needs to be done because many processes share many files.

Now, to basically handle deadlock and ensure that a deadlock free envelope comes, that becomes a big challenge. Deadlock can also be a denial of service. And so... So, there is also some sort of security implications for this. So synchronization in Linux prior to kernel version 2.6, the synchronization happens like this.

I want to have an atomic instruction that means it is uninterruptible. So, how do I relay an uninterruptible instruction? Go and disable interrupt when it starts executing, enable interrupt after it completes execution. But that is a very trivial naive way of doing it.

In version 2.6 and later, it has become fully preemptive. And, Linux actually provides semaphores and spin locks. Okay.

So, this is all that I wanted to talk about process synchronization, some depth about race conditions and how do you implement mutual exclusion, etc. Right. So, this will form some basis for you to appreciate operating systems security and administration at a later point of time.

So, I also guide you to some of the test books, the standard test books like Galvin to basically the Look into this chapters in detail. The objective of this course is to actually teach you administration of operating systems and administration of network security, networks basically from a security perspective. Nevertheless, these are some title.

which need to be understood in great detail and that is why we gave a glimpse of it. It is not a complete education on process synchronization, but whatever is necessary is given an initial, but there are also MOOC courses on. on operating systems plus standard test books and other NPTEL lectures which you are welcome to read to understand more about process synchronization. So, we will meet in the next module.

Thank you.

Transcript for:Understanding Process Synchronization in Operating Systems

Transcript for:
Understanding Process Synchronization in Operating Systems