2
$\begingroup$

Our professor gave us the following algorithm that's supposed to solve the critical section problem. I'm guessing the code is just pseudocode so I'm not trying to focus on the strange syntax and just trying to understand what it does.

 Main
  begin
   process_number=1;
   parbegin
    process1;
    process2;
   parend;
  end

Process1;
  begin
   while process_number=2 do;
   critical_section1;
   process_number=2;
   other_stuff;
  end;

Process2;
 begin
  while process_number=1 do;
  critical_section2;
  process_number=1;
  other_stuff;
 end;

After the code he says the following:

"Algorithm Guarantees mutual exclusion.

Price is high: P1 must go first, so if P2 is ready to enter its critical section, it must wait.

When P1 enters and leaves its CS, P2 must go next even P1 is ready, and P2 is not ready.

If one of the processes is terminated, then eventually the other will not be able to proceed"

I don't even know what's going on. My best guess is that since process 1 and process 2 are running concurrently, and the variable process_number is originally equal to 1, Process 1 is going to stop at the condition (while process_number = 2). But for process 2 the condition (while process_number = 1) is true, so...it will do whatever lines of code follow it. But the lines of code that follow it are (critical_section2;) and why in the world would it be running critical_section2 if it the variable process_number = 1 is true. I..honestly have no idea what my professor was trying to get across in this confusing code.

$\endgroup$
  • 1
    $\begingroup$ "I don't even know what's going on." -- that a bit weak of a premise for a question. Try a few pen-and-paper executions of the program, using a die for deciding which process gets to execute a step next. $\endgroup$ – Raphael Nov 21 '15 at 11:01
1
$\begingroup$

Note that the while bodies are empty, i.e., if the condition is false, they just fall through to the next line.

Horrible, horrible code; extremely restrictive (taking turns!), and very inefficient (busy waiting), if you ask me.

$\endgroup$
  • $\begingroup$ wouldn't they just "fall through to the next line" if it were true as well? then what is the purpose of the while condition? @vonbrand $\endgroup$ – FrostyStraw Nov 21 '15 at 1:37
  • $\begingroup$ when the value of process_number is changed, does that mean that at the point the process running is going to be the one that process_number just got assigned? so when the line (process_number=2) occurs after (critical_section1) is done executing, it means that it will jump to process 2? @vonbrand $\endgroup$ – FrostyStraw Nov 21 '15 at 1:40
  • $\begingroup$ wait, sorry. I think maybe I understand it? Since they are running concurrently, once process 1 finishes its critical section, it will continue running "other_stuff" while at the same time process 2 will begin running its critical section. The while condition is just a way of making it wait if it's not a processes turn to run? @vonbrand $\endgroup$ – FrostyStraw Nov 21 '15 at 1:55
  • $\begingroup$ FWIW, I have found busy waiting to outperform any kind of lock or wait/notify mechanism in some practical examples. $\endgroup$ – Raphael Nov 21 '15 at 11:01
1
$\begingroup$

Assumptions

Consider a Petri Net model of the algorithm, based on the pseudo code (“Help”, 2015) and the following assumptions:

  1. Main executes first.
  2. process1; in Main is actually a call to schedule the execution of Process1.
  3. process2; in Main is actually a call to schedule the execution of Process2.
  4. When Main ends, it “waits” and Process1 and Process2 continue to their end. “End” does not mean Main, Process1 or Process2 stops executing. After Process1 or Process2 reaches its end, it is rescheduled to start again.
  5. The actual start and restart times for Process1 or Process2 are stochastic. The lengths of time for Process1 and Process2 to complete their tasks are also stochastic.
  6. Each of Process1 and Process2 runs on its own thread. Both threads run on a single processor. The processor can run one (and only one) thread at a time.

Net Model and Pseudo Code

Petri Net Model of Main: Petri Net Model of Main

Petri Net Model of Process1: Petri Net Model of Process1

Petri Net Model of Process1: enter image description here

Petri Net Model of Algorithm: enter image description here

Petri Net Model of Algorithm with (Abnormal) Termination enter image description here

Notes

In the “Petri Net Model of the Algorithm with (Abnormal) Termination”, each process can terminate before it begins or after it ends, while it is performing its critical section, or while it is doing other stuff.

For the PDF version of this reply, The “Petri Net Model of the Algorithm” and the “Petri Net Model of the Algorithm with Termination” are interactive, dynamic diagrams. Stepping through the algorithm using an interactive, dynamic diagram may help in understanding some properties of the algorithm.

The Petri Net model of the algorithm for Process1 and Process 2 is similar to Figure 14 on page 163 of Petri’s “General Net Theory” (1977); an interactive, dynamic version of the figure is also available.

References

Petri, C. A. (1977). General Net Theory. Computing System Design: Proc. of the Joint IBM University of Newcastle upon Tyne Seminar, Sep., 1976 / Shaw, B. (ed.) --- University of Newcastle upon Tyne, 1977, p. 131-169. Retrieved on Mar. 15, 2013 from http://www.informatik.uni-hamburg.de/TGI/mitarbeiter/profs/petri/doc/GeneralNetTheory.pdf.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.