Classical Problems of Synchronization

• Classical problems used to test newly-proposed synchronization schemes
  • Bounded-Buffer Problem
  • Readers and Writers Problem
  • Dining-Philosophers Problem

• 새로 제안된 동기화 체계를 테스트하는 데 사용되는 고전적인 문제
  • 경계 버퍼 문제
  • 독자 및 작가 문제
  • 식사-철학자 문제

Bound-Buffer Problem

• n buffers, each can hold one item
• Semaphore mutex initialized to the value 1
• Semaphore full initialized to the value 0
• Semaphore empty initialized to the value n

• n 버퍼, 각각 하나의 항목을 저장할 수 있다.
• Semaphore mutex가 값 1로 초기화됨
• Semaphore full 값이 0으로 초기화됨
• semaphore empty 값이 n으로 초기화됨

---

• The structure of the producer process
  

---

• The structure of the consumer process
  

Readers-Writers Problem

• A data set is shared among a number of concurrent processes
  • Readers – only read the data set; they do not perform any updates
  • Writers – can both read and write
• Problem – allow multiple readers to read at the same time
  • Only one single writer can access the shared data at the same time
• Several variations of how readers and writers are considered – all involve some form of priorities
• Shared Data
  • Data set
  • Semaphore rw_mutex initialized to 1
  • Semaphore mutex initialized to 1
  • Integer read_count initialized to 0

• data set이 여러 동시 프로세스 간에 공유됨
  • Readers – 데이터 세트만 읽고 업데이트를 수행하지 않는다.
  • Writers – 읽고 쓸 수 있다.
• 문제 – 여러 독자가 동시에 읽을 수 있도록 허용
  • 한 명의 작성자만 동시에 공유 데이터에 액세스할 수 있다.
  • 독자와 작가를 고려하는 방법에는 몇 가지 변형이 있다. 모두 어떤 형태의 우선 순위를 포함한다.
• 공유 데이터
  • 데이터 세트
  • Semaphore rw_mutex가 1로 초기화됨
  • 세마포어 mutex가 1로 초기화됨
  • 0으로 초기화되는 정수 read_count

---

• The structure of a writer process
  

---

• The structure of a reader process
  

Readers-Writers Problem Variations

• First variation – no reader kept waiting unless writer has permission to use shared object
• Second variation – once writer is ready, it performs the write ASAP
• Both may have starvation leading to even more variations
• Problem is solved on some systems by kernel providing reader-writer locks

• 첫 번째 변형 – 작성자가 공유 개체를 사용할 수 있는 권한이 없는 경우 계속 기다리는 독자가 없다.
• 두 번째 변형 – 작성기가 준비되면 가능한 한 빨리 쓰기를 수행한다.
• 둘 다 starvation으로 인해 훨씬 더 많은 변화가 있을 수 있다.
• 일부 시스템에서는 읽기-쓰기 잠금을 제공하는 커널을 통해 문제가 해결된다.

Dining-Philosophers Problem

• Philosophers spend their lives alternating thinking and eating
• Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time) to eat from bowl
  • Need both to eat, then release both when done
• In the case of 5 philosophers
  • Shared data
    • Bowl of rice (data set)
    • Semaphore chopstick [5] initialized to 1

• 철학자들은 생각과 식사를 번갈아 하면서 그들의 삶을 보낸다.
• 이웃들과 교류하지 말고, 때때로 그릇에서 먹기 위해 젓가락 두 개(한 번에 하나씩)를 집으려고 노력해라.
  • 둘 다 먹어야 하고, 다 먹으면 둘 다 풀어준다.
• 5명의 철학자의 경우
  • 공유 데이터
    • 밥그릇 (자료세트)
    • 세마포어 젓가락[5]는 1로 초기화됨

Dining-Philosophers Problem Algorithm

• Semaphore Solution
• The structure of Philosopher i:
  
• What is the problem with this algorithm?

Monitor Solution to Dining Philosophers

Solution to Dining Philosophers

---

• Each philosopher i invokes the operations pickup() and putdown() in the following sequence:

          DiningPhilosophers.pickup(i);
  
               /** EAT **/
  
          DiningPhilosophers.putdown(i);

• No deadlock, but starvation is possible

• 각 철학자 i는 다음 순서로 pickup()과 down() 연산을 호출한다.
• 교착상태는 없지만 기아는 가능하다.

Synchronization

Kernel Synchronization - Windows

• Uses interrupt masks to protect access to global resources on uniprocessor systems
• Uses spinlocks on multiprocessor systems
  • Spinlocking-thread will never be preempted
• Also provides dispatcher objects user-land which may act mutexes, semaphores, events, and timers
  • Events
    • An event acts much like a condition variable
  • Timers notify one or more thread when time expired
  • Dispatcher objects either signaled-state (object available) or non-signaled state (thread will block)

• 인터럽트 마스크를 사용하여 유니프로세서 시스템의 글로벌 리소스에 대한 액세스를 보호한다.
• 멀티프로세서 시스템에서 spinlocks 사용
  • 스핀 잠금 스레드는 절대 우선되지 않는다.
• 또한 mutexs, semaphores, events 및 timers를 수행할 수 있는 Dispatcher 개체 user-land 제공
  • 이벤트
    • 이벤트는 조건 변수와 매우 유사하다.
  • 타이머는 시간이 만료되면 하나 이상의 스레드에 알린다.
  • 발송인 개체 signaled-state(개체 사용 가능) 또는 non-signaled state(스레드가 차단됨)

---

• Mutex dispatcher object
  

Linux Synchronization

• Linux:
  • Prior to kernel Version 2.6, disables interrupts to implement short critical sections
  • Version 2.6 and later, fully preemptive
• Linux provides:
  • Semaphores
  • atomic integers
  • spinlocks
  • reader-writer versions of both
• On single-cpu system, spinlocks replaced by enabling and disabling kernel preemption

• Linux:
  • 커널 버전 2.6 이전에서는 짧은 중요 섹션을 구현하기 위해 인터럽트를 비활성화한다.
  • 버전 2.6 이상, 완전 선제적
• 리눅스는 다음을 제공한다.
  • 세마포어
  • 원자 정수
  • 방아쇠
  • 두 가지 모두의 독자-작가 버전
• 싱글 CPU 시스템에서 스핀 잠금 대신 커널 선점 활성화 및 비활성화

---

• Atomic variables
  • atomic_t is the type for atomic integer
• Consider the variables
  • atomic_t counter;
  • int value;

POSIX Synchronization

• POSIX API provides
  • mutex locks
  • semaphores
  • condition variable
• Widely used on UNIX, Linux, and macOS

POSIX Mutex Locks

• Creating and initializing the lock
  

• Acquiring and releasing the lock
  

POSIX Semaphores

• POSIX provides two versions – named and unnamed.
• Named semaphores can be used by unrelated processes, unnamed cannot.

• POSIX는 named와 unnamed의 두 가지 버전을 제공한다.
• 명명된 세마포어는 관련 없는 프로세스에서 사용될 수 있지만 명명되지 않은 프로세스에서는 사용할 수 없다.

POSIX Named Semaphores

• Creating an initializing the semaphore:
  

• Another process can access the semaphore by referring to its name SEM.

• Acquiring and releasing the semaphore:
  

POSIX Unnamed Semaphores

• Creating an initializing the semaphore:
  

• Acquiring and releasing the semaphore:
  

POSIX Condition Variables

• Since POSIX is typically used in C/C++ and these languages do not provide a monitor, POSIX condition variables are associated with a POSIX mutex lock to provide mutual exclusion: Creating and initializing the condition variable:

• POSIX는 일반적으로 C/C++에서 사용되며 이러한 언어들은 모니터를 제공하지 않기 때문에 POSIX 조건 변수는 상호 배제를 제공하기 위해 POSIX 뮤텍스 잠금과 연관된다. 조건 변수 생성 및 초기화는 다음과 같다.

POSIX Condition Variables

• Thread waiting for the condition a == b to become true:
  

• Thread signaling another thread waiting on the condition variable:
  

Java Synchronization

• Java provides rich set of synchronization features:
  • Java monitors
  • Reentrant locks
  • Semaphores
  • Condition variables

Java Monitors

• Every Java object has associated with it a single lock.
• If a method is declared as synchronized, a calling thread must own the lock for the object.
• If the lock is owned by another thread, the calling thread must wait for the lock until it is released.
• Locks are released when the owning thread exits the synchronized method.

• 모든 Java 객체는 단일 잠금과 연결되어 있다.
• 메서드가 synchronized로 선언된 경우 호출 스레드는 개체에 대한 잠금을 소유해야 한다.
• 잠금이 다른 스레드에 의해 소유되는 경우 호출 스레드는 잠금이 해제될 때까지 기다려야 한다.
• 소유 스레드가 synchronized 메서드를 종료하면 잠금이 해제된다.

Bounded Buffer - Java Synchronization

Java Synchronization

• A thread that tries to acquire an unavailable lock is placed in the object’s entry set:

• 사용할 수 없는 잠금을 획득하려는 스레드가 개체의 entryset에 배치된다.

---

• Similarly, each object also has a wait set.
• When a thread calls wait():
  • 1. It releases the lock for the object
  • 2. The state of the thread is set to blocked
  • 3. The thread is placed in the wait set for the object

• 마찬가지로 각 개체에도 대기 집합이 있다.
• 스레드가 wait()를 호출할 때:
  • 1. 객체의 잠금을 해제한다.
  • 2. 스레드의 상태가 차단됨으로 설정되어 있다.
  • 3. 스레드가 개체의 대기 집합에 배치된다.

---

• A thread typically calls wait() when it is waiting for a condition to become true.
• How does a thread get notified?
• When a thread calls notify():
  • 1. An arbitrary thread T is selected from the wait set
  • 2. T is moved from the wait set to the entry set
  • 3. Set the state of T from blocked to runnable.
• T can now compete for the lock to check if the condition it was waiting for is now true.

• 스레드는 일반적으로 조건이 참이 되기를 기다릴 때 wait()를 호출한다.
• 스레드는 어떻게 알림을 받는가?
• 스레드가 알림()을 호출할 때:
  • 1. 대기 집합에서 임의 스레드 T가 선택된다.
  • 2. T가 wait set에서 entry set로 이동된다.
  • 3. T의 상태를 blocked에서 runnable로 설정한다.
• 이제 T는 대기하고 있던 조건이 참인지 확인하기 위해 잠금을 경쟁할 수 있다.

Bounded Buffer - Java Synchronization

Java Reentrant Locks

• Similar to mutex locks
• The finally clause ensures the lock will be released in case an exception occurs in the try block.

• mutex locks과 유사함
• finally* 절은 try** 블록에서 예외가 발생할 경우 잠금이 해제되도록 보장한다.

Java Semaphores

• Constructor:
  

• Usage:
  

Java Condition Variables

• Condition variables are associated with an ReentrantLock.
• Creating a condition variable using newCondition() method of ReentrantLock:
  
• A thread waits by calling the await() method, and signals by calling the signal() method.

• 조건 변수는 재입력 잠금과 연관되어 있다.
• 재입력 잠금의 새 조건() 메서드를 사용하여 조건 변수 만들기:
  
• 스레드는 await() 메서드를 호출하여 대기하고 signal() 메서드를 호출하여 신호를 보낸다.

---

• Example:
• Five threads numbered 0 .. 4
• Shared variable turn indicating which thread’s turn it is.
• Thread calls doWork() when it wishes to do some work. (But it may only do work if it is their turn.
• If not their turn, wait
• If their turn, do some work for awhile …...
• When completed, notify the thread whose turn is next.
• Necessary data structures:
  

• 예:
• 5개의 실에 0..4 숫자가 매겨졌다
• 스레드 턴을 나타내는 공유 변수 턴이다.
• 스레드는 작업을 수행하고자 할 때 doWork()를 호출한다.
• 그들의 차례가 아니라면, 기다려라.
• 그들이 차례가 되면, 잠시 일을 좀 해라 …….
• 완료되면 다음 차례가 될 쓰레드에 알린다.
• 필요한 데이터 구조:=

---

Alternative Approaches

• Transactional Memory
• OpenMP
• Functional Programming Languages

Transactional Memory

• Consider a function update() that must be called atomically. One option is to use mutex locks:

• 함수 업데이트()는 원자적으로 호출되어야 하는 함수이다. 한 가지 옵션은 mutex 잠금을 사용하는 것이다:
  

• A memory transaction is a sequence of read-write operations to memory that are performed atomically. A transaction can be completed by adding atomic{S} which ensure statements in S are executed atomically:

• 메모리 트랜잭션은 메모리에 대한 읽기-쓰기 작업의 시퀀스로, 원자적으로 수행된다. 트랜잭션은 atomic{S}를 추가하여 완료할 수 있으며, S의 statements가 원자적으로 실행되도록 보장한다:
  

OpenMP

• OpenMP is a set of compiler directives and API that support parallel progamming.
  
• The code contained within the #pragma omp critical directive is treated as a critical section and performed atomically.

• OpenMP는 병렬 프로그래밍을 지원하는 컴파일러 지시어와 API의 집합이다.
• #pragma omp critical directive에 포함된 코드는 중요 섹션으로 취급되며 원자적으로 수행된다.

Functional Programming Languages

• Functional programming languages offer a different paradigm than procedural languages in that they do not maintain state.
• Variables are treated as immutable and cannot change state once they have been assigned a value.
• There is increasing interest in functional languages such as Erlang and Scala for their approach in handling data races.

• 함수형 프로그래밍 언어는 상태를 유지하지 않는다는 점에서 절차형 언어와는 다른 패러다임을 제공한다.
• 변수는 불변으로 처리되며 값이 할당된 후에는 상태를 변경할 수 없다.
• 데이터 레이스를 처리하는 접근 방식에 대해 얼랑, 스칼라와 같은 기능 언어에 대한 관심이 높아지고 있다.