동기화를 위한 동기

동기화를 위한 동기

• 프로세스는 병렬적으로 실행될 수 있음
  • 언제든지 인터럽트를 받을 수 있고 부분적으로만 완료될 수 있음
• 공유 데이터에 대한 동시 접근은 데이터 불일치를 일으킬 수 있음
• OS에는 높은 수준의 동기화 기본 요소들이 구축되어 있음
  • 스레드 간 명령어의 올바른 순서를 보장하는 작업
• 동기화 기본 요소의 예는 다음과 같음
  • 모니터, 잠금, 세마포어, 조건 변수
  • 로드, 저장, Test&Set, 인터럽트 비활성화

Locks: 기본 아이디어

• 임계 영역이 단일한 원자적 명령어인 것처럼 실행되도록 보장
  • 공유 변수의 정규 업데이트의 예
    • balance = balance + 1;
• 임계 영역 주위에 일부 코드 추가
  • lock_t mutex; // 전역적으로 할당된 '뮤텍스' 잠금
  • lock(&mutex);
  • balance = balance + 1;
  • unlock(&mutex);

Locks: 기본 아이디어

• 잠금 변수는 잠금의 상태를 유지
  • 사용 가능(또는 잠금 해제됨 또는 비어 있음)
    • 스레드가 잠금을 보유하지 않음
  • 획득됨(또는 잠김 또는 보류됨)
    • 정확히 하나의 스레드가 잠금을 보유하고 아마도 임계 영역에 있음

lock()의 의미

• lock()
  • 잠금을 획득하려고 시도
  • 다른 스레드가 잠금을 보유하지 않으면 스레드가 잠금을 획득
  • 임계 영역으로 들어감
    • 이 스레드를 잠금의 소유자라고 함
  • 잠금을 보유한 첫 번째 스레드가 그 안에 있는 동안 다른 스레드는 임계 영역에 들어오지 못함

잠금 구현 목표

• 정확성
  • 상호 배제
    • 한 번에 임계 영역에 스레드가 하나만 있음
  • 프로그레스 (교착 상태 없음)
    • 여러 동시 요청이 있는 경우 하나가 진행되도록 허용해야 함
  • 범위 지정 (기아 없음)
    • 각 대기 스레드가 결국 들어가도록 허용해야 함
• 공정성
  • 각 스레드가 동일한 시간 동안 대기함
• 성능
  • CPU가 불필요하게 사용되지 않음 (예: 스피닝)

잠금 구축

• 효율적인 잠금은 낮은 비용으로 상호 배제를 제공
• 잠금을 구축하려면 하드웨어와 OS의 도움이 필요

인터럽트 제어

• 임계 영역에 대한 인터럽트 비활성화
  • 상호 배제를 제공하는 데 사용되는 가장 초기의 솔루션 중 하나
  • 단일 프로세서 시스템용으로 발명됨
    • void lock() { DisableInterrupts(); }
    • void unlock() { EnableInterrupts(); }
• 문제점
  • 응용 프로그램에서 너무 많은 신뢰가 필요
    • 탐욕스럽거나 악의적인 프로그램이 프로세서를 독점할 수 있음
  • 멀티프로세서에서 작동하지 않음
  • 인터럽트 마스크 또는 언마스크 코드가 최신 CPU에서 느리게 실행됨

하드웨어 지원이 필요한 이유는 무엇입니까?

• 첫 번째 시도: 잠금이 보류되었는지 여부를 나타내는 플래그 사용
  • 코드에 문제가 있음
    • typedef struct __lock_t { int flag; } lock_t;
    • void init (lock t *mutex) {mutex->flag = 0;} //락이 사용 가능하면 0, 잠금되면 1
    • void lock (lock t *mutex) {while (mutex->flag == 1) ; // 테스트 플래그 // spin-wait (아무 것도 안 함) mutex->flag = 1; // 이제 설정하세요! }
    • void unlock (lock t *mutex) {mutex->flag = 0;}

하드웨어 지원이 필요한 이유는 무엇입니까? (계속)

• 문제 1: 상호 배제 없음 (플래그=0이라고 가정)
  • 스레드 1
    • call lock ()
    • while (flag == 1)
    • interrupt: 스레드 2로 전환
    • flag = 1; // 플래그를 1로 설정!(너무!)
  • 스레드 2
    • call lock ()
    • while (flag == 1)
    • flag = 1;
    • interrupt: 스레드 1로 전환
• 문제 2: 스핀 대기 시간은 다른 스레드를 기다리는 데 시간을 낭비
• 솔루션: 하드웨어에서 지원하는 원자적 명령어가 필요!
  • test-and-set 명령어, 원자적 교환으로도 알려져 있음

Peterson's Algorithm

• 하드웨어 지원 없이 임계 영역을 원자적으로 보장할 수 있는 알고리즘 방법
• 두 개의 스레드만 해당 (tid = 0, 1)
• 로드 및 스토어만 사용 (원자적 명령어)
  • 1개의 고급 언어가 여러 개의 명령어로 나뉘지 않음
    • int turn = 0; // 공유
    • Boolean lock[2] = {false, false};
    • Void acquire() { lock[tid] = true; turn = 1-tid; while (lock[1-tid] && turn == 1-tid) /* wait */; }
    • Void release() { lock[tid] = false; }

Different Cases: All Work

• 스레드 0만 잠금을 원함
  • Lock[0]= true;
  • turn = 1;
  • while (lock[1] && turn ==1);
  • LOCK AQUIRED !
  • Lock[0]=false;
• 스레드 1만 잠금을 원함
  • Lock[1] = true;
  • turn = 0;
  • while (lock[0] && turn ==0);
  • LOCK AQUIRED !
  • Lock[1]=false;

Different Cases: All Work

• 스레드 0과 스레드 1이 모두 잠금을 원함;
  • Lock[0] = true;
  • turn = 1;
  • while (lock [1] && turn ==1);
  • LOCK AQUIRED !
  • Lock[0]=false;
  • Lock[1] = true;
  • turn = 0;
  • while (lock [0] && turn == 0)
  • LOCK AQUIRED !
  • Lock[1]=false;

Peterson's Algorithm: 직관

• 상호 배제: 다음 경우에만 임계 영역에 들어감
  • 다른 스레드가 들어오기를 원하지 않음
  • 다른 스레드가 들어오기를 원하지만 차례가 되면
• 프로그레스: 두 스레드 모두 while() 루프에서 영원히 대기할 수 없음
  • 다른 프로세스가 들어오기를 원하지 않는 경우 완료 다른 프로세스 (매칭 turn)는 결국 완료됨
• 범위 지정 대기(예제에 표시되지 않음)
  • 각 프로세스는 최대 하나의 임계 영역에서 대기
• 문제점
  • 최신 하드웨어에서 작동하지 않음 (캐시 일관성 문제)
  • 3개 이상의 스레드에서 작동하지 않음

동기화 구현

• 구현하려면 원자적 작업이 필요
• 원자적 작업: 다른 명령어를 인터리브할 수 없음
• 원자적 작업의 예
  • 유니프로세서에서 인터럽트 사이의 코드
    • 타이머 인터럽트 비활성화, I/O를 수행하지 않음
  • 단어의 로드 및 저장
    • Load r1, B
    • Store rl, A
  • 특별 HW 명령어
    • Test&Set
    • Compare&Swap

Test And Set (Atomic Exchange, XCHG)

• 간단한 잠금 생성을 지원하는 명령어
  • int TestAndSet (int *ptr, int new) {
  • int old = *ptr; // ptr에서 이전 값 가져오기
  • *ptr = new; // 'new'를 ptr에 저장
  • return old; // 이전 값을 반환
  • }
• ptr이 가리키는 이전 값을 반환(테스트)
• 동시에 해당 값을 새로 업데이트(설정)
• 이 작업 시퀀스는 원자적으로 수행됨

XCHG를 사용한 LOCK 구현

• typedef struct lock_t { int flag; } lock_t;
• void init(lock t *lock) { lock->flag = 0; }
• void acquire(lock_t *lock) { while(xchg(&lock->flag, 1) == 1) ; // spin-wait (아무 것도 안 함) }
• void release (lock t *lock) { lock->flag = 0; }

Compare-And-Swap

• 주소 (ptr)의 값이 예상 값과 같은지 테스트
  • 같으면 ptr이 가리키는 메모리 위치를 새 값으로 업데이트
• 어느 경우든 해당 메모리 위치에서 실제 값을 반환
  • int CompareAndSwap (int *ptr, int expected, int new) {
  • int actual = *ptr;
  • if (actual == expected) *ptr = new;
  • return actual;
  • }
• Compare-and-Swap 하드웨어 원자적 명령어(C 스타일)
  • void lock (lock t *lock) {
  • while (CompareAndSwap(&lock->flag, 0, 1) == 1) ; // 스핀
  • }
• Compare-and-swap을 사용한 스핀 잠금

Compare-And-Swap (컨트)

• compare-and-swap의 C 호출 가능 x86 버전
  • char CompareAndSwap (int *ptr, int old, int new) {
    • unsigned char ret;
    • // Note that sete sets a 'byte' not the word
    • asm volatile (
    • " lock\n"
    • " cmpxchgl %2,%1\n"
    • " sete %0\n"
    • : "=q" (ret), "=m" (*ptr)
    • : "r" (new), "m" (*ptr), "a" (old)
    • : "memory");
    • return ret;
  • }

Load-Linked and Store-Conditional

• int LoadLinked(int *ptr) { return *ptr; }
• int StoreConditional (int *ptr, int value) {
  • if (no one has updated *ptr since the LoadLinked to this address) {
  • *ptr = value;
  • return 1; // 성공!
  • } else {
  • return 0; // 업데이트 실패
  • }
• }
• Load-linked And Store-conditional
  • 저장 조건은 주소에 간헐적인 저장이 발생하지 않는 경우에만 성공
    • 성공: 1을 반환하고 ptr에서 value로 값을 업데이트
    • 실패: ptr의 값이 업데이트되지 않고 O가 반환

Load-Linked and Store-Conditional (Cont.)

• void lock (lock_t *lock) {
  • while (1) {
  • while (LoadLinked(&lock->flag) == 1) ;
  • if (StoreConditional(&lock->flag, 1) == 1)
  • return;
  • }
• }
• void unlock (lock_t *lock) { lock->flag = 0; }
• LL/SC를 사용하여 잠금 구축
• void lock (lock t *lock) {
  • while (LoadLinked(&lock->flag) || !StoreConditional(&lock->flag, 1)) ;
  • }
• LL/SC를 사용한 lock ()의 더 간결한 형식

Pthread Locks - mutex

• 앞의 명령어를 프로그래머가 바로 갖다 쓰기에는 제한적
• POSIX 라이브러리에서 잠금에 사용하는 이름
  • 스레드 간 상호 배제 제공에 사용
    • pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
    • Pthread_mutex_lock(&lock); // pthread_mutex_lock()용 wrapper
    • balance = balance + 1;
    • Pthread_mutex_unlock(&lock);
• 다양한 변수를 보호하기 위해 다른 잠금을 사용할 수 있음 -> 동시성 증가 (더 세분화된 접근 방식)

잠금 구현 목표

• 정확성
  • 상호 배제
    • 한 번에 임계 영역에 스레드가 하나만 있음
  • 프로그레스 (교착 상태 없음)
    • 여러 동시 요청이 있는 경우 하나가 진행되도록 허용해야 함
  • 범위 지정 (기아 없음)
    • 각 대기 스레드가 결국 들어가도록 허용해야 함
• 공정성
  • 각 스레드가 동일한 시간 동안 대기함
• 성능
  • CPU가 불필요하게 사용되지 않음

기본 스핀락은 공정하지 않음

• 스케줄러는 잠금/잠금 해제와 무관함

Fetch-And-Add

• 특정 주소에서 이전 값을 반환하면서 값을 원자적으로 증가
  • int FetchAndAdd (int *ptr) {
  • int old = *ptr;
  • *ptr = old + 1;
  • return old;
  • }
• Fetch-And-Add 하드웨어 원자적 명령어(C 스타일)

Ticket Lock (1)

• 티켓 잠금은 fetch-and add로 구축할 수 있음
  • 모든 스레드에 대한 프로그레스 보장 -> 공정성
    • typedef struct lock_t {
    • int ticket;
    • int turn;
    • } lock t;
    • void lock_init (lock t *lock) {
    • lock->ticket = 0;
    • lock->turn = 0;
    • }
    • void lock (lock t *lock) {
    • int myturn = FetchAndAdd(&lock->ticket);
    • while (lock->turn < myturn)
    • ; // 스핀
    • }
    • void unlock(lock_t *lock) {
    • FetchAndAdd(&lock->turn);
    • }

Ticket Lock (2)

• 티켓 잠금은 fetch-and add로 구축할 수 있음
  • 모든 스레드에 대한 프로그레스 보장 -> 공정성
    • typedef struct lock_t {
    • int ticket;
    • int turn;
    • } lock t;
    • void lock init(lock t *lock) {
    • lock->ticket = 0;
    • lock->turn = 0;
    • }
    • void lock(lock t *lock) {
    • int myturn = FetchAndAdd(&lock->ticket);
    • while (lock->turn != myturn)
    • ; // 스핀
    • }
    • void unlock (lock t *lock) {
    • FetchAndAdd(&lock->turn);
    • }

Ticket Lock (3)

• 잠금 해제에도 FAA가 필요함??
  • typedef struct lock_t {
  • int ticket;
  • int turn;
  • } lock t;
  • void lock_init(lock_t *lock) {
  • lock->ticket = 0;
  • lock->turn = 0;
  • }
  • void lock (lock t *lock) {
  • int myturn = FetchAndAdd(&lock->ticket);
  • while (lock->turn != myturn)
  • ; // 스핀
  • }
  • void unlock (lock t *lock) {
  • &lock->turn++; /* no other thread can touch it ! */
  • }

너무 많은 회전

• 하드웨어 기반 스핀 잠금은 간단하고 작동함
• 일부 경우에는 이러한 솔루션이 매우 비효율적일 수 있음
  • 스레드가 spinning 상태가 되면 전체 시간 조각을 가치를 확인하는 것 외에는 아무 것도 하지 않는 데 낭비

스핀 잠금 평가

• 정확성: 확인
  • 스핀 잠금은 단일 스레드만 임계 영역에 진입할 수 있도록 허용
• 공정성: 아니요
  • 스핀 잠금은 공정성을 보장하지 않음
  • 실제로 스레드 spinning이 영원히 돌 수 있음
• 성능:
  • 단일 CPU에서는 성능 오버헤드가 매우 고통스러울 수 있음
  • 스레드 수가 CPU 수와 대략 동일한 경우 스핀 잠금이 상당히 잘 작동

간편한 접근 방식: Yield만 하기

• spinning 상태로 유지하려는 경우 CPU를 다른 스레드에 제공
  • OS 시스템 호출은 호출자를 실행 상태에서 준비 상태로 이동
• 컨텍스트 전환의 비용이 상당할 수 있으며 기아 문제가 여전히 존재
  • void init() { flag = 0; }
  • void lock() {
  • while (TestAndSet(&flag, 1) == 1)
  • yield(); // CPU를 제공하세요
  • }
  • void unlock() { flag = 0; }
• Test-and-set 및 yield가 있는 잠금

큐 사용: 스핀 대신 sleep

• 잠금을 입력하기 위해 기다리는 스레드를 추적하는 큐
• park()
  • 호출 스레드를 sleep 상태로 전환
• unpark(threadID)
  • threadID로 지정된 특정 스레드를 깨우기

큐 사용: 스핀 대신 sleep

• typedef struct lock_t { int flag; int guard; queue_t *q; } lock_t;
• void lock init(lock_t *m) {
  • m->flag = 0;
  • m->guard = 0;
  • queue_init(m->q);
• }
• void lock (lock_t *m) {
  • while (TestAndSet(&m->guard, 1) == 1)
  • ; // 스핀으로 가드 잠금 획득
  • if (m->flag == 0) {
  • m->flag = 1; // 잠금 획득됨
  • m->guard = 0;
  • } else {
  • queue_add (m->q, gettid());
  • m->guard = 0;
  • park();
• }
• }
• 큐, Test-and-set, Yield 및 wakeup이 있는 잠금

큐 사용: 스핀 대신 sleep

• void unlock (lock_t *m) {
  • while (TestAndSet(&m->guard, 1) == 1)
  • ; // 스핀으로 가드 잠금 획득
  • if (queue_empty(m->q)) m->flag = 0; // 잠금을 release; 원하는 사람이 없으면
  • else unpark (queue_remove (m->q)); // 다음 스레드에 대한 hold lock (for next thread!)
  • m->guard = 0;
• }
• 큐, Test-and-set, Yield 및 wakeup이 있는 잠금 (Cont.)

Wakeup/waiting race

• 잠금 release가 park() 호출 직전인 경우 (스레드 B) -> 스레드 B는 (잠재적으로) 영원히 sleep 상태로 유지됨
• Solaris는 setpark()라는 세 번째 시스템 호출을 추가하여 이 문제를 해결
  • 이 루틴을 호출하면 스레드가 park()에 대해 표시할 수 있음
  • 인터럽트가 발생하고 다른 스레드가 park 가 실제로 호출되기 전에 unpark 를 호출하는 경우 후속 park는 sleep 대신 즉시 반환
    • queue_add (m->q, gettid());
    • setpark(); // 신규 코드
    • m->guard = 0;
    • park();
• lock () 내의 코드 수정

Futex

• Linux는 futex를 제공 (Solaris의 park 및 unpark와 유사)
  • futex_wait(address, expected)
    • *address == expected인 경우 호출 스레드를 sleep 상태로 전환
    • 그렇지 않으면 호출은 값 EAGAIN으로 즉시 반환
  • futex_wake(address)
    • 큐에서 대기 중인 스레드를 깨우기

Futex

• futex는 사용 공간의 atomic 정수에 연결된 커널 공간 대기 큐로 구성.
• 여러 프로세스 또는 스레드가(서로 간섭하지 않도록 원자적 연산을 사용하여) 사용자 공간에서 정수 전체에서 작동
• 대기 큐에서 연산을 요청하도록 비싼 시스템 호출에 resorting하는 것만으로, 또는 대기 큐에 현재 프로세스를 넣습니다
• 적절하게 프로그래밍 Futex 기반 잠금 대기 중 lock가 없을 때를 제외하고 시스템 호출이 사용되지는 않습니다: 이러한 작업의 대부분은 프로세스 간 arbitration 필요하지 않기 때문에, 대부분의 경우 일어나기가 쉽지 않을 것입니다

Futex (컨트)

• nptl 라이브러리에서 lowlevellock.h의 스니펫
  • 정수 v의 높은 비트: 잠금이 보관되는지 아닌지 추적
  • 다른 모든 비트: 대기자의 수
    • void mutex_lock (int *mutex) {
    • int v;
    • /* Bit 31 was clear, we got the mutex (this is the fastpath) */
    • if (atomic_bit_test_set (mutex, 31) == 0)
    • return;
    • atomic_increment (mutex);
    • while (1) {
    • if (atomic_bit_test_set(mutex, 31) == 0) {
    • atomic_decrement (mutex);
    • return;
    • }
    • /* We have to wait now. First make sure the futex value
    • we are monitoring is truly negative (i.e. locked). */
    • v = *mutex;
    • ...
• Linux 기반 Futex 잠금

Futex (컨트)

• if (v >= 0) /Checking again that lock is still unavailable/
  • continue;
  • futex wait (mutex, v); /* mutex == v (!0)인 경우 sleeps */
  • }
  • }
  • void mutex_unlock(int *mutex) {
  • /* Adding 0x80000000 to the counter results in 0 if and only if
  • there are not other interested threads: 0x80 + 0x80 = 0x00 */
  • if (atomic add zero (mutex, 0x80000000))
  • return;
  • /* There are other threads waiting for this mutex,
  • wake one of them up */
  • futex wake (mutex);
  • }
• Linux 기반 Futex 잠금 (Cont.)

잠금 평가

• 잠금 구현이 좋은지 확인하는 방법
• 공정성:
  • 프로세스가 요청된 것과 동일한 순서로 잠금을 획득합니까?
• 성능
  • 두 가지 시나리오:
    • 낮은 경합 (스레드 수가 더 적고 일반적으로 잠금이 사용 가능)
    • 높은 경합(CPU당 스레드 수가 많고 각 CPU가 경합)

스핀 잠금 성능

• 빠를 때...
  • 다수의 CPU
  • 잠금이 짧은 시간 동안 보관
  • advantage: 컨텍스트 스위치를 피합니다
• 느릴 때...
  • 하나의 CPU
  • 잠금이 긴 시간 동안 보관
  • disadvantage: 스핀이 비생산적

스핀 잠금 성능

• no yield: A B C D A B C D
• yield: A A B
• Yield가 유용한 이유는 무엇입니까?
• Yield가 모든 성능 문제를 해결하지 못하는 이유는 무엇입니까?

스핀 잠금 성능

• Waste...
  • Yield 없음: O(스레드 * time_slice)
  • Yield 있음: O(스레드 * context_switch)
• 따라서 Yield가 있더라도 높은 경합에서는 느립니다

잠금 구현: 대기 시 차단

• 잠금 구현은 대기 중인 스레드를 스케줄러 준비 큐에서 제거 (예: park() 및 unpark())
• 스케줄러는 준비된 스레드를 실행함
• 우려 사항이 잘 분리됨

스핀 대기 대 차단

• 각 접근 방식은 다른 상황에서 더 적합
• 유니프로세서
  • 대기 중인 프로세스가 스케줄링됨 --> 잠금을 보유한 프로세스가 아님
  • 대기 중인 프로세스는 항상 프로세서를 포기해야 함
  • 각 잠금에 대기자 큐를 연결(이전 구현에서와 같이)
• 멀티프로세서
  • 대기 중인 프로세스가 스케줄링됨 --> 잠금 보유 프로세스가 스핀 상태이거나 차단 상태일 수 있음
  • 잠금이 release되는 시간(t)에 따라 다름
  • 잠금이 빠르게 release됨 --> 스핀 대기
  • 잠금이 느리게 release됨 --> 차단
  • 빠름과 느림은 컨텍스트 전환 비용(C)과 관련

스핀 대기를 할까? 차단을 할까?

• 잠금 release되기 전 시간(t)을 안다면 최적의 행위를 결정할 수 있음
• 스핀 대기 시 CPU가 낭비되는 시간
  • t
• 차단 시 낭비되는 시간
  • C
• 가장 적합한 행위 (t<C)일 때
  • 스핀 대기
• (t>C)일 때
  • 차단
• 문제점:
  • 미래를 알아야 함; 특정한 예측을하는데 너무 많은 간접비가 발생

2단계 대기

• 이론: 최악의 경우 성능 바운딩; 실제/최적의 ratio 최악의 성능이 언제 발생합니까?
  • 매우 긴 시간 동안 스핀 >> C
  • Ratio: t/C (범위 없음)
• 알고리즘: C에 대해 스핀 대기한 후 차단 --> 최적의 2 요소.
• 두 가지 케이스:
  • t < C: 최적의 스핀대기 t에 대한 스핀대기, 스핀대기 t도
  • t > C: (C비용) 즉시 블록하면, 스핀 C 지불하기 때문에 (2 C의 가격) ->2 대립의 알고리즘
• 경쟁적인 분석의 예시

2단계 잠금

• 2단계 잠금 락은 spining 락 잠금이 해제될 것 같다면 유용할 것이라는 생각에서 비롯
• 1단계
  • 잠금을 획들이 가능한 시점까지 스핀락을 잠시 동안 작동시킨다
  • 1단계 작동 구간에서 잠금 획득 실패 시에는 2단계 작동 구간으로 넘어간다
• 2단계
  • 요청 스레드를 sleep 상태로 전환시킨다
  • 요청 스레드는 잠금 해제가 감지된 시점에서 부터 스레드를 깨운다

Filter Lock

• class Filter implements Lock {
  • int[] level; int[] victim;
  • public Filter(int n) {
  • level = new int[n]; victim = new int[n]; // use 1..n-1
  • for (int i = 0; i < n; i++) { level[i] = 0; }
  • }
  • public void lock() {
  • int me = ThreadID.get();
  • for (int i = 1; i < n; i++) { //attempt level 1 .. n-1
  • level[me] = i; victim[i] = me; // 스핀으로 lock을 획득
  • while ((∃k != me) (level[k] > = i && victim[i] == me)) {};
  • }
  • }
  • public void unlock() {
  • int me = ThreadID.get(); level[me] = 0;
  • }
• }

Bakery Algorithm by Lamport

• class Bakery implements Lock {
  • volatile boolean[] flag;
  • volatile Label[] label;
  • public Bakery (int n) {
  • flag = new boolean[n];
  • label = new Label [n];
  • for (int i = 0; i < n; i++) {
  • flag[i] = false; label [i] = 0;
  • }
  • }
  • public void lock() {
  • flag[i] = true;
  • label [i] = max(label[0], …,label[n-1])+1;
  • while (∃k flag[k]
  • && (label[i],i) > (label[k],k));
  • }
  • public void unlock() {
  • flag[i] = false;
  • }
• }

Bakery Algorithm by Lamport

• First-Come-First-Serve 제공
• 교착 상태 없음
• 어떻게 작동 하는 가?
  • "번호" 가져오기
  • 더 낮은 번호가 제공될 때까지 기다리기
• 어휘 편집 순서
  • (a,i) > (b,j)
  • a > b이거나 a = b이고 i > j인 경우
• label[i]로 오버플로가 가능합니까? (32비트: 예, 64비트??)