프로그램적 해결법의 충족 조건
-
Mutual Exclusion
- 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
- 여러 프로세스가 동시에 공유 자원을 변경하는 것을 방지
-
Progress
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
- critical section이 비어있을 때, 프로세스가 자원을 이용할 수 있음.
-
Bounded Waiting(유한 대기)
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
- 특정 프로세스가 계속해서 다른 프로세스에게 밀려서 자원을 사용하지 못하도록 방지
-
가정
- 모든 프로세스의 수행 속도는 0보다 크다.
- 프로세스들은 실질적으로 작업을 수행하며, 무한히 대기하지 않음.
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
- 각 프로세스는 독립적으로 동작하며, 다른 프로세스의 상태나 속도에 대한 가정을 하지 않음
- 모든 프로세스의 수행 속도는 0보다 크다.
Semaphores
정수 변수로서 공유 데이터의 동시 접근을 제어하기 위해 사용. 세마포어는 일반적으로 P와 V라는 두 가지 atomic(원자적인) 연산에 의해서만 접근이 가능
P(S)
- P(S) 연산은 공유 데이터를 획득하는 과정, 일반적으로 "lock" 작업
- P(S) 연산은 S의 값이 양수인지 확인합니다. 만약 S가 0 이하인 경우, 즉 공유 데이터가 이미 다른 프로세스에 의해 사용 중인 경우, 현재 프로세스는 대기 상태로 전환
- 대기 상태에서는 "no-op" (no operation) 즉 아무 작업도 수행하지 않음.
: 다른 프로세스가 공유 데이터를 반납하여 S 값이 양수가 되고, 현재 프로세스가 다시 실행될 수 있도록 기다림 - S 값이 양수인 경우, 현재 프로세스는 공유 데이터에 대한 접근 권한을 얻고, S 값을 1 감소시킴
V(S)
- V(S) 연산은 공유 데이터를 사용하고 반납하는 과정, 일반적으로 "unlock" 작업
- V(S) 연산은 S 값을 1 증가시킴.
: 이는 공유 데이터를 사용한 후 해당 데이터를 반납하여 다른 프로세스가 접근할 수 있도록 해줌
Algorithm 1
0 프로세스는 turn이 0이 아니면 기다리고, 0인 경우 critical section 코드 처리.
turn을 1로 만들어 다음 1번 프로세스 들어가게 해준다.
=> progress 조건을 만족시키지 못함.
Algorithm 2
프로세스가 critical section에 진입하고자 하는 의사를 표시하기 위해 flag[i]를 설정
만약 flag[j]가 참인 경우, 즉 다른 프로세스가 critical section에 진입하고자 하는 의사를 표시한 경우, 현재 프로세스는 while 루프에서 기다림. => 끊임없이 양보하는 상황 발생 가능
Algorithm 3(Peterson's Algorithm)
모든 조건 만족하지만, Busy Waiting (계속 CPU와 메모리를 사용하면서 대기하는 상태) 문제가 발생
두 프로세스가 동시에 critical section에 진입하고자 하는 의사를 표시한 경우, 두 프로세스 모두 while 루프에서 대기하면서 CPU와 메모리를 계속 사용
Synchronization Hardware
- lock이 true로 설정되어 있다면, 다른 프로세스가 critical section에 들어가고 있는 것을 의미하므로 현재 프로세스는 대기 상태
- lock 변수가 false로 설정 => 이는 critical section에 진입할 수 있는 상태
Critical Section of n Processes
Mutex 값이 양수인 경우에만 critical section에 진입하고, 그렇지 않은 경우에는 대기 - busy-waiting 또는 spin lock이라고 불리는 문제가 발생 가능
=> 프로세스가 Mutex 값을 확인하고 양수가 아닌 경우에는 계속해서 반복문을 수행하며 CPU를 낭비
Block & Wake-up (=Sleep lock) 기법 개발
P(S) 연산
S.value 값을 1 감소시킴: S.value--;
S.value가 음수인지 확인.
S.value < 0인 경우:
현재 프로세스를 S.L (세마포어에 대한 Wait Queue)에 추가합니다: add this process to S.L;
프로세스를 Block 상태로 만듦: block();
=> 세마포어가 특정 자원의 사용을 제어하고 있는 상황에서 자원을 얻을 수 없는 프로세스를 대기 상태로 만드는 것입니다. 자원을 얻을 수 없는 경우, 프로세스는 block되어 다른 프로세스에게 CPU 자원을 양보하고 대기
V(S) 연산
S.value 값을 1 증가시킴: S.value++;
S.value가 0보다 작거나 같은지 확인.
S.value <= 0인 경우:
S.L (세마포어에 대한 Wait Queue)에서 프로세스 P를 제거: remove a process P from S.L;
프로세스 P를 깨워 Ready Queue로 보냄: wakeup(P);
=>V (S) 연산은 세마포어 값을 증가, 해당 값을 확인하여 대기 중인 프로세스를 깨워 Ready Queue로 보냄. 이는 세마포어가 특정 자원의 사용을 제어하고 있을 때, 대기 중인 프로세스가 자원을 얻을 수 있도록 하는 것
Block은 커널이 호출된 프로세스를 중단시켜 대기 상태로 만드는 작업. 프로세스가 세마포어를 사용하여 특정 자원을 얻을 수 없는 상황에서 발생
Block된 프로세스의 상태는 보류 상태로 변경되며, 그 프로세스의 PCB는 세마포어의 Wait Queue에 저장. 프로세스는 대기 상태에서 자원의 해제를 기다림
Wake-up은 block 상태에 있는 프로세스를 깨워 실행 가능한 상태로 전환하는 작업. Wake-up은 세마포어를 통해 대기 중인 프로세스를 깨워주고, 그 프로세스의 PCB를 Ready Queue로 옮김 - 대기 중인 프로세스는 다시 CPU 자원을 얻을 수 있음
Block은 자원을 얻을 수 없는 프로세스를 중단시켜 다른 프로세스에게 CPU 자원을 양보하고 대기
Wake-up은 자원이 해제되면 대기 중인 프로세스를 깨워 실행 가능한 상태로 전환
-
busy wait는 프로세스가 일정 조건이 충족될 때까지 반복문을 수행하며 계속해서 조건을 확인하는 방식 => Busy wait는 프로세스가 대기 상태에 있을 때 CPU 자원을 계속해서 소비하면서 기다림, 프로세스가 불필요하게 CPU 자원을 낭비하는 결과
-
Block Wake-up 기법은 프로세스가 필요한 자원을 얻을 수 없는 경우, 해당 프로세스를 block 상태로 만들고 다른 프로세스에게 CPU 자원을 양보. 대기 중인 프로세스는 자원이 해제되고 해당 자원을 얻을 수 있을 때까지 block 상태로 대기하며, 이후 깨어나 Ready Queue로 전환
Types of semaphore
Counting semaphore
- 도메인이 0 이상인 임의의 정수값을 가지는 세마포어
- 주로 resource counting에 사용 - 여분의 자원 counting 하는 용도로 사용
Binary semaphore(=mutex)
- 주로 mutual exclusion(lock/unlock)에 사용
- 0또는 1값만 가질 수 있는 semaphore
Deadlock and Starvation
이미 상대방이 소유한 자원을 갖고 있기 때문에 원하는 자원을 얻을 수 없게 되고, 이로 인해 두 프로세스는 영원히 대기 상태에 머무르게 됨 => 이러한 상태를 Deadlock
=> 작업자 A는 작업장 Y를 점유한 작업자 B가 작업장 X를 반납할 때까지 무한히 대기하고, 작업자 B도 작업장 X를 점유한 작업자 A가 작업장 Y를 반납할 때까지 무한히 대기
starvation
- 특정 프로세스가 자원을 얻지 못하고 무한히 기다리는 현상
[이화여자대학교 반효경 교수님 운영체제 강의를 정리한 내용입니다.]
