멀티 프로세싱(Multi-Processing), 멀티프로그래밍(Multi-Programming), 멀티쓰레딩(Multi-Threading) 에 대한 기본적인 정의와 차이점 등을 살펴보겠습니다.

1) Multi-processing(멀티 프로세싱)

- 멀티프로세싱은 단어 그대로 하나의 프로세서가 아닌 하나 이상의 프로세서가 서로 협력하여 일을 처리하는 것을 가르킵니다. 처리해야 하는 작업이 간단한 경우에는 상관 없지만, 많은 작업을 빠른 시간에 처리하기 위해서는 하나의 프로세서가 처리하는 것은 보다 많은 시간을 요구하게 됩니다.

따라서, 여러 개의 프로세서가 하나의 작업을 병렬처리 하는 것이 효율적입니다. 여러 개의 프로세서가 하나의 컴퓨터에 있을 수도 있고, 여러 대의 컴퓨터가 있을 수도 있습니다. 따라서 멀티프로세싱의 개념을 컴퓨터로 나누기 보다는 여러 개의 프로세서, 즉 하나 이상의 프로세서가 작업을 병렬처리하는 것으로 정의하는 것이 좀 더 정확한 개념일 것이라고 볼 수 있습니다.

2) Multi-programming(멀티 프로그래밍)

- 초기의 컴퓨터는 하나의 프로그램을 처리한 후에 다음 프로그램을 처리해야 했는데, DOS를 사용해 본 사람이라면 쉽게 이해가 갈 것이라고 생각합니다. 하지만 하나의 프로그램을 사용할 때 프로세서의 처리속도와 입출력 속도간의 차이가 너무 크기 때문에 입/출력 작업이 완료 될 때까지 프로세서는 대기해야 합니다. 이후에 하나의 프로그램 처리를 마무리해야 다음 프로그램을 수행할 수 있었습니다.

이것은 프로세서의 자원을 낭비하는 결과를 가져오게 되었고, 따라서 프로세서가 입/출력 작업의 응답을 대기할 동안 다른 프로그램(프로세스)를 수행시킬 수 있도록 하는 것이 멀티프로그래밍이라 합니다. 요즘은 모든 운영체제에서 멀티프로그래밍을 지원하기 때문에 잘 쓰이지 않는 용어입니다.

정리하면, 멀티프로그래밍은 프로세서의 자원낭비를 최소화 하기 위해 낭비되는 시간을 다른 프로그램(프로세스) 수행에 쓰게 하여, 하나의 프로세서에서 여러 프로그램(프로세스)을 교대로 수행할 수 있게 하는 것입니다.

3) 멀티태스킹(Multi-tasking) - (추가)

- 여러 가지 의미가 존재하지만 간단히 말해 task는 어떤 정해진 일을 수행하기 위한 명령어 집합이라고 볼 수 있습니다.

이러한 의미가 앞서 말한 프로그램이 될 수 있겠지만 조금 차이점이 존재합니다. 하나의 프로그램은 프로그램 내에 정의에 따라 하나 또는 그 이상의 프로세스가 될 수 있습니다. 하지만 프로그램이 동작하기 위해서는 프로그램 실행으로 메모리에 로드된 프로세스 외에도 이미 수행되고 있는 운영체제 상의 많은 프로세스와 상호작용이 필요하게 됩니다.

따라서 하나의 task라는 개념은 프로세스의 개념보다 조금 확장된 개념이라고 생각하면 좋습니다. 이러한 task가 하나의 프로세서상에서 운영체제의 스케줄링에 따라 조금씩 번갈아 가면서 수행되는 것이 Multi-Tasking(멀티태스킹)입니다. 멀티프로그래밍과 다른 점은 프로그램과 task의 구분으로도 그 의미가 다르겠지만 멀티프로그래밍이 낭비되는 자원을 최소화하기 위해 교대로 실행하였다면, 멀티태스킹은 좀 더 확장하여 정해진 시간 동안 교대로 task를 수행하는 것입니다.

4) 멀티쓰레딩(Multi-threading)

- 쓰레드는 프로세스내에서 생성되는 하나의 실행 주체입니다. 한 프로세스 내에서 생성되는 것으로 여러개가 동시에 생성이 가능합니다. 또한 생성된 여러 쓰레드는 하나의 공유메모리를 가지게 됩니다. 그렇기 때문에 서로간의 정보를 주고 받는데 최소한의 오버헤드로써 제한이 많이 없는 편입니다.

예를 들어, 네트워킹을 지원하는 프로그램이 있다고 가정하겠습니다. 한 프로그램 내에 사용자가 접속할 때마다 사용자 각각을 처리할 수 있는 처리모듈이 생성되어야 하는데, 이것이 쓰레드라고 볼 수 있습니다.

Multi-Threading(멀티쓰레딩)이 Multi-tasking(멀티태스킹)과 차이점은, 

Multi-Threading은 앞서 말한대로 서로간의 자원공유가 가능하며, 프로그래밍을 통해 구현이 된다는 점입니다. 

하지만 Multi-tasking은 운영체제에서 지원해주는 것으로 서로간의 자원이 공유되지 못하기 때문에 자원전달을 위해서 별도의 IPC(Inter-Process Communication)을 구현해야 하며, 멀티쓰레딩에 비해 운영체제에게 부담을 줄 수 있습니다.

하지만 멀티태스킹은 서로 간의 독립된 메모리를 가지고 있기 때문에 독립된 수행이 가능하므로 멀티쓰레딩과 멀티태스킹은 그 용도에 맞게 적절히 사용되어야 합니다.

(과거 학부생 때, 운영체제 과목에서 공부했던 사진입니다. 저에게는 이해하는데 많은 도움이 되었던 그림이므로 참조하게 되었습니다.)

 (Multi-threading - 종류)

1-좌측상단) 1-프로세스, 1-쓰레드 = 가장 안좋다.(비효율적)

2-우측상단) 1-프로세스, n-쓰레드 = 장점 : 공유할수 있고, 문맥이 가볍다. <-> 단점 : 프로세스가 죽으면 전체가 종료된다.

3-좌측하단) n-프로세스, 1-쓰레드(프로세스 당) = 장점 : 하나가 죽어도 다른 것은 살아있다. <-> 단점 : 공유되지 못함

4-우측하단) n-프로세스, n-쓰레드(프로세스 당) = 가장 진보된 형태!

==> 2번과 3번은 반대되는 개념으로써, 어떤 차이점과 장/단점을 가지고 있는 지 잘 이해하고 있어야 합니다.!!

[참고 사진입니다.]

- 각 쓰레드들은 각각의 스택영역을 가지며, 그 외 프로세스의 자원을 공유하게 됩니다.

이번에는 메모리에 대한 참조 지역성에 대해 공부 해보겠습니다.

- 참조 지역성의 정의 : 동일한 값 또는 해당 값에 관계된 스토리지 위치가 자주 액세스되는 특성으로, 지역성의 원리(principle of locality)라고도 불립니다. 

참조 지역성의 3가지 기본형 : 시간, 공간, 순차(sequential) 지역성.

- 참조 지역성의 종류 -

1) 공간(spatial) 지역성 : 특성 클러스터의 기억 장소들에 대해 참조가 집중적으로 이루어지는 경향으로, 참조된 메모리 근처의 메모리를 참조합니다.

2) 시간(temporal) 지역성 : 최근 사용되었던 기억 장소들이 집중적으로 액세스되는 경향으로, 참조했던 메모리는 빠른 시간에 다시 참조될 확률이 높습니다.

3) 순차(sequential) 지역성 : 데이터가 순차적으로 액세스되는 경향으로, 프로그램 내의 명령어가 순차적으로 구성되어 있다는 것이 대표적인 경우입니다. 공간 지역성에 편입되어 설명되기도 합니다.

추후 페이징에 대한 포스팅도 하겠지만, (조만간 올릴 예정이니 참고하시면 됩니다.)

위 의 그림은 메모리에 페이지가 적재 된 모습입니다.

검정 부분은 페이지가 적재된 부분이고, 흰 부분은 페이지가 실리지 않은 부분입니다.

만약 Page fault(페이지 폴트)가 발생하면 흰 부분이 검정 부분으로 바뀌게 될 텐데, 이렇게 페이징폴트가 발생할 때에도 참조 지역성의 원리를 참조하여 페이지를 적재하게 됩니다. 

OS에서 핵심적인 부분 중 하나인 Scheduling입니다.

상당히 중요한 부분인 만큼 긴 내용이 되겠군요..ㅜ

먼저 대표적인 스케줄링 기법으로 라운드로빈 방식이 있습니다.

- 라운드 로빈 스케줄링(Round Robin Scheduling, RR)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum/Slice)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘입니다.

(==) 같은말로, 컴퓨터 운영에서, 컴퓨터 자원을 사용할 수 있는 기회를 프로그램 프로세스들에게 공정하게 부여하기 위한 한 방법으로서, 각 프로세스에 일정시간을 할당하고, 할당된 시간이 지나면 그 프로세스는 잠시 보류한 뒤 다른 프로세스에게 기회를 주고, 또 그 다음 프로세스에게 하는 식으로, 돌아가며 기회를 부여하는 운영방식이라 풀어 말할 수 있겠습니다.

보통 시간 단위는 10 ms ~ 100 ms 정도로, 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 되고, 문맥 전환의 오버헤드가 큰 반면에 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리합니다.

그렇다면 이 스케줄링이란 무엇일까요?

1) 스케줄링(Scheduling) 이란?

- 일반적인 스케줄링이란 처리할 일들의 진행순서를 정하는 일입니다. 

1) 프로세스 스케줄링이란 CPU를 사용하려고 하는 프로세스들 사이의 우선 순위를 관리하는 일을 말하고, 

2) 디스크 스케줄링은 디스크를 사용하려고 하는 프로세서들 사이의 우선 순위를 관리하는 일들을 말합니다. 

스케줄링은 처리율과 CPU 이용률을 증가시키고, 오버헤드/응답시간/반환시간/대기시간을 최소화 시키기 위한 기법입니다. 즉, CPU가 쉬지않고 계속 열심히 일할 수 있도록 효율적인 계획을 잡아 주는 것이 스케줄링입니다.

2) 스케줄링 방식 -> 비선점 스케줄링과 선점 스케줄링

- 스케줄링의 적용 시점에 따라 비선점형과 선점형의 2가지로 구분할 수 있습니다.

1) 비선점형 스케줄링은 프로세스가 (실행->대기), (실행->종료) 로의 상태전이가 있을 때 적용되며,

2) 선점형 스케줄링은 (실행->대기), (실행->준비), (대기->준비), (수행->종료) 모든 상태변화에서 적용됩니다.

 (앞선 Process State Trasition Diagram, 선점형/비선점형 글을 참고로 보시면 됩니다.)

- 비선점 스케줄링 은 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법입니다. 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드도 적습니다. 일괄처리 시스템에 적합하고, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점도 있습니다.

- 선점 스케줄링 은 하나의 프로세스가 CPU를 할당 받아 실행하고 있을 때 우선 순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 기법입니다. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있으며, 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있습니다.

(이 또한, 앞선 선점형 OS와 비선점형OS 글에서 다루었던 부분입니다.)

그렇다면, 이 스케줄링 알고리즘들에는 어떤것들이 있는지 아래에서 살펴보겠습니다.

3) 비선점형 스케줄링 알고리즘 : FIFO, SJF, HRN

-FIFO(First In First Out) : 가장 간단한 방식으로 선입선출의 방식입니다. 먼저 들어오면 먼저 나가는 방식으로, 아무리 중요한 작업이 있다 하더라고 그 작업 보다 먼저 들어온 작업이 끝나기 전까지는 절대 먼저 실행될 수 없는 비효율적인 방식이라고 말할 수 있습니다. FIFO라고도 하고 FCFS(First Come First Served Scheuling)이라고도 합니다. 관련은 없지만 선입선출이라는 면에서 자료구조의 Queue를 한번 떠올려보게되네요.ㅎㅎ

-SJF(Shortest Remaining Time First Scheduling) : 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식입니다. 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 연기 상태에 빠질 수 있다는 단점이 있습니다.

-HRN(Highest Response-ratio Next) : 실행시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로 대기 시간과 서비스 시간을 이용하는 방식입니다. '우선순위 = (대기시간+서비스시간)/서비스시간' 의 공식을 이용하여 우선순위를 계산하여 우선순위가 높은 것부터 실행하는 방식입니다. 

이렇게 프로세스가 자원을 기다리고 있는 시간에 비례하여 우선순위를 부여함으로서 무한 연기의 문제를 방지하는 것을 ‘에이징(Aging)기법’이라고 합니다.

4) 선점형 스케줄링 알고리즘 : SRT, RR, MQ

-SRT(Shortest Remaining Time) : 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법입니다. SJF처럼 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식으로, 단지 차이점은 ‘선점형’으로 바뀌어 중요한 프로세스가 있으면 점유시간이 길어도 먼저 실행 시킬수 있는 권한이 생겼다는 것입니다.

- RR(Round Robin) : 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위로 CPU를 할당하는 방식입니다. 보통 시간 단위는 10ms ~ 100ms 정도이고 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 됩니다. 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하고, 할당되는 시간이 클 경우 비선점 FIFO기법과 같아지게 됩니다.

(위에서 설명한 부분입니다..^^)

- 다단계 큐(MQ, Multi-level Queue) : 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 분비 상태 큐를 사용하는 기법입니다. 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없습니다. 하위 준비 상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비 상태 큐에 프로세스가 들어오면 상위 프로세스에게 CPU를 할당해야 합니다.

사진에 보이는 것처럼 Level 1, 2, 3으로 큐가 불리 되어 있습니다. 레벨 1의 큐가 모두 완료 되어야만 레벨 2의 큐로 넘어갈 수 있고 레벨2의 큐가 모두 완료되어야 그다음으로 넘어 갈수 있는 방식입니다.

OS의 기본. Process Control Block(PCB)입니다.

- 프로세스 제어 블록(Process Control Block, 줄여서 PCB)은 특정한 프로세스를 관리할 필요가 있는 정보를 포함하는, 운영체제 커널의 자료구조입니다. PCB는 운영 체제가 프로세스를 표현한 것이라 할 수 있습니다.

- 운영체제가 프로세스 스케줄링을 위해 프로세스에 관한 모든 정보를 가지고 있는 데이터베이스를 PCB라 합니다.

- 운영체제에서 프로세스는 PCB로 나타내어지며, PCB는 프로세스에 대한 중요한 정보를 가지고 있는 자료입니다. 각 프로세스가 생성될 때마다 고유의 PCB가 생성되고, 프로세스가 완료되면 PCB는 제거됩니다.

- 프로세스는 CPU를 점유하여 작업을 처리하다가도 상태가 전이(앞에서 살펴본 Process State Trasition Diagram 참조!) 되면, 진행하던 작업 내용들을 모두 정리하고 CPU를 반환해야 하는데, 이때 진행하던 작업들을 모두 저장하지 않으면 다음에 자신의 순서가 왔을 때 어떠한 작업을 해야하는지 알 수 없는 사태가 발생합니다.

따라서 프로세스는 CPU가 처리하던 작업의 내용들을 자신의 PCB에 저장하고, 다음에 다시 CPU를 점유하여 작업을 수행해야 할 때 PCB로부터 해당 정보들을 CPU에 넘겨와서 계속해서 하던 작업을 진행할 수 있게 됩니다.

(PCB에 저장되어 있는 정보)

1) 프로세스 식별자(Process ID)

2) 프로세스 상태(Process State) : 생성(create), 준비(ready), 실행 (running), 대기(waiting), 완료(terminated) 상태가 있습니다.

3) 프로그램 계수기(Program Counter) : 프로그램 계수기는 이 프로세스가 다음에 실행할 명령어의 주소를 가리킵니다.

4) CPU 레지스터 및 일반 레지스터

5) CPU 스케줄링 정보 : 우선 순위, 최종 실행시각, CPU 점유시간 등

6) 메모리 관리 정보 : 해당 프로세스의 주소 공간 등

7) 프로세스 계정 정보 : 페이지 테이블, 스케줄링 큐 포인터, 소유자, 부모 등

8) 입출력 상태 정보 : 프로세스에 할당된 입출력장치 목록, 열린 파일 목록 등

9) 포인터 : 부모프로세스에 대한 포인터, 자식 프로세스에 대한 포인터, 프로세스가 위치한 메모리 주소에 대한 포인터, 할당된 자원에 대한 포인터 정보 등.

이번엔 OS의 프로세스 상태 다이어그램에 대해 공부하고자 합니다.

new 단계 : 프로세스가 생성되는 단계

-> 프로그램을 실행시켰을 때의 첫 번째 상태가 됩니다.

************************************************************************************

준비(ready)단계 : 프로세스가 프로세서에 할당되기를 기다리고 있는 상태

실행(running)상태 : 프로세스가 실행중인 상태

대기(waiting)상태 : 프로세스가 어떤 사건(event)을 기다리고 있는 상태

************************************************************************************

terminated상태 : 프로세스의 실행이 종료된 상태

디스패치(dispatch) : 준비(ready)상태에서 실행(running)상태로 전이되는 과정을 말하며, 이는 작업 스케줄러가 해당 프로세스를 선택하여 실행되어지는 것으로 이때 실행된 프로세스가 CPU를 점유하게 됩니다.

인터럽트(Interrupt) : 인터럽트 신호를 받게되면, 실행(running)중이던 프로세스는 준비(ready)상태로 전이되고, 우선순위(Priority)가 높은 프로세스를 실행(running)상태로 전이시키게 됩니다. (프로세스는 각각 우선순위를 부여받고, 우선순위에 따라 프로세스가 준비상태로 전이되거나, 실행상태로 전이됩니다.)

입출력 혹은 이벤트대기(I/O or event wait) : CPU를 점유하고 있는 프로세스가 입출력 처리를 해야만 하는 상황이라면, 실행되고 있는 프로세스는 실행(running)상태에서 대기/보류(waiting) 상태로 바뀌게 됩니다. 그리고 대기상태로 바뀐 프로세스는 입출력 처리가 모두 끝날때까지 대기상태로 머물게 됩니다. 그리고 실행 상태이던 프로세스가 대기상태로 전이됨과 함께, 준비상태이던 또 다른 프로세스가 실행 상태로 전이됩니다. 또한 대기 상태인 프로세스는 우선순위가 부여되지 않으며 스케줄러에 의해 선택 될 수 없습니다.

입출력 혹은 이벤트완료(I/O or event completion) : 입출력 처리가 끝난 프로세스는 대기상태(waiting)에서 준비상태(ready)로 전이되어 스케줄러에게 선택될 수 있게 됩니다. 추가로 프로세스를 종료(Terminate)시킬 때에도 Blocked 상태를 거칠 수 있습니다.

** 단일 프로세스 시스템에서는 현재 실행 상태에 있을 수 있는 프로세스가 

오직 하나!

but, 많은 프로세스가 waiting or ready상태에 있을 수 있습니다.!

이번에는 선점형 OS와 비선점형 OS의 차이를 보겠습니다.

기본적으로 프로세스가 자원을 선점한다, 비선점한다 의 개념은 알고 있다는 가정하입니다.

- 특정 프로세스가 CPU 를 독점하는것이 가능 (프로세스가 스스로 CPU 점유를 포기해야만 다른 프로세스가 실행)하면 비선점형

- 특정 프로세스가 CPU 를 독점하는것이 불가능(운영체제가 강제로 프로세스의 CPU 점유를 제어)하면 선점형

(CPU의 스케줄링 결정 시점)

- CPU 스케줄링의 결정 시점은 다음과 같은 프로세스의 상태 변화가 있을 때입니다.

1) 수행 → 대기

2) 수행 → 준비

3) 대기 → 준비

4) 수행 → 종료

(1) 비선점형 스케줄링(Non-preemptive Scheduling) : 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장합니다. 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있으며, 

선점 방식보다 스케줄러 호출 빈도 낮고 문맥 교환에 의한 오버헤드가 적습니다. 일괄 처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점이 있습니다.

(2) 선점형 스케줄링(Preemptive Scheduling) : 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있습니다. 

모든 프로세스에게 CPU 사용 시간을 동일하게 부여(Round Robin - RR)할 수도 있습니다. 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있습니다. '운영 체제가 프로세서 자원을 선점'하고 있다가 각 프로세스의 요청이 있을 때 특정 요건들을 기준으로 자원을 배분하는 방식입니다.

Deadlock에 이어, Semaphore와 mutex에 대해 설명하고자 합니다.

- 프로세스 간 메시지를 전송하거나, 공유메모리를 통해 특정 데이터를 공유하게 되는 경우 문제가 발생할 수 있습니다.

즉, 공유된 자원에 여러 개의 프로세스가 동시에 접근하면서 문제가 발생하는 것으로써 공유된 자원 속 하나의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한해 두어야 하는데, 

이를 위하여 고안된 것이 바로 Semaphore 세마포어 입니다.

(세마포어와 뮤텍스의 차이)

- 세마포어(Semaphore) : 공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌(즉, 동기화 대상이 하나 이상)

- 뮤텍스(Mutex) : 공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 하나의 Process 혹은 Thread가 접근하는 것을 막아줌(즉, 동기화 대상이 하나)

** Critical section 이란 ?

OS에서 Critical Section은 아주 중요한 부분입니다.

- 다중 프로그래밍 운영체제에서 여러 프로세스가 데이타를 공유하면서 수행될 때 각 프로세스에서 공유 데이터를 접근(Access)하는 프로그램 코드 부분을 가리키는 말입니다.

공유 데이터를 여러 프로세스가 동시에 액세스하면 시간적인 차이 등으로 인하여 잘못된 결과를 만들어 낼 수 있기 때문에 한 프로세스가 위험 부분을 수행하고 있을 때, 즉 공유 데이타를 액세스하고 있을 때는 다른 프로세스들은 절대로 그 데이타를 액세스하지 못하도록 하여야 합니다.

예제 )

컴퓨터가 여러 프로그램을 동시에 수행하는 다중 프로그래밍 시스템에서는 프로세스들간의 상호배제와 동기화를 위한 기본적인 연산이 필요하게 되고 세마포어는 여러 프로세스들에 의해 공유되는 변수로 정의됩니다.

그런데 이 변수는 보통의 방법으로는 액세스할 수 없고 오직 P와 V라는 연산으로만 다룰 수 있습니다.

P와 V연산의 정의는 아래와 같습니다.

-------------------------

procedure P(S)            --> 최초 S값은 1

while S=0 do wait        --> S가 0이면 1이 될 때까지 wait

S := S-1                     --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함

end P

-------------------------

------------------------- 

procedure V(S)          --> 현재상태는 S가 0

S := S+1                  --> S를 1로 원위치시켜 해제하는 과정

end V                     -->이제는 다른 프로세스가 들어 올수 있음

------------------------- 

즉 한 프로세스가 P나 V를 수행하고 있는 동안에는 프로세스가 인터럽트를 당하지 않게 됩니다. 이제 P와 V를 사용하면 다음과 같이 위험지역(cirtical section)에 대한 상호배제를 구현할 수 있게 됩니다.

P(S);

------------------------

위 험 지 역(Critical Section) = 임계영역

------------------------

V(S);

최초에 S의 값은 1이고, 위와 같은 위험지역을 포함하는 두개의 프로세스 A와 B가 있다고 할 때,

A와 B는 서로 독립적으로 수행되지만, 두 프로세스가 동시에 위험 지역으로 들어가서는 안된다.

위와 같이 세마포어를 사용하면 P(S)를 먼저 수행하는 프로세스가 S를 0으로 해놓고 위험지역에 들어가므로 나중에 도착하는 프로세스는 P에서 더이상 진행되지 못하고 기다리게 된다. 먼저 들어갔던 프로세스가 V(S)를 해주어야 비로서 P(S)에서 기다리던 프로세스가 위험지역에 들어갈 수 있고 따라서 상호배제가 실현된다. 

(정리)

** 뮤텍스란(Mutex)? **

“Mutual Exclusion 으로 상호배제라고도 한다. Critical Section을 가진 쓰레드들의 Runnig Time이 서로 겹치지 않게 각각 단독으로 실행되게 하는 기술입니다. 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 locking과 unlocking을 사용합니다. 

즉, 쉽게 말하면 뮤텍스 객체를 두 쓰레드가 동시에 사용할 수 없다는 의미입니다.

** 세마포어란?(Semaphore) **

” 세마포어는 리소스의 상태를 나타내는 간단한 카운터로 생각할 수 있습니다. 일반적으로 비교적 긴 시간을 확보하는 리소스에 대해 이용하게 되며, 유닉스 시스템의 프로그래밍에서 세마포어는 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스에서 행동을 조정하거나 또는 동기화 시키는 기술입니다. 

세마포어는 운영체제 또는 커널의 한 지정된 저장장치 내 값으로서, 각 프로세스는 이를 확인하고 변경할 수 있습니다. 확인되는 세마포어의 값에 따라, 그 프로세스가 즉시 자원을 사용할 수 있거나, 또는 이미 다른 프로세스에 의해 사용 중이라는 사실을 알게 되면 재시도하기 전에 일정 시간을 기다려야만 합니다. 세마포어는 이진수 (0 또는 1)를 사용하거나, 또는 추가적인 값을 가질 수도 있습니다. 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 기다리도록 해야합니다.

( 차이점들!! )

<Mutex vs Semaphore>

1) Semaphore는 Mutex가 될 수 있지만 Mutex는 Semaphore가 될 수 없습니다.

(Mutex 는 상태가 0, 1 두 개 뿐인 binary Semaphore)

2) Semaphore는 소유할 수 없는 반면, Mutex는 소유가 가능하며 소유주가 이에 대한 책임을 집니다. (Mutex 의 경우 상태가 두개 뿐인 lock 이므로 lock 을 ‘가질’ 수 있습니다.)

3) Mutex의 경우 Mutex를 소유하고 있는 쓰레드가 이 Mutex를 해제할 수 있습니다. 하지만 Semaphore의 경우 이러한 Semaphore를 소유하지 않는 쓰레드가 Semaphore를 해제할 수 있습니다.

4) Semaphore는 시스템 범위에 걸쳐있고 파일시스템상의 파일 형태로 존재합니다. 반면 Mutex는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 Clean up된다.

★★★ 가장 큰 차이점은 관리하는 동기화 대상의 갯수입니다. Mutex는 동기화 대상이 오직 하나뿐일 때, Semaphore는 동기화 대상이 하나 이상일 때 사용합니다.

*Linux에서 Mutex를 사용 해 본 예입니다.)

-> pthread_mutex_lock(&mutex_lock);

// critical section

pthread_mutex_unlock(&mutex_lock);

의 형태로 사용하게 되며 while구문 안에서 앞, 뒤로 mutex를 lock, unlock 해줍니다.

그리고 main화면에서 mutex 객체를 초기화 시키기 위해서 사용합니다.

OS에 대해 기본적인 상식 중 Deadlock으로 운영체제 부분을 시작 해볼까 합니다.

먼저,  DeadLock의 개념입니다.

1. DeadLock의 개념

- 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로, ‘교착 상태’라고도 하며 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생합니다.

- 데드락이 발생할 수 있는 경우 :

P1과 P2가 리소스 A, B 둘 다를 얻어야 한다고 가정할 때,

t1에 P1이 리소를 A를 얻고 P2가 리소스 B를 얻었다면 t2때 P1은 리소스 B를, P2는 리소스 A를 기다리게 됩니다.

하지만 서로 원하는 리소스가 상대방에게 할당되어 있기 때문에 이 두 프로세스는 무한정 기다리게 되는데 이러한 상태을 DeadLock상태라고 합니다.

(발생되는 상황)

- 멀티 프로그래밍 환경에서 한정된 자원을 사용하려고 서로 경쟁하는 상황이 발생 할 수 있습니다.

- 어떤 프로세스가 자원을 요청 했을 때 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있고 그 때는 프로세스가 대기 상태로 들어 가게됩니다.

- 대기 상태로 들어간 프로세스들이 실행 상태로 변경 될 수 없을 때 이러한 상황을 교착 상태라 합니다.

2. 데드락 (Dead lock)의 발생 조건

- 교착 상태는 한 시스템 내에서 다음의 네 가지 조건이 동시에 성립 할 때 발생합니다

- 따라서, 아래의 네 가지 조건 중 하나라도 성립하지 않도록 만든다면 교착 상태를 해결할 수 있습니다.

1) 상호 배제 (Mutual exclusion)

- 자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다.

 2) 점유 대기 (Hold and wait)

- 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

 3) 비선점 (No preemption)

- 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.

 4) 순환 대기 (Circular wait)

- 프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

3. 데드락 (Dead lock) 처리

(1) 교착 상태 예방(Prevention) 및 회피(Avoidance)

< 예방(Prevention)법 >

: 교착 상태 발생 조건 중 하나를 제거함으로써 해결하는 방법

- 자원의 낭비가 심하다.

1) 상호 배제 (Mutual exclusion) 부정

- 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.

2) 점유 대기 (Hold and wait) 부정

- 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.

3) 비선점 (No preemption) 부정

- 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.

4) 순환 대기 (Circular wait) 부정

- 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

<회피(Avoidance)법>

 : 교착 상태가 발생하면 피해나가는 방법

- 은행원 알고리즘 (Banker’s Algorithm)

E,J,Dijkstra가 제안한 방법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법이다.

프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피하는 기법

안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기함

교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 이용하는 방법

(2) 교착 상태 탐지 및 회복

 : 교착 상태가 되도록 허용한 다음에 회복시키는 방법

교착 상태 무시

** 대부분의 시스템은 교착 상태가 잘 발생하지 않으며, 교착 상태 예방, 회피, 탐지, 복구하는 것은 비용이 많이 든다. **

< 교착 상태 탐지 (Detection) >

- 자원 할당 그래프를 통해 교착 상태를 탐지할 수 있다.

- 자원 할당 그래프 예시

- 프로세스 Pi로부터 자원 Rj로의 방향 간선은 Pi ->Rj로 표현하며 이것은 프로세스 Pi가 자원 꺼을 요청하는 것으로 현재 이 자원을 기다리는 상태이다.

- 자원 Rj로부터 프로세스 Pi로의 방향 간선은 Rj->Pi로 표현하며 이것은 자원이 프로세스 Pi에 이미 할당된 것을 의미 한다.

- 자원을 요청할 때마다 탐지 알고리즘을 실행하면 그에 대한 오버헤드가 발생한다.

< 교착 상태로부터 회복 (Recovery) >

- 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복하는 것을 의미한다.

- 프로세스를 종료하는 방법

1. 교착 상태의 프로세스를 모두 중지

2. 교착 상태가 제거될 때까지 한 프로세스씩 중지

- 자원을 선점하는 방법

1. 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지 시키는 방법

2. 우선 순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점한다.