CS343 Midterm Study

Fall 2023 Peter Buhr

• a)Rewrite the following code fragment to remove the exit from the middle of the loop.

for(;;) {
	S1;
	if(C){
		E
	} else {
		S2;
	}
}

bool flag = false;
while ( !flag ) {
    S1; // S1 can change C
    if ( C ) flag = true;
    else S2; // S2 can change C
}
if ( flag ) E;

Explanation:

• Flag Initialization: flag is initialized to false before entering the loop.

• Loop Condition: The while loop continues as long as flag remains false.

• Condition Check Within the Loop:

  • After executing S1, the code checks if the condition C is true.
  • If C is true, it sets flag to true, which will cause the loop to exit after the current iteration.
  • If C is false, S2 is executed, which may change C for the next iteration.

• Post-Loop Action: Once the loop exits, there is an additional check for if ( flag ) E; outside the loop, which executes E if flag was set to true inside the loop.

• b)Explain why a loop exit never needs an else clause.

  • Since if the condition triggers a break statement, the loop will immediately exit. Which makes the else clause unnecessary. The else block is redundant since the code following the if statement will only execute if the if condition is false.

• c)Why are flag variables the variable equivalent to a goto?

  • Flag variables tells you where to go, just like a goto statement.
  • Because flag variables can be set/reset/tested at arbitrary locations in a program.

• d) Why is it good practice to always label exits (break statements)?

  • avoid confusion
  • New nested control structures can be added without having to change existing code.

• e) Normal and labelled break are a goto with what two limitations?

  • break can only have forward branching $\to$ cannot loop! $\to$ only loop constructs branch back.
  • break cannot branch into a control structure.

• f) Explain the only situation where a goto is necessary.

  • to perform static-level exit when labelled break and continue are unavailable

• g) Explain the purpose of uArray and how it differs from unique_ptr.

  • uArray allocates dynamic size array space on the stack without running a default constructor!
  • Since the default constructor doesn’t run, you get uninitialized memory, which you then initialize later by running a specific constructor with arguments on each array element.
  • unique_ptr allocates the array in the heap

• h) 2. What issue is removed by the $O(N$) matching search during propagation versus: i. return codes exiting multiple call-levels. ii. fixup routines passed into a call.

• i) What is the problem with a destructor raising an exception? Is there a way around this problem?

  • Destructors are called during exception propagation, and C++ does not allow another exception to be raised during propagation.
  • A destruction can conditionally raise an exception only if it is not invoked during propagation (uncaught_exceptions ).

Locks

• This is when two people opens the door and enter into the bathroom at the same time.
• The entry protocol must check if the critical section is being used and wait if it is. If it is being used, there is a busy loop that spins around constantly checking the status of the lock
• busy waiting should be avoided: using too much CPU
• Break rule 1: Two threads both execute the test in the entry protocol at the same time. They both see the lock is open, they both close the lock, and they both enter the critical section!

Alternation:

• The shared variable Last, declared in uMain::main indicates which thread was last in the bathroom; this corresponds to the chalk board on the outside of the bathroom door.
• Fix rule 1: achieve mutual exclusion
• Breaks rule 3: if a thread is not in the critical section or the entry protocol or exit protocol, it may not prevent other threads from entering the critical section.
  • If one person finishes in the bathroom and goes to work, the other person can enter the bathroom at most once before the other person comes home! So when the person at home leaves the bathroom, they become the last person to use the bathroom and have to wait until the person at work comes home and uses the bathroom.
• A thread must be able to go into critical section multiple times in succession if the other thread does not want to go in!

Declare intent:

• To solve rule 3, need to know if a person is interested in entering the bathroom.
• Requires two chalk boards on the outside of the bathroom.
• The shared variables me and you, declared in uMain::main, correspond to the two chalk boards on the outside of the bathroom door; both initialized to not intending to enter the critical section.
• The entry protocol marks the intent to enter, i.e., that thread’s me, and starts a busy loop waiting until the other thread retracts intent, which means it has exited the critical section.
• The exit protocol retracts intent by changing that thread’s me.
• Breaks rule 4: because in selecting a thread for entry to a CS, the selection can be postponed indefinitely. Failure scenario occurs when threads arrive simultaneously.
  • both threads indicate intent to enter at the same time, both notice the other thread wants in, and both wait for the other thread to retract intent on exit from the critical section.
  • both threads are spinning in the empty busy loop, mistakenly thinking the critical section is occupied. LIVELOCK

Retract Intent:

• We can solve livelock by letting one back down so the other can make progress.
• The thread that backs down then waits until the other thread exits the bathroom and retracts its intents. At that point, the thread that backed down starts the entire entry protocol again.
• But it is impossible to tell if a thread is in the entry protocol or critical section when its intent is set, so simultaneous arrival must be assumed.
• The only change from the last program is the entry protocol.
• The entry protocol marks the intent to enter and then checks the other thread’s intent. If the other thread’s intent is set, intent is retracted and a busy loop is started waiting until the other thread retracts intent.
• When the other thread retracts its intent, which means it has exited the critical section, the entry protocol is started again.
• If one thread does not declare intent, the other thread is free to enter CS multiple times in a row.
• Breaks rule 4: with low probability.
  • Problem occurs when threads arrive simultaneously.
  • The two threads both indicate intent to enter at the same time. They both notice the other thread wants in, and so both retract intent. They both exit the busy loop immediately because neither thread has indicated intent and so both start the protocol over again.

Prioritized Retract Intent:

• One possible approach is to assign different priorities to the people as a tie-breaking mechanism.
• When simultaneous arrival occurs, the high-priority person always goes ahead of the low-priority person.
• The entry protocol is now divided into two parts by the if statement: code for the high-priority thread and code for the low-priority thread.
• The code for the high-priority thread is the declare-intent algorithm.
• the code for the low-priority thread is the retract-intent algorithm.
• Basically, the high-priority thread never retracts intent; if it detects the other thread has indicated its intent, it just spins with its intent set until the other thread retracts intent, either in the entry protocol or by exiting the critical section.
  • The low-priority thread always retracts intent in the entry protocol, if it detects the high-priority thread wants into or is already in the critical section.
• Breaks rule 5: No guarantee of eventual entry into the CS after a thread has made a request to enter it.
  • In theory, the high-priority thread can always barge ahead of the low-priority thread by racing out of the critical section and back into it, so the low-priority thread starves

Dekker (modified retract intent):

• The program is a modification of combination of the alternation program (Fig. 6.6) but with variable rather than fixed priority assignment. The shared variable Last indicates which thread was last in the bathroom by alternately pointing at the two intent variables in uMain::main; this corresponds to the new chalk board on the outside of the bathroom door.

• The low-priority loop is nested in the high-priority loop because of the two steps in the exit protocol: setting Last and retracting intent.
• In Decker’s Algorithm, the low-priority thread retracts intent, so when the high-priority thread exits the critical section and attempts reentry, it does not exclude itself.
• Now it can take the low priority thread an arbitrary amount of time to restart, exit the low priority busy wait, and set its intent. During this delay, the new low- priority thread (because it was last to enter) can perform an arbitrary number of entries into the critical section.
  • $\to$ Unbounded overtaking is allowed by the new low-priority thread.

Peterson:

• After a person indicates intent on their own chalk board, they race with the other person to put their name on the third chalk board. The person who wins the race breaks the tie and goes into the critical section, which handles livelock problems (rule 4).
• Fairness (rule 5) is provided by ensuring a person cannot win two races in a row.
• If both threads arrive simultaneously, they both indicate their intent to enter and they both race to put the address of their me variable in Last.
• Starvation cannot occur for the following reason (which also applies to read race). If a thread exits the critical section, and tries to barge ahead of a waiting thread, it must first indicate its intent and run a race with itself in the entry protocol (the other thread is still in the busy loop).
  • In this case, the thread that runs the race by itself loses the race and waits in the busy loop.
• In Peterson’s algorithms, the race loser does not retract intent, so if the thread in the critical section attempts reentry, it immediately excludes itself from reentering.

Questions?

• Why not use while to simulate for?

• Thread graph for:??????

• Why is there a suspend() after _Resume Stop() at *c

• fully understand exception lis and exception parameter