Context Switching

Context란?

context switching에 대해 이야기하기 전, 먼저 context에 대한 이해가 필요하다.

프로세스는 자신만의 PCB(Process Control Block)을 갖는다. PCB에 대한 자세한 이야기는 여기에서 확인할 수 있다.

[PCB]

이때, context는 PCB에 저장된다. context는 CPU가 해당 프로세스를 실행하기 위해서 필요한 정보들을 말한다.

Context Switching 이란?

context switching 이 필요한 이유는?

CPU는 한 번에 하나의 프로세스만 실행시킬 수 있다. 하지만 OS가 CPU에게 다른 프로세스를 실행시키라고 명령했을 때, 해당 프로세스를 멈추고 다른 프로세스로 변경해야하기 때문에 context switching이 필요하다.

기존의 프로세스의 상태와 context를 저장하고, CPU가 다음 프로세스를 실행시킬 수 있도록 새로운 프로세스의 상태와 context를 교체하는 작업을 context switching 이라고 한다.

프로세스 상태
생성 상태 : PCB를 할당받았지만, CPU의 할당을 기다리는 상태
준비 상태 : CPU를 할당받았지만, 아직 차례가 아닌 상태
실행 상태 : CPU를 할당받아 실행 중인 상태
대기 상태 : 입출력 작업을 요청한 프로세스가 입출력장치의 작업을 기다리는 상태
종료 상태 : PCB와 프로세스가 사용한 메모리는 정리됨

context switching 은 어떻게 진행될까?

현재 실행 중인 프로세스의 정보는 CPU 내부의 레지스터에 저장하고 있다.
만약, 시스템 콜로 다른 프로세스를 실행해야한다면, CPU는 현재 실행중인 프로세스의 정보를 PCB에 저장한다.
다음 실행할 프로세스의 PCB 정보를 레지스터에 적재한다.

Context Switching 을 하는 주체

context switching 은 시스템콜(system call) 혹은 인터럽트(interrupt) 에 의해 발생할 수 있다.

Interrupt(인터럽트)

인터럽트란, 예외상황이 발생했을 때, CPU에게 알려 처리할 수 있도록 하는 것을 말한다.

하드웨어 인터럽트

하드웨어인 외부장치(키보드 입력, 마우스 클릭)가 발생시키는 인터럽트로, CPU가 아닌 다른 하드웨어 장치가 어떤 이벤트를 발생시켜 CPU 사용을 요청해야하는 경우이다.

alt + tab 과 같은 키를 입력하면, 입력 장치 관련(키보드, 마우스 등) 하드웨어에 의한 인터럽트 발생

소프트웨어 인터럽트

소프트웨어의 명령어에 의해 발생하는 인터럽트로, 특정 함수나 서비스를 요청하기 위해서 운영체제에 의해 의도적으로 발생된다. 예를 들어, 시스템 콜은 소프트웨어 인터럽트의 한 예라고 할 수 있다.

System call

응용 프로그램은 운영체제(OS)가 제공하는 서비스에 접근하기 위해서는 system call 이라는 인터페이스를 사용해야 한다.

[노래를 스피커로 출력하기 위해서 운영체제가 제공하는 오디오 출력 장치 관련 시스템 콜 사용]

위와 같은 예시에서는 다음과 같은 단계를 거친다.

사용자가 재생 버튼을 누르면, 응용 프로그램은 오디오 파일을 재생하기 위해 시스템 콜 요청
시스템 콜이 발생하면, CPU는 커널 모드로 전환
커널은 오디오 출력을 관리하는 장치 드라이버 호출
장치 드라이버는 디지털 오디오 데이터를 아날로그 신호로 변환하여 스피커를 통해 소리를 낼 수 있도록 함

[화면에 어플리케이션 인터페이스를 보여주기 위해 운영체제가 제공하는 그래픽 관련 시스템 콜 사용]

위와 같은 예시에도 동일하게 시스템콜을 사용한다.

만약, 사용자가 크롬 어플리케이션을 사용하고 있다면 운영체제는 CPU에 크롬 프로세스를 할당했을 것이다. 사용자가 카카오톡 어플리케이션으로 전환하려고 한다면, 운용체제는 카카오톡 프로세스의 PCB를 CPU 레지스터에 적재할 것이다.

시스템 콜이 발생하면 운영체제의 스케줄러는 다른 프로세스를 실행시키기 위해 컨텍스트 스위칭을 수행한다.

OS Scheduler (OS 스케줄러)

Scheduler

스케줄러란, 어떤 프로세스에게 자원을 할당할지 결정하는 운영체제 커널의 모듈이다. 운영체제는 스케줄러를 통해 CPU를 사용하려고 하는 프로세스들의 우선순위를 관리한다.

현 프로세스에서 다음에 어떤 프로세스를 실행시킬지 결정하는데에는 여러가지 방법이 있다. 스케줄러가 채택할 수 있는 알고리즘에 대해 알아보자.

Scheduling Algorithm

1. FIFO (First In First Out)

FIFO 알고리즘은 말 그대로 먼저 요청한 프로세스가 먼저 실행되는 알고리즘이다. 비선점형(Non-Preemptive) 스케줄링이다.

비선점형(Non-Preemptive) 스케줄링
CPU에 한 프로세스가 할당되면, 그 프로세스는 종료 혹은 I/O 처리를 위해 CPU를 방출할 때까지 CPU를 점유하는 방식

스케줄링이 단순하다.
모든 프로세스가 순서대로 실행될 수 있다.
프로세스가 길면, 다음 프로세스들은 해당 프로세스가 끝날 때까지 기다려야 한다.
즉, 한 프로세스가 오랫동안 CPU를 점유하여 손해가 발생한다.

2. Shortest Job First(SJF) 최단 작업 우선 스케줄링

프로세스의 실행 시간(next CPU burst)을 이용하여 가장 짧은 시간을 갖는 프로세스를 먼저 실행시키는 알고리즘이다. 두 프로세스가 동일한 실행 시간을 가지면 FIFO 방식으로 처리한다.

시간이 딜레이 되는 문제는 줄일 수 있다.
프로세스를 실제로 실행하기 전에 프로세스의 실행 시간은 예측하기는 어렵다.

3. Shortest Remaining Time(SRT) 최소 잔여 시간 우선 스케줄링

선점형 SJF라고 할 수 있다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다 더 짧은 실행시간을 가지고 있다면, context switching이 발생하는 알고리즘이다.

SJF보다 평균 대기시간이나 평균 반환시간에 효율적이다.
SJF와 동일하게 프로세스를 실제로 실행하기 전에 프로세스의 실행 시간은 예측하기는 어렵다.
context switching이 자주 발생하기 때문에 오버헤드가 크다.`

4. Priority-based 우선순위 기반 알고리즘

프로세스별로 우선순위를 설정하여 높은 것부터 실행시키는 알고리즘이다. 우선순위가 같다면 FIFO 방식으로 처리한다.

프로세스의 중요성에 따른 알고리즘이기 때문에 합리적이다.
우선순위가 낮은 프로세스에 대하여 starvation(기아) 상태가 발생할 수 있다.
- aging 기법: 해당 단점을 해결하기 위해서, 오랫동안 시스템에 대기하는 프로세스의 우선순위를 점진적으로 높인다.

5. Round Robin Scheduling

시간 할당량(Time-Slice)를 정의하여 모든 프로세스에게 해당 시간만큼씩 CPU를 할당하는 알고리즘이다. (시간 할당량이 매우 크면 FIFO와 같은 알고리즘이 된다.) 이때, 시간 간격은 quantum 이라고 한다.

[장점]

모든 프로세스가 공정하게 스케줄링을 받을 수 있다.
평균 대기 시간이 짧다.

[단점]

time slice가 너무 짧으면 context switching이 자주 발생하여 오버헤드가 크다.
시간 할당량을 통해 프로세스가 완료되지 못하면, 다음 차례가 올 때까지 기다려야하기 때문에 평균 처리 시간이 높다.

위와 같은 단점을 보완하기 위해서 변형 알고리즘들이 개발되었다.

여러 알고리즘 중, 내가 생각했을 때 가장 합리적인 알고리즘은 라운드 로빈 스케줄링이다. 모든 프로세스가 공정하게 실행되어 기아가 발생하지 않기 때문이다. 때문에 라운드 로빈 알고리즘을 변형하고 개선한 알고리즘에 대해 더 알아보고자 한다.

가중치 라운드 로빈

가중치 라운드로빈의 핵심 아이디어는 모든 작업이 동일한 시간을 받는 기존 라운드로빈 방식에서 벗어나, 각 작업의 중요도나 요구사항에 따라 다른 길이의 서비스 시간을 할당하는 것이다.

위 그림처럼 각 프로세스의 가중치를 설정하고, 이 가중치가 각 프로세스가 할당받을 시간을 결정하게 되는 것이다.

가중치를 통해 할당받는 시간을 결정하므로, 기존 라운드로빈 알고리즘을 공정성은 그대로 가져옴과 동시에 효율성을 증가시키는 알고리즘이다.