Race Condition

게시 2023/11/10 업데이트 2024/08/29

By Mascari4615

16 분읽는 시간

@0418

병행처리 Concurrent Processing와 경쟁상황Race Condition
- 병행처리
  - 하나의 CPU가 여러 개의 프로세스를 조금씩 번갈아 처리
  - 거시적 관점에서 여러 개의 프로세스를 한꺼번에 처리하는 효과
  - 어느 순간에 보면 오직 하나의 프로세스만이 처리되지만, 공유 변수를 접근한다면 경쟁상황이 발생할 수 ‘있음’ = 무조건 발생이 아님 (병렬처리보다는 빈도가 낮음, 섞일 수도 있음)
병렬처리 Parallel Processing와 경쟁상황
- 병렬처리
  - 다수의 CPU가 여러 개의 프로세스를 한꺼번에 처리
  - 어느 순간에 보면 여러 개의 프로세스들이 처리
  - 공유변수를 접근한다면 경쟁상황이 더욱 심하게 발생할 수 ‘있음’ = 무조건 발생이 아님 (근데 병행처리보다는 빈도가 높음, 섞일 수도 있음)
임계영역 Critical Section
- 경쟁상황이 발생되어 처리의 오류를 일으킬 수 있는 부분
상호배제
- 임계 영역에서는 오직 하나의 프로세스만이 진입할 수 이ㅆ도록함
- 상호배제는 잠금 Looking 장치와 채제 UnLock 장치로 실형
프로그램 동기화 Process Synchronization
- 임계 영역을 설정하고 그리고 그 어 구분에다가 상호배제 잘치를 잘 설치
상호배제 절차 (잠금과 해제 장치)의 조건
- 계속 진행
  - 임계 영역에 진입한 프로세스가 없을 때는 원하는 프로세스가 곧바로 진입할 수 있어야함
- 항호 배제
  - 임계 영역에 진입한 프로세스가 존재하면 다른 프로세스들의 진입을 불허되어야 함
- 대기 한정
  - 임계 영역 진입을 원하는 프로세스들은 랜덤하고 공평하게 진입할 수 있는 기회가 주어져야 함
상호배제의 구현 방법
- 순전히 SW로만 구현하는 방법
- HW의 지원을 받아 구현하는 방법

@0420

미완성 SW 상호배제 시도들
공통 깃발 체크 방법
- whilie(flag == 1); flag = 1;
- 병렬 처리일때 거의 동시에 진입하면 경쟁상황 발생 가능
- 병행 처리일때 한 프로세스가 대기 이후 flag = 1; 처리 직전, 주도권이 다른 프로세스로 넘어가고, 해당 프로세스에서도 flag = 0; 처리 직전, 주도권이 다른 프로세스에 넘어가면 경쟁상황 발생 가능 (공유 변수가 덮어씌워지는)
자기 깃발 표시 방법
- while(flag[1] == 1); flag[0] = 1;
- 공통 깃발 체크 방법과 유사
- flag[0] = 1; while(flag[1] == 1);
차례지키기 방법
- 동시에는 못들어감
- 근데 자기 차례가 아니면 공회전 하는 경우 +> 계속 진행 X

@0504

Spin Lock 스핀 록 (if then else white, TAS SAWP, 빙글빙글 돈다 - CPU를 쓴다)
- 앞에서 제시된 SW 및 HW 상호배제 기법들은 모두 바쁜 대기 기반의 잠금장치들임 ← 스핀록
- 이런 방법들은 때에 따라 CPU 낭비가 심하고 임계 영역에 진입한 프로세스가 비정상적으로 활동하면 파급효과가 큼
- 따라서 보다 편리하고 보편적인 개념의 잠금장치가 필요 ← 세마포
세마포 (빙글빙글 돌지 않고 대기)
- S 열쇠
- P(S) 열쇠를 가져가는 연산 (열쇠 -= 1)
- P(S) 연산 시 열쇠가 없으면 (열쇠 == 0) 대기 → OS가 처리
- V(S) 열쇠를 돌려놓는 연산 (열쇠 += 1)
이진 세마포와 카운팅 세마포
- 이진 세마포 : 주로 상호배재 용으로, 박자 맞추기
  - 세마포 변수 S를 0 or 1로 초기화하고 0 or 1 이외의 값을 사용치 않는 경우
  - 1로 초기화 시 상호 배재, 0으로 초기화 시 보조동기화용으로 사용됨
    - While(1) P(S) … (V), V(S) P(S), V(S) 이후 기다렸다가 P(S) 하는
- 카운팅 세마포 : 박자 맞추기, 리소스 카운팅
  - 기능은 똑같은 데 1 이상의 값을 사용하는
  - S를 Buffer 개수로 생각, 가져갈 때 P(S)
  - 왜 S -= 1 일반 연산 안씀 ? → 이거 자체가 임계 영역
생산자-소비자 문제 Producer-Consumer Problem
- 개념
  - 한 쪽 프로세스는 데이터를 생산하여 전달하고, 다른 한 쪽 프로세스는 전달 받은 데이터를 처리하여 소모함
  - E Empty, F Full, M Mutual Exclusion (상호배재용 = 열쇠?)
  - I.E. Circular Queue 에 한 쪽은 데이터를 넣고, 한 쪽을 데이터를 꺼냄
  - 소비자 (P(F), P(M), F 하나 채움, 0이면 대기, V(M), V(F))
  - 생산자 (P(E), P(M), E 하나 채움, 0이면 대기, V(M), V(E))
  - I.E. 박자 맞추기
  - 소비자 While P(S) Process(Data)
  - 생산자 While GetData() V(S)
Dining Philosophers Problem 식사하는 철학자들 문제
- 개념
  - 잠금 (세마포)이 해재디기를 영원히 기다리는 상황, 즉, 교착 상태를 살표보는 상징적 문제
모니터의 개념
- 프로그래밍 언어 수준에서 제공되는 고수준 상호배재 장치
  - 함수(서브루틴, 메소드) 형태로 구분된 임계 영역들의 모임
  - 모니터 내에서는 오로지 하나의 프로세스만이 진입 가능
  - 모니터는 고유의 식별 이름을 가짐
  - 세마포의 잘못된 사용에 따른 오류 가능성을 개선
  - @ 알잘딱으로 한 놈만 들어가도록 감시
모니터의 내부(조건) 큐
- 모니텅 진입한 프로세스가 시간이나 자원을 기다리기 위해 잠시 실행을 유보해야 하는 상황
- 해당 프로세스는 모니터 잠금 장치를 해제하고 자신은 내부 큐에서 대기
- 다른 ㄹ프로세스가 모니터에 진입하여 처리르 마치고 나가면서, 필요한 경우 내부 큐에 대기중인 프로세스에게 잠금을 인계 ← 대기 중이던 프로세스가 모니터 내에서 실행을 제개
자바 모니터
- 자바는 객체 단위로 모니터를 형성
- 해당 모니터에는 synchronized 메소드들만 포함함

@0509

교착 상태 Deadlocks
- 고장난 좌물쇠 → 나가지도 못하고 나오지도 못함
- 진퇴양난 → 영원히 기다리는 상황
- 주요 원인 : 고장이나 기타 이유로 인한 자원의 부족
컴퓨터 자원의 유형
- HW 자원과 SW 자원
- 선점 가능한 자원과 선점 불가능 자원
- 공유 가능 자원과 배타적 사용 자원
컴퓨터의 자원 관리 모델
- 요청 → 사용 → 반납 (묵시적, 명시적)
  - 프로세스들은 OS에게 필요한 자원을 요청
  - 지원 요청은 시스템 콜을 사용하여 이루어짐
  - 유닉스/리눅스의 대표적인 자원 요청 시스템 콜은 open(), 자원 반납 시스템 콜은 close()
교착 상태의 필요조건
- 자원의 배타적 사용 Mutual Exclusion
- 자원의 점유 대기 Hole & Wait
  - 자원의 부분 할당 Partial Allocation
- 자원 비선점 No Preemption
- 자원에 대한 환형 대기 Circular Wait
  - 자원 할당 그래프 RAH Resource Allocation Graph로 판별 가능
교착 상태 대응 방안
- 교착 상태 예방 Prevention
  - 교착 상태의 필요조건 중 하나가 성립하지 않는 할당정책 도입
- 교착 상태 회피 Avoidance
  - 자원을 할당하면서 교착 상태 발생 가능성이 있으면 추가 할당 보류
- 교착 상태 탐지 및 복구 Detection & Recovery
- 교착 상태 방치 Don’t Care

@0511

교착 상태 예방 Prevention
- 교착 상태의 필요조건 중 하나가 성립하지 않는 할당정책 도입
- 자원의 배타적 사용 조건 제거
  - 컴퓨터 자원의 대부분은 배타적으로 사용되어야함, 도입 불가
- 자원의 점유 대기 조건 제거
  - 사용할 자원 전체를 한꺼번에 할당할 수 있을 때까지 기다림
  - 여러 종류의 자원이 필요한 프로세스의 기아 상태 가능성
  - 자원을 미리 확보함으로써 활둉도 저하, 도입 곤란
- 자원의 비선점 조건 제거
  - 자원이 부족하면 이지 점유 중인 자원을 강제 회수
  - 롤백 Rollback, 등 큰 비용 동반, 도입 곤란
- 자원에 대한 환형 대기 조건 제거
  - 모든 자원에 일련 번호를 부여하고, 프로세스에게 자원을 할당할 때는자원의 번호 순서대로만 할당, 환형 대기 조건 발생하지 않음
교착 상태 회피 Avoidance
- 자원을 할당하면서 교착 상태 발생 가능성이 있으면 추가 할당 보류
- Safe 상태와 Unsafe 상태
  - Safe State
    - 자원 할당이 이루어지더라도 교착 상태가 결코 일어나지 않는 상태
    - 현재 남은 자원이 부족하더라도 점유 중인 프로세스 종료로 자원이 반납되어 모든자원 할당 요구를 만족-하는 시나리오가 존재하면
  - Unsafe State
    - 자원 할당이 이루어진 후, 이후의 모든 자원 할당을 만족시킬 시나리오가 존재하지 않는 경우
- 자원 할당 그래프 예약 간선, 안전 상태 판별, 교착 상테 회피
  - 자원 할당 그래프의 예약 간선
    - 현재요청된 자원을 할당 햇다는 가정 하의 자원 할당 그래프
    - 예약 간선이 포함된 자원 할당 그래프로부터 안정 상태 여부 판별
    - 안전 상태가 아니면 자원 요청 보류
- Dijstra의 은행가 알고리즘 Banker’s Algorithm
  - 개념
    - 자원에 대한 잠재 수요 및 재고 현황으로부터 안전 상태 식별
교착 상태 탐지 및 복구 Detection & Recovery (주기적으로, 가끔)
- 자원 할당 그래프로부터 안전 상태 여부 판별
  - 점유 대기 현상 (환형 대기, 사이클, Cycle) 이 존재하는지 조사
  - 사이클이 존재한다고 하여 반드시 교착 상태는 아님
- 사이클 탐색 알고리즘
- 교착상태 복구
  - 교착 상태를 복구 (해제)하기 위해서는 자원 강제 회수가 불가피
    - 프로세스 단위의 자원 회수
      - 희생 Victim 프로세스를 선정하고, 그 프로세스의 점유 자원 전체를 회수
      - 자원이 부족하면 계속해서 희생 프로세스를 선정하여 회수
      - 자원을 회수 당한 프로세스는 강제 종료 (Roolback)
    - 개별 자원 단위의 회수
      - 희생 프로세스가 점유하고 있는 자원 중 일부만 회수
      - 자원의 일부를 회수당한 프로세스는 후퇴하여 재실행 Rollback
교착 상태 방치 Don’t Care
- 교착 상태 예빵, 회피, 탐지 및 복구는 심각한 부담 (성능 저하)를 동반
  - OS는 교착 상태와 관련하여 어떠한 활동도 하지 않음
  - 교착 상태에 관계되어 실행이 중단된 프로세스들은 사용자가 인식하고 처리
  - 대부분의 사용 OS에서 채택

💫Computer, 🌑Computer-OS

Computer OS Race-Condition

인기 태그