Process Synchronization with Busy Waiting

#muict #os #process #busywaiting

HELLO :D This post is dedicated to BUSY WAITING! But first of all, we have to (or should) know what's process synchronization is first.

Process Synchronization (???)

Process synchronization means many processes share some system resources in a way that concurrent accesses to those resources cause little to no data inconsistency. But sometimes, some resources cannot be accessed at the same time or there will be some inconsistency.

For example, you and your friend want to use a printer to print your hundreds of pages report. Now, imagine you and your friends both hit print at the same time and one of you guys' reports is gone because the printer only picked up one! Ok, I know these days printers are smart, but that's because it has amazing process synchronization, but you get the picture. The printer is the shared resource and you guys are processes that want to use the resources.

Busy Waiting

That is where many algorithms and techniques come in to solve the problem where everyone wants to enter the critical region; a.k.a. an area where no more than one process should be in, so there's no error (like using shared resources).

One of those algorithms is Mutual Exclusion. The name sounds complicated, but the concept is simple; 1 process working IN the critical region, the others keep waiting. Yes, it is that simple; I'll be using this printer, you wait.

That's fine and all, but how do the other processes KNOW when they can take their turn? Well, they just keep checking to see if the process working inside the critical region is done. They've got to keep checking, and checking, and checking, and checking...... This makes them SO busy, they can do NOTHING ELSE!

And that, sire, is what we call Busy Waiting.

No one:
Literally no one:
Me: But.. ugh.. It sounds too easy
Also me: hold your Operation System

According to Wikipedia,

busy waiting is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available.

Oh, but we are far from done. *smirk* If only life WAS the-above-paragraph easy. The thing is, there are a variety of busy waiting's versions. They range from plain stupid to 'ok, fine'. In this post, I'm gonna introduce 5 of them!
_{*SPOILER ALERT* You're not gonna use any of these in your OS.}

Before we go over them, remember that all these algorithms are here to make process synchronization works when there is a critical region. So, their main goal is to make sure mutual exclusion happens.

1) Disabling Interrupt

The first one is the plain stupid one I talked about. You see, the genius behind this might actually be thinking something like...

Which is TRUE, but that kills the whole point of PROCESS SYNCHRONIZATION! What this algorithm does is not allowing other processes to get in at all, they can just wait indefinitely until who knows when. The process inside will keep working until it's done which, of course, we don't know when! Thus, this is not the ideal algorithm.

2) Lock Variable

This one seems better because instead of not making a door, now we have a door and a lock; to be more precise, a single shared lock. When the process wants to enter the critical region, it checks whether the door is locked (test lock) where the lock is initially set as 0. If the lock = 0, then the door is not locked, the process can enter the critical region and lock the door (set it to 1). However, if the lock = 1, the door is locked, so the process has to wait until it turns into 0.

Now, this might sound promising because we have a door and a lock to prevent other processes from entering at the same time, BUT we just create another problem. The processes not only have to compete to enter the critical region (get in the room), but it has to compete for the lock! This is called race condition or a condition where 2 or more processes (in this case) have to compete for a resource which cannot be used simultaneously (I know, I introduced many weird vocabs, but bear with me. TvT).

Also, what if the process inside finishes, but doesn't give up the lock and continues using it? Well, the other processes have to keep busy waiting. What's worse is 2 processes can be inside AT THE SAME TIME, but HOW? When the first process checks and sees that the lock = 0, it will change the lock to 1, right? But before it could change to 1, process 2 comes in and check the lock, too, and finds that the lock is 0 (even though it's about to be changed into 1!). Now, both of them accidentally posses the key to enter the room and accidentally enter at the same time. AND with those, this idea is also a no.

3) TSL

The next one here is called Test and Set Lock. This one is like Lock Variable, but it is a bit better because this algorithm requires a little help from the hardware. It solves the problem where one process can read the lock's value before the first process changes the value and thus 2 processes get inside the critical region at the same time. But TSL allows one process to read and change the value of the lock in an atomic way; meaning unless it finishes reading and writing the lock, no other processes can interfere. However, it still doesn't solve a problem where only one process keeps hogging the lock to itself.

4) Strict Alternation

Ok, fine, let's get a little smarter. If they have to compete for the lock, then we will specify whose lock this is, so only the owner of the lock can unlock the door and doesn't have to compete for it. This algorithm works with only 2 processes though. But now, no one is competing and no more than specified (which is one by the way) process can stay inside. This sounds better, right? Well, yeah, it is better; a bit better.

But imagine this scenario; process A just finished using the critical region, thus process A gave the key to process B. HOWEVER, process B doesn't want to use the critical region, yet, so it doesn't use the key and the key remain its. Meanwhile, process A now wants to use the key, but it's with process B and unless B uses the key, no other processes can use it. Thus, this algorithm is also problematic and so this doesn't quite work.

5) Peterson's Solution

We're getting more sophisticated with this algorithm. We have more variables which are turn and flag. This algorithm also works with only 2 processes.

The way it works is first, let's say process A wants to use the critical region, so it sets its own flag to 1 which means process A is interested in entering the critical region, and it changes the turn to its turn (process A's turn). Then process B, which comes a little later, wants to enter the critical region, so it does the same thing; set its flag to 1 and changes the turn to its own. Since process B comes later and changes the turn after process A, the turn, instead of being process A's, it becomes process B's.

The algorithm will first check if both process A's and B's flags are 1 to see if they're both interested. Then, it will check whose turn it is. If they're both interested and the turn is process B's, then process A can enter the critical region first. This is because it knows that whoever comes later can overwrite the turn as its own, and whoever comes first will get its turn overwritten. Then process B which comes later can enter after process A is done. However, if only one process's flag is 1, then that process can just enter the critical region.

This one is great because every process will have a chance to get inside and no more than 1 process can stay inside simultaneously. Everything seems perfect and all, but is this all?

The sad truth

The thing is, no matter how perfect these algorithms are, they still create some busy waiting processes. Some processes aside from the one inside the critical region will have to wait and check and wait and check until they can enter. This wastes CPU resources because instead of actually working on other important tasks, it just waits and checks indefinitely.

So, what can we do? What we can is we have to think of other algorithms that don't require busy waiting (hint: sleep and wake algorithm). But we are not covering that in this post 😬😬, so see you in the next one! (maybe 😅)