오래 못 할 짓 하지 않기
[ 운영체제 ] 15. 동기화와 관련된 문제 해결 본문
https://velog.io/@chy0428/OS-HW-support-for-Synchronization
위 두 블로그에 정리 잘 되어 있음.
우선 동기화와 관련하여 생기는 문제를 해결하는 방법은 여러 가지가 있다.
하지만 어떠한 방법이든 다음 3가지 조건을 충족해야한다.
1. 상호 배제 ( Mutual exclusion )
: Critical section에는 1개의 프로세스만 접근할 수 있다.
2. 진행 ( Progress )
: 자신의 Critical section에 실행되고 있는 프로세스 X
and Critical section에 들어오려고 하는 프로세스가 있을 때
→ 무기한 연기되지 않고 Critical section에 들어올 수 있어야 한다.
3. 한정된 대기 ( Bounded waiting )
: 프로세스가 Critical section에 들어가려고 할 때 각자 들어갈 수 있는 횟수에 제한이 필요하다.
Peterson's Solution
특징
1. 현대 컴퓨터 구조에서는 작동한다는 보장을 할 수 없음
2. 그러나 이 문제 해결하는 알고리즘 설명에는 좋다.
3. 두 개의 프로세스가 int turn / boolean flag[2] 를 공유한다.
● Peterson's Soulution 1단계 접근
turn = 0 으로 초기화하였고
j= 0 , i = 1로 가정해보자
j 프로세스의 모습이다. ( i 프로세스도 똑같이 생기고, i와 j위치만 바뀌어 있음 )
1번 프로세스에서 Critical Section에서 작업을 하고 있다면
do 아래 While에서 기다리고, 다 마치면 turn = 0로 바뀐다.
하지만 이는 Progress를 위반한다.
turn = 0 일 때, P1이 준비상태가 되어 Critical section에 들어가려고 하면 turn != 1이라서
계속 While을 돈다.
( turn =1 일 때 되어야 하는 애 먼저 시작하면 계속 기다려야 한다는 뜻 같음 )
● Peterson's Soulution 2단계 접근
프로세스 개수만큼 flag 를 만든다.
초기값은 모두 false이고
flag[i]가 true면 i번 프로세스가 준비되었다는 의미이다.
Progress 위반
하지만, P0에서 flag[0]이 true가 되고 critical section에 들어가려고 하는데
그 순간 P1에서 flag[1]를 true가 되게 한다면, 임계구역에는 아무 프로세스도 접근을 하지 못했기에
둘 다 대기하게 된다.
● Peterson's Soulution 3단계 접근
이번에는 flag랑 turn 둘 다 사용한다.
flag 같은 경우에는 둘 다 True일 수 있지만
turn 은 하나만 가능하다.
따라서 flag 모두 true로 되어있더라도 turn 값에 따라 조정이 되므로
Critical section에 하나의 프로세스만 진입하는 걸 보장해준다.
이 방식은 [ 상호배제 , 진행, 한정된 대기 ] 세 조건 모두 만족한다.
● 한계
- 현대 컴퓨터 구조에서는 동작할지는 보장할 수 없다.
- Performance를 올리기 위해서, 프로세서나 컴파일러는 종속성이 없는 작업의 순서를 변경할 수 있다.
▶ 이는 MultiThread에서 inconsistent 혹은 unexpected results를 야기한다.
→ 이를 해결하기 위해서 하드웨어의 지원을 받는다.
Synchronization Hardware
● [ 배경 ]
Single - core 프로세서면 비선점으로 작동시킬 수 있기 때문에 interrupt 없이 돌아갈 수 있다.
하지만, 그렇게 돌리기엔 비효율적이라 Multicore로 작동시킨다.
● [ 방법 ]
- Memory Barriers
- Hardware instructions
- Atomic variables
Memory Barriers
해당 명령어는 LW,SW 같은 연산이 실행되기 전에,
현재 프로세스에서 진행되는 저장 작업이 메모리에서 완료되도록 한다.
뭔가 급하게 와다다닥 하려고 할 때
" 얘들아 잠깐 정리하고 천천히 가자." 하는 역할
따라서 현재 프로세스에서 실행되어야 하는 LW ,SW 작업을 하고 그 다음 명령어들을 실행한다.
이는 다른 프로세스들도 급하게 섞이는 값들이 아닌 다 정리된 값(동기화 된 값)을 memory에서 참조할 수 있다.
Hardware랑 가까운 명령어이므로 Low level operation
컴파일러와 프로세서는 효율성을 위해 연산 순서를 바꿀 수도 있다.
하지만 memory_barrier는 연산 순서가 섞이지 못하게 해준다.
Thread 1에서 조건문에 걸려서 계속 memory_barrier에 있는다.
▶ Thread 2에서 x주소에 100을 넣는다. (무조건 얘가 flag=true보다 먼저 실행됨)
▶ 그 다음 flag = true 실행
▶ 출력은 100.
피터슨 솔루션에 적용하면 다음과 같다.
다른 프로세스들에게 다 멈추고 나 지금 저장한다.
▶ 다들 다시 시작해
Hardware instructions
: Hardware 에 관련된 명령어를 한 덩어리로 만들면
그 사이에는 Interrupt가 생기지 않으므로 값을 바꿔줄 때 Unexpected 값이 생기지 않는다.
이렇게 만들어진 명령어는 Atomic하게 실행된다.
● Test and Set
- Lock 변수는 False로 초기화 시킨다.
- 해당 프로세스에서 임계 구역이 끝나면 Lock 변수를 false로 바꾸고 나와서
다른 프로세스가 접근할 수 있도록 한다.
● 한계
- Lock 변수가 True라면 계속 사용하므로, Bounded Waiting 조건은 충족시키지 못한다.
Mutual exclusion은 해결함.
● Swap
현재 주어진 값이 해당 프로세스가 원하는 값인지 판단하는 Atomic한 함수를 만든다.
lock의 값의 기대값 0이면 1을 Return한다.
(그냥 예상값,현재 값 두 개 맞추면 뒤에 마지막 인자를 return한다)
● 한계
- Lock 변수가 True라면 계속 사용하므로, Bounded Waiting 조건은 충족시키지 못한다.
Mutual exclusion은 해결함.
하지만 코드에서 3줄만 추가하면 Bounded Waiting 도 가능하다.
▶ 다음은 i번 프로세스에서 실행되는 코드이다.
이 i번째 프로세스가 Critical section에 들어가는 건 두 가지 경우가 있다.
Waiting[i] == False 혹은 key == 0 일 때임.
▶ Waiting[i] 가 False가 되는 경우 : 다른 프로세스가 Critical section을 떠날 때
▶ Key 가 0이 되는 경우 : compare_and_swap에서 lock을 통해서만 가능 ( lock이 1로 바뀌면 탈출 가능 )
Bounded waiting을 해결하기 위한 부분은 주황색으로 칠해져있다.
근데 이거는 큐 형식으로 해서 계속 볼 수 있게 하는 것 같음
근데 이거 j = ( j+1)%n이어야 하는 거 아닌가 싶음
Atomic variable
동기화를 위해 사용되는 Compare_and_swap 를 구현하는데 필요한 tool 중에 하나이다.
Interrupt 없이 순서를 보장해주는 변수
(출처)
운영체제 공룡책 6단원 정리 (witch.work)
https://velog.io/@chy0428/OS-HW-support-for-Synchronization
한동대학교 고윤민교수님 - 운영체제
'3학년 1학기 > 운영체제 (OS)' 카테고리의 다른 글
| [ 운영체제 ] 17. Liveness / Sychronization example (0) | 2024.05.07 |
|---|---|
| [ 운영체제 ] 16. Sychronization tool (0) | 2024.05.06 |
| [ 운영체제 ] 14. 동기화 (Synchronization) (0) | 2024.04.19 |
| [ 운영체제 ] 13. 리눅스 스케줄러 (0) | 2024.04.19 |
| [ 운영체제 ] 12. Scheduling ( Multiple - Process / Real - Time CPU ) (1) | 2024.04.16 |
