Synchronization: Discussion about Mutex and Semaphore - Article 2
Let's do a double this week. I had mentioned about synchronization in computers but if I had discussed in previous article, it would be very big, hence I have split the previous article to discuss examples of synchronization in computers separately.
In the previous article, I discussed about synchronization giving real world examples here:
Synchronization article - 1
Let's see what synchronization is all about in the computers:
The processor executes instructions serially one by one if it's a uniprocessor system. But synchronization involves things executing in parallel. Let's dig deep.
1. In uniprocessor systems, the OS takes care of scheduling different processes (Not covered in detail here) and makes multi tasking and multi processing possible.
- The parallelism is pseudo and virtual to the humans because humans can't see and perceive the speed of processor's execution.
- Even though instructions are executed serially, it appears to the users that everything is happening parallely.
- Imagine how many programs you can run on your desktop? You could be listening to the music, editing your word document and have your mailbox open and many more.
2. In multiprocessor system, of course many processors will be executing instructions really parallely. So is synchronization really just needed in case 2? Of course if processes were independent like listening to music, word document and mailbox, even though they are executing parallely, question of synchronization does not arise.
Let's see a real world example:
Imagine you are travelling in a flight listening to music next to a beautiful girl who is also listening to music. Is it required for both of you to synchronize? No because both of you are independently listening to different music.
Imagine what would happen if left speaker is slower and right speaker is little ahead in playing the same music file.
But in computers, there is also a case of threads in a process (Not covered in detail here). Multi threading is used extensively in applications. Imagine in a mail program like outlook, Send/Receive is happening parallely and you are also able to read the mail. So, the OS takes care of scheduling different threads with in a process as well.
The order of execution of instructions within threads or within different processes (Multi processor) can't be determined and the programmer will not have any control on that.
Example 1:
Thread 1: Print values 0 to 4 in a loop
Thread 2: Print values 5 to 9 in a loop
In the above example, can we say for sure that the order will be 0 1 2 3 4 5 6 7 8 9 or 5 6 7 8 9 0 1 2 3 4? The output will be mixed. This is because the OS takes care of scheduling the threads.
Example 2:
The threads and processes can share data among them. Let's say there is a queue of 5 integers and 2 threads share them.
T1: Responsible to write to the Queue (Enqueue operation).
T2: Responsible only to read the element and process it (Dequeue operation).
Here the threads need to be synchronized. T2 can proceed only if there is a new element in the queue put by T1. Suppose just T1 is adding elements and Queue is full (Count reaches 5). Now, T1 can proceed only if T2 has processed at least 1 element.
Example 3:
Let's take a simple variable update by 2 threads:
T1: count = count + 1;
T2: count = count + 1;
It appears that count will have a proper update, but the machine instructions (executed by processor) will internally be:
T1.a temp = count;
T1.b count = temp + 1;
T2.a temp = count;
T2.b count = temp + 1;
In this example, if count is initially having a value 1 and the instructions are named as T1.a, T1.b, T2.a and T2.b and if both the threads want to increment it, the expected final value is 3. But if the OS schedules threads in such a way that the order is T1.a, T2.a, T2.b and T1.b, final value will be 2 itself. How? After T1.a, temp has 1. After T2.a, temp has 1. After T2.b, count has 2 (OK). But, finally after T1.b, the value of count is again 2 which was not expected. Here, the requirement is, either of the threads should finish both the instructions. Till then, the other thread has to wait. With this, we can ensure proper update. Such code is called critical section.
With these examples, we can conclude that synchronization is needed in computers and there are 2 constraints that need to be tackled:
1. Serialization - Event A must happen before Event B (Example 2)
2. Mutual exclusion - Event A and Event B must not happen at the same time (Example 3)
What about example 1? Does it fall under Serialization or mutual exclusion? It's serialization because there is no shared data. Suppose if we need output as 0 1 2 3 4 5 6 7 8 9, we need to ensure T1 executes first (Event A) and then signals T2 (Event B) to proceed. So, Event A happens before Event B.
What about example 2? Does only events coordination suffice? No, since the Queue is shared, enqueue and dequeue operations automatically qualify as critical section code.
With this, I will end this article. In the next article, I will discuss more problems and examples in computers and techniques to solve the problems.
Some homework for you: Think about examples in computers where synchronization is required and what problems can occur and how you can solve them.
Don't forget to leave your questions and comments.
In the previous article, I discussed about synchronization giving real world examples here:
Synchronization article - 1
Let's see what synchronization is all about in the computers:
The processor executes instructions serially one by one if it's a uniprocessor system. But synchronization involves things executing in parallel. Let's dig deep.
1. In uniprocessor systems, the OS takes care of scheduling different processes (Not covered in detail here) and makes multi tasking and multi processing possible.
- The parallelism is pseudo and virtual to the humans because humans can't see and perceive the speed of processor's execution.
- Even though instructions are executed serially, it appears to the users that everything is happening parallely.
- Imagine how many programs you can run on your desktop? You could be listening to the music, editing your word document and have your mailbox open and many more.
2. In multiprocessor system, of course many processors will be executing instructions really parallely. So is synchronization really just needed in case 2? Of course if processes were independent like listening to music, word document and mailbox, even though they are executing parallely, question of synchronization does not arise.
Let's see a real world example:
Imagine you are travelling in a flight listening to music next to a beautiful girl who is also listening to music. Is it required for both of you to synchronize? No because both of you are independently listening to different music.
Imagine what would happen if left speaker is slower and right speaker is little ahead in playing the same music file.
But in computers, there is also a case of threads in a process (Not covered in detail here). Multi threading is used extensively in applications. Imagine in a mail program like outlook, Send/Receive is happening parallely and you are also able to read the mail. So, the OS takes care of scheduling different threads with in a process as well.
The order of execution of instructions within threads or within different processes (Multi processor) can't be determined and the programmer will not have any control on that.
Example 1:
Thread 1: Print values 0 to 4 in a loop
Thread 2: Print values 5 to 9 in a loop
In the above example, can we say for sure that the order will be 0 1 2 3 4 5 6 7 8 9 or 5 6 7 8 9 0 1 2 3 4? The output will be mixed. This is because the OS takes care of scheduling the threads.
Example 2:
The threads and processes can share data among them. Let's say there is a queue of 5 integers and 2 threads share them.
T1: Responsible to write to the Queue (Enqueue operation).
T2: Responsible only to read the element and process it (Dequeue operation).
Here the threads need to be synchronized. T2 can proceed only if there is a new element in the queue put by T1. Suppose just T1 is adding elements and Queue is full (Count reaches 5). Now, T1 can proceed only if T2 has processed at least 1 element.
Example 3:
Let's take a simple variable update by 2 threads:
T1: count = count + 1;
T2: count = count + 1;
It appears that count will have a proper update, but the machine instructions (executed by processor) will internally be:
T1.a temp = count;
T1.b count = temp + 1;
T2.a temp = count;
T2.b count = temp + 1;
In this example, if count is initially having a value 1 and the instructions are named as T1.a, T1.b, T2.a and T2.b and if both the threads want to increment it, the expected final value is 3. But if the OS schedules threads in such a way that the order is T1.a, T2.a, T2.b and T1.b, final value will be 2 itself. How? After T1.a, temp has 1. After T2.a, temp has 1. After T2.b, count has 2 (OK). But, finally after T1.b, the value of count is again 2 which was not expected. Here, the requirement is, either of the threads should finish both the instructions. Till then, the other thread has to wait. With this, we can ensure proper update. Such code is called critical section.
With these examples, we can conclude that synchronization is needed in computers and there are 2 constraints that need to be tackled:
1. Serialization - Event A must happen before Event B (Example 2)
2. Mutual exclusion - Event A and Event B must not happen at the same time (Example 3)
What about example 1? Does it fall under Serialization or mutual exclusion? It's serialization because there is no shared data. Suppose if we need output as 0 1 2 3 4 5 6 7 8 9, we need to ensure T1 executes first (Event A) and then signals T2 (Event B) to proceed. So, Event A happens before Event B.
What about example 2? Does only events coordination suffice? No, since the Queue is shared, enqueue and dequeue operations automatically qualify as critical section code.
With this, I will end this article. In the next article, I will discuss more problems and examples in computers and techniques to solve the problems.
Some homework for you: Think about examples in computers where synchronization is required and what problems can occur and how you can solve them.
Don't forget to leave your questions and comments.
Comments
Post a Comment