CSCD467 midterm study guide

midterm_studyGuide.md

CSCD467 Parallel & Cloud Computing Midterm Study guide.

Author : shawnkoon. Web : github.com/shawnkoon

1. Concept of barrier and semaphore

• Barrier - Datastructure that allows threads to wait for each other to reach a same barrier point. CyclicBarrier - barrier that is re-used after the threads are released.

• Semaphore - Datastructure that maintains a set of permits and it ensures that only N threads can access a certain resource at a given time. Tip : Why getItem() method is not synchronized? A : because semaphore encapsulates the synchronization inside itself.

2. object.wait() method and busy wait

• Object.wait() - suspends the current thread which does NOT consume CPU resources while it is waiting. It releases all locks it has owned.

• busy wait - Usually a form of while loop that constantly checks to see if the conidtion is met, This consumes CPU resources while it is waiting.

3. what is a good practice when we are using busy wait together with mutual exclusion?

• Putting shared variables (includind condition variables) and other shared data into one or more separate classes. Because if not, it can get tricky and error-prone.

4. concepts of thread interference and race condition

• Thread interference - When interference between threads causes error result. Usually happens when two operations running in different threads gets executed on the same data.
• Race condition - When the result depend on the sequeneces or timing of other events.

5. Monitor in a parallel program, and its two major properties.

• Monitor (formal) - An Object intended to be used safely by more than one thread and thread-shared condition variables and data are put into a Monitor.
  Monitor (in_formal) - Like a traffic organizer.

• Two major properties :

  • Monitor Mutual Exclusion Property
    • (formal) - Access to shared variables and data are protected with mutual exclusion.
    • (in_formal) - Property defines how monitor class uses synchronized keyword.
  • Monitor Wait and Signla Property
    • (formal) - Provide a mechanism for threads to temporarily give up exclusive access, in order to wait for some condition to be met && provides a mechanism for signaling other threads that such conditions have been met.
    • (in_formal) - Property defines how monitor class has wait() calls and notify() or notifyAll() calls to wait or signal.

6. why should we always put a wait() method in a while loop? Rather than in an if statement?

• Due to Spurious Wakeup - Thread waking up without being notified, interruped, or timing out. Once it wakes up and condition is still not met, then needs to go back to sleep.

7. Deadlock and Dining Philosopher Problem.

• Deadlock - If two or more threads are each waiting for the other to release one of several locks ( or resources ), we have deadlock.
• 4 sufficient and necessary conditions
  • Serially reusable resources:
    • the processes involved share resources which they use under mutual exclusion.
  • Incremental acquisition:
    • processes hold on to resources already allocated to them while waiting to acquire additional resources.
  • No pre-emption:
    • once acquired by a process, resources cannot be pre-empted (forcibly withdrawn) but are only released voluntarily.
  • Wait-for cycle:
    • a circular chain (or cycle) of processes exists such that each process holds a resource which its successor in the cycle is waiting to acquire.
  • Simply : Using shared resource, wait for other while holding one already, have to wait till released naturally, and in wait-for cycle.

8. Locking or Resource Hierarchy? how is it applied to Dining Philosophers problem?

• Locking & Resource Hierarchy - Requiring threads to acquire thier locks in the same order to prevent wait cycle.
• Applied : If four of the five philosophers simultaneously pick up their lower-numbered fork,
  • Only the highest numbered fork will remain on the table,
  • The fifth philosopher will not be able to pick up any fork.
  • Therefore, only one philosopher will have access to that highest-numbered fork, so he will be able to eat using two forks.

9. Starvation and Single-lane Bridge Problem.

• Starvation - problem encountered in parallel systems where a process/thread is perpetually denied access to necessary resources.
• Priority inversion - when one process goes into starvation due to new process being created with higher priority.
• Solution to Single-lane Bridge Problem - Give a boolean variable to control which color of cars need to go now.

10. Synchronized methods and blocks in Java

• Synchronized methods are methods that can only be acceced by one thread at a time. It creates block called Critical section by aquiring intrinsic lock for the CLASS.

• Synchronized bocks are also known as synchronized statements. Basically is a block of code that is protected. Unlike synchronized methods, synchronized blocks must specify the object that prvides intrinsic lock. ex) synchronized(this).

11. volatile keyword

• Volatile keyword makes that variable atomic (including long and double variables). It also brings happens-before relationshisp : ``.
• Volatile can be useful when you do not need locking for any other reasons, also useful when it is somehow known that only one thread can change a field, but many other threads are allowed to read it at any time.

12. Guarded Block

• Such block that checks if condition is met by polling before the block can proceed.

13. thread join() method

• <target>.join(). This method provides ability for current thread to wait for the completion of other target thread. Just like sleep() method, join() responds to an interrupts by exiting with an InterrupedException.

14. Java thread state diagram

• First, New state (where thread gets created). Second, Runnable state (either ready or running) depends on OS. Third, out of these 4 states (Wait, TimedWait, Terminate, Blocked).

15. Java thread interrupt() method

• <target>.interrupt(). This will send signal to a target thread from current thread. Once the target thread receives interrupt signal, it needs to do something else. Common practice is to terminate target thread.
• 2 useful senerios: a. When thread frequently goes into sleep. b. When thread needs to be terminated from doing constant busy work.

16. Concepts of thread and process

• Process (formal) - An execution of a program, which contains information about program resources and program execution state.
  Process (in_formal) - Parents.

• Thread (formal) - An independent stream of instructions that can be scheduled to run as such by the OS, procedures that runs independently from its main program, and program that exists within the process resource.
  Thread (in_formal) - Childrens.

17. Thread sleep() method

• sleep(millisecond) causes the currently running thread to sleep which goes into timed wait state from runnable state. Used for a way of giving other thread chance to run in processor. This method will NOT lose ownership of any monitors (very greedy).

18. Java thread start() method

• start() method causes thread to begin execution which moves it from new state into runnable(ready or running) state. Calling this method more than once is NOT allowed.

19. Concepts of concurrent and parallel

• Concurrent (formal) - Processes or threads that run on separate processors which do not share any memory.
  Concurrent (in_formal) - OS quickly switches processes threads on computer with single cpu to make it look like it is running simultaniously.

• Parallel (formal) - Process or threads that multiple processors with sharing information.
  Parallel (in_formal) - processes/threads that runs on their own cpu. Real simultaneity.

20. Priority value of a thread

• Purpose - To help determine the order in which threads are scheduled.
  Range - MIN (1) and MAX (10). Default = 5.
  Special - New threads inherit priority of thread that created it.
  Important - It can't be used as substitute for locking. Because this doesn't guarentee the correctness. So use priority only to express relative urgency of different threads since it is platform dependent.

21. concept of mutual exclusion

• Mutual Exclusion (formal) - only one thread is allowed to execute a block of code at the same time using synchronized keyword. This block is called Critical Section.
  Mutual Exclusion (in_formal) - Private restroom. (Critical Section 😉)

22. intrinsic lock of a monitor object.

• Intrinsic locks (formal) - Enforces exclusive access to an object's state, Establish happens-before relationships that are essential to visibility.
  
• Intrinsic locks (in_formal) - Lock that is created behind the scene when synchronized keyword is used. This pretty much defines how mutual exclusion happens.