일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- Activity
- 문맥 교환
- 동기 비동기
- 인터락 함수
- 유저 모드의 동기화
- Light Weight Process
- Non-Preemptive
- Process Control Block
- 커널 모드의 동기화
- Stack영역
- 스레드
- 은행원 알고리즘
- 교착 상태
- Heap영역
- 뮤텍스(Mutex)
- 스레드 동기화
- 프로세스 제어 블록
- 방금 그 곡
- 경량 프로세스
- 임계 구역
- Reentrant
- 유저 모드
- 커널 모드
- The DIning Philosopher Problem
- 프로세스
- 모니터(Monitor)
- The Banker's Algorithm
- Multi-level Queue
- 블로킹 논블로킹
- 프로세스 상태 전이도
Blog For Me
[운영체제] Test_and_Set, Compare_and_Swap, Bounded-waiting 본문
최근에 lock 방법이 지닌 문제점을 해결하기 위하여 소프트웨어적 방법을 이용하기보다는 더 이상 쪼개지지 않는 원자적 명령어로 구현하거나 Interrupt 제어로 해결한다.
하드웨어 명령어
lock 함수 코드부분
void lock(struct lock *i) {
while(i->held);
i->held=1;
}
이 lock 함수의 문제점은 A 프로세스가 2번 라인의 코드를 실행하고 다음에 3번 라인의 코드를 실행하기 직전에 Interrupt 걸렸을 상황에서 두드러진다. 즉, A 프로세스가 3번 코드인 'i->held=1'을 실행하기 직전에 Interrupt 걸려서 B 프로세스로 전환된 것이다. 그럼 B 프로세스는 아직 held 값이 0인 걸 보고 바로 임계영역에 진입해버리므로 Race Condition이 발생하게 된다. 이러한 상황이 발생하는 이유는 진입 후 바로 held를 1로 바꿔줘야 하는데, 이 코드가 2개의 라인에 걸쳐 이루어지므로 남이 낄 수 있는 여지가 발생하기 때문이다.
Test_and_Set은 이런 문제를 해결하기 위해 위의 2~3번 코드를 한 라인으로 구현한다.
while(test_and_set(&lock));
쪼개지지 않고 한번에 수행하므로 이를 atomic operation이라 한다. 이는 쪼개질 수 없는 하나의 Unit이다. 이는 하드웨어 명령어 API를 이용한 것이고, 또 다른 atomic operation으로는 compare_and_swap이 있다. 이로써 속도도 더 빠르고 쪼개질 수 없다는 특징을 지닌다.
test_and_set 함수
do {
while(test_and_set(&lock)); //lock이라는 변수의 값을 먼저 test해서 값이 false인지 true인지 return
// 이후 lock이라는 변수를 true로 설정
//critical section
lock = false; // 임계 구역 나올때 lock을 false로 설정
//remainder section
} while(true);
compare_and_swap
while(true) {
// compare_and_swap은 세 개의 매개변수를 필요로 한다.
// 첫 번째 매개변수와 두 번째 매개변수가 같을 때, 즉 lock이 0일 때에만 lock을 1로 설정
// return 할 때는 항상 lock의 상태를 반환
// lock이 걸려 있지 않으면 0을 반환한 후 1로 바꿔주고, lock이 걸려 있으면 1 반환 후 그대로 둔다.
// lock이 1이면 while문에서 빠져나오지 못하고 무한반복한다.
while(compare_and_swap(&lock, 0, 1) != 0);
//critical section
lock = 0; // 임계 구역에서 일을 마치고 다른 프로세스가 들어갈 수 있게 lock을 해제한다.
//remainder section
}
Bounded-waiting mutual exclusion
위의 코드들은 mutual-exclusion을 만족시키나 bounded-waiting requirement, 즉 한정 대기 조건을 만족시키지 못한다. 따라서 이를 해결하기 위해 compare_and_swap()을 이용하면서 모든 임계영역 해결조건을 만족시키는 알고리즘이 존재한다.
while(true) {
waiting[i] = true; // i번째 프로세스가 공유 자원을 쓰고 싶다는 신호
key = 1;
while(waiting[i] && key == 1) // i번째 프로세스가 쓰고 싶어도 key가 1이라면 들어가지 못하고 while문에 머무름
key = compare_and_swap(&lock, 0, 1); //key는 compare_and_swap을 이용해서 lock을 반환, 누가 사용하고 있으면 진입 불가능
waiting[i] = false; // 임계 영역에 진입할 수 있는 6번 라인에 오면 임계 영역 코드를 수행중이므로 기다리는 대기 배열에서 빼준다.
//critical section
// i 번째 프로세스가 독차지 하지 않도록 다른 프로세스에 권한을 넘겨주는 코드이다. 실행 시켜줄 j 프로세스를 찾는다.
// 예를 들어 n이 7일때, i가 1이라면 j는 2가 되고, i가 2라면 j는 3이 되는 방식이다.
// 여기서 j가 자원을 쓰고 싶어하지 않으면 수행시킬 필요가 없으므로 자원 쓰고 싶어하는 j가 나올 때까지 while문을 돌려준다.
j = (i + 1) % n;
while((j != i) && !waiting[j])
j = (j + 1) % n; // j를 1씩 증가시킨 후에 n으로 나누었을 때의 나머지를 j 값으로 설정한다.
if(j == i) //j가 i일 경우는 한 바퀴 다 돌았는데 공유자원을 사용하고 싶어하는 프로세스가 없다는 의미이다.
lock = 0; // 이때 lock을 해제해준다. (lock이 0인 의미는 lock을 해제해주는 의미이다.)
else // 이 때는 공유자원을 사용하고 싶어하는 프로세스를 발견했다는 의미이다.
waiting[j] = false; // 이때 waiting[j]를 false로 바꿔주는데, j는 4번 while문에서 계속 무한루프에 있는 상황이었다.
// 그래서 false로 바꿔주면 while문에서 빠져나와 임계 구역에 진입할 수 있다.
// 이후 i번째 프로세스는 남은 코드 수행 후 종료한다.
// lock은 풀 필요가 없는데, 어차피 j가 사용하면 lock은 유지되어야 하기 때문이다.
//remainder section
}
참고자료
https://jhnyang.tistory.com/41?category=815411
'컴퓨터과학 > 운영체제' 카테고리의 다른 글
[운영체제] 동기화 문제들(The Dining-Philosophers Problem) (0) | 2021.12.06 |
---|---|
[운영체제] 동기화 관련 여러 문제(The Bounded-Buffer Problem, The Reader-Writer Problem) (0) | 2021.12.05 |
[운영체제] Peterson's Algorithm(피터슨의 알고리즘) (0) | 2021.12.03 |
[운영체제] lock & busy-waiting 문제 (0) | 2021.12.03 |
[운영체제] 뮤텍스, 모니터, 세마포어 차이점 (0) | 2021.11.30 |