2024. 5. 26. 16:08ㆍCS/운영체제
프로세스들 간에는 공유하고 있는 데이터에 대하여 그 내용을 변경하는 작업이 수시로 이루어진다.이 과정에서 데이터가 예상 밖의 내용으로 변경되어 있는 경우가 존재한다.이러한 경우를 공유 데이터의 일관성(Consistency)이 유지되지 못했다 하고 이러한 일관성을 유지하기 위해 동기화(Synchronization)이 필요하다.이는 시스템의 공유 메모리뿐만 아니라 프로세스들간에 공유되는 모든 자원에서 발생이 가능한 문제이다.
우선 이러한 코드를 가정해보자
insertItem(item)
{
item->next = listHead;
listHead = item;
}이때 첫번째줄을 실행하고 문맥교환이 이루어져서 똑같이 insertItem을 실행한다하면 다음과 같다.
따라서 적절한 동기화 처리가 필요하다.일반적으로 어느 프로세스가 공유데이터를 사용하는 부분을 실행 중이면 이 부분을 완료하기 전에는 다른 프로세스가 동일한 공유데이터를 사용하는 부분을 실행하지 못하게 처리하면 된다.하지만 커널부분일 경우 인터럽트가 발생하는 경우 인터럽트 처리루틴에서 데이터를 수정하거나 선점형 커널일 경우 시스템 콜 호출로 커널 부분을 실행하면서 그 데이터를 변경한다.이로서 일관성이 커널부분에서는 일관성의 문제가 발생한다.
레이스 컨디션(Race Condition)
실행순서는 미리 예측할 수 없고,실행 순서가 달라지면 그 결과에도 영향을 미치는 경우다.
크리티컬 섹션(Critical Section)
프로그램에서 공유데이터를 사용하는 코드섹션으로 위의 insterItem함수 자체가 크리티컬 섹션이다.크리티컬 섹션은 상당히 복잡해질 수 있다.크리티컬 섹션속에 크리티컬 섹션이 중복되거나 하나의 프로세스가 여러개의 크리티컬 섹션을 가질 수도 있기 때문이다.이러한 크리티컬 섹션 문제를 해결하기 위해서는 크티리컬 섹션간에는 상호 배제(Mutual exclusion)이 되도록 해야 한다.단순하게 생각을 해보면 크리티컬 섹션의 시작부분과 끝부분에는 허가를 휙득하고 반납하는 코드를 추가하는 것이다.예는 다음과 같다.
increment() {
entry section of counter:
counter = counter + value;
exit section of counter;
}
decrement() {
entry section of counter:
counter = counter - value;
exit section of counter;
}
따라서 특정 공유 데이터를 사용하는 크리티컬의 entry 섹션과 exit 섹션을 구현할때는 다음의 조건이 만족되어야 한다.
- 상호배제(Mutual exclusion):공유데이터와 관련된 크리티컬 섹션을 한 프로세스가 실행중이면 어떤 프로세스도 크티리컬 섹션을 실행하면 안됨.
- 진행(Progress):특정 공유데이터의 크리티컬 섹션을 아무도 실행중이지 않으면,크리티컬 섹션을 실행하고자 하는 프로세스들 중 하나는 일정한 시간 내에 실행해야한다.
- 제한된 대기시간(Bounded Waiting):공유데이터와 관련된 크리티컬 섹션을 실행하고자 하는 프로세스는 일정한 시간 내에 자신의 크리티컬 섹션을 실행할 수 있어야 한다.
이러한 Entry,Exit섹션을 구현하는 방법으로는 인터럽트 금지,스핀락,뮤텍스,세마포어 등등이 있다.
인터럽트 금지
커널 내부에서 사용이 가능한 가장 간단한 방법으로 Entry섹션에는 인터럽트 금지 명령어를 적용하고 Exit 섹션에서는 원상 복구 시켜준다.
이는 크리티컬 섹션들간의 실행 중복은 실행중에 문맥교환 방지로 해결하는 것이다.그리고 커널에서 문맥교환을 실행하는 이유는 인터럽트로부터 발생하기 때문이다.하지만 인터럽트 금지명령은 특권명령이기에 커널모드에서만 실행이 가능하고 크리티컬 섹션과 관련이 없는 프로세스에서의 인터럽트도 제한된다.또한 만일 멀티프로세서 시스템에서 서로 다른 CPU에서 실행하는 프로세스들은 인터럽트 금지에 상관없이 언제든지 공유 데이터를 사용할 수 있으므로 인터럽트 금지 방법은 해법이 될 수 없다.
또한 인터럽트 금지하는 기간동안 다른 인터럽트가 실행되지 않기에 가능한 짧게 금지되어야 하고 따라서 인터럽트를 금지하는 동안 실행하는 코드는 간단한 것이어야 한다.
펜티엄 프로세서에서는 cli명령어,ARM 프로세서에서는 PSR 레지스터에 I 비트를 통해 제어한다.
스핀락(Spin Lock)
인터럽트 금지하지않고 CPU가 제공하는 특수 명령어를 이용하는 방법으로 알고리즘으로 크리티컬 섹션 문제를 해결하는 것이다.
Entry 섹션에 lock 변수가 0이 될때까지 기다렸다가 lock 변수를 1로 설정하고 Exit 섹션에서 다시 lock 변수를 0으로 설정하는 것으로
코드로 나타내면 다음과 같다.
//Entry Section
while (counterLock == 1)
;
counterLock = 1;
//Exit Section
counterLock = 0;
우선 알고리즘상 문제될 이유는 없지만 counterLock역시도 공유변수라는 점이다.즉 크리티컬 섹션 문제가 발생한다.
따라서 이를 해결하기 위해서는 CPU의 특수 명령어를 사용한다.펜티엄 프로세서의 XCHG,ARM 프로세서의 SWP명령어가 대표적으로
이는 지정된 레지스터의 내용과 메모리의 내용을 하나의 명령어로 서로 교환하는 작업을 수행한다.이러한 명령어를 Read - Modify - Write 사이클 명령어라 한다.값을 변경하는 과정은 여러개의 단계를 거친다.CPU가 메모리의 값을 읽고 연산을 하고 기록하는 과정이 변경하는 작업인데 결국 어셈블리 언어상에서는 여러단계를 거치지만 이를 특수한 명령어로 한번에 작동하도록하는 것이다.즉,중간 단계에서 문맥교환이 일어나지 않도록 하는 것이다.
스핀락은 특히 멀티 프로세서 시스템에 적합하다.싱글 프로세서 시스템에서는 스핀락의 문제점인 Busy Waiting문제가 발생하기 때문이다.이 문제는 스핀락을 하면 문맥교환이 안일어난다는 점에서 비롯된다.만일 프로세서A가 크리티컬 섹션을 실행하다가 스케줄링을 통해 프로세스B로 스케줄링되면 B는 while문의 조건을 만족시킬때 까지 Busy Waiting상태가 된다.이때 A는 문맥교환이 이루어지지 않기에 실행기회가 없다.이는 CPU의 자원낭비로 이루어진다.아무런 프로세스도 실행할 수 없기 때문이다.따라서 싱글 프로세서 시스템에서는 사용하지 않고 반면 멀티 프로세스 시스템에서는 다른 CPU에서 관련된 크리티컬 섹션을 실행하면 정상적으로 작업을 완료할 수 있기 때문이다.
따라서 스핀락은 멀티프로세서 시스템에서 짧고 중간에 문맥교환이 없는 크리티컬 섹션에 사용한다.
뮤텍스(Mutex)
크리티컬 섹션을 위해 프로세스에서 직접 사용할 수 있도록 운영체제가 제공하는 기능으로서 응용프로그램에서 사용이 가능하다.
lock/unlock 방식을 사용하지만 스핀락과 다르게 비지 웨이팅을 하지 않고 lock함수의 조건에 맞지 않으면 해당 프로세스는 waiting상태로 전환한다.그리고 unlock 함수에서 lock을 해제하면서.waiting상태의 프로세스 모두를 ready상태로 전환한다.물론 몇몇 운영체제는 모든 프로세스가 아닌 하나의 프로세스만 ready상태로 전환한다.뮤텍스의 알고리즘은 다음과 같다.반드시 lock을한 프로세스가 unlock을 한다.
mutexLock(int *lock)
{
int flag = 1;
XCHG(*lock, flag);
while (flag != 0) {
//do spinLock or disable interrupt
//chage state to WAITING
//Context switch
//able interrupt,spinUnlock
XCHG(*lock, flag);
}
}
mutexUnlock(int *lock)
{
*lock = 0;
//do spinLock or disable interrupt
//wake - up all processes waiting
//able interrupt or spinUnlock
}
뮤텍스 함수는 커널에서 구현하고 시스템 콜 함수 형태로 제공된다.이때 프로세스의 상태를 전환하고 문맥교환 하는 부분은 크리티컬 섹션으로 처리해야 한다.따라서 이 부분은 싱글 프로세서일 경우 인터럽트 금지로 처리하거나 멀티 프로세서일 경우 스핀락으로 처리하면 된다.
그리고 실제 운영체제에서 제공하는 뮤텍스는 보통 lock을 통과한 프로세스를 뮤텍스의 소유자로 등록한다.이는 데드록을 해결하는데 유용하게 사용된다.
세마포어(Semaphore)
다익스르타에 의해 제안된 방법으로 lock/unlock을 이용했던 뮤텍스와 다르게 세마포어는 임의의 정수 값을 가지며 Wait(P operation),Signal(V operation) 두 동작만 적용 가능한 객체로 정의된다.wait동작에서는 현재의 세마포어 값이 양수가 될 때까지 기다렸다가 값을 1만큼 줄인다.이후 signal동작에서는 정수 값을 1만큼 증가시킨다.세마포어의 초기 값을 1로 설정하고 Entry/Exit 섹션에 각각 wait/signal을 사용하면 된다.세마포어는 크리티컬 섹션뿐만 아니라 유한버퍼 문제와 같은 여러가지의 동기화 문제에 범용으로 사용할 수 있다.
세마포어의 알고리즘은 다음과 같다.
semWait(int *sem)
{
//do spinLock or disable interrupt
while (*sem <= 0) {
//change state to WAITING
//context switch to another
}
*sem = *sem - 1;
//do spinUnlock or able interrupt
}semSignal(int *sem)
{
//do spinLock or disable interrupt
*sem = *sem + 1;
//wake-up all the processes waiting for sem
//do spinUnlock or able interrupt
}세마포어도 뮤텍스와 비슷하게 busy waiting문제를 해결하도록 구현하고 크리티컬 섹션 부분은 스핀락,인터럽트 금지로 처리한다.
유한버퍼(Bounded buffer) 문제
생산자-소비자 문제로서 세마포어로 해결이 가능한 대표적인 문제다.우선 이 문제가 발생하는 원인은 데이터를 생산하는 생산자 프로세서와 데이터를 소비하는 소비자 프로세스간에 한정된 공유 버퍼를 사용하는 문제다.생산자는 빈 버퍼가 있을 때에 한해서 생성한 데이터를 버퍼에 저장할 수 있고,컨슈머는 버퍼에 저장된 데이터가 있을 때에 한해서 데이터를 버퍼에서 꺼내 사용할 수 있다.따라서 이를 어긋나면 발생하는 문제로서 세마포어를 통해 쉽게 해결이 가능하다.이 문제는 뮤텍스로는 접근하기 힘들다.
struct dataItem buffer[N]; //데이터를 저장할 순환 버퍼
int head = 0, tail = 0; //버퍼의 인덱스
semaphore Full = 0; //버퍼에 데이터가 들어 있음을 표시
semaphore Empty = N; //버퍼에 빈공간이 있음을 표시
void producer() {
struct dataItem item;
while (1) {
//item을 생산자의 목적에 따라 생성
semWait(Empty); //빈공간이 생길 때까지 대기
buffer[tail] = item; //버퍼에 item을 복사하여 보관
tail = tail + 1; //버퍼에 tail 인덱스 증가
if (tail == N) //버퍼가 끝이면 처음으로 변경
tail = 0;
semSignal(Full); //데이터가 기록되었음을 알림
}
}
void consumer() {
struct dataItem item;
while (1) {
semWait(Full); //버퍼에 데이터가 들어올 때까지 대기
item = buffer[head]; //버퍼로부터 데이터를 item에 복사
head = head + 1; //버퍼의 head 인덱스 증가
if (head == N) //버퍼의 끝이면 처음으로 변경
head = 0;
semSignal(Empty); //버퍼에 빈 공간이 생겼음을 알림
//소비자의 목적에 따라 읽어낸 item 사용
}
}
사실 이 코드에도 head,tail은 크리티컬 섹션으로 처리해야하는 공유변수이지만 처리되지 않았다.하지만 소비자,생산자가 다수일 경우에는 반드시 상호배제를 해줘야 한다.
Readers-Writers 문제
공유 데이터의 일관성 유지에 있어서 상호배제 형태로만 처리하면 지나치게 사용을 제한하는 부분이 있다.예를 들어서 크리티컬 섹션에서 공유 데이터를 읽기만 하는 프로세스(reader)들과 쓰기만 하는 프로세스(writer)들로만 구분된다면 reader들은 두개 이상이 동시에 실행되어도 데이터의 일관성에 문제가 없다.즉,reader들은 불필요한 대기 없이 크리티컬 섹션을 실행하게 함으로써 불필요한 대기시간을 줄이는 것이다.물론 writers는 값을 수정할 수 있기에 상호배제되어야 한다.
이를 해결하기 위해서는 우선 세마포어가 writer가 쓰기 작업 중에는 reader들이 읽기 작업을 하지 못하도록 하고 reader가 읽기 작업을 하고 있다면 writer들이 쓰기 작업을 하지 못하도록 하고.만일 다른 reader들이 읽기 작업을 하고 있어도 reader들은 크리티컬 섹션에 접근 할 수 있도록 하면 된다.이를 코드로 구현해보면 다음과 같다.
void writer()
{
while (1) {
//쓰기 작업 전의 적절한 작업 수행;
writerLock();
//공유 데이터에 쓰기 작업 진행
writerUnlock();
//쓰기 작업 후의 적절한 작업 수행;
}
}
void reader()
{
while (1) {
//읽기 작업 전의 적절한 작업 수행;
readerLock();
//공유 데이터에 읽기 작업 진행
readerUnlock();
//읽기 작업 후의 적절한 작업 수행;
}
}
//Reader-Writers 동기화 처리를 위한 변수들
semaphore semData; //공유 데이터 사용을 위한 세마포어
int readerCount = 0; //읽기 작업 중인 reader 개수
mutex mutexCount; //readerCount 관리를 위한 뮤텍스
void writerLock(void)
{
semWait(semData);
}
void writerUnlock(void)
{
semSignal(semData);
}
void readerLock(void)
{
mutexLock(mutexCount);
readerCount = readerCount + 1;
if (readerCount == 1)
semWait(semData);
mutexUnlock(mutexCount);
}
void readerUnlock(void)
{
mutexLock(mutexCount);
readerCount = readerCount - 1;
if (readerCount == 0)
semSignal(semData);
mutexUnlock(mutexCount);
}모니터(Monitor),컨디션 변수(Condition variable)
뮤텍스,세마포어를 프로그래밍 언어 차원에서 제공하는 기능으로 공유변수들은 모니터 속에 선언되고 모니터 속의 procedure들에서만 사용 가능하다.모니터의 procedure들을 실행할 때 크리티컬 섹션의 조건들을 만족하도록 보장한다.procedure를 실행할 때 특정 조건이 만족될 때까지 대기할 필요가 있으면 컨디션 변수를 사용한다.
즉,사용자가 모니터 객체를 선언하면 컴파일러에서 알아서 상호배제를 자동으로 처리해주는 개념이다.
자바에는 Synchronize,wait(),notify(),notifyAll() .. 등등으로 사용이 가능하다.
'CS > 운영체제' 카테고리의 다른 글
| 프로세스 간의 통신 (0) | 2024.06.07 |
|---|---|
| 데드락 문제 및 그 해법 (0) | 2024.06.02 |
| 저장장치 입출력 및 스케줄링 (0) | 2024.05.19 |
| 파일 관리 (0) | 2024.05.15 |
| 가상 메모리 (0) | 2024.04.21 |