Initial Attempts to Solve Process Synchronization Problem
프로세스 간 동기화 문제를 해결하기 위한 초기의 방법론
프로그램적 해결법의 충족조건
mutual exclusion 상호배제
프로세스 Pi 가 critical section 부분을 수행중이면 다른 모든 프로세스들은 그들의 critical section 에 들어가면 안된다.
progress
아무도 critical section 에 있지 않은 상태에서 critical section 에 들어가고자 하는 프로세스가 있으면 critical section 에 들어가게 해주어야 한다.
bounded waiting 유한대기
프로세스가 critical section 에 들어가려고 요청한 후 부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section 에 들어가는 횟수에 한계가 있어야 한다.
요청한 후에 특정시간 이내에는 들어갈 수 있어야 한다.
가정
모든 프로세스의 수행속도는 0보다 크다.
프로세스들 간의 상대적인 수행속도는 가정하지 않는다.
첫번째 알고리즘 - turn 변수 사용
mutual exclusion 은 충족하지만, progress 는 충족하지 못한다.
과잉보호가 발생하게 됨. 반드시 교대로 한번씩 들어가야 하는데, 그가 turn 을 내 값으로 바꿔줘야만 내가 들어갈 수 있다.
특정 프로세스가 더 빈번히 critical section 을 들어가야 한다면 어떻게 될까?
두번째 알고리즘 - 플래그
플래그가 동시에 켜질 때, 서로 플래그가 켜진 상태기 때문에 아무도 while 문 안으로 진입하지 못하는 문제가 발생할 수 있다.
세번째 알고리즘 - 피터슨 알고리즘 - 플래그와 turn 변수 모두 사용
mutual exclusion, progress, bounded waiting 의 세 가지 조건을 모두 만족하는 알고리즘이다.
둘다 critical section 에 들어가고자 할 때, turn 을 따진다.
둘다 들어가고 싶지 않다면, turn 대로 들어간다.
발생할 수 있는 문제점 : busy waiting = spin lock
Synchronization Hardware
고급언어에서는 필연적으로 instruction 이 여러 개로 나누어지기 때문에 이런 알고리즘들을 고민해야한다.
데이터를 읽는 명령과 쓰는 명령을 동시에 수행할 수 없기 때문에 발생하는 문제들이다.
하지만 하나의 instruction 으로 데이터을 읽고 쓰는 것을 동시에 수행할 수 있다면, 사실 고민할 문제가 아니다.
하드웨어적으로 test & modify 를 atomic 하게 수행할 수 있도록 지원하는 경우, 앞의 문제는 간단히 해결될 수 있다.
test and set a : a의 값을 읽고 쓰는 것을 동시에 수행하는 명령
하지만 프로그래머가 이런 일을 계속 프로그램 내에서 하는 것은 굉장히 불편한 일이다. 이때 우리는 semaphore 를 이용할 수 있다.
Last updated
