워밍업 클럽 CS 2주차 발자국 : 운영체제

CPU 스케줄링 알고리즘

SJF: Shortest Job First

SJF는 Burst time(실행 시간)이 짧은 프로세스를 먼저 실행하는 알고리즘입니다.

• 이론적으로는 FIFO보다 성능이 좋습니다.

• 하지만 실제 구현에서는 두 가지 문제가 발생합니다:

   

  • 프로세스의 실행 시간을 미리 예측하기 어렵습니다.

     

  • 짧은 프로세스만 우선적으로 처리되면서, 긴 프로세스는 오랫동안 실행되지 않을 수 있습니다.

결과적으로, 이러한 문제들로 인해 SJF 알고리즘은 실제 운영체제에서 많이 사용되지 않습니다.

RR: Round Robin

Round Robin(RR) 알고리즘은 FIFO의 단점을 해결하기 위해 고안된 알고리즘입니다.

• 각 프로세스에 타임 슬라이스 또는 타임 퀀텀이라는 고정된 시간 동안 CPU를 할당합니다.

• 할당된 시간이 지나면 해당 프로세스는 큐의 뒤로 밀려나고, 다음 프로세스가 실행됩니다.

성능:

• 평균 대기 시간은 상황에 따라 FIFO와 비슷할 수 있습니다. 그러나 RR 알고리즘은 컨텍스트 스위칭으로 인해 추가적인 오버헤드가 발생합니다.

• 타임 슬라이스 크기에 따라 성능이 달라집니다:

   

  • 타임 슬라이스가 크면: 사실상 FIFO와 비슷해집니다.

     

  • 타임 슬라이스가 작으면: 마치 여러 프로세스가 동시에 실행되는 것처럼 보이지만, 잦은 컨텍스트 스위칭으로 인해 오버헤드가 커집니다.

최적의 타임 슬라이스는 여러 프로세스가 버벅거리지 않고 동시에 실행되는 것처럼 보이면서도, 오버헤드가 최소화되는 값을 찾아야 합니다.

MLFQ: Multi-Level Feedback Queue

MLFQ는 오늘날 운영체제에서 널리 사용되는 CPU 스케줄링 기법으로, RR 알고리즘을 개선한 방식입니다.

주요 개념:

• CPU-bound 프로세스: CPU 연산을 많이 수행하며, CPU 사용률과 처리량이 중요한 프로세스.

• I/O-bound 프로세스: I/O 작업이 많아 응답 속도가 중요한 프로세스.

MLFQ는 CPU-bound와 I/O-bound 프로세스를 적절히 구분하여 최적의 성능을 제공합니다.
프로세스의 특성에 따라 타임 슬라이스를 다르게 적용하는데, CPU-bound 프로세스에는 더 긴 타임 슬라이스를, I/O-bound 프로세스에는 짧은 타임 슬라이스를 할당합니다.

동작 원리:

운영체제는 CPU-bound 프로세스와 I/O-bound 프로세스를 어떻게 구별할까여요?

• I/O-bound 프로세스는 주로 입출력 작업을 수행하므로, CPU를 잠깐 사용하고 스스로 CPU를 반납합니다. 이 때문에 CPU 사용이 적은 경우가 많아 I/O-bound 프로세스일 확률이 높습니다.

• 반면, CPU-bound 프로세스는 CPU에서 연산을 주로 수행하며, 타임 슬라이스를 초과하여 CPU를 사용하다가 강제로 CPU를 빼앗기게 됩니다. 이 경우 CPU 사용량이 많아 CPU-bound 프로세스일 가능성이 큽니다.

이를 바탕으로 MLFQ는 여러 개의 우선순위 큐를 사용해 프로세스를 관리합니다.

• 우선순위가 높은 큐에는 작은 타임 슬라이스가 할당되어 빠른 응답이 필요한 프로세스가 실행됩니다.

• 우선순위가 낮은 큐로 갈수록 타임 슬라이스가 커지며, CPU-bound 프로세스는 우선순위가 낮은 큐로 이동해 더 긴 시간을 할당받고 실행됩니다.

요컨대,

1. 타임 슬라이스를 초과하여 강제로 CPU를 뺏긴다면, 해당 프로세스는 우선순위가 더 낮은 큐로 이동합니다.

2. 이후, 더 큰 타임 슬라이스가 할당되며, 우선순위가 낮은 큐로 이동할수록 타임 슬라이스는 점점 커집니다.

3. 결국, 프로세스는 거의 FIFO처럼 연속적으로 실행될 수 있게 됩니다.

이 방식으로 CPU 사용량이 많은 프로세스와 응답 속도가 중요한 프로세스 모두에게 적절한 스케줄링을 제공합니다.

프로세스 동기화

프로세스 간 통신

프로세스는 독립적으로 실행될 수 있지만, 다른 프로세스와 데이터를 주고받으며 통신할 때도 있습니다. 이러한 통신은 같은 컴퓨터 내의 프로세스 간이거나, 네트워크를 통해 다른 컴퓨터와 할 수도 있습니다.

통신의 종류

1. 한 컴퓨터 내에서의 통신

   • 파일: 여러 프로세스가 하나의 파일을 사용해 데이터를 읽고 씁니다.

   • 파이프: 운영체제가 생성한 파이프를 통해 데이터를 주고받습니다.

    

2. 스레드 간 통신

   • 스레드는 코드, 데이터, 힙을 공유하고, 각자의 스택만 따로 갖습니다. 전역 변수나 힙을 사용해 데이터를 주고받을 수 있습니다.

    

3. 네트워크 통신

   • 운영체제가 제공하는 소켓 통신이나 RPC(원격 프로시저 호출)를 통해 네트워크로 통신합니다.

공유 자원과 임계 구역

프로세스 간 통신에서 여러 프로세스가 동시에 사용하는 변수나 파일을 공유 자원이라 부릅니다.

하지만 공유 자원에 대한 접근 순서에 따라 연산 결과가 달라질 수 있습니다. 컨텍스트 스위칭으로 인해 어떤 프로세스가 먼저 실행될지 예측할 수 없어 동기화 문제가 발생합니다.

• 임계 구역: 여러 프로세스가 동시에 접근해서는 안 되는 영역.

• 경쟁 조건: 공유 자원에 대해 여러 프로세스가 경쟁하는 상황.

이 문제를 해결하려면 상호 배제 메커니즘이 필요합니다.

상호 배제 요구 사항:

1. 임계 구역에 동시에 하나의 프로세스만 접근해야 합니다.

2. 여러 요청이 있어도 한 번에 하나의 프로세스만 접근을 허용해야 합니다.

3. 임계 구역에 들어간 프로세스는 빠르게 나와야 합니다.

세마포어

• 세마포어는 상호 배제를 구현하는 메커니즘 중 하나로, 여러 프로세스가 동시에 공유 자원에 접근하지 못하게 합니다.

• 세마포어는 정수형 변수로 표현되며, 여러 개의 세마포어가 존재할 수 있습니다.

세마포어의 동작 방식:

1. 프로세스 A가 세마포어를 받으면(wait) 공유 자원을 사용하고, 그동안 프로세스 B는 대기합니다.

    

2. A가 자원을 사용한 후 세마포어를 반납(signal)하면 B가 자원을 이어서 사용합니다.

단점: 세마포어를 잘못 사용할 경우 문제가 발생할 수 있습니다

모니터

• 모니터는 세마포어의 단점을 보완한 상호 배제 메커니즘입니다.

• 모니터는 운영체제에서 처리하는 것이 아닌 프로그래밍 언어 차원에서 제공됩니다.

• 자바에서는 synchronized 키워드를 사용해 모니터를 지원하며, 이 키워드가 붙은 함수는 여러 프로세스에서 동시에 실행되지 않도록 보장합니다.

public class Health {
	private int health = 100;
	
	synchronized void increase(int amount) {
		health += amount;
	}

	synchronized void decrease(int amount) {
		health -= amount;
	}	
}

모니터는 세마포어처럼 wait와 signal 함수를 직접 사용할 필요가 없기 때문에, 프로그래머가 더 안전하고 편리하게 동기화 문제를 해결할 수 있습니다.

데드락 : 교착상태

데드락이란

교착상태(Deadlock)는 여러 프로세스가 서로 다른 프로세스가 사용하는 자원의 해제를 기다리며, 아무도 작업을 진행하지 못하는 상태를 의미합니다.

주된 원인은 공유 자원 때문입니다. 공유 자원이 없으면 교착상태가 발생하지 않으며, 대표적인 예로 식사하는 철학자 문제가 있습니다.

교착상태 발생 조건:

교착상태는 다음 4가지 조건 중 하나라도 충족하지 않으면 발생하지 않습니다:

1. 상호배제: 하나의 자원을 한 프로세스만 점유하며, 다른 프로세스는 사용할 수 없습니다.

2. 비선점: 프로세스가 점유하고 있는 자원을 다른 프로세스가 강제로 빼앗을 수 없습니다.

3. 점유와 대기: 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리는 상황입니다.

4. 원형 대기: 여러 프로세스가 점유와 대기를 하면서 원형 구조를 이룹니다.

교착상태 예방을 위해 이 조건들을 통제하는 방법이 있지만, 비효율적이고 제약이 많아 예방 대신 해결 방법이 더 많이 연구되었습니다.

데드락 해결 방법

1. 교착상태 회피 (Deadlock Avoidance)

교착상태 회피는 프로세스에게 자원을 할당할 때, 교착상태가 발생하지 않도록 필요한 자원만을 할당하는 방식입니다.

자원 상태를 안정 상태와 불안정 상태로 나누며, 운영체제는 자원이 부족해 교착상태로 이어질 위험이 없도록 안정 상태를 유지하려 합니다.

• 은행원 알고리즘

  • 교착상태 회피를 설명하는 알고리즘으로, 은행이 대출 가능한 자원을 관리하는 방식에 비유됩니다.

  • 은행은 자원을 대출할 때, 자신이 가진 자원과 대출 요청을 비교해 안정 상태를 유지하며, 불안정 상태가 될 가능성이 있는 요청은 거부합니다.

  • 은행이 자원을 대출하는 과정에서, 대출 요청을 모두 수용하면 나중에 대출금을 회수하지 못해 교착상태에 빠질 수 있기 때문에 안정 상태를 유지해야 합니다.

  • 이 알고리즘은 교착상태를 피할 수 있지만, 구현이 복잡하고 비용이 많이 듭니다.

2. 교착상태 검출 (Deadlock Detection)

교착상태 발생을 예방하는 것이 비효율적일 때, 교착상태가 발생하면 이를 검출하고 해결하는 방법이 있습니다.

• 가벼운 교착상태 검출:

   

  • 타이머를 사용하여 일정 시간 동안 프로세스가 작업을 진행하지 않으면 교착상태로 간주하고 해결합니다.

  • 타임아웃 시 체크포인트에서 롤백하여 상태를 복구할 수 있지만, 불필요하게 종료되는 프로세스가 발생할 수 있습니다.

     

• 무거운 교착상태 검출:

   

  • 자원 할당 그래프를 이용하여 운영체제가 자원과 프로세스 간의 관계를 지속적으로 추적합니다. 교착상태가 발생하면 이를 탐지해 교착 상태를 일으킨 프로세스를 강제 종료하거나 롤백합니다.

  • 하지만 자원 할당 그래프를 유지하는데 오버헤드가 발생합니다.

  ---

  메모리

메모리 종류

• 레지스터

  • CPU 내에 있는 가장 빠른 메모리.

  • CPU가 사용하는 메모리로, 굉장히 속도가 빠름.

  • 휘발성 메모리로, 전원이 꺼지면 데이터가 사라짐.

  • CPU 구분 시 32bit, 64bit는 레지스터의 크기를 의미.

  • CPU는 계산 시 메인메모리에 있는 데이터를 레지스터로 가져와 처리 후, 다시 메인메모리에 저장.

• 캐시

  • 레지스터와 메인메모리 사이에 존재하며, 휘발성 메모리.

  • 레지스터는 빠르지만 메인메모리는 느리기 때문에, 자주 사용될 데이터를 미리 캐시에 저장하여 처리 속도를 높임.

  • 여러 단계로 구성되어 있으며, L1 캐시가 가장 빠르고, L2, L3 순으로 속도가 느려짐.

  • CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면, 단계에 따라 L1 캐시를 보고, 여기 없다면 L2 캐시를 확인해보고, 여기도 없다면 메인메모리에서 값을 가져옴.

• 메인메모리

  • 운영체제와 각종 프로세스가 실행되는 공간.

  • 휘발성 메모리로, 전원이 꺼지면 데이터가 사라지는 휘발성 메모리.

  • 하드디스크나 SSD보다 빠르지만 가격이 비싸, 실행 중인 프로그램들만 올려서 사용.

• 보조저장장치

  • 하드디스크나 SSD처럼 비휘발성 메모리로, 전원이 꺼져도 데이터를 유지.

  • 가격이 저렴하고, 대용량 데이터를 저장하는 데 사용.

메모리와 주소

이제 메인메모리를 간단히 "메모리"라고 부르기로 하자.

멀티프로그래밍 환경에서는 여러 프로세스가 메모리에 올라오기 때문에, 메모리 관리가 복잡해진다.

운영체제는 메모리를 관리하기 위해 메모리를 1바이트 단위로 나누고, 각 구역에 번호를 매기는데, 이 번호를 "주소"라고 한다.

32bit와 64bit

• 32bit CPU: 레지스터 크기가 32비트며, CPU가 다룰 수 있는 메모리는 최대 4GB(2^32)이다.

• 64bit CPU: 64비트는 32비트보다 더 많은 메모리를 처리할 수 있으며, 성능도 더 뛰어나다.

물리주소와 논리주소

• 물리주소: 컴퓨터가 메모리에서 실제로 사용하는 주소.

• 논리주소: 사용자 관점에서 본 메모리 주소. 사용자는 물리주소를 직접 다루지 않고, 논리주소를 통해 메모리에 접근한다.

운영체제는 메모리의 일부를 자신만을 위한 공간으로 예약한다. 사용자 프로세스가 이 공간에 접근하면 보안 문제가 발생할 수 있어, 경계 레지스터를 사용해 이를 방지한다.

경계 레지스터는 CPU내에 존재하는 레지스터로 메모리 관리자(MMU)가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고, 만약 벗어났다면 그 프로세스를 종료시킨다.

절대주소와 상대주소

• 절대주소: 메모리 관리자(MMU)가 물리적으로 메모리를 관리할 때 사용하는 실제 주소

• 상대주소: 개발자가 프로그램을 개발할 때, 주소를 0번지부터 시작한다고 가정하는 방식.

사용자는 프로그램이 메모리의 어느 위치에 있는지 알 필요 없이, 컴파일러가 생성한 상대주소(논리주소)를 사용한다

사용자가 요청한 논리주소를 메모리 관리자가 재배치 레지스터 값을 이용해 물리주소로 변환하여 접근한다.

재배치 레지스터는 프로그램이 메모리의 어느 주소에서 시작하는지를 저장하는 레지스터로, 프로그램이 실행될 때마다 그 시작 주소를 기록한다. 메모리 관리자는 프로그램이 실행될 때마다 이러한 재배치 작업을 수행하므로, 사용자 프로그램은 메모리의 어느 위치에서 실행되는지 신경 쓰지 않고도 동작할 수 있다.

이 방식 덕분에 개발자는 프로그램이 항상 0번지에서 시작한다고 가정하고 작성할 수 있으며, 실제 메모리 배치는 운영체제가 알아서 처리한다. 만약 프로그램이 다른 위치에서 실행되더라도, 재배치 레지스터만 변경해주면 되기 때문에 매우 유연한 방식이다.

메모리 할당방식

초기 유닛 프로그래밍 환경에서는 큰 프로그램을 실행하기 위해 필요한 부분만 메모리에 올리고, 나머지는 스왑영역(보조 저장장치)에 저장하는 메모리 오버레이 기법을 사용했다.

*swap : 스왑영역에 있는 데이터 일부를 메모리로 가져오고, 메모리에 있는 데이터를 스왑영역으로 옮기는 것

오늘날 메모리에 여러 프로세스가 올라오는 멀티프로그래밍 환경에서의 메모리 관리

메모리 분할 방식

가변 분할 방식 

• 프로세스 크기에 맞춰 메모리를 연속된 공간에 할당하는 방식.

• 장점: 내부 단편화가 없음. 

• 단점: 외부 단편화 발생.

프로세스가 실행을 마치고 메모리에서 내려가면, 해당 프로세스가 차지하던 공간이 빈다. 이 빈 공간이 여러 군데 흩어져 있을 경우, 새로운 프로세스를 메모리에 올리기 위해 필요한 만큼의 연속된 메모리 공간을 찾기 어려워진다. 이를 외부 단편화라고 한다.

외부 단편화를 해결하기 위해 조각 모음(Defragmentation) 작업을 수행한다. 이 과정은 메모리 내에 흩어져 있는 빈 공간을 한데 모아, 연속된 큰 메모리 블록을 확보하는 방식이다. 그러나 조각 모음을 실행하려면, 현재 메모리에서 실행 중인 프로세스들을 일시 중지하거나, 메모리 내 프로세스의 위치를 이동해야 하므로 오버헤드가 발생한다.

고정 분할 방식

• 프로세스를 크기와 상관없이 일정 크기로 나누어 할당하는 방식.

• 장점: 구현이 간단하고 오버헤드가 적음.

• 단점: 작은 프로세스에도 큰 공간이 할당되어 내부 단편화 발생.

• 내부 단편화를 해결하는 방법은 없고, 분할되는 크기를 적절히 최소화해서 내부단편화를 최소화해야 함.

내부 단편화는 메모리가 고정된 크기로 분할되었을 때 발생하는 문제이다. 고정된 크기의 메모리 블록에 작은 프로세스를 할당하면, 프로세스가 차지하지 않은 나머지 공간이 낭비되는 현상을 내부 단편화라고 한다.

작은 크기의 프로세스를 큰 메모리 블록에 할당할 때 문제가 심각해진다. 이를 해결하기 위해 메모리 블록의 크기를 줄이면 내부 단편화는 감소하지만, 블록이 너무 작으면 관리해야 할 메모리 조각이 많아져 또 다른 성능 문제가 발생할 수 있다. 결국 메모리 블록의 크기를 적절히 조정하는 것이 내부 단편화를 최소화하는 데 중요한 전략이 된다.

버디 시스템

• 고정 분할 방식과 가변 분할 방식의 장점을 결합하여 메모리 관리의 효율성을 높이기 위한 방법

• 2의 제곱수로 메모리를 분할해, 메모리의 단편화 문제를 줄이는 것이 핵심.

• 장점: 외부 단편화를 방지하고, 메모리 할당 및 해제가 용이하다.

• 내부 단편화가 발생하긴 하지만, 공간 낭비는 최소화된다.

메모리를 2의 제곱수 크기로 나누고, 프로세스가 필요로 하는 메모리 크기에 가장 가까운 2의 제곱수 크기를 할당한다. 할당된 메모리 블록을 버디(buddy)라고 부르며, 만약 프로세스가 할당된 메모리를 반환하면 이 버디는 다시 인접한 버디와 결합하여 더 큰 블록으로 병합할 수 있다.