병행 제어

Sumin Kim·2022년 9월 19일
CSOS
1

✔ Operating system

목록 보기
5/5
post-thumbnail

본 글은 KOCW 이화여대 반효경 교수님의 운영체제 강의를 듣고 정리한 내용입니다.
http://www.kocw.net/home/m/search/kemView.do?kemId=1226304

  1. 동기화의 문제에 대해 알아본다
  2. 동기화 문제의 해결방법에 대해 알아본다.
  3. 세마포 연산에서 생길 수 있는 문제인 데드락과 동기화와 관련된 전통적인 세가지 문제에 대해 알아본다
  4. 동기화 문제 해결을 위해 세마포 이외의 모니터 방식에 대해 알아본다.
  5. 데드락의 문제, 발생 조건, 처리방법 네 가지중 하나인 프리벤션을 알아본다.

✔ Race Condition

  • 하나의 공유데이터를 여럿이 동시에 접속할때 생기는 문제점

  • CPU가 하나있든 여러개있든 문제가 생기는 이유 - 운영체제가 끼어드는 경우

    • ex) 한개일때,
      • A 라는 프로세스가 실행 중일때 프로세스는 운영체제에게 system call을 할 수 있고 할당시간이 끝나면 프로세스 B에게 넘어간다. B 또한 운영체제에게 system call 할 경우에는 운영체제의 동일한 데이터에 접근이 가능
      • 그 과정에서 race condition 문제가 생길 수 있음

  • Race condition이 언제 발생하는가

    • kernel 수행 중 인터럽트 발생시

      • 해결책 : 변수를 건드리기 전에 disable 시키고 interrupt가 끝나면 다시 enable 시킴

    • Process가 system call을 하여 kernel mode 로 수행중인데 context switch 가 일어난 경우

      • 해결책 : 커널모드에서 수행중일때는 CPU를 preempt하지 않고, 사용자모드로 다시 돌아갈때 preempt

    • Multiprocessor에서 shared memory 내의 kernel data

      • CPU 가 여러개있는 상황 (운영체제가 관여할때)
      • 1번 방법은 운영체제 커널 전체가 lock, 2번은 각 데이터별로 lock

🔹 동기화 문제

  • 공유데이터의 동시접근은 데이터의 불일치 문제를 발생시킬 수 있음
  • 일관성 유지를 위해 협력프로세스간의 실행순서를 정해주는 메커니즘이 필요
  • Race condition을 막기위해서는 concurrent process 는 동기화되어야함
  • The Critical-Section Problem : 공유데이터를 건드리는 문제
    • N개의 프로세스가 공유데이터를 동시에 사용하기를 원하는 경우
    • 각 프로세스의 code segment에는 공유데이터를 접근하는 코드인 critical section 이 존재
    • 문제점 : 하나의 프로세스가 critical section 에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야함


🔹 Solve Problem

  • Initial Attempts to solve..

  • Algorithms

    1. Algorithm 1

      • Synchronization variable
      • 차례를 왔다갔다 하면서 하겠다
      • 동시에 들어가면 안되는 문제는 해결했지만 아무도 안들어가있을때 들어가게해주는 part가 없음

    2. Algorithm 2

      • flag 를 두어 프로세스마다 critical section 에 들어가고싶다는 의중을 표함
      • 눈치를 보다 아무도 못들어가는 경우 생길 수 있음

    3. Algorithm 3 (Peterson's Algorithm)
      - Algo1,2 모두 사용

      - 깃발을 든 경우에 한해 turn 을 주어 알고리즘이 제대로 동작
      - spin lock (busy waiting) : 자원 낭비

  • 충족 조건
    1. Mutual Exclusion
    - 동시에 들어가면 안됨 (상호배타적으로)
    - 프로세스 p가 critical section 부분을 수행중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안됨
    2. Progress (진행)
    - 아무도 critical section 에 있지않은상태에서 들어가고자하는 프로세스가 있으면 들어가게해줘야함
    3. Bounded Waiting (유한대기)
    - 프로세스가 들어가려고 요청한 후 그 요청이 허용될때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야함

  • Synchronization Hardware

    • 하드웨어적으로 Test & modify를 atoic 하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결됨
    • Test & Set (a)
      • a라는 값을 읽어가고 그걸 True 로 만드는걸 한번에 수행하는 hardware

🔹 1. Semaphore

  • 일종의 추상자료형
  • S ; integer variable
    • 아래의 두가지 atomic 연산에 의해서만 접근 가능

      - P 연산 : 자원을 획득하는 과정, V 연산 : 자원을 반납하는 과정
      -Critical Section of n Processes
  • Block / Wakeup Implementation
    • Semaphore를 구두체처럼 정의해서 값이 하나있고, 줄세우는 리스트구조로
    • block 과 wakeup을 다음과 같이 가정
      • block : 커널은 block 을 호출한 프로세스를 suspend 시킴,
        • 이 process의 PCB를 semaphore에 대한 wait queue 에 넣음
      • wakeup(P) : block 된 프로세스 P를 wakeup 시킴
        • 이 process의 PCB 를 ready queue로 옮김
  • Implementation version of P() & V()
    • Semaphore 연산이 다음과 같이 정의됨
  • Then.. Which one?
    • Busy-wait 보단 Block/wakeup 이 더 좋음
      • 굳이 여분이 없는 상황에서 cpu를 계속 쓰는 busy-wait 은 비효율적
    • Block/wakeup overhead vs Critical section의 길이
      • Critical section 의 길이가 긴 경우(or 경쟁이 치열하면) block/wakeup이 적당
      • " 이 매우 짧은 경우(or 경쟁이 치열하지않으면)엔 block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
      • 일반적으로는 Block/wakeup 방식 WIN

  • Two types of semaphores
    • Counting semaphore
      • 도메인이 0이상인 임의의 정수값
      • 주로 resource counting에 사용 (자원의 갯수)
    • Binary semaphore (=mutex)
      • 0 또는 1값만 가질 수 있는 semaphore
        • 1인 경우는 동시접속을 못하게 하는 것 - lock
      • 주로 mutual exclusion (lock/unlock)에 사용

🔹 Deadlock and Starvation

  • Deadlock

    • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

  • Starvation

    • Indefinite blocking. 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

🔹 Classical Problems of Synchronization

  1. Bounded-buffer problem

    - Synchronization variables
    : Semaphore full = 0, empty = n, mutex = 1;


  2. Readers and Writers Problem

    • 한 process가 DB에 write 중일 때 다른 프로세스가 접근하면안됨
    • read는 동시 가능
    • solution
      • writer가 DB에 접근 허가를 아직 얻지못한 상태에선 모든 대기중인 readers를 다 DB에 접근하게해줌

      Shared data:

      • DB 자체
      • readcount; //현재 DB에 접근중인 reader의 수

      Synchronization Variables

      • mutex // 공유변수 readcount를 접근하는 critical section의 mutual exclusion 보장을 위해 사용
      • db // Reader와 writer가 공유 DB 자체를 올바르게 접근하게하는 역할

    • Starvation 발생가능

  3. Dining-Philosophers Problem

    • Synchronization variables
    • 앞의 solution의 문제점
      • Deadlock 가능성 있음
        (모든 철학자가 동시에 왼쪽젓가락을 집은 경우)
    • Solution
      • 4명의 철학자만이 테이블에 동시에 앉도록
      • 젓가락 두개 모두 집을 수 있을때만 젓가락을 잡도록
      • 짝수 철학자는 왼쪽부터 홀수철학자는 오른쪽부터 (비대칭적)

🔹 2. Monitor

profile
Sumin Kim
이전 포스트

CPU 스케줄링

0개의 댓글