Critical Section Problem

Am I getting this right? (p 230)

The code given for Peterson's solution, Entry section, ends on the Busy Waiting condition?

In other words I think now that

Language: C++
while (flag[j] && turn == j);

is the busy waiting loop, itself. If you have that conjunction of conditions, you're going to spin there forever if need be.

At first I got really stuck trying to work out how one was meant to go in to the critical section from this! I thought it was meant to be the condition for the end of one's wait. The only thing I can say to my credit there was that at least I realized it didn't make sense!

Right. So as a way IN to the critical section (flag[j] && turn == j) is never going to work.
And what I'm hoping for confirmation of is that that one line "while" is the entire spinlock.

Comments?

Anyone else think that this is the difficult part of the course?

============= Edit ===========

Another way of reading the while is

while( ...&& ...)
NOP; // in Assemblysprache.

A sequence of events:

...
flag(i] = 1 ... (the flags can init in any order)
flag[j] = 1 ... (now P_j has arrived and also said it's ready)
turn = i ... (P_j finishes its entry section. It's first)
turn = j ... (P_i now catches up)
... So turn has been overwritten with a j.

We have flag[j]=1 && turn = j. So then P_i starts to spin NOP, NOP, NOP ...
Meanwhile P_j is OK. It would only spin on flag(i]=1 && turn = i.

P_j goes on into its critical section, and P_i is locked out.

So far we have mutual exclusion, then.

Now P_j finishes its critical section. The exit is flag[j] = 0. So it unlocks the section. Next time P_i gets to that NOP loop, the spell will be broken, and it'll be able to go critical.

It was the "critical" process that released the lock. I think that is somehow significant ...

... but unfortunately I seem to have gone into a spinlock state myself at this point in time.

>Anyone else think that this is the difficult part of the course?
Its making my head spin!

Your explanation is much better than the book's.
Thanks slow_eddy

Thanks Ben. So you're saying at least the both of us are mistaken on this point?

(No, no, no, just joking. I'll take that as confirmation that at least that part is now unravelled).

Unfortunately the joy of solving the Peterson riddle is short lived. Shortly thereafter, we have monitors ... which marks I'm afraid will at this point have to be sacrificed if they come up in the paper.

Weird. I thought I had this all sewn up a while ago, and now I return with a more critical eye I see I got everything backwards.

Is there a simpler explanation of monitors?

Looks like Wikipedia is a good place to go for monitors (search on monitor synchronization, otherwise you'll have the nightmare of returning to virtual school).

It's a class. I got that. But didn't stop a little to think of the implications: Class has methods.

A monitor class has "exclusive methods". If anyone has one of the methods in hand, it has that method exclusively.

So provisionally it looks like a monitor is "the next logical step up" from a semaphore.

And I'll leave that impression there, and carry on...

@Eddy & Ben - the most difficult part of the course? The whole course! This is definitely not the easiest textbook ever.

Enough complaining. What questions do you guys think they will ask? Any thoughts on the types of theory questions we could get?

I'm quite sure they'll ask the Banker's algorithm and a scheduling algorithm, with regard to the practical ones (maybe evern page replacement), but I'm finding the theory difficult to structure logically in my already-saturated brain.....

For theory I worked backwards on the assumption that I'd already done a good job on the first few chapters. As I said, I'm starting to realise I got a lot of it back to front.

Wikipedia looks quite good on monitors, but I may have to let that go a bit now.

The exam tut letter (on myUnisa if they didn't post you one) does give some idea of the layout. If you know your calcs well you can survive on them alone. That basically means making sure you understand the solutions to whatever you didn't get in the assignments, I suppose.

In principle the practical isn't that difficult. It's just a matter of doing enough so that you can do it Quickly enough (and yet accurately enough) in the 2 hours.

I think in the final run-up the trick would be abandon what remains of theory to the wolves and just hammer those practicals.

As for how to do theory? I work on the "Do One Thing" principle. Instead of taking on the whole course (which can get overwhelming), I set out to know one thing properly. If I manage that I iterate. If I'm too stuck I bail out if time's an issue. I don't bail out mid-semester, though - beating your head against a brick wall is good for you.

>I think in the final run-up the trick would be abandon what remains of theory to the wolves and just hammer those practicals.
I concur there is just so much theory.

I have been studying the 83 pg summary of the TB found on:
Wiki Student
to get into the mode of things, and then I'll concentrate on the practical bits.

If I can make my way through to the end of my somewhat defective run through Ch6 and to the end of Deadlocks by the end of the night, good and well. If not, it waits indefinitely in a locked thread, and prac gets an exclusive lock on the meatspace processor.

My mnemonic for deadlocks is to grab my left forearm with my right hand. That's a "hold and wait".

My left hand now asks please can't it also hold my left forearm. "No. This is mutually exclusive".

So I have to grab my right forearm with my left hand. That's a circle for a "circular" wait.

Now my right hand tells my left hand to let go. No luck. There's No Premption.

It's a work in progress, as you can guess, this mnemonic.

@slow_eddy:
You're weird and funny at the same time.
Not mutually exclusive: LOL

Long as it helps with remembering the properties of the deadlock (it being too late for silly things like first principles).

Good news is that section 6.9 is essentially a recap of what you did in INF303 if you've done that. You treat the OS as a kind of "database" to manage concurrency.

I think I'll still wet the exam paper with my tears if asked such a question after a few messed up calcs, though... (Edit)

When one feels weak kneed a good cure is to pick the right broadcast from this selection:

http://www.archive.org/details/Winston_Churchill

No problem did INF303 last semester.