# Computer Science - Spinlock Question

Hay there CS folks, I’m just curious if anyone else can give me some feedback on a sample problem from the comprehensive exams that I’m going to be taking on Friday for my Masters degree. I’m trying to solve this problem, #1 at this link:

http://www.sci.csueastbay.edu/mathcs/comps/csexams/sample.html#SYSTEMS

Suppose there are N worker processes (0…N-1), each with a critical section where work is done. There is also a special process which executes the following code:

`````` int p    = -1;    // GLOBAL variable shared by all processes, initialized once
int lock = 0;     // GLOBAL variable shared by all processes, initialized once

while (1) {
while (lock == 1) {}   // empty loop body
p = (p+1) % N;
}
``````

Each worker process has its own process ID mypid, and executes the following code:

`````` while (1) {
while (p != mypid) {}   // empty loop body
lock = 1;
// CRITICAL SECTION WHERE THE PROCESS DOES WORK
lock = 0;
}
``````

a) Does the solution guarantee mutual exclusion?

b) Does the solution guarantee that work will be done?

c) Does the solution guarantee fairness?

I’m thinking that for a system that doesn’t preempt or interrupt it looks like it should be “Yes” for all three questions (mutually exclusive, guarantees work will be done, and will be fair). However, the question of whether preemption and interrupts should be considered is bothering me a bit.

Also, it looks like a modified version of Petersons Algorithm. This would suggest that I am correct about mutual exclusivity despite the lack of an atomic test-and-lock.

Anyone have comments? I think I’ll send an e-mail to my old OS design prof to see what he has to say…

nKoan noticed that if one thread tests and locks and then unlocks and exits, since it is not using a queued wait it could potentially test and lock again before the control threads increments the lock ID “p” and would re-enter the C.S. So this would mean that it isn’t a fair algorithm, and it doesn’t guarantee that other threads would get anything done.

Let me spend 1 minute thinking about it, and 10 minutes writing this post. (I suck at time management. Kitsune! Help!)

a) No. You have no guarantee that the 1st thread manages to set the lock back to 1 before the kernel loop increments p the second time. Then, multiple processes can set the lock to 1. This the what the test+set atomic operation is designed to fix. When the second process test+set lock to 1, expecting original to be 0, and finds out the original was 1, it knows it failed to get the lock, and should go back to wait.

b) No. There’s nothing here that shows if the processor threads will wake up often enough to notice that p==myPID, while the kernel thread is spinning in a tight loop incrementing p until someone gets the lock. For example, if the kernel thread manged to increment p 3 times before the lock got acquired, can you say for certain that it’s the last process that got the lock? The first one? Just can’t tell…

c) No way, if a) doesn’t work, you can’t attempt c).

I’ve never seen Peterson’s algorithm before. Now that I’ve spent another minute looking at it, I like it. The test question is missing the turn variable. And also, Peterson’s applies to 2 threads only…have to follow the external link on the page to find out the general case implementation.

Isn’t it a problem that the spinlock condition doesn’t additionally check the lock status? (If you wanted to make an N thread version of Petersons)

Why? p will never change unless lock is 0.

No, one worker thread can set the lock, do the critical section, unlock, and then run again instead of other threads for a subsequent thread loop. It would then test P and set lock to 1 between the busy-wait (while loop) and the following line of code that sets a new value to p in the control thread. There is no atomicity or queueing, nor is the algorithm safe on multiprocessor systems.

You are never guaranteed that something will not execute one or more lines of code between any section of another threads code.

I’ve found the easiest way to think about this stuff is to realize that yes, barring explicit work on your part, virtually nothing is an atomic operation.

The only thing atomic here is Jason’s post-count.

A) No.
B) No.
C) No.

If the system does not preempt, then why do you need a critical section and all that? Just write it like you would write a single threaded application.

Since that system is NOT written like a single threaded application, I would assume the system must preempt.

If the system does preempt, chaos will ensue using that algorithm. My reasons are that of KaoFloppy.

There aren’t any locks at all in that code. It’s just a bunch of variables, access to which will be mangled beyond all comprehension by compiler optimizations and (possibly) memory caching.

As DeepT says: Chaos will ensue.

I completely missed the “preempt” part of the question. But yeah, what DeepT says if it’s a non-preemptive system.

I’d just point out that usually the simple integer assignment statement and an integer comparison statement are considered to be atomic, along with that special test+set thingie. All other statements are compound and can be interrupted halfway.

Integer assignment is generally kinda-sorta atomic, except when it isn’t. That is, the actual act of assigning to an integer will almost certainly be atomic–but if the compiler decides to reorder instructions, or delay assignment, or some other such optimization, the exact timing of the assignment is entirely up for grabs.

Even more entertaining: If you write “while (lock == 1) {}”, as in the code above, the compiler may well never check the actual value of the ‘lock’ variable while executing that loop–it could transfer the contents of ‘lock’ into a register at the start of the loop and never check anything other than that register during execution. Or it could notice that the loop body doesn’t touch the variable and rewrite it into “if (lock != 0) { while (1); }”. You can get around this by declaring the variable to be volatile…but that’s really not a level you want to be getting into unless you really know what you’re doing and why.