Lesson 19 - Threads, Tasks & Concurrent Programming (pg 241 - 255)

[Admin]

What is the overall objective of this chapter?
• Cooperating processes can either directly share a logical address space (that is both code and data) or be allowed to share data only through files or messages. The problem lies in sharing the data. Why? Concurrent access to shared data may result in data inconsistency.

Chapter Objectives
• To introduce the critical section problem, whose solutions can be used to ensure the consistency of shared data
• to present both software and hardware solutions to the critical-section problem
• to introduce the concept of an atomic transaction and describe mechanisms to ensure atomicity

---

BACKGROUND

Race Condition := Situation that arises when several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place.

* MultiCore systems = there is a tremendous emphasis on developing multithreaded applications where several threads are not only executing at the same time, but they may be sharing data with one another and operating on different threads (e.x. games).

---

The Critical-Section Problem

Code:

While (true) {
    [table border="1"]
[tr]
[td] entry section [/td]
[/tr]
[/table]

    critical section
  [table border="1"]
[tr]
[td] exit section [/td]
[/tr]
[/table]

    remainder section
}

* Each process has a segment of code called:
• Critical Section = process may be changing common variables, updating a table, writing a file, and so on. When on eprocess is executing in its critical section, no other process is to be allowed to execute in its critical section.
• Entry Section = each process must request permission to enter its critical section.
• Exit section = self explanatory
• Remainder Section = the rest of the code

Critical-Section Problem = how can we design a protocol that allows processes to cooperate with one another? They must satisfy these three conditions.

• Mutual exclusion = if Process Pi is executing in its critical section, the no other processes can be executing in their critical sections.

• Progress = if no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.

• Bounded Waiting = there exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted

• Make no assumptions about relative speed of some process

What are some examples where a Race Condition may exist?
• List of open files
• structures for maintaing memory allocation, process lists, and for interrupt handling.

What are two general approaches used to handle critical sections in operating systems
• Preemptive Kernels = allows a process to be preempted while it is running in kernel mode.
• Nonpreemptive kernel = does not allow a process running in kernel mode to be preempted; a kernel-mode process will run until it exists kernel mode, blocks, or voluntarily yields control of the CPU.

---

Peterson's Solution

• no guarantee will work on modern operating system
• restricted to two processes that alternate execution between their critical sections and remainder sections. The key idea is sharing these two items.

Code:

int turn; // indicates whose turn it is to enter its critical section
boolean flag[2]; // indiciate if a process is ready to enter its criticla section


Code:

While (true) {
    flag[i] = TRUE;
    turn = j;
    while (flag[j] && turn ==j)
          Critical Section
    flag[i]
          remainder section
}

---

Synchronization Hardware

• We implemented a software implementation, but what about hardware? The Answer? LOCKS

Code:

while (true) {
    ACQUIRE LOCK
          critical Section
    Release Lock
          remainder section
}

• in a single processor system, you can use a interrupt prevention on a shared variable. This is not feasible in a multiprocessor environment because it can be time consuming, as the message is passed to all the processors. This message passing delays entry into each critical section, and system efficiency decreases. Also consider the effect on a system's clock if the clock is kept updated by interrupts

Atomically one uninterruptible unit. e.x. in the coding below, the get-and-set instructions allow two get-and-set instructions to be executed arbitrarily. The OS will simply execute them in some sequential order.

Code:

public class HardwareData // DATA STRUCTURE FOR HARDWARE SOLUTIONS
{
    private boolean value = false;
   
    public HardwareData(boolean value) {
          this.value = value;
    }

    public boolean get() {
          return value;
    }

    public void set(boolean newValue) {
          value = newValue;
    }

    public boolean getAndSet(boolean newValue) {
          boolean oldValue = this.get();
          this.set(newValue);

          return oldValue;
    }

    public void swap(HardwareData other) {
          boolean temp = this.get();

          this.set(other.get());
          other.set(temp);
    }
}

// lock is shared by all threads
HardwareData lock = new HardwareData(false);

while(true) {
while(lock.getAndSet(true))
Thread.yield();

// critical section
lock.set(false);
//remainder section
}

What does Yield do?

Yield = keeps the thread in a runnable state but also allows the JVM to select another runnable thread to run.

---

Semaphores := contains an integer variable that, apart from initialization, is accessed only through two standard operations: acquire() and release();