day53 🌕

장미·2022년 8월 5일

오늘의 성과

목록 보기

53/129

스프링 MVC 2편 - 백엔드 웹 개발 활용 기술 섹션 6 완강하기

+) 22. 08. 10. day51 🌕 에 정리 완료!

Critical Section

프로세스는 독립적으로 작업을 할 수도 있고, 공유된 자원을 가지고 공동 작업을 할 수도 있다.
여기서 공유 자원(shared resource)은 여러 프로세스가 공동으로 사용하는 변수, 메모리, 파일 등을 말한다.
공유 자원은 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다. 따라서 프로세스들의 공유 자원 접근 순서를 정하여 예상치 못한 문제가 발생하지 않도록 해야 한다.

그림 1. 공유 자원의 접근

위 그림을 보면 전역 변수 ‘예금’에 대해 두 프로세스가 모두 입금을 한다.
예금은 원래 있던 10만원에 P1이 입금한 10만원과 P2가 입금한 5만원을 합한 25만원이 되어야 한다. 그런데 5만원이 어디론가 사라지고 20만원뿐이다.
정상적으로 예금이 25만원이 되려면 P1이 작업을 마친 후 P2가 입금을 하거나, P2가 작업을 마친 후 P1이 돈을 입금해야 한다. 하지만 두 프로세스가 예금 10만원을 동시에 읽은 후 다른 프로세스의 작업을 무시하고 덮어쓰는 바람에 총액이 맞지 않는 문제가 발생하게 된 것이다.

이처럼 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 Race Condition이 발생했다고 한다. Race Condition이 발생하면 위 그림처럼 공유 자원 접근 순서에 따라 실행 결과가 달라질 수 있다.

공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역을 Critical Section이라 한다.
위의 그림에서는 각 프로세스가 전역 변수를 사용하는 부분, 즉 예금을 확인하고 입금을 한 후 저장하는 부분이 Critical Section이다.

Critical Section에서는 프로세스들이 동시에 작업하면 안 된다. 어떤 프로세스가 Critical Section에 들어가면 다른 프로세스는 그 밖에서 기다려야 하며, Critical Section의 프로세스가 나와야만 들어갈 수 있다.

Critical Section 해결 조건

Critical Section 문제를 해결하는 방법 중 어떤 방법이든 다음의 세 가지 조건을 만족해야 한다.

상호 배제(Mutual Exclusion)
한 프로세스가 Critical Section에 들어가면 다른 프로세스는 들어갈 수 없다. 이것이 지켜지지 않으면 Critical Section을 설정한 의미가 없다.
Critical Section 내에는 한 번에 하나의 프로세스만 있어야 한다.
한정 대기(Bounded Waiting)
어떠한 프로세스도 무한 대기(Infinite Postpone)하지 않아야 한다. 즉, 특정 프로세스가 Critical Section에 진입하지 못하면 안 된다.
진행의 융통성(Progress Flexibility)
한 프로세스가 다른 프로세스의 진행을 방해해서는 안 된다는 것을 의미한다. 즉, 프로세스 A는 B의 작업 속도와 관계없이 Critical Section이 비어 있으면 언제든 사용할 수 있어야 한다.

Critical Section 해결 방법

Critical Section 문제를 해결하는 단순한 방법은 Lock을 이용하는 것이다.
예를 들어 Critical Section이 화장실이라면 사용자는 화장실 문을 잠그고 사용한 후 나올 때 잠금을 해제한다. 그리고 기다리는 사람이 있다면 사용해도 좋다는 신호를 보낸다.

Critical Section 해결 조건을 고려한 코드 설계

상호 배제 문제

boolean lock=false;
두 프로세스가 공유하는 변수인 lock의 초기값은 false이다. → 잠금이 해제되어 있다.
```
 //프로세스 P1
 while(lock==true);
 lock=true;
 /* Critical Section */
 lock=false;
```
```
 //프로세스 P2
 while(lock==true);
 lock=true;
 /* Critical Section */
 lock=false;
```
P1과 P2는 Critical Section에 진입하기 전에 코드를 통해 Critical Section에 잠금이 걸려 있는지 확인한다. → lock==true
만약 잠겨 있으면 잠금이 해제될 때까지 무한 루프를 돌면서 기다린다. → while(lock==true)
Critical Section에 있는 프로세스가 작업을 마치고 잠금을 해제하면 → lock=false
무한 루프를 나와 작업을 시작한다.

이는 문제없이 작동할 것 같지만 가끔 제대로 작동하지 않을 때가 있다.

만약 Critical Section에 진입한 프로세스가 없을 경우 → lock=false

① P1이 while문을 실행하고 Critical Section에 프로세스가 없기 때문에 무한 루프를 빠져나온다. 이어서 다음 문장을 실행하려는 순간, 주어진 CPU 시간을 다 써서(타임아웃) 준비 상태로 옮겨진다. 이 때 Context Switching이 발생하고 P2가 실행 상태로 바뀐다.

② P2가 while문을 실행하고, 아직 P1이 잠금을 걸지 않았기 때문에 P2는 Critical Section에 진입할 수 있다.

③ P1이 lock=true 문을 실행하여 Critical Section에 잠금을 걸고 진입한다.

④ P2도 lock=true 문을 실행하여 Critical Section에 잠금을 걸고 진입한다. 결국 둘 다 Critical Section에 진입하게 된다.

또 다른 문제는, 잠금이 풀리기를 기다리려면 Busy Waiting을 해야 한다는 것이다.
바로 while(lock==true) 부분인데, 이는 작업을 할 필요가 없는 시간에도 계속 무한 루프를 돌면서 시스템 자원을 낭비하게 된다.
한정 대기 문제

boolean lock1=false;
boolean lock2=false;
전역 변수로 lock1, lock2를 사용하며 초기값은 둘 다 false이다.
```
//프로세스 P1
lock1=true;
while(lock2==true);
/* Critical Section */
lock1=false;
```
```
//프로세스 P2
lock2=true;
while(lock1==true);
/* Critical Section */
lock2=false;
```
P1은 Critical Section에 진입하기 전에 먼저 잠금을 설정하고 → lock1=true
P2가 잠금을 설정했는지 확인한다. → while(lock2==true)
만약 잠금을 설정하지 않았다면 Critical Section에 진입하여 작업을 마친 후 잠금을 해제한다. → lock1=false

아까와 달리 일단 잠금을 하고 다른 프로세스가 잠겼는지 확인하므로 두 프로세스의 상호 배제가 보장된다. 하지만 이 상황에서는 두 프로세스가 모두 Critical Section에 진입하지 못하는 무한 대기 현상이 일어난다.

① P1은 lock1=true를 실행한 후 자신의 CPU 시간을 다 써버렸다. Context Switching이 발생하고 P2가 실행 상태로 바뀐다.

② P2도 lock2=true를 실행한 후 자신의 CPU 시간을 다 써버렸다. Context Switching이 발생하고 다시 P1이 실행 상태로 바뀐다.

③ P2가 lock2=true를 실행했기 때문에 P1은 while(lock2==true) 문에서 무한 루프에 빠진다.

④ P1이 lock1=true를 실행했기 때문에 P2도 while(lock1==true) 문에서 무한 루프에 빠진다.

이는 한정 대기 조건을 보장하지 못하는 상황으로, Dead Lock이라고 한다. 즉, 프로세스는 살아 있으나 작업이 진행되지 못하는 상태를 말한다.

또한 위 코드에는 확장성 문제도 존재한다.
P1은 자신의 lock1을 잠그고 lock2를 검사한다. 만약 프로세스가 3개라면 lock3을 만들고 다른 프로세스들이 lock3을 검사해야 할 것이다.
이처럼 프로세스가 늘어나면 검사해야 하는 lock의 개수도 늘어나 비효율적이다.
진행의 융통성 문제

int lock=1; 공유 변수
lock 값이 1이면 프로세스 P1이 Critical Section을 사용한다는 뜻이고, lock 값이 2이면 P2가 Critical Section을 사용한다는 뜻이다.
```
//프로세스 P1
while(lock==2);
/* Critical Section */
lock=2;
```
```
//프로세스 P2
while(lock==1);
/* Critical Section */
lock=1;
```
공유 변수 lock의 값을 통해 다른 프로세스가 Critical Section에 있는지 확인하고, 없으면 진입한다.

위 코드는 상호 배제와 한정 대기를 보장한다. 그러나 서로 번갈아가면서 실행된다는 것이 문제이다. 한 프로세스가 연달아 Critical Section에 진입하고 싶어도 그럴 수 없다. 우선순위에 상관없이 번갈아가며 Critical Section에 진입한다.

P1은 P2가 Critical Section에 진입했다가 나온 다음에야 다시 진입할 수 있으므로 P2가 P1의 진행을 방해하는 구조다.

이렇게 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상을 경직된 동기화(Lockstep Synchronization)라고 한다.

지금까지 소개한 알고리즘은 Critical Section 해결 조건을 완벽하게 충족하지 못했다. 피터슨 알고리즘과 데커 알고리즘은 이러한 문제를 해결했으나 구조가 복잡하여 현재 잘 사용되지 않는다.
그래서 나온 세마포어에 대한 설명은, 아래 링크로 들어가면 자세하게 볼 수 있다.

세마포어와 뮤텍스

여기서는 모니터에 대한 설명만 하겠다. (참고로 세마포어에 대해 알고 있어야 모니터에 대한 이해가 쉬울 것이다.)

모니터

세마포어의 가장 큰 문제는 잘못된 사용으로 인해 Critical Section이 보호받지 못한다는 것이다.

프로세스가 세마포어를 사용하지 않고 바로 Critical Section에 들어간 경우 Critical Section을 보호할 수 없다.
P()를 두 번 사용하여 wake_up 신호가 발생하지 않은 경우, 프로세스 간의 동기화가 이루어지지 ㅇ낳아 세마포어 큐에서 대기하고 있는 프로세스들이 무한 대기에 빠진다.
P()와 V()를 반대로 사용하여 상호 배제가 보장되지 않은 경우 Critical Section을 보호할 수 없다.

모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화를 시킨다.

그림 2. 모니터의 작동 원리

① Critical Section으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.

② 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에게 알려준다.

아래 코드는 그림 1에서 예금 5만원이 사라진 문제를 모니터를 사용하여 해결한 코드이다.

P1 increase(10);
P2 increase(5);

사용자는 잠금이나 세마포어를 사용하지 않고 입금하라는 명령, 즉 increase() 문만 사용한다. 이 방법은 사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋고, 시스템 입장에서는 Critical Section을 보호할 수 있어서 좋다.

//모니터 내부 코드
monitor(shared_balance) {
	private:
		int balance=10; //shared data
		boolean busy=false;
		condition mon; //condition variable

	public:
		increase(int amount) { //public interface
			if(busy==true) mon.wait(); //waiting in queue
			busy=true;
			balance=balance+amount;
			mon.signal(); //wake up next waiting process
	}
}

위 코드에서 10만원이 들어있는 예금 balance, 잠금 역할을 하는 busy, 잠금 해제 역할을 하는 mon 변수는 private으로 선언되어 있다. 이 변수는 public 영역에 있는 increase()를 통해서만 값을 변경할 수 있다.
즉, 입금하려는 프로세스는 increase()만 사용하여 예금 데이터에 접근할 수 있다는 소리다.

모니터는 Critical Section 보호와 동기화를 위해 내부적으로 상태 변수(Condition Variable)를 사용한다.
상태 변수에는 wait()와 signal()이 있는데, 위 모니터 내부 코드에서는 상태 변수가 mon이다.