we dont need atomicity for MAX() in the original bakery algorithm. if two processes are assigned the same numbers, ties are broken in favor of the process with smaller process id. Check the last part of video its explained.
Hi, thanks for the great videos! But I'm confused about the while loop around the time 8:00 in the video, if num[p] != 0 and num[p] < num[i] is true, how would it be possible to "break" the loop and enter the critical section?
Sorry I was actually referring to 6m:50s in the vidoe, quote: "process with the lowest non-zero value of num would enter into the critical section". Can anyone teach me how does this work? Thanks!
Xiaoyan Qu Each waiting process i would be stuck in the while loop apart from the one which has the lowest non zero value because it checks itself against all other processes in for loop and break every time. For non waiting process num[p] is zero and for rest waiting process it has the lowest token number so num[other_process] < num[ this process] is false everytime. Hence it goes into critical section. Hope that explains.
For future reference: The basic idea is to implement a FIFO like structure i.e processes with smaller tokens get a higher priority. The while loop in the simplified algorithms does the follows: it checks if there exists a value which is not zero and which is less than the current value it has. For example, if P1 has a value of 1. Now it checks through the entire loop to find that there are no such values which is non zero and less than 1. Thus, it can safely go into the critical section. Now assume that while it is executing, it gets pre-empted and P2 now executes. P2 will have a value of 2 and it will scan through the entire queue. While scanning, it will find that P1 already has a value of 1 (i.e non zero and less than 2 of P2). Therefore, the condition is met and it loops. When P1 finishes executing, the value of P1 becomes 0 and now, P2 is free to execute as there is no value smaller than 2 present in the loop.
it is an NPTEL video so you can find this course NPTEL website. This course url is nptel.ac.in/courses/106/106/106106144/ . You can find many other courses on operating system there
WHAT IS THE USE OF CHOOSING ARRAY. THE SAME RESULTS CAN BE OBTAINED WITHOUT USING IT WITH THE HELP OF COMPLEX CHECK..ie AT THE LAST LINE ...........(PROCESS HAVING LEAST I VALUE)
How can we decide which is least when there are processes still choosing the token value? Choosing array stops that from happening. eg: p1 p2 p3 p4 p5 6 7 choosing 5 4 At this point p5 should enter C.R as it has smallest token...but how do you know p5 has smallest of all when p3 is still getting the token. it might happen p3 got token 3 and got preempted before setting num[3]. So while(choosing) loop stops p5 going before p3.
It would have been better if we would have prevented another process from choosing if one process is already choosing. We wouldn't have to do any other changes.
At around 15:18, if any process dies after setting choosing[i] = True, it will block all other processes from entering the critical section, isn't this a problem?
Say if process A ( index 3 ), runs the MAX function and adds 1 ( say 2 ), but gets context switched at that point... in this case, the value for process A is still 0, eventhough it has computed its ticket.. Now process B ( index 5 ), comes in.. calculates the max function and gets a value equal to or greater than process A ( say 2 ) without the choosing check, the process B can now go into the critical section, since process A's ticket is still not set to its value of 2. But unfortunately B is again context switched when it is inside the critical section. and A now gets the CPU. Now A finally gets assigned its ticket of 2, it runs through the loop and finds that only B has a token of 2, but B's index (5) is still higher than A's ( 3 ), so A also now enters the critical section. Which breaks mutual exclusion. Now with the choosing check, if the same situation happens.. B would get stuck at the choosing loop, because A has not turned it off. So until A gets assigned the ticket with index 2, B cant proceed to the next loop where it gets entry into the critical section.
Very clear and exhastive coverage of bug 1 and bug 2, especially with obstacles
Can't find a better OS video lecture on you tube than this.Long live sir.Thanks
great video, very clear and explained well, thank you ! it helped me alot!
thats the first time i understand an indian on youtube and i love it. thanks, really helped me.
Well he is a prof from IIT Madras one of the top and pristine institute in India so this was obvious .
yes I find that he has a clear accent too
really great work..best way of explaining algorithm...!Thank You Sir
That was amazing, thanks for such a easy explanation
Fantastic Explanation
Great lecture! Thank u Prof. Rebeiro!
It looks like Bakery algorithm should work for n ≥ 2, but there are simpler ways for mutual exclusion for n = 2, hence the video mentions n > 2.
crystal clear :) thank you sir
how to ensure atomicity of that MAX(..) operation ? how to ensure there will be no context switch ? please anyone explain
we dont need atomicity for MAX() in the original bakery algorithm. if two processes are assigned the same numbers, ties are broken in favor of the process with smaller process id. Check the last part of video its explained.
very nice and simple explanation. thank you very much!!
Thank you sir :) You made it simple .
Hi, thanks for the great videos! But I'm confused about the while loop around the time 8:00 in the video, if num[p] != 0 and num[p] < num[i] is true, how would it be possible to "break" the loop and enter the critical section?
Sorry I was actually referring to 6m:50s in the vidoe, quote: "process with the lowest non-zero value of num would enter into the critical section". Can anyone teach me how does this work? Thanks!
Its wrong , wrong explanation of that while loop
it means if num[i]≥num[p] then only it can break the loop and execute critical section.
Xiaoyan Qu Each waiting process i would be stuck in the while loop apart from the one which has the lowest non zero value because it checks itself against all other processes in for loop and break every time. For non waiting process num[p] is zero and for rest waiting process it has the lowest token number so num[other_process] < num[ this process] is false everytime. Hence it goes into critical section.
Hope that explains.
For future reference:
The basic idea is to implement a FIFO like structure i.e processes with smaller tokens get a higher priority.
The while loop in the simplified algorithms does the follows: it checks if there exists a value which is not zero and which is less than the current value it has. For example, if P1 has a value of 1. Now it checks through the entire loop to find that there are no such values which is non zero and less than 1. Thus, it can safely go into the critical section.
Now assume that while it is executing, it gets pre-empted and P2 now executes. P2 will have a value of 2 and it will scan through the entire queue. While scanning, it will find that P1 already has a value of 1 (i.e non zero and less than 2 of P2). Therefore, the condition is met and it loops. When P1 finishes executing, the value of P1 becomes 0 and now, P2 is free to execute as there is no value smaller than 2 present in the loop.
I finally got it!! Do you know guys whether this teacher has a concurrency course or where I can find the entire course for this video?
it is an NPTEL video so you can find this course NPTEL website. This course url is nptel.ac.in/courses/106/106/106106144/ . You can find many other courses on operating system there
Excellent video. Thank you very much!
Excellent video! Thanks.
WHAT IS THE USE OF CHOOSING ARRAY. THE SAME RESULTS CAN BE OBTAINED WITHOUT USING IT WITH THE HELP OF COMPLEX CHECK..ie AT THE LAST LINE ...........(PROCESS HAVING LEAST I VALUE)
How can we decide which is least when there are processes still choosing the token value? Choosing array stops that from happening.
eg: p1 p2 p3 p4 p5
6 7 choosing 5 4
At this point p5 should enter C.R as it has smallest token...but how do you know p5 has smallest of all when p3 is still getting the token.
it might happen p3 got token 3 and got preempted before setting num[3].
So while(choosing) loop stops p5 going before p3.
It would have been better if we would have prevented another process from choosing if one process is already choosing. We wouldn't have to do any other changes.
why is p1 always 0. Wont it invoke the lock process?
How do we know that the num[i]=Max(... code line is atomic or non atomic even it's not mentioned in the question having this code
I think, choosing variable should be set to false in unlock function(original bakery algo)
At around 15:18, if any process dies after setting choosing[i] = True, it will block all other processes from entering the critical section, isn't this a problem?
How is it that all processes have access to num ...don't that defeat the purpose of distributed algorithm?
when we are doing tuple comparison then whats the need for choosing array???
Say if process A ( index 3 ), runs the MAX function and adds 1 ( say 2 ), but gets context switched at that point... in this case, the value for process A is still 0, eventhough it has computed its ticket..
Now process B ( index 5 ), comes in.. calculates the max function and gets a value equal to or greater than process A ( say 2 )
without the choosing check, the process B can now go into the critical section, since process A's ticket is still not set to its value of 2.
But unfortunately B is again context switched when it is inside the critical section. and A now gets the CPU. Now A finally gets assigned its ticket of 2, it runs through the loop and finds that only B has a token of 2, but B's index (5) is still higher than A's ( 3 ), so A also now enters the critical section. Which breaks mutual exclusion.
Now with the choosing check, if the same situation happens.. B would get stuck at the choosing loop, because A has not turned it off. So until A gets assigned the ticket with index 2, B cant proceed to the next loop where it gets entry into the critical section.
Thank you sir!
Thankyou
Thanks!
why is P1 0?
yeaaaaaaaah why o--O?????
p1 doesn't enter the critical section. p2 also can be set to 0 if you like. 0 just mean the process doesn't participate in the competition
All the processes which don't wanna access their critical sections receive 0 as their values in this algorithm :)
becoz p1 does not want to execute critical section. So it does not need to execute the entry section.
thanx a lot
Since numbering in a C like array starts from 0 why the processes are numbered from 1 to 5 in your example? Should be P0, ...P4
Sometimes I can't understand what you say :/
Platwn Ace essentially everything lol
sir, please explain base on the code, not the idea of the algorithm!!!
Why are these videos always made by indians?
because these videos come under a free course provided by government of India. Guys who are giving lectures are from IITs.
because india is world's teacher in every field .
@@vineetrathee2070 Yes, India can't educate it's own people on birth control, but alright.