📀 운영체제
12. 동기화 문제의 해결책: Chapter 6. Synchronization Tools (Part 2)
락꿈사
2022. 6. 7. 11:29
6.3 Peterson의 해결안Peterson's Solution
- Dekker's Algorithm
- 2개의 프로세스를 위한 해결책
- Eisenberg & Mcguire's Solution
- N개의 프로세스가 lower bound N-1 waiting time을 보장하는 해결책
- Peterson의 해결안
- critical section에 대한 고전적인 소프트웨어 기반 해결책
- 현대 컴퓨터 구조가 load & store 같은 기본적인 기계어를 수행하는 방식 때문에 이러한 구조에서 올바르게 수행한다고 보장할 수 는 없음
- 그러나 critical section 문제를 해결하기 위한 좋은 알고리즘적인 설명을 제공
- 상호 배제, 진행, 한정 대기의 요구 조건을 중점으로 다루는 소프트웨어 설계를 하는 데 필요한 복잡성을 잘 설명함
Peterson의 해결안
- 임계구역과 나머지 구역을 번갈아 실행하는 2개의 프로세스로 한정
- 두 프로세스가 두 개의 데이터 항목을 공유함
- int turn;
- 임계구역으로 진입할 순번을 나타냄
- turn == 0이면 P0이 임계구역에 진입할 수 있음
- turn == 1이면 P1이 임계구역에 진입할 수 있음
- boolean flag[2];
- 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타냄
- flag[0] == true이면 P0이 임계구역에 진입할 준비가 됨
- flag[1] == true이면 P1이 임계구역에 진입할 준비가 됨
- int turn;
- 코드
#include <stdio.h>
#include <pthread.h>
#define true 1
#define flase 0
int sum = 0;
int turn;
int flag[2];
void *producer(void *param){
int k;
for (k=0; k<100000; k++){
// entry section
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1)
;
// ciritical seciton
sum++;
// exit section
flag[0] = flase;
// remainder section
}
pthread_exit(0);
}
void *consumer(void *param){
int k;
for (k=0; k<100000; k++){
// entry section
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0)
;
// ciritical seciton
sum--;
// exit section
flag[1] = flase;
// remainder section
}
pthread_exit(0);
}
int main(int argc, char const *argv[])
{
pthread_t tid1, tid2;
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
printf("sum = %d\n", sum);
return 0;
}
- 위 이미지를 통해 앞서 말했듯 Peterson의 해결책은 최신 컴퓨터 아키텍처에서 동기화가 보장 되지 않음을 알 수 있음
- 주된 이유는 시스템 성능을 향상하기 위해 프로세서 또는 컴파일러가 읽기 및 쓰기 작업을 재정렬 할 수 있기 때문임
6.4 동기화를 위한 하드웨어 지원
- 임계구역 문제를 해결하기 위한 3가기 하드웨어 명령어 지원
- 메모리 장벽Memory barriers
- 컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근시 보장되는 사항을 결정한 방식
- 하드웨어 명령Hardware Instructions
- 원자적 변수Atomic Variables
- 메모리 장벽Memory barriers
- 이러한 프리미티브 연산은 동기화 도구로 직접 사용될 수 있거나 더 추상적인 동기화 기법의 기초 형태로 사용될 수 있음
하드웨어 명령Hardware Instructions
- 두 워드의 내용을 원자적Atomically으로 교환swap 할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서 특별한 하드웨어 명령어를 제공함
- test_and_set(boolean *target) 명령어
- 명령어가 원자적으로 실행됨
- 1) 임계영역에 진입할 수 있는지 확인 (target == true인지 확인)
- 2) target이 true인지 fasle인지 return 해줌
- 3) 임계 영역에 진입했다고 target을 true로 표시
- 위 3가지 작업을 원자적으로 수행 가능
- 상호 배제를 구현할 수 있음
- 명령어가 원자적으로 실행됨
do {
while (test_and_set(&lock))
;
lock = flase;
} while(true);- compare_and_swap(*target, int expected, int new_value) 명령어
- 명령어가 원자적으로 실행
- 1) 임계영역에 진입할 수 있는지 확인 (target == expected인지 확인)
- 2) target이 0인지 1인지 return 해줌 (target이 0이면 0반환, 1이면 1 반환)
- 2) 임계 영역에 진입했다고 target을 true로 표시
- 위 3가지 작업을 원자적으로 수행 가능
- 상호 배제 구현 가능
- 명령어가 원자적으로 실행
while (true) {
while (compare_and_swap(&lock, 0, 1) != 0) {
;
lock = 0;
}
원자적 변수Atomic Variables
- 일반적으로 compare_and_swap() 명령어는 상호 배제를 제공하기 위해서 직접 사용되지 않음
- 임계 구역 문제를 해결하는 다른 도구를 구축하기 위한 기본 구성 요소로 사용됨
- 그러한 도구 중 하나는 원자적 변수로, 정수 및 부울 과 같은 기본 데이터 유형에 대한 원자적 연산을 제공함
- 실습 코드
package com.os_study;
public class Peterson1 {
static int count = 0;
static int turn = 0;
static boolean[] flag = new boolean[2];
public static void main(String[] args) throws Exception{
Thread t1 = new Thread(new Producer());
Thread t2 = new Thread(new Consumer());
t1.start(); t2.start();
t1.join(); t2.join();
System.out.println(Peterson1.count);
}
static class Producer implements Runnable {
@Override
public void run(){
for (int k=0; k < 100000; k++){
// entry section
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1)
;
// critical section
count++;
// exit section
flag[0] = false;
// remainder section
}
}
}
private static class Consumer implements Runnable {
@Override
public void run(){
for (int k=0; k < 100000; k++){
// entry section
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0)
;
// critical section
count--;
// exit section
flag[1] = false;
// remainder section
}
}
}
}
package com.os_study;
// atomic variable을 사용할 수 있는 라이브러리
import java.util.concurrent.atomic.AtomicBoolean;
public class Peterson2 {
static int count = 0;
static int turn = 0;
static AtomicBoolean[] flag;
// static 생성자. 클래스가 로드 될 때 초기화 해줌
static {
flag = new AtomicBoolean[2];
for (int i=0; i <flag.length; i++){
flag[i] = new AtomicBoolean();
}
}
public static void main(String[] args) throws Exception{
Thread t1 = new Thread(new Producer());
Thread t2 = new Thread(new Consumer());
t1.start(); t2.start();
t1.join(); t2.join();
System.out.println(Peterson2.count);
}
static class Producer implements Runnable {
@Override
public void run(){
for (int k=0; k < 100000; k++){
// entry section
flag[0].set(true);
turn = 1;
while (flag[1].get() && turn == 1)
;
// critical section
count++;
// exit section
flag[0].set(false);
// remainder section
}
}
}
private static class Consumer implements Runnable {
@Override
public void run(){
for (int k=0; k < 100000; k++){
// entry section
flag[1].set(true);
turn = 0;
while (flag[0].get() && turn == 0)
;
// critical section
count--;
// exit section
flag[1].set(false);
// remainder section
}
}
}
}
원자적 변수Atomic Variables