Exercise 3. Process Synchronization

Cash coherence

캐시는 현대 컴퓨터 아키텍처, 특히 성능에서 중요한 구성 요소입니다. 캐시는 메모리에 데이터 복사본을 유지 관리하므로 프로세서 코어의 데이터에 더 빨리 액세스할 수 있습니다. 일반적으로 프로세서는 여러 레벨의 캐시를 포함하며, 이는 그림 1과 같이 속도와 크기 면에서 다릅니다. 이 경우 캐시와 메인 메모리에 여러 개의 데이터 복사본이 존재할 수 있습니다. 한 코어가 로컬 캐시의 데이터를 수정하는 경우 다른 코어가 로컬 캐시의 오래된 데이터를 사용하지 않기 때문에 프로세서는 캐시 간의 데이터 일관성을 보장해야 합니다. 캐시 쓰기를 처리하는 데는 두 가지 일반적인 접근 방식이 있습니다:

1. Write through: 캐시와 메모리를 즉시 write (시간이 오래 걸림)
2. Write back: 우선 캐시를 write 한 뒤 나중에 메모리에 write (flush)

캐시 간 데이터 일관성을 제공하려면 캐시 일관성 프로토콜이 필수적이지만 쓰기 작업에 추가적인 지연 주기가 발생할 수 있습니다. 따라서 최신 프로세서는 프로세서가 정지되지 않고 즉시 진행할 수 있도록 처리되는 동안 저장소 버퍼를 사용하여 저장소 작업을 기록합니다.

 

 

 

Memory barrier

메모리 장벽 또는 펜스는 메모리의 모든 변경 사항이 다른 모든 프로세서에 전파되도록 강제하는 명령입니다. 메모리 차단 명령이 수행되면 시스템은 후속 로드 또는 저장 작업이 수행되기 전에 모든 로드 및 저장이 완료되도록 합니다. 그런 다음 프로세서 코어는 저장소 버퍼에 기록된 저장소를 커밋하는 저장소 버퍼를 플러시해야 합니다.

 

 

 

Critical section

n개의 프로세스 {P0, P1, ..., Pn-1}로 구성된 시스템을 생각해 보십시오. 각 프로세스에는 크리티컬 섹션이라고 하는 코드 세그먼트가 있으며, 여기서 프로세스는 적어도 하나의 다른 프로세스와 공유하는 데이터에 액세스하고 업데이트할 수 있습니다. 시스템의 중요한 특징은 한 프로세스가 중요 섹션에서 실행될 때 다른 프로세스가 중요 섹션에서 실행될 수 없다는 것입니다. 즉, 두 프로세스가 중요한 섹션에서 동시에 실행되지 않습니다. 중요 섹션 문제는 프로세스가 데이터를 협력적으로 공유하기 위해 활동을 동기화하는 데 사용할 수 있는 프로토콜을 설계하는 것입니다. 각 프로세스는 중요 섹션에 들어가려면 권한을 요청해야 합니다. 이 요청을 구현하는 코드 섹션은 entry section입니다. Critical section 뒤에는 exit section이 따라옵니다. 나머지 코드는 remaining section입니다. Critical section에 대한 해결책은 다음 세가지 요구사항을 충족해야 합니다:

1. Mutual exclusion: 프로세스 Pi가 중요 섹션에서 실행 중인 경우 다른 프로세스는 해당 중요 섹션에서 실행될 수 없습니다.
2. Progress: 중요 섹션에서 실행 중인 프로세스가 없고 일부 프로세스가 중요 섹션에 진입하려는 경우, 나머지 섹션에서 실행되지 않은 프로세스만 다음에 중요 섹션으로 진입할 프로세스를 결정하는 데 참여할 수 있으며, 이 선택을 무기한 연기할 수 없습니다.
3. Bounded-waiting: 프로세스가 중요 섹션에 진입하도록 요청한 후 해당 요청이 허용되기 전에 다른 프로세스가 해당 중요 섹션에 진입할 수 있는 횟수에 대한 제한 또는 제한이 있습니다.

 

 

 

Peterson’s solution

Problem - Modern architecture에서는 reordering이 일어날 수 있기 때문에 적용되기 어렵다.

 

 

 

Deadlock

시스템에서 다음 네 가지 조건이 동시에 유지되는 경우 교착 상태가 발생할 수 있습니다:

1. Mutual exclusion: 하나 이상의 리소스가 공유 불가능 모드로 유지되어야 합니다. 즉, 한 번에 하나의 스레드만 리소스를 사용할 수 있습니다. 다른 스레드가 해당 리소스를 요청하는 경우 요청 스레드는 리소스가 해제될 때까지 지연되어야 합니다.
2. Hold and wait: 스레드는 하나 이상의 리소스를 보유하고 있으며 다른 스레드가 현재 보유하고 있는 추가 리소스를 획득하기 위해 대기하고 있어야 합니다.
3. No preemption: 리소스를 선점할 수 없습니다. 즉, 해당 스레드가 작업을 완료한 후 리소스를 보유하고 있는 스레드에 의해서만 리소스를 자발적으로 해제할 수 있습니다.
4. Circular wait: 대기 스레드 집합 {T0, T1, ..., Tn}이(가) 있어야 T0이 보유한 리소스를 대기하고, T1이 보유한 리소스를 대기하고, Tn-1이 보유한 리소스를 대기하고, Tn이 보유한 리소스를 대기합니다.

Deadlock이 발생하기 위해서는 네가지 조건이 모두 만족해야 합니다. Circular wait condition은 hold and wait condition을 함축하고 있고 네가지 조건은 완전히 독립적이지 않습니다.