잡지식창고

기아 상태는 병행 프로세스에서 프로세스가 실행되는데에 필수적인 자원을 끊임없이 사용하지 못하는 상황을 말한다.

기아 상태는 스케줄러나 상호배제 알고리즘의 에러로부터 발생할 수 있고, 자원 누수에 의해 발생하기도 하고, 포크 밤같은 서비스 거부 공격에 의해 발생하기도 한다.

대표적인 예로 다익스트라의 식사하는 철학자가 있다.

교착상태(Deadlock)는 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 결과적으로 아무 일도 일어나지 않는 상태를 말한다.

교착상태가 일어나기 위해선 다음 네 조건을 만족해야한다.

1) 상호배제
2) 점유 대기
3) 비선점
4) 순환대기

교착상태는 이 네 조건을 동시에 모두 만족해야 일어나기 때문에, 이 중 하나라도 성립하지 않게 만들면 교착 상태를 해결할 수 있다. 

교착상태를 해결하는 방법에는 예방, 회피, 탐지, 무시가 있다.

1) 예방(Prevention)

교착상태를 예방하는 방법에는 다음과 같은 방법이 있다.

2) 회피(Avoidance)

교착상태의 회피는 교착상태의 모든 발생 가능성을 미리 제거하는것이 아닌, 발생 가능성을 인정하고 교착 상태가 발생하려고 할 때 적절히 회피하는것을 말한다.

교착상태의 회피는 다음 두가지 방법이 있다.

1) 프로세스의 시작 중단

2) 자원 할당 거부 (은행가 알고리즘)

은행가 알고리즘은 자원의 할당 허용 여부를 결정하기 전에 미리 결정된 모든 자원의 최대 가능한 할당량을 시뮬레이션 하여 안전 여부를 검사한다. 그리고 대기중인 다른 모든 활동의 교착 상태 가능성을 조사하여 안전 상태 여부를 검사/확인 한다.

안전 상태는 시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태로 안전 순서열이 존재하는 상태를 말한다.

불안전 상태는 안전순서열이 없는 상태를 말한다. 교착상태는 불안전상태에서만 발생하지만, 무조건 일어나는것은 아니다.

은행가 알고리즘은 자원 요청을 승낙하는것이 불안전 상태에서 시스템을 배치할 수 있다고 판단하면 이 요청을 연기하거나 거부해 교착 상태를 예방한다.

3) 탐지(Detection)

교착상태 탐지는 교착상태의 발생을 허용한다. 그런 다음 교착상태가 발생했는지 탐지하기 위해 시스템 상태를 지속적으로 검사한다. 리소스 할당 및 프로세스 상태를 추적하는 알고리즘이 사용되고, 감지된 교착상태를 제거하기 위해서는 하나 이상의 프로세스를 롤백하고 다시 시작하게 한다. 운영체제의 자원 스케줄러에서 프로세스가 요청하거나 잠근 자원의 정보를 알 수 있기 때문에 이미 발생한 교착상태를 탐지하기는 쉽다.

교착상태가 탐지되면, 다음 방법들로 정정될 수 있다.

1) 프로세스 중단 (process termination)

2) 자원 선점 (resource preemption)

4) 무시(Ignore)

교착상태의 무시는 교착 상태 발생 간격이 크고, 발생했을 경우의 데이터 손실이 허용 범위 내일 때 사용 한다.

상호배제 (Mutual exclusion)는 공유 불가능한 자원의 동시 사용을 막기 위한 알고리즘이다.

상호배제는 다음 네 가지 조건을 만족해야한다.

1. 두 프로세스는 동시에 공유 자원에 진입할 수  없다.
2. 프로세스의 속도나 프로세서 수에 영향을 받지 않는다.
3. 공유 자원을 사용하는 프로세스만 다른 프로세스를 차단할 수 있다.
4. 프로세스가 공유 자원을 사용하려고 너무 오래 기다려서는 안 된다.

임계 영역(Critical Section)

공유 데이터에 여러 프로세스가 동시에 접근하면 시간 차이로 예상치 못한 결과를 만들 수 있기 때문에 임계 영역에는 반드시 한 번에 하나의 프로세스만 진입할 수 있어야 한다.

선행 그래프를 이용한 상호 배제

뮤텍스(mutual exclusion)

가장 흔하고 쉬운 예제로, 화장실과 열쇠에 비유할 수 있다.

화장실 한 칸과 열쇠 하나가 존재한다.

화장실 한 칸에는 한 사람밖에 들어가지 못하고, 그 화장실을 사용하려면 열쇠를 가지고 들어가야 한다.

그렇다면 다른 사람이 화장실을 사용하려면 앞서 화장실에 들어간 사람이 열쇠를 들고 나올 때 까지 기다려야 한다.

여기서 화장실 = 임계영역, 열쇠 = 소유권한으로 이해할 수 있다.

세마포어(semaphore)

뮤텍스에 반해 세마포어는 화장실이 여러 칸이고, 화장실 입구에 사용 가능한 칸의 개수를 나타내는 카운터가 있다고 생각하면 된다.

화장실이 세 칸이고, 카운터가 3 일때, 세 사람이 들어가면 카운터는 3이 감소해 0이 된다.
이 때 화장실에 들어가려는 사람이 있다면 카운터가 1 이상으로 증가할 때까지 기다려야한다.

병행 프로세스는 운영체제가 프로세서를 빠르게 전환시켜 프로세서 시간을 나눠 마치 프로세스 여러개가 동시에 실행 되는것처럼 하는것을 병행 프로세스라고 한다.

병행프로세스는 독립 프로세스, 협력 프로세스로 구분된다.

병행성은 시스템의 신뢰도를 높이고 처리 속도를 개선하여 처리 능력을 높이는데 매우 중요하다.
그리고 이를 위한 다음 몇 가지 해결 과제가 있다.

1) 공유 자원을 상호 배타적으로 사용해야 한다.
2) 병행 프로세스 간 협력이나 동기화가 되어야 한다. 상호배제도 동기화의 한 형태이다.
3) 두 프로세스 사이에서는 데이터를 교환할 수 있도록 통신이 되어야 한다.
4) 프로세스는 동시에 수행하는 다른 프로세스의 실행 속도와 관계없이 항상 일정한 실행 결과를 보장하는 결정성을 확보해야한다.
5) 교착 상태(deadlock)을 해결해야 한다
6) 병행 프로세스를 수행하는 과정에서 발생하는 상호배제, 즉, 어떤 프로세스가 작업을 실행 중일때 나머지 프로세스는 그것과 관련된 작업을 수행할 수 없도록 보장해야 한다.

병행성과 병렬성

병행성은 프로세서가 빠르게 여러 프로세스를 번갈아 처리해 마치 동시에 실행되는것처럼 보이는것이다.

반면에, 병렬성은 실제로 여러 프로세서를 사용해 여러 프로세스를 동시에 처리하는것이다. 

작업을 병렬로 처리할 때, 프로세서들이 모든 입출력 장치와 메모리를 참조할 수 있기 때문에 동시에 동일한 자원에 접근할 때 충돌이 발생할 수 있다.

따라서 프로세서간 충돌을 방지할 상호배제가 필요하다.

스레드란 프로그램이 자체적으로 둘 이상의 동시에 실행중인 작업으로 분할하는 방법이다.

같은 프로세스의 스레드들은 프로세스의 직접 실행 정보를 제외한 나머지 프로세스 관리 정보를 공유한다. 

프로세스 하나에 포함된 스레드들은 공동의 목적을 달성하기 위해 병렬로 수행한다.

스레드를 이용하면 다음과 같은 이점들이 있다.

1) 사용자 응답성 증가 : 응용프로그램의 일부분을 봉쇄하거나 긴 작업을 수행하더라도 병렬 프로그래밍으로 프로그램을 계속 실행할 수 있어 사용자 응답성이 증가한다. 예를 들면 다중 스레드를 적용한 웹 브라우저는 스레드 한 개가 파일을 로딩하는 동안 다른 스레드는 상호 작용을 할 수 있다.

2) 프로세스의 자원과 메모리 공유 가능 : 프로세스 내의 스레드들은 동일한 주소 공간에서 자원과 메모리를 공유하므로 시스템 성능이 향상된다.

3) 경제성이 좋음 : 프로세스간 문맥 교환보다 스레드간 문맥 교환이 오버헤드가 적다.

4) 멀티 프로세싱으로 성능과 효율 향상 : 다수의 스레드를 여러 프로세서에서 병렬로 실행해 성능과 효율성을 높일 수 있다.

멀티 스레드 vs 멀티 프로세싱

멀티 스레드 - 자원을 공유하기 때문에 멀티 프로세싱에 비해 메모리 절약

멀티 프로세싱 - 프로세스가 독립적으로 운용되기 때문에 멀티 스레드에 비해 안정성 향상

스레드의 구현

1) 사용자 수준 스레드

2) 커널 수준 스레드

3) 혼합형 스레드

프로세스는 일반적으로 '실행 중인 프로그램'을 의미한다.

또한 프로세스는 다음과 같이 다양하게 정의되기도 한다.

-실행 중인 프로그램
-비동기적 행위
-실행 중인 프로시저
-실행 중인 프로시저의 제어 추적
-운영체제에 들어 있는 PCB(프로세스 제어 블록)
-프로세서에 할당하여 실행할 수 있는 개체 디스패치가 가능한 대상

프로그램은 보조 기억장치에서 실행되기를 기다리는 코드와 정적인 데이터의 묶음이다.
이 프로그램이 메모리에 적재되면 프로세스가 된다.

프로세스가 메모리에 적재되었을 때 위 그림과 같은 구조를 지닌다.

스택

스택은 데이터를 일시적으로 저장하는 영역이다.
지역변수에 사용하고, 변수가 범위 밖으로 이동하면 공간을 해제한다. 호출한 함수의 반환 주소, 반환 값, 매개 변수 등에 사용하고, 함수를 호출할수록 커지고 반환하면 줄어든다.

힙

힙은 코드 영역과는 별도로 유지되는 자유 영역이다. 동적으로 메모리를 할당하려고 프로그램 실행 중 시스템 호출을 사용했다가 해제하는 방법으로 활용한다.

데이터

데이터는 프로그램의 가상 주소 공간이다. 전역변수나 정적변수를 저장하거나 할당하고 실행하기 전에 초기화한다.
그런데 변수 값은 실행 시간에 변경할 수 있어 읽기 전용 영역은 아니지만 읽기 전용 영역이나 읽기와 쓰기 영역으로 초기화할 수 있다. 정적 변수는 0으로 초기화하거나 초기화하지 않아도 된다. 초기화하지 않은 데이터는 데이터 영역의 끝에서 시작한다.

코드

코드는 실행 명령을 포함하는 메모리이거나 목적 파일에 있는 프로그램 영역이다. 프로그램을 시작할 때 프로세서가 디스크에서 읽어 실행하는 컴파일한 프로그램을 저장한다. 프로세스로 변경할 수 없고, 읽기 전용이므로 프로그램이 코드 영역을 침범하여 쓰기를 시도하면 오류가 발생해서 프로그램을 종료한다. 코드 영역은 공유할 수 있으므로 자주 실행하는 워드 프로세서, C 컴파일러, 셸 같은 프로그램의 사본 하나는 메모리에 존재한다.

스택과 힙 사이는 서브루틴을 실행하는 영역으로 운영체제로 매핑되지 않는다.

프로세스의 상태 변화

프로세스 제어 블록(PCB)

프로세스 제어블록은 특정한 프로세스를 관리할 필요가 있는 정보를 포함하는 운영 체제 커널의 자료 구조이다.

실행중인 프로세스는 모두 PCB를 가지고, 수행이 완료되면 PCB도 삭제된다.

문맥 교환(Context Switch)

문맥 교환이란 하나의 프로세스가 프로세서를 사용중인 상태에서 다른 프로세스가 프로세서를 사용하도록 하기 위해, 이전의 프로세스의 상태(문맥)를 보관하고 새로운 프로세스의 상태를 적재하는 작업을 말한다. 문맥교환이 일어나는 동안에는 다른 작업을 할 수 없고, 이를 오버헤드라 한다.