운영체제 공룡책 공부하며 정리한 내용입니다.
Github : https://github.com/orgs/gochu-charmchi/discussions 정리보다는 머리에 넣고, 개념을 체화하는걸 중요하게 생각합니다. 그에 따라 정리가 이상할 수 있습니다.
협력적 프로세스
- 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나, 영향을 받는 프로세스
- 데이터 공유 방법
- 논리 주소 공간(즉, 코드 및 데이터)을 직접 공유
- 공유 메모리 또는 메시지 전달을 통해서만 데이터를 공유
- 공유 데이터를 동시 접근하면, 데이터 일관성을 망칠 수 있음.
- 질서 있는 실행을 보장하고, 데이터 일관성을 유지하는 방법
6.1 배경
- 병행 또는 병렬로 실행 될 때 데이터의 무결성에 관해…
- 한 쪽에서 count++ 하고, 다른 쪽에서 count—할 때, 결과를 보장할 수 없다.
- 경쟁 상황
- 동시에 여러 개의 프로세스가 동일한 자료에 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황
6.2 임계구역 문제
- 임계구역
- 하나 이상의 다른 프로세스와 공유하는 데이터에 접근 & 갱신하는 코드 부분
- 동시에 두 프로세스는 그들의 임계구역에 들어갈 수 없다.
- 진입 구역 - 임계 구역 - 퇴출 구역 / 나머지 구역
- entry section - critical section - exit section / remainder section
- 해결법
- 상호 배제
- mutual exclusion
- 한 프로세스가 임계구역에서 실행될 때, 다른 프로세스들은 임계구역에서 실행될 수 없다.
- 진행
- progress
- 자신의 임계구역에서 실행되는 프로세스가 없고, 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는데 참여할 수 있다.
- 이 선택은 무한정 연기될 수 없다.
- 한정된 대기
- bounded waiting
- 프로세스가 자신의 임계구역에 진입하려는 요청을 한 후부터, 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
- 상호 배제
- 커널 코드는 경쟁 조건이 발생하기 쉽다.
- 단일 코어 환경에서는 공유 변수 수정 중 인터럽트가 발생하지 않는다면, 선점 없이 순서대로 실행될 수 있다는 것을 확신할 수 있다.
- 다중 프로세서 환경에서는 메시지(인터럽트 발생 중단)가 전달되는데 시간이 많이 걸릴 수 있어 불가능하다.
- 시스템 효율성 감소, 임계구연 진입 지연 등의 문제가 생긴다.
- 선점형 커널과 비선점형 커널 두 가지의 접근법이 사용된다.
- 비선점형 커널은 커널 자료구조에 대한 경쟁 조건을 염려할 필요는 없다.
- 선점형 커널에서는 신중하게 설계해야 한다.
- SMP(symmetric multiprocessing)에서 더 어렵다
- 선점형 커널이 민첩하기 때문에 선호된다.
6.3 Peterson의 해결안
- 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.
- int turn, boolean flag[2];
- turn이 궁극적인 값이 누가 임계구역에 진입할 것인지를 결정한다.
- 상호 배제
- flag[j] false or turn i 여야 한다.
- turn 은 i이거나 j이다.
- 진행 & 한정된 대기
- 임계 구역을 flag[j] true && turn j 로 묶어두기
- 최신 컴퓨터 아키텍처에서는 프로세서, 컴파일러가 작업을 재정렬 함
- 종속성이 없는 읽기 및 쓰기 작업을 재정렬 함.
6.4 동기화를 위한 하드웨어 지원
메모리 장벽
- 메모리 모델
- 프로그램이 메모리에 접근할 때 그 접근 순서와 동작이 어떻게 보장되는지를 규정한 규칙
- 강한 순서 : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임.
- 약한 순서 : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음.
- 메모리 장벽 (메모리 펜스)
- memory barriers, memory fences
- 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어
- 실행될 때, 시스템은 후속 적재 또는 저장 연산이 수행되기 전에, 모든 적재 및 저장이 완료되도록 한다.
- 상호 배제를 보장하는 특수 코드를 작성하는 커널 개발자만 사용한다.
하드웨어 명령어
- 운영체제는 한 워드의 내용을 검사 & 변경, 두 워드의 내용을 swap할 수 있는 원자적 명령어를 제공한다.
test_and_set()을 통해 간단히 상호 배제를 구현할 수 있다.compare_and_swap()(CAS) 를 이용해 하나의 변수를 이용해서 상호배제 구현 가능- 한정된 대기를 만족시키지 못함
- 모두(상호배제, 진행, 한정된 대기)를 충족하는 코드가 있음.
- boolean waiting[n], int lock 을 이용.
- p.296
원자적 변수
- 기본 데이터 유형에 대한 원자적 연산을 제공한다.
- 상호 배제를 보장하는데 사용될 수 있다.
- 하지만 경쟁 조건을 완벽히 해결하지는 않는다.
6.5 Mutex Locks
- 하드웨어 기반 해결책은 응용 프로그래머는 사용할 수가 없다.
- MUTual EXclution → mutex
- 임계구역 보호, 경쟁 조건 방지
- 임계구역 들어가기 전에 락 획득, 빠져나올 때 락 반환
- 사용 불가 락을 획득하려고 하면, block된다.
acquire()와release()는 원자적으로 수행되어야 한다.- CAS로 구현될 수 있다.
- 바쁜 대기(busy wating)를 해야한다.
- 다른 프로세스가 임계구역에 있는 동안 CPU에서 while을 호출하며, 문제가 된다.
- CPU 낭비
- 다른 프로세스가 임계구역에 있는 동안 CPU에서 while을 호출하며, 문제가 된다.
- busy waiting을 하는 락을 스핀락(spinlock)이라고도 한다.
- 락을 사용할 수 있을 때까지, 프로세스가 회전하기 때문,
- 문맥 교환이 필요하지 않다는 장점이 있다.
- 락이 잠깐 걸리는 상황에서는 선호된다.
[! question] 스핀락의 장점과 단점은? 장점 : 문맥 교환이 필요하지 않다. 단점 : busy waiting을 하기 때문에, CPU 실행 시간이 낭비된다.
6.6 Semaphores
- 정수 변수 S, 초기화를 제외하거는 원자적 연산인
wait(),signal()로 접근할 수 있다. - 세마포의 정수 값을 변경하는 연산은 원자적으로 수행되어야 한다.
- wait(S)의 경우, S 정수 값 검사(
S<=0) 작업과, 그에 따라S--작업 인터럽트 되지 않고 실행되어야 한다.
- wait(S)의 경우, S 정수 값 검사(
세마포 사용법
- Semaphore usage
- counting
- 카운팅 세마포의 값은 제한 없는 영역을 갖는다.
- 유한한 개수의 자원에 대한 접근을 제어하는데 사용될 수 있다.
- binary
- 0과 1사이의 값만 가능하다.
- mutex락과 유사하게 동작한다.
세마포 구현
- busy waiting 이 아닌, 프로세스를 semaphore에 연관된 대기 큐에 넣고, 다른 프로세스가
signal()하면 프로세스를 준비 완료 상태로 변경하고 준비 완료 큐 넣는다. - 세마포 음수 가능 → 음수일 때, 절댓값은 세마포를 대기하고 있는 프로세스들의 수
- 세마포 리스트에 임의의 큐잉 전략을 사용할 수 있다.
- FIFO로 한정된 대기를 구현할 수 있다.
- 세마포는 원자적으로 실행되어야 한다
- 단일 처리기 환경에서는 인터럽트를 금지함으로써 해결할 수 있다.
- 다중 처리기 환경에서는 모든 처리 코어에서 인터럽트를 금지하여야만 한다.
- CAS 또는 스핀락을 제공하여야 한다.
- 바쁜 대기는 극도로 비효율적이다.
6.7 모니터
- mutex 혹은 세마포를 사용할 때에도 그러한 오류는 일어날 수 있다.
- 프로그램의 세마포에 대한 wait, signal의 연산의 순서가 뒤바뀔 경우
- 여러 프로세스가 임계구역 안에서 실행될 수 있다.
- signal 써야할 곳에 wait를 쓴 경우.
- 세마포를 사용할 수 없다.
- 프로세스가 wait나 signal, 또는 둘 다 빠뜨릴 경우.
- 상호 배제 위반 or 영원히 locking
- 프로그램의 세마포에 대한 wait, signal의 연산의 순서가 뒤바뀔 경우
모니터 사용법
- 추상화된 데이터 형(ADT)
- 데이터와 데이터 조작 함수들의 집합을 하나의 단위로 묶어 보호한다.
- 함수의 구현은 ADT의 특정 구현과는 독립적이다.
- 모니터 형
- 모니터 내부에서 상호 배제가 보장되는 프로그래머가 정의한 일련의 연산자 집합
- 변수들의 선언을 포함하고 있는데, 모니터 내에 정의된 함수만에 접근할 수 있다.
- 모니터 안에 항상 하나의 프로세스만에 활성화되도록 보장해 준다.
- condition
- condition x; x.wait(), x.signal()
세마포를 이용한 모니터의 구현
- mutex 라는 이진 세마포
- wait(mutex), signal(mutex)
- 모니터 구현 시, signal-and-wait 기법 사용
- signaling 프로세스는 실행 재개되는 프로세스가 모니터를 떠나든지
- wait 할 때까지 자신이 기다리던지
- 자신이 기다리기 위해 next라는 이진 세마포 추가 필요.
- wait 할 때까지 자신이 기다리던지
- signaling 프로세스는 실행 재개되는 프로세스가 모니터를 떠나든지
- 진짜 무슨 소리인지 모르겠어요
모니터 내에서 프로세스 수행 재개
- 여러 프로세스가 대기 중일때, 어떤 프로세스가 수행 재개될 것인가
- conditinal-wait
x.wait(c)- wait 연산이 호출 될 때, 값이 계산된다.
- c의 값은 우선순위 번호
- ResourceAllocator 모니터
- 한 개의 자원을 여러 프로세스 사이에 할당해 준다.
- 자원 할당 필요시, 자원 사용 최대 시간 설정
- 가장 적은 시간을 희망한 프로세스에 자원 할당
- 문제
- 프로세스가 자원에 대한 허락 없이 액세스할 경우
- 프로세스가 자원에 대한 허락 이후, 방출하지 않을 경우
- 프로세스가 자원에 대한 허락 없이, 방출할 경우.
- 프로세스가 자원에 대한 허락을 받은 다음, 방출없이, 또 요청할 경우
- 해결 (둘 다 지켜져야 함)
- 프로세스들이 정확한 순서에 맞추어 호출하는지 검사
- 비협조적 프로세스가 액세스 제어 프로토콜 사용치 않아서 상호 배제 규칙 경우를 무시하여 공유 자원 직접 액세스 하지않는다는 것을 보장해야 한다.
6.8 라이브니스
- 프로세스가 실행 수명주기 동안 “진행”되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성
- 라이브니스 실패
- 성능과 응답성이 나쁜 것이 특징
교착 상태
- 두 개 이상의 프로세스들이 대기중인 프로세스들 중 하나에 의해서만 야기될 수 있는 이벤트를 기다리는 상황
- 이벤트 : 자원의 획득과 방출
우선순위 역전
- 높은 우선순위 프로세스가 낮은 우선순위 프로세스에 의해 접근되는 커널 데이터를 읽거나, 변경할 필요가 있을 때 어려움.
- L < M < H
- 해결책
- 우선순위 상속 프로토콜
- 우선순위가 높은 프로세스가 필요로 하는 자원을 사용하는 낮은 프로세스에게 높은 우선순위를 상속한다.
평가
- CAS 기반 접근은 낙관적인 접근법
- 변수를 갱신 → 충돌 감지 (갱신 중인지 확인) → 갱신될 때까지 반복 시도
- 상호 배재 락킹은 비관적 전략
- 다른 스레드가 갱신 중이라고 가정하고 갱신 전에 비관적으로 락 획득
- 평가
- 경합 없음 : CAS 동기화 > 기존 동기화
- 적당한 경합 : CAS 동기화 >> 기존 동기화
- 심한 경합 : 기존 동기화 >> CAS 동기화
- 원자적 정수
- 기존 락보다 훨씬 가벼움
- 일반 변수에 대한 단일 업데이트에서 적합
- 스핀락
- 락이 짧은 다중 처리기 시스템에서 적합
- mutex
- 세마포보다 간단, 오버헤드 적음
- 임계구역에 대한 접근 보호에 적합
- 세마포
- 한정된 수의 자원에 대한 접근을 제어하는 것
- reader-writer 락, mutex 락
- reader-writer 락이 선호된다.
- 모니터, 조건 변수
- 고급 도구
- 단순성, 사용 편의성
- 상당한 오버헤드가 있을 수 있음.
- 구현에 따라 심한 경합 상황에서 확장성 좋지 않을 가능성 높음
- 연구
- 더 좋은 코드 생성하는 컴파일러 설계
- 병행 프로그래밍 지원 언어 개발
- 기존 라이브러리 및 API의 성능 향상