스케줄링이란?

운영체제가 CPU를 최대한 활용하고 프로그램들을 빨리 실행시키기 위해서 고안한 실행 스케줄 로직을 뜻합니다.

배치 처리 시스템

배치 처리 시스템은 여러 프로그램을 순차적으로 실행시키는 것입니다. 프로그램이 끝날 때마다 다른 프로그램을 연결해주어야 하는 수고로움을 덜 수 있는 점은 좋았지만, 앞선 프로그램 실행시간이 너무 길다면 뒤에 간단한 프로그램도 앞에 프로그램이 다 끝날 때까지 기다려야하는 단점도 있습니다. 즉, 동시에 여러 프로그램을 실행할 수 없는 점, 다중 사용자가 사용하기에 너무 불편한 점 등이 문제가 되어 새로운 스케줄링 방법들이 나왔습니다.

시분할 시스템

다중 사용자 지원을 위해 컴퓨터 응답시간을 최소화하는 시스템입니다. 응용 프로그램이 CPU를 점유하는 시간을 잘게 쪼개어서 동작하는 시스템입니다.

멀티 프로그래밍

최대한 cpu를 많이 활용하도록 고안한 시스템입니다. 응용프로그램이 CPU사용 외에 I/O사용 등을 위해 시간이 쓰여야 한다면 그 때 놀고 있는 CPU를 사용하기 위해서 프로세스(app)를 바꿔 동작하는 것입니다.

멀티 태스킹

하나의 운영체제에서 여러 개의 프로세스를 실행하는 방식. 실제로는 동시에 실행된 것이 아니지만 인간의 인지속도보다 빠르게 동작하여 동시에 실행된 것 처럼 보입니다.

멀티 프로세싱

여러 cpu가 응용 프로그램을 병렬로 실행하는 시스템.

프로세스란?

실행 중인 프로그램을 프로세스라고 합니다. 실행 중이라는 뜻은 운영체제가 메모리에 해당 프로그램을 올려주어서 실행되는 것을 말합니다. 그렇다면 응용 프로그램은 실행 중이지 않은 프로그램이죠. 즉, 파일이 저장 장치에 저장되어 있지만 메모리에는 올라가 있지 않은 정적인 상태를 의미합니다. 둘은 상태 측면에서 반대 개념입니다.

또, 하나의 응용 프로그램이 꼭 하나의 프로세스로 이루어져 있진 않습니다. 뒤에 나올 IPC 기법 등으로 인해 프로세스 간에 통신을 하면서 프로그램을 작성할 수도 있어서 여러 개의 프로세스가 상호작용 하면서 실행될 수도 있습니다.

스케줄링 알고리즘

스케줄러가 프로세스를 실행하는 규칙을 스케줄링 알고리즘이라고 합니다. 어떤 규칙에 의해서 프로세스를 선택하여 진행하는지를 알아봅시다.

FIFO 스케줄러

먼저 들어온 것을 먼저 실행하는 자료구조 방식으로 진행. 배치 처리 시스템에서 사용하고 가장 간단한 스케줄러임. FCFS(First Come First Srved)스케줄러라고도 불림.

SJF(Shortest Job First) 스케줄러

최단 작업 우선 스케줄러로 가장 프로세스 실행시간이 짧은 프로세스부터 실행시키는 알고리즘. 응답시간을 더 단축시킬 수 있는 방법이지만 실행시간을 미리 다 알긴 어렵습니다. RTOS에서 유용한 방식.

RTOS(RealTime OS): 응용 프로그램의 시작 완료 시간을 보장하는 OS
GPOS(Genral Purpose OS): 프로세스 실행시간에 민감하지 않고 일반적인 목적으로 사용되는 OS

Priority-Based 스케줄러

우선순위 기반 스케줄러. 정적 우선순위(프로세스마다 우선순위를 미리 지정)와 동적 우선순위(스케줄러가 상황에 따라 우선순위를 동적으로 변경)가 있습니다.

Round Robin 스케줄러

시분할 시스템 기반으로 일정시간마다 프로세스를 계속 바꿔주는 스케줄러.

상태 기반 스케줄링

cpu 활용도를 극대화하는 스케줄링 알고리즘입니다. 이를 이해하기 위해 프로세스 상태를 먼저 살펴봅니다.

프로세스 상태

프로세스 상태	설명
new	프로세스 생성
ready	프로세스 실행가능(대기)상태
blocked	특정 이벤트 대기 상태
running	현재 cpu 실행 상태
exit	프로세스 종료

상태 기반 스케줄링은 프로세스가 blocked 상태일 때 스케줄러가 다른 프로세스로 실행을 교체하는데 이 때 ready state queue에 있는 것 순으로 교체.

(wait상태로 cpu가 있다는 것은 cpu가 아무 것도 하고 있지 않은 상태로 idle 상태라고도 합니다.)

선점형과 비선점형 스케줄러

• 선점형 스케줄러: 하나의 프로세스가 다른 프로세스 대신에 프로세서(cpu)를 차지할 수 있음
  즉, 프로세스가 running 중이어도 스케줄러가 이를 중단시키고 다른 프로세스로 교체 가능
  ex) RoundRobin
• 비선점형 스케줄러: 하나의 프로세스가 끝나지 않으면 다른 프로세스는 cpu를 사용할 수 없음
  즉, 프로세스가 자발적으로 blocking상태로 들어가거나 실행이 끝났을 때만 다른 프로세스로 교체 가능
  ex) FIFO, SJF, Priority-based

인터럽트

cpu에 예외상황이 발생했음을 알리는 기술. cpu가 프로그램을 실행하고 있을 때 다른 상황이 발생해서 프로세스를 바꾸거나 다른 처리를 해야함을 알려주어서 재정비를 할 수 있게 합니다. 인터럽트가 발생하면 진행중인 프로세스가 중단되고 커널모드로 진입이 됩니다.

예외상황의 예
1. 선점형 스케줄러일 경우, running을 중단시키고 다른 프로세스로 교체할 타이밍을 알려줌
2. IO devices와의 커뮤니케이션이 끝나고 다시 cpu 프로세스를 진행해야 할 때 알려줌.
3. 오류가 났을 때 알려주어 해당 프로세스를 중지하거나 에러 표시를 할 수 있게 함.
4. 시스템콜을 만났을 때 cpu의 사용자 모드를 커널 모드로 바꿔줌

인터럽트의 종류

내부 인터럽트

• 주로 프로그램 내부에서 잘못된 명령 또는 잘못된 데이터 사용시 발생
• 사용자 모드에서 허용되지 않은 명령 또는 공간 접근
• 계산 결과가 overflow/underflow날 때
• 0으로 나눴을 때

외부 인터럽트

• 하드웨어 오류
• 타이머 이벤트

시스템콜 인터럽트

시스템콜을 실행하려면 강제로 코드에 인터럽트 명령을 넣어 cpu에게 실행시켜야 합니다.
1. 시스템콜 인터럽트 명령을 호출하면서 xxx값을 넘김
2. cpu는 사용자모드를 커널모드로 바꿈
3. IDT(Interrupt Descriptor Table)에서 xxx에 해당하는 주소(함수)를 찾아서 실행
4. 해당 시스템콜 함수 실행 후, 다시 커널모드에서 사용자 모드로 변경하고 다시 해당 프로세스 다음 코드 진행

IDT

인터럽트의 종류를 정의하고 번호와 실행 코드를 가리키는 주소가 매핑된 표.
리눅스의 경우,
0~31: 예외상황 인터럽트
32~47: 하드웨어 인터럽트
128: 시스템콜

프로세스와 컨텍스트 스위칭

프로그램: 컴퓨터 저장매체에 저장되어 있는 코드 덩어리
프로세스: 실행 중인 프로그램

프로세스의 구성

프로세스는 운영체제에 따라 조금 다를 순 있지만 일반적으로 4개의 영역으로 구성되어 있습니다.
위에서부터 stack, heap, data, code

• stack: 임시 데이터(함수 호출, 로컬 변수). 아래로 데이터를 쌓아감.
• heap: 코드에서 동적으로 만들어지는 데이터. 위로 데이터를 쌓아 감.
• data: 변수, 초기화된 데이터
  - bss: 초기화되지 않은 전역변수
  - data: 초기값이 있는 전역변수
• text(code): 프로그램 코드.

컨텍스트 스위칭

스케줄러가 cpu에 실행할 프로세스를 교체하는 기술. a process를 running상태로 바꾸는 것. 이는 빠르게 이루어져야 하므로 어셈블리어로 진행함.

Process Control Block
프로세스를 교체할 때, 이전 정보를 기억하고 있어야 하므로 프로세스 b로 넘어가기 전 a 프로세스의 program counter, stack pointer 값을 pcb라는 공간에 저장함.
1. Process ID
2. Register value(PC, SP)
3. scheduling info(process state)
4. memory info(momory size limit)
ex) linux

디스패치 순서
디스패치란 ready상태의 프로세스를 running 상태로 바꾸는 것.
1. 실행 중지할 프로세스 정보를 해당 프로세스의 PCB에 업데이트 해서 메인 메모리에 저장
2. 다음 실행할 프로세스 정보를 메인 메모리에 있는 해당 PCB 정보(PC, SP)를 CPU의 레지스터에 넣고 실행

IPC(InterProcess Communication)

ipc란 프로세스간 커뮤니케이션을 의미합니다. 기본적으로 프로세스 간에는 다른 프로세스의 공간에 접근할 수 없습니다. 그러나 성능을 높이기 위해 여러 프로세스를 만들어서 동시에 실행하는 등의 처리를 하기 위해 프로세스 간 통신할 수 있는 방법을 따로 제공합니다.

파일을 사용한 커뮤니케이션

공유해야 하는 내용을 공용 파일에 쓰고 읽는 방식이 있습니다. 그러나 이 방식은 실시간으로 직접 원하는 프로세스에 데이터 전달은 어려울 수 있습니다. 실시간으로 계속 이 파일만 바라볼 수는 없기 때문입니다.

커널 공간을 활용한 커뮤니케이션

커널 공간은 여러 개일 필요가 없으므로 공용 공간으로 빼놓고 그 부분을 통해 통신합니다.
이 방식을 사용하는 방법으로는 Message Queue, Shared Memory, Pipe, Signal, Semaphore, Socket방식이 있습니다.

Pipe

기본적으로 파이프는 단방향 통신입니다.
fork()로 자식 프로세스를 만들면 부모와 자식간의 통신이 이루어집니다. 리액트의 props같네요.

message queue

메세지 큐는 파이프와 다르게 부모에서 자식으로만 데이터가 연결되는 것이 아니라 어느 프로세스 간에라도 데이터 송수신이 가능합니다. 하지만 큐 자료형식이기 때문에 먼저 넣은 데이터 순서대로 읽혀집니다.

Shared Memory

커널 공간에 메모리 공간을 만들어두고 해당 공간을 변수처럼 사용하는 방식입니다. 해당 메모리 주소를 변수처럼 접근이 가능합니다. 공유메모리 key를 가지고 여러 프로세스가 접근도 가능합니다.

ipc외의 방법

signal

유닉스에서 30년 이상 사용된 전통적인 기법으로 커널 또는 프로세스에서 다른 프로세스에 어떤 이벤트가 발생되었는지를 알려주는 기법입니다. 프로세스 관련 코드에 관련 시그널 핸들러를 등록하면 pcb에서 해당 프로세스가 블록 또는 처리해야하는 시그널 관련 정보를 관리합니다. 블록을 푸는 순간 프로세스에 해당 시그널을 전달하여 핸들러로 특정 동작을 수행하고, 등록된 시그널 핸들러가 없다면 커널에서 기본 동작을 수행합니다. 이건 이벤트 사용이랑 비슷한 거 같네요.

주요 시그널 기본 동작

• SIGKILL: 프로세스를 죽임
• SIGALARM: 알람 발생
• SIGSTP: 프로세스 멈춤
• SIGCONT: 멈춘 프로세스 실행
• SIGINT: 프로세스에 인터럽트를 보내 프로세스 죽임
• SIGSEGV: 프로세스가 다른 메모리 영역을 침범

socket

소켓은 네트워크 통신을 위한 기술입니다. 즉, 기본적으로 두 개의 다른 컴퓨터 간의 네트워크 기반 통신을 위한 기술인데 이를 하나의 컴퓨터 안에서 두 개의 프로세스 간에 통신 기법으로 사용하는 것입니다.