Algorithm Grading Quiz Solution – Georgia Tech – Advanced Operating Systems

Algorithm Grading Quiz Solution – Georgia Tech – Advanced Operating Systems


So I’m going to give you the solution for this particular question by filling out this table. And as I said, take your time thinking about it. And, and verifying your own intuition against what I’m presenting to you here. Now what you’ll find is that MCS Link-based queue lock and Anderson’s array-based queue lock are the two things, two algorithms that done, do quite well on most of the different categories of attributes that I have mentioned to you. But I should tell you that if you, if you have fancy instructions. Fancy read, modify, write instructions. Then Anderson’s and MCS lock give you the best performance on all these attributes. But on the other hand, if the architecture does not support fancy read modified op operations and it only has testing set operation available, then some sort of a, a delay base, is a, in a exponential delay base or. Starting delay based, spin lock algorithm, may turn out to be the best performer. And in fact, when the amount of contention for lock is, is, fairly low, it’s best to use a spin lock with exponential delay, start out a small delay and keep increasing it. On the other hand, if it is a highly contended lock Then it is good to use a Spin Lock that has categorically assigned various spots for every processor. And one of the things that I also want you to notice is that the number of re modify right operations that, you need to do for the different lock algorithms really depends on the amount of contention that is there for the lock in the case of spin algorithms. In the case of Anderson’s and MCS the number of Atomic operation is always one, regardless of how much contention there is. And of course, in MCS, this is the quanta keys that you have to worry about during, during unlocking that might result in an extra remodified item operation. But in the case of the Spin algorithms the amount of contention is really dependent on the number of re modified item operations that you have to perform per critical section. Really depends on the, mode of, mode of contention that is there for the lock.