🌑 Race Condition

---

@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에서 채택