잡지식창고

메모리 관리

메모리 관리는 프로세스들을 위해 메모리를 할당하고 제거하며 보호하는 활동이다. 이는 저장장치 전반(하드디스크, DB, etc..)에 해당한다.

메모리 관리는 메모리 관리자가 담당한다. 메모리 관리자는 운영체제의 관리 모듈과 메모리 관리장치(Memory Management Unit)가 협업하여 관리한다.

메모리 관리자는 메모리와 관련된 여러 관리 정책을 수립해 이에 따라 메모리를 관리한다.

관리 정책

1) 적재 정책

디스크에서 메모리로 프로세스를 반입할 시기 결정한다.

적재는 다음 두 가지 방법으로 실행된다.

2) 배치 정책

디스크에서 반입한 프로세스를 메모리 어느 위치에 저장할 것인지 결정한다.

3) 대치 정책

메모리가 충분하지 않을 때 현재 메모리에 적재된 프로세스 중 제거할 프로세스를 결정하는 방법이다.

시기 및 사용 빈도에 따라 선입선출(FIFO) 대치 알고리즘, 최근 최소 사용(LRU) 대치 알고리즘 등 다양한 방법이 있다.

스케줄링 알고리즘의 선택 기준

스케줄링 알고리즘을 비교할 때 참조할 수 있는 기준은 다음과 같다.

1) 프로세서 사용률 - CPU가 놀지 않고 얼마나 많이 사용되고 있는가?
2) 처리율 - 단위시간당 처리하는 일의 양
3) 반환시간 - 수행 요청을 한 다음 끝날때까지 걸리는 시간
4) 대기시간 - 작업이 준비 큐에서 기다리는 시간
5) 반응시간 - 대화형으로 동작할 때 작업 요청 후 반응하는데 까지의 간격

라운드 로빈 스케줄링

라운드 로빈 스케줄링은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나이다.

라운드 로빈 스케줄링은 작은 단위의 시간인 규정 시간량(time quantum)또는 시간 할당량(time slice)을 정의한다. 보통 규정 시간량은 10ms ~ 100ms정도이다. 준비 큐를 순환 큐로 설계해서 스케줄러가 준비 큐를 돌아가며 한 번에 한 프로세스에 정의된 규정 시간량만큼 프로세서를 제공한다. 준비 큐는 FIFO(First In First Out) 큐로 되어있어 새로운 프로세스를 추가할 때는 준비 큐의 맨 뒤에 붙인다.

스케줄러는 준비 큐의 가장 앞부분의 프로세스에 프로세서를 할당하는데, 해당 프로세스가 규정 시간 안에 작업을 마친 경우엔 프로세서가 준비 큐의 다음 프로세스에 할당된다. 규정 시간을 초과한 경우에는 운영체제가 인터럽트해 중단된 프로세스의 레지스터들을 PCB에 저장하고 프로세스는 준비 큐의 마지막 위치에 들어간다.

라운드 로빈 스케줄링의 장단점

다단계 큐 스케줄링

각 작업을 여러개의 큐에 분할하여 스케줄링 하는 방식이다.

각 큐는 각자 독자적인 스케줄링을 가지고, 고정된 선점 우선순위를 가진다.

이때 하위 우선순위를 가진 큐는 상위 우선순위를 가진 큐가 다 처리되어야만 처리가 가능하다. 이 때문에 기아 상태가 발생할 수 있다. 

다단계 피드백 큐 스케줄링과 다른 점은 작업이 하나의 큐에 고정된다는점이다.

다단계 피드백 큐 스케줄링

모든 프로세스는 다 같이 가장 우선순위가 높은 큐에 들어온다. 이 때 큐에 지정된 time-quantum을 채운(초과한) 프로세스는 그보다 한단계 아래 우선순위의 큐에 들어가게 된다.

HRN 스케줄링

각 작업의 우선순위에 따라 서비스해주는 스케줄링 방법이다.

이 때, 우선순위는 다음과 같이 정한다.

우선순위 = (서비스를 받을 시간 + 대기한 시간)/서비스를 받을 시간

HRN 스케줄링은 자원을 효율적으로 사용하고, 기아가 발생하지 않는 특징이 있다.

이에 반해 오버헤드가 높은 단점이 있다.

스케줄링은 다중프로그래밍을 가능하게 하는 운영체제의 동작 기법이다.

운영체제는 프로세스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선할 수 있다.

스케줄링의 목표는 다음과 같다.

• 단위시간당 처리량 최대화
  
• 자원할당의 공정성 보장
• 적절한 반환시간 보장
• 자원 사용의 균형 유지
• 서비스 사용기회 확대
• 예측 가능성 보장
• 실행 대기 방지
• 서비스 수 감소 방지
• 오버헤드 최소화
• 우선순위 배정

단위시간당 처리량을 최대화하는것은 가장 중요한 목표중 하나지만, 이 때문에 자원이 균등하게 할당되지 않아 무한대기에 빠질 수 있다. 그렇기 때문에 자원을 할당하는데에 있어서 공정성이 보장되어야한다.

스케줄링의 기준 요소 - 버스트

프로세서(CPU) 버스트 -> 프로세스를 프로세서에서 실행할 때
입출력(I/O) 버스트 -> 프로세스가 추가로 실행하려고 입출력을 기다리고 있을 때

프로세서 버스트가 길면 CPU 바운드, 입출력 버스트가 길면 I/O 바운드이다.

스케줄링을 할 때, 어떤 버스트가 길게 걸리는지에 따라 우선순위에 영향을 미친다.

스케줄링의 단계

1단계 스케줄링 (장기 스케줄링)
-어느 작업부터 시스템 내의 자원들을 실제로 사용할 수 있도록 할지를 결정한다.

2단계 스케줄링 (중기 스케줄링)
-어느 프로세스부터 CPU를 차지할 수 있게 할지를 결정한다. 프로세스들을 보류시키고 다시 활성화하는 기법을 사용하여 시스템에 대한 단기적인 부하를 조절한다. 이로써 시스템을 적절히 운영한다.

3단계 스케줄링 (단기 스케줄링)
-CPU가 사용 가능한 경우 어느 프로세스에게 배당할지를 결정한다.

스케줄링 큐

준비 큐(ready queue)는 프로세서를 할당받아 실행하려고 기다리는 프로세스들이 대기하는 큐다.
장치 큐(device queue)는 장치를 사용하려는 프로세스들이 대기하는 큐다.

스케줄링에서는 여러개의 큐가 우선순위에 따라 번갈아가며 자원을 사용한다.

큐잉 도표

프로세스에 프로세서가 할당되면 다음 상황이 일어난다.

1. 프로세스가 I/O 요청을 보내고 I/O 큐에 들어간다.
2. 프로세스가 Sub-process를 생성하고(fork) 생성한 프로세스의 종료를 기다린다.
3. 프로세스가 인터럽트되어 다시 준비큐에 들어간다.
4. 프로세스가 시간 할당량을 초과해 준비큐로 들어간다.

장기 스케줄러와 단기 스케줄러

장기 스케줄러는 작업 스케줄러라고도 하며, 스케줄링에 따라 디스크에서 메모리로 작업을 가져와 처리할 순서를 결정한다.

단기 스케줄러는 메모리에 적재된 프로세스 중 프로세서를 할당하여 실행 상태가 되도록 결정하는 프로세스 스케줄링을 한다. 이때는 프로세스가 실행하는 데 필요한 자원의 요청을 만족해야 한다.

장기 스케줄러와 단기 스케줄러의 가장 큰 차이는 실행 빈도이다. 단기 스케줄러는 실행할 프로세스를 수시로 선택한다.
반면에 장기 스케줄러는 시스템에 새로운 작업이 분단위로 들어오므로 단기 스케줄러에 비해 상대적으로 드물게 수행된다.

대부분의 작업이 입출력 중심 작업(I/O bound)과 프로세서 중심 작업(CPU bound)으로 구성되므로 스케줄러가 작업을 선택한 두 종류의 작업을 잘 혼합하여 선택해야 시스템의 성능을 높일 수 있다.

중기 스케줄러

중기 스케줄러는 프로세스들이 프로세서를 서로 차지하려고 할 때 프로세스를 별도의 기억장소에서 빼낼 수 있어 다중프로그래밍의 정도를 줄일 수 있다. 시간이 흐른 후 빼낸 프로세스는 다시 메모리에 들어가 실행을 중단했던 곳부터 다시 실행한다. 이 방법을 스왑이라고 하는데, 스왑 인과 스왑 아웃을 중기 스케줄러가 결정한다. 스왑은 작업의 혼합을 개선하거나 프로세스가 가지고 있던 메모리를 사용할 수 있게 하는 데 필요하다.

선점 스케줄링과 비선점 스케줄링

비선점 스케줄링(Non-Preemptive scheduling)은 이미 할당된 cpu를 다른 프로세스가 강제로 빼앗아 사용할 수 없게 하는 기법이다.

반면에 선점 스케줄링(Preemptive scheduling)은 하나의 프로세스가 cpu를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 cpu를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.

선점 스케줄링은 프로세스 하나가 장시간 동안 프로세서를 독점하는 것을 방지하기 때문에 모든 프로세스에 프로세서를 서비스할 기회를 늘릴 수 있다. 따라서 우선순위가 높은 프로세스들이 긴급 처리를 요청할 때 용이하다.

하지만 선점 스케줄링은 오버헤드가 커질 수 있어 이를 효과적으로 이용하려면 메모리에 프로세스가 많이 적재되어 있어야 한다. 즉, 프로세서를 사용 가능할 때마다 실행할 수 있는 프로세스들이 준비 상태에 있어야 효과적이다. 따라서 선점 스케줄링에서는 우선순위라는 개념을 반드시 고려해야 하는데, 우선순위는 의미 있게 부여하지 않으면 효과가 없다.

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

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

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

교착상태(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 이상으로 증가할 때까지 기다려야한다.