4주차 - Chapter 9~11

Contents

Chapter 9 운영체제 시작하기

운영체제를 알아야 하는 이유

• 운영체제가 없다면?
• 사용자가 컴퓨터 시스템을 제어하기 위한 하드웨어 단위의 코드를 일일이 작성하고, 작동시켜야 한다. 이 과정에서 잘못된 조작을 했다면 시스템 전체 또는 하드웨어에 악영향을 줄 수 있다.
• 프로그램을 효율적으로 실행하기 어렵다.
• 컴퓨터 시스템에 문제가 생겼을 때, 이를 대처하기 어렵다.

• 운영체제를 이해함으로써 하드웨어와 소프트웨어 사이에 어떤 상호작용이 이루어지는지, 운영체제에서 제공하는 기능을 활용하여 효과적인 소프트웨어를 개발할 수 있다.

운영체제의 큰 그림

커널

• 커널 외에도 운영체제가 제공하는 대표적인 기능들은 다음과 같다.
• 유저 인터페이스
• GUI (Graphical User Interface)
• CLI (Command Line Interface)

• 커널은 메모리에서의 커널 영역에 위치해 있다. 메모리에서 응용프로그램이 적재되는 영역은 사용자 영역이다. 이렇게 응용프로그램이 위치하는 사용자 영역과 커널이 위치하는 커널 영역이 분리되어 있기 때문에, 응용프로그램이 커널에 직접 접근할 수 없게 된다.

User mode와 Kernel mode

• 운영체제는 응용프로그램이 커널과 같은 운영체제의 핵심 부분을 직접적으로 접근하지 못하도록 CPU에 안전장치를 걸어 놓았다.
• 프로그램을 실행하는 주체는 언제나 CPU다. 따라서 응용프로그램이 운영체제의 핵심 부분을 직접 접근하지 못하게 하려면 CPU가 현재 사용자 응용프로그램을 실행하는지 커널을 실행하는지 구분해야 할 필요가 있다.
• CPU가 User mode면 응용프로그램을 실행하고 있다는 것이며, 이때는 사용자 영역에만 CPU가 접근할 수 있다.
• 반대로, CPU가 Kernel mode면 커널 코드를 실행하고 있다는 것이다. 이때는 커널 영역에만 CPU가 접근할 수 있다.

시스템 콜

• 응용프로그램은 직접적으로 컴퓨터 자원에 접근할 수 없다.

• 따라서, 응용프로그램이 컴퓨터 자원을 이용해야 할 때, 직접 접근하는 대신 운영체제에 이용할 컴퓨터 자원과 데이터, 버퍼와 같은 정보를 특정 함수에 인자로 포함하여 호출해야 한다.

• 해당 함수가 호출되면 CPU는 User mode에서 Kernel mode로 전환되며, 현재 실행중인 프로그램의 실행을 잠시 중단한 후, 현재 CPU의 상태 정보를 커널 영역의 PCB (Process Control Block)에 저장한다. 그리고 호출된 함수와 그 인자에 맞추어 컴퓨터 자원을 이용한다.

• 이용이 끝나면 실행 중이었던 응용프로그램으로 돌아와 다시 실행해야 하므로, PCB에 저장되어 있던 상태 정보를 다시 CPU로 불러들이고 Kernel mode에서 User mode로 전환한다. 그런 다음 호출했던 함수 그 다음에 실행할 명령어가 있다면 계속 이어서 실행한다.

• 일반적으로 응용프로그램은 실행 과정에서 컴퓨터 자원을 빈번하게 이용하며, 이를 위해 시스템 콜이 호출된다. 즉 User mode와 Kernel mode를 오가며 프로그램이 실행된다는 것이다.

운영체제의 핵심 기능들

• 프로세스 관리
• 실행 중인 프로그램을 프로세스라고 한다.
• 컴퓨터 시스템에서는 많은 수의 프로세스들이 실행되고 있으며, 새로 생성되는 프로세스가 있는가 하면 종료되는 프로세스도 있다. 종료된 프로세스는 운영체제에 의해 메모리에서 해제된다.
• CPU는 기본적으로 한 번에 하나의 프로세스만 실행할 수 있다. 사용자의 시각에서는 여러 개의 프로세스가 한 번에 실행되고 있는 것 같지만, 실제로는 끊임없이 빠르게 실행할 프로세스가 전환되고 있는 것이다.
• 각각의 프로세스는 그 성향이 다를 수 있다. 입출력 작업을 주로 하는 프로세스가 있고, CPU 작업을 주로 하는 프로세스가 있다. 혹은 즉각적으로 처리되어야 하는 프로세스가 있고, 반대로 당장은 실행할 수 없는 프로세스가 있다.
• 운영체제는 이렇게 각기 다른 프로세스들의 상태에 따라 능동적으로 대처할 수 있어야 한다. 프로세스들을 어떻게 관리하는지는 이후에 다룬다.

• 자원 접근 및 할당
• CPU : 운영체제는 CPU 스케줄러를 통해 가급적 모든 프로세스들이 공평하게 실행될 수 있도록 조율하는 역할을 한다.
• 메모리 : 운영체제는 프로세스마다 메모리를 어떻게 할당할지에 대한 방법을 결정한다. 또한 메모리에서 낭비되는 공간을 적절히 활용할 수 있다.
• 입출력장치 : 입출력장치에서 발생하는 인터럽트 신호를 받으면, CPU는 현재 하던 작업을 멈추고 인터럽트 신호에 대한 인터럽트 서비스 루틴을 실행한다. 운영체제는 이러한 CPU의 인터럽트 처리 과정을 도운다.

• 파일 시스템 관리
• 컴퓨터 시스템에는 여러 개의 파일이 있다. 파일들을 한데 묶어 디렉토리 구조로 관리할 수도 있다. 운영체제는 보조기억장치에서 이러한 구조로 파일들을 관리한다.

Chapter 10 프로세스와 스레드

프로세스 개요

프로세스의 종류

• 포그라운드 프로세스 (Foreground) : 사용자가 보는 앞에서 실행되는 프로세스

• 백그라운드 프로세스 (Background) : 사용자가 보지 못하는 곳에서 실행되는 프로세스
• 데몬 프로세스 (Daemon) : 백그라운드 프로세스 중에서도 사용자와 상호작용하지 않고, 정해진 일만 하는 프로세스

PCB (Process Control Block)

• 프로세스의 현재 상태와 관련된 정보가 저장되어 있는 메모리 공간으로, 커널 공간에 할당되어 있다.

• 프로세스 간 context switching을 위해 꼭 필요한 공간이다.

• 프로세스 생성 시 해당 프로세스에 대한 PCB도 생성되고, 프로세스가 종료되면 PCB도 제거된다.

• PCB에 저장되는 정보는 운영체제마다 조금씩 다르지만, 대표적으로 다음과 같다.
• PID (프로세스 ID)
• 레지스터 값
• 프로세스 상태
• CPU 스케줄링 정보
• 메모리 관리 정보
• 사용한 파일과 입출력장치 목록

Context Switching

• 프로세스에서 다른 프로세스로 실행 순서를 넘기기 위해 행해지는 일련의 작업

• Context
• 실행 중이거나 실행 중이었던 프로세스의 현재 상태로, 커널 영역의 PCB에 저장되어 있다.

• Context switching의 과정은 대략 다음과 같다.
1. 현재 실행중인 프로세스의 context를 PCB에 저장한다. (현재 실행중인 Context 백업)
2. 다음에 실행할 프로세스의 PCB를 CPU에 불러온다. (그 다음에 실행할 Context 복구)
3. 불러온 context 중 프로그램 카운터에 저장된 메모리 주소값으로 메모리에 접근하여, 다음에 실행할 프로세스의 명령어를 가져와 실행한다.

• 실제 운영체제는 이러한 Context switching을 굉장히 빠르게, 자주 하기 때문에 사용자의 눈으로는 프로그램 여러 개가 한 번에 실행되고 있는 것처럼 보인다. 그러나 너무 자주 하면 CPU가 불필요한 작업을 수행하게 되는 상황이므로 (오버헤드) 꼭 좋은 상황은 아니다.

프로세스의 메모리 구조

• .stack 이 가장 높은 주소이며 .code 가 가장 낮은 주소다.

• .stack 과 .heap 은 서로를 향해 메모리를 확장해 나간다.
• 서로의 영역을 둘 중 하나가 침범하면 메모리 여유 공간이 부족함을 의미한다.

 

• .stack : 스택 영역. 함수의 매개변수와 함수의 지역 변수가 저장되는 공간이다. 함수의 매개변수는 CPU 아키텍처에 따라 다르지만, Intel x86-64 기준으로 6번째 매개변수까지 메모리가 아닌 CPU 레지스터에 저장되며, 7번째부터는 스택 영역에 저장된다.

• .heap : 힙 영역. malloc() 과 같은 함수를 호출하여 동적 할당한 메모리가 할당되는 공간이다.
• 프로세스가 종료되어 메모리 공간이 통째로 해제되기 전까지 그대로 할당되어 있어, 특정 코드 블럭에서 동적 할당을 하여 힙 영역에 메모리가 할당되었다면 반드시 수동으로 해제해 주어야 한다. 만약 해제하지 않고 프로세스가 계속 실행된다면, 할당했던 자리는 그대로 그 자리에 자리잡아 있어 사용하지 않는 공간임에도 다른 데이터가 그 자리를 사용할 수 없게 된다. 이러한 오류를 메모리 누수 (Memory leak)라고 한다.

• 데이터 영역 (Data segment)
• .bss : Block Started by Symbol. 초기화되지 않은 전역 변수가 여기에 할당된다.
• .data : Data segment. 초기화된 전역 변수 및 정적 변수가 여기에 할당된다.
• .rodata : Read-only data. 말 그대로 한 번 초기화된 변수로, 프로세스가 종료되어 메모리가 해제될 때까지 변경될 수 없는 문자열과 상수가 여기에 할당된다.

• .code : 코드 영역 (Code segment). 프로그램의 명령어들이 여기에 저장된다.

프로세스 상태와 계층 구조

프로세스의 상태

• New : 프로세스가 메인 메모리에 적재되어 생성

• Ready : 생성된 프로세스가 Ready queue에 삽입되어, 스케줄러에 의해 스케줄되기를 대기한다. Running 상태인 스레드가 스스로 자원을 양보하거나, 타임 슬라이스가 만료되어 타이머 인터럽트가 발생할 경우 다시 Ready queue에 삽입되고, Ready 상태가 된다.

• Running : 스케줄러에 의해 스케줄되어 현재 실행 중

• Blocked : 실행 도중 잠자기 또는 I/O 작업으로 인해 CPU가 실행중이지 않은 상태로, Wait queue에서 대기한다. 대기 상태가 끝나 Wait queue에서 프로세스가 나오면 Ready queue에 삽입되어 Ready 상태가 되고, 스케줄러의 스케줄링을 기다린다.

• Terminated/Exit : 프로세스가 실행 종료되면 부모 프로세스가 해당 프로세스의 exit code를 읽는다. 부모 프로세스가 exit code를 읽고 나면 프로세스가 완전히 종료되며, 이후 운영체제가 종료된 프로세스의 메모리 영역을 반환하여 그 영역이 있던 공간을 다른 프로세스가 할당할 수 있는 공간으로 만든다.

프로세스의 계층 구조

• 일반적으로 트리 형태로 나타난다.

• 모든 자식 프로세스는 하나의 부모 프로세스를 가지며, 부모 프로세스가 종료되면 자식 프로세스는 모두 종료된다.
• 예외적으로, 부모 프로세스는 종료됐지만 자식 프로세스가 정상적으로 종료되지 않고 살아있는 경우가 존재하는데, 이를 고아 프로세스 (orphan process)라고 한다.
• 이 경우, init/systemd 프로세스에 입양하여 새 부모 프로세스로 지정한다.
• 운영체제에 따라서는, 종료될 부모 프로세스의 자식 프로세스를 모두 종료할 수 있다.

프로세스 생성하기

• 전체 과정
• 새로운 PID 번호 할당
• PCB 구조체 생성
• 프로세스 테이블에서 새 항목 할당
• 새로 할당된 프로세스 테이블 항목에 PCB 연결
• 새로운 프로세스를 위한 메모리 공간 할당
• 프로세스의 코드, 데이터, 힙, 스택 영역
• 할당받은 메모리 공간에 프로세스의 코드 및 데이터 적재
• PCB에 프로세스 정보 기록
• PCB에 프로세스 상태를 Ready 상태로 표시하고, Ready Queue에 넣어서 스케줄러에 의해 실행될 수 있도록 함

• 시스템 콜 함수를 통해 생성 및 제어
• fork() : 새 프로세스를 생성 → 이때 fork()를 호출한 프로세스가 새로 생성된 프로세스의 부모 프로세스가 됨
• fork()를 호출한 시점에서의 프로세스 내 모든 환경, 메모리, PCB가 자식 프로세스에 모두 복사된다.
• 부모 프로세스와 이름은 동일하나, PID 값을 새로 부여받고 (일반적으로 부모 프로세스의 PID + 1), 독립된 주소 공간을 가진다.
• 반환값
• 부모 프로세스에 자식 프로세스의 PID 반환 (pid > 0)
• 자식 프로세스에 0 반환 (pid == 0)
• 프로세스 생성 실패 시 음수 반환 (pid < 0)
• exec() : 기존에 실행 중인 프로세스의 메모리 영역을 fork() 함수로 새로 실행된 프로세스가 그대로 사용하게 됨
• wait() : 호출 시, 부모 프로세스는 자식 프로세스가 종료될 때까지 대기한다.
• exit(): 프로세스 종료 및 종료 코드 부모 프로세스에 전달 (SIGCHLD 시그널 형태)

스레드

스레드란?

• 스레드 (Thread) : 프로세스를 구성하는 작업 단위

• 모든 프로세스는 최소 하나 이상의 스레드를 가진다.

• 멀티스레딩 (Multi-threading) : 프로세스가 여러 스레드를 작동하고 있는 상태로, 이 경우 한 번에 여러 작업을 병렬적으로 처리할 수 있다.
• 멀티스레딩의 이점
• 응답성
• GUI 프로그램에서 어떤 작업 하나 돌리면 프로그램 전체가 응답 없음 상태로 빠지는 경우를 멀티스레딩이 막을 수 있음 → 사용자와의 상호작용 향상
• 자원 공유
• 스레드 간에 메모리 영역을 일부 공유하여 리소스 절약 가능
• 경제성
• 프로세스 위에서 작동하므로 기본적으로 요구하는 CPU 자원 및 메모리 자원이 멀티프로세싱보다 크게 적음
• 프로세스 간 context switching보다 스레드 간 context switching이 오버헤드가 훨씬 적게 걸리기 때문에 성능상으로도 효율적이다.
• 확장성
• 여러 개의 스레드는 여러 개의 CPU 코어가 개별적으로 돌아가며 처리하므로 CPU의 처리율이 향상된다.

스레드의 특징

• 프로세스 위에서 동작하므로, 해당 프로세스가 종료되면 프로세스 위에서 동작하는 스레드는 모두 종료된다.

• 프로세스 위의 모든 스레드가 종료되면 프로세스가 종료된다.
• 프로세스와 달리, 메인 스레드와 자식 스레드가 돌고 있을 때 메인 스레드가 종료되어도 프로세스는 종료되지 않는다.
• 자식 스레드가 하나라도 돌고 있다면 프로세스는 계속 돌아간다.

• 스레드는 실행 단위이자 CPU 스케줄링 단위다.

• 스레드가 수행할 작업을 함수 형태로 정의하고, 생성 시 해당 함수를 스레드가 실행한다.
• 함수마다 스택 프레임이 존재하므로, 스택 공간은 스레드 간에 공유하지 않는다.

• 스레드가 공유하는 / 공유하지 않는 메모리 영역
• .code, .data, .heap, .file → 공유
• .stack, CPU 레지스터 → 공유 X

Chapter 11 CPU 스케줄링

기본 개념

CPU Burst vs I/O Burst

• CPU Burst : CPU 연산이 연속적으로 실행 중인 상황

• I/O Burst : I/O 장치의 입출력이 이루어지는 상황

CPU 스케줄러, 스케줄링

• 스케줄링 : CPU 스케줄러는 Ready queue (list)에 있는 프로세스 (혹은 스레드)들 중에서 선택하고, 선택한 프로세스 (혹은 스레드)를 CPU 코어 중 하나에 할당하여 실행되게 한다.

• Ready queue의 형태는 꼭 FIFO 구조의 큐 구조가 아니다. → 트리, 우선순위 큐, 순서 없는 연결 리스트 형태도 있다.

• 다양한 스케줄링 알고리즘과 Ready queue가 존재한다.

디스패치 코드

• Context switching을 실행하는 코드로, 주로 현재 실행중인 프로세스 (혹은 스레드)가 스케줄러에 의해 종료 혹은 CPU 자원이 만료되어, 다음 순서로 스케줄된 프로세스 (혹은 스레드)가 Context switching에 의해 실행될 때 디스패치 코드가 실행된다.

스케줄링 코드

• 스케줄링 코드는 커널 코드의 일부로, 별도로 실행되는 프로세스나 스레드의 형태가 아니다.
→ 커널 영역에 적재되는 바이너리 코드 형태

• 스케줄링 코드는 시스템 콜이나 인터럽트 서비스 루틴이 끝나는 마지막 단계에서 실행된다.

비선점 스케줄링 vs 선점 스케줄링

• 비선점형 (Non-preemptive) : 현재 실행중인 스레드를 강제로 중단시키지 않음
• 스레드가 CPU 자원을 사용할 수 없는 경우
• I/O Blocking
• wait() 혹은 sleep() 시스템 콜
• 스레드가 스스로 CPU 자원을 양보할 때
• 스레드가 스스로 종료할 때

• 선점형 (Preemptive) : 현재 실행중인 스레드를 중단 (인터럽트) 후 다음 순서의 스레드를 실행
• 실행 중인 스레드에 할당된 CPU 자원이 만료될 때 → 타이머 인터럽트 발생
• Ready queue에 있는 다른 프로세스 혹은 스레드에 의해 인터럽트가 발생할 때
• 인터럽트 서비스 루틴 or 시스템 콜이 종료되는 시점에서, 우선순위가 더 높은 스레드가 준비 상태일 때

기아와 에이징

• 기아 (Starvation) : 스레드가 스케줄러에 의해 스케줄링받지 못해 실행되지 못하고 Ready queue에 오랫동안 머물러 있는 상태
• 보통은 실행 시간이 긴 CPU bound 스레드가 기아 상태에 빠질 가능성이 높다.
• 이를 해결하기 위해 에이징 (Aging) 기법을 사용한다.

• 에이징 (Aging) : Ready queue에 머무른 시간에 비례하여 스케줄링 우선순위를 높혀, 우선순위가 낮은 스레드라도 언젠가는 실행될 수 있게 함

CPU 스케줄링 알고리즘

First Come First Served (FCFS, 비선점)

• 일반적으로 알고 있는 큐 개념으로 스레드가 우선순위를 가짐

• 실행 순서는 큐에 입력된 순서이므로, 오래 기다리면 언젠가는 실행되어 기아는 발생하지 않음
• 예외 : 앞에서 실행 중인 스레드가 무한 루프에 빠질 때

• 특징
• 스케줄링 파라미터 : 스레드별 도착 시간
• 스케줄링 타입 : 비선점

• 단점
• Throughput (처리율)이 낮다.
• 입출력 여부, 실행 시간과 상관없이 Ready queue에 입력된 순으로 실행하므로
• Convoy effect (호위 효과)가 발생할 수 있다.
• 실행 시간이 긴 스레드가 CPU를 오래 사용하면, 늦게 도착한 실행 시간이 짧은 스레드는 오랜 시간동안 대기해야 한다.

Shortest Job First (SJF, 비선점)

• 스레드가 도착할 때, 예상 실행 시간을 계산하여 실행 시간이 짧은 스레드를 높은 우선순위로 스케줄링

• 짧은 스레드가 우선적으로 실행되어, 평균 대기 시간이 최소화된다. (SJF optimal)

• 특징
• 스케줄링 파라미터 : 스레드별 예상 실행 시간
• 스케줄링 타입 : 비선점

• 단점
• 실행 시간이 짧은 스레드가 계속해서 들어오면, 실행 시간이 긴 스레드의 우선순위는 계속해서 밀리게 되어 기아가 발생할 수 있다.

Shortest Remaining Time First (SRTF, 선점)

• Ready queue에 현재 실행중인 스레드의 남은 실행 시간보다 짧은 실행 시간의 스레드가 들어오면 현재 실행중인 스레드를 멈추고, 새로 들어온 스레드를 실행한다.

• 특징
• 스케줄링 파라미터 : 스레드별 예상 실행 시간 및 현재 실행중인 스레드의 남은 실행 시간
• 스케줄링 타입 : 선점

• 단점
• 실행 시간이 짧은 스레드가 계속해서 들어오면, 실행 시간이 긴 스레드의 우선순위는 계속해서 밀리게 되어 기아가 발생할 수 있다.

Round-robin (RR, 선점)

• Ready queue에 대기중인 스레드들을 타임 슬라이스 주기로 돌아가면서 스케줄링

• 도착하는 순서대로 Ready queue에 삽입

• 스레드가 타임 슬라이스를 소진하면 큐 끝으로 이동

• 특징
• 스케줄링 파라미터 : 타임 슬라이스
• 스케줄링 타입 : 선점
• 기아는 없으며 구현이 쉽다 - 스레드의 우선순위가 없으며, 타임 슬라이스에 따라 모든 스레드를 번갈아가며 스케줄링하기 때문

• 단점
• 잦은 스케줄링으로 인한 오버헤드가 큼
• 처리율 관련
• 타임 슬라이스가 크면 FCFS에 가깝고, 작으면 SRTF에 가깝다.
→ 늦게 도착한 짧은 스레드는 FCFS일 때보다 빨리 완료되고, 긴 스레드는 SRTF보다 빨리 완료된다.

Priority Scheduling (PS, 비선점/선점)

• 고정된 우선순위에 따라 스케줄링
• 스레드 도착 시 고정된 우선순위를 부여받고, 이는 스레드 종료까지 바뀌지 않음
• 도착한 스레드는 우선순위 순으로 큐에 삽입된다.

• 특징
• 스케줄링 파라미터 : 스레드별 고정 우선순위
• 스케줄링 타입 : 선점, 비선점 둘 다 가능
• 기아 발생 가능
• 높은 순위의 스레드가 계속 도착하는 경우, 낮은 순위의 스레드가 언제 실행될지 예상할 수 없음
→ 에이징 기법으로 극복
• 높은 우선순위의 스레드일수록 대기시간 및 응답시간 짧음
• 스레드별 고정 우선순위를 갖는 실시간 시스템에서 사용됨

• Round robin과 함께 적용되어, 우선순위가 같은 스레드끼리는 time slice가 부여되어 번갈아가며 실행된다.
• 특정 우선순위가 적용된 스레드가 하나라면, 비선점으로 처리된다.

• 문제점?
• n개의 스레드가 하나의 큐에 삽입되어 가장 우선순위가 높은 스레드를 선택하기 위한 연산 복잡도는
• 보다 낮은 복잡도로 처리할 수는 없을까? → 성능 향상
• 해결책 : 같은 우선순위별로 큐를 관리하자.

Multi-level Queue Scheduling (MLQ, 비선점/선점)

• 설명
• 스레드를 n개의 우선순위 레벨로 구분 후, 같은 우선순위의 스레드끼리 별도의 큐 구성
• 각 큐는 각자의 기법으로 스케줄링한다.
• 스레드는 도착 시 우선순위에 따라, 그에 맞는 큐에 삽입된다.
• 한 번 특정한 큐에 삽입되면, 다른 큐로 이동할 수 없다.
• 가장 높은 우선순위의 큐에 스레드가 없을 때, 그 다음 우선순위의 큐에서 스케줄링된다.

• 특징
• 스케줄링 파라미터 : 스레드의 고정 우선 순위
• 스케줄링 타입 : 선점, 비선점 둘 다 가능
• 선점 : 높은 레벨의 큐에 스레드가 도착하면 현재 실행중인 스레드를 중단하고 높은 레벨 큐에서 스케줄링
• 비선점 : 현재 실행중인 스레드가 종료한 후 스케줄링
• 기아 발생 가능
• 높은 순위의 스레드가 계속 도착하는 경우, 낮은 순위의 스레드가 언제 실행될지 예상할 수 없음
→ 에이징 기법으로 극복

• 스레드의 고정 순위를 가진 시스템에서 활용
• ex) 전체 스레드를 백그라운드 스레드와 포그라운드 스레드의 두 그룹으로 편성
• ex2) 시스템 스레드, 대화식 스레드, 배치 스레드 등 3개 레벨로 나누고, 시스템 스레드를 우선적으로 스케줄링
• 실시간 스레드, 시스템 스레드는 특히 Critical한 부분이므로 우선순위가 가장 높게 배치됨

Multi-level Feedback Queue Scheduling (MLFQ, 비선점/선점)

• 설명
• 기아를 없애기 위해 여러 레벨의 큐 사이에 스레드가 이동할 수 있도록 설계
• 짧은 스레드와 I/O가 많은 스레드 (I/O bound), 대화식 스레드의 우선 처리 (스레드 평균 대기시간 단축)

• 여러 레벨의 큐
• 여러 개의 고정 큐 → 큐마다 스케줄링 알고리즘이 다를 수 있다.
• 큐마다 스레드에 주어지는 타임슬라이스의 길이가 다를 수 있다.
• 높은 우선순위의 큐일수록 타임슬라이스가 짧고, 낮은 우선순위의 큐일수록 타임슬라이스가 길다.
• I/O 집중 스레드 (대화식 스레드)는 높은 순위의 큐에 있을 가능성이 높다.

• 스케줄링 알고리즘
• 스레드는 도착 시 최상위 레벨 큐에 삽입
• 가장 높은 레벨 큐에서 스레드를 선택하는데, 비어 있다면 낮은 레벨의 큐에서 스레드를 선택
• 스레드의 CPU burst time이 큐의 타임슬라이스보다 길다면 보다 낮은 레벨의 큐로 내려보냄
• 스레드가 자발적으로 실행을 중단하면, 현재 레벨 큐의 끝에 삽입
• 스레드가 I/O로 실행이 중단된 경우, I/O가 끝나면 현재 레벨 큐의 끝에 삽입
• 큐에 있는 시간이 오래되면 기아를 막기 위해 한 단계 위의 레벨 큐로 올려보냄
• 최하위 레벨 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄 ex) batch processing

• 특징
• 스케줄링 파라미터 : 각 큐의 타임슬라이스
• 스케줄링 타입 : 선점
• 스레드 우선 순위 : 없음 (계층화된 큐가 우선순위 대체)
• 기아 발생 없음 → by 에이징

• 성능
• 실행 시간이 짧거나, 입출력이 빈번하거나 (I/O bound), 대화형인 스레드는 높은 우선순위의 큐에서 스케줄링되어 빨리 실행된다 → 높은 CPU 활용률

스케줄링 순서 비교하기

문제풀이