이 포스트는 이준희님의 운영체제 강의 내용을 정리한 학습 노트입니다.

---

기초 용어

Queue: FIFO(First-In First-Out), 선입선출 구조로 맛집 줄서기를 생각하면 이해가 쉬운 구조입니다.

• Batch Processing System: 여러 프로그램이 순차적으로 실행되는 시스템입니다. 동시에 여러 프로그램을 실행시킬 수 없기 때문에 다른 프로그램의 대기 시간이 존재하는 것이 큰 단점입니다.
• Multi Tasking: 단일 CPU에서, 여러 응용 프로그램이 동시에 실행되는 것처럼 보이도록 하는 방법입니다.
• Multi Processing: 여러 CPU로 하나의 프로그램을 병렬로 처리해서 실행속도를 빠르게 하는 방법입니다.
• Multi Programming: CPU의 유후 상태를 최소화하여 활용도를 높이는 방법입니다.
  
  데이터를 읽거나 쓰는 것은 많은 시간을 필요로 합니다. 멀티프로그래밍이란 이 시간에 다른 프로그램의 연산을 수행하는 것입니다.
• Process: 메모리에 올려져서 실행 중인 프로그램을 프로세스라고 합니다. (bynary, exe, ELF) 응용 프로그램은 하나 이상의 프로세스 간 통신하며(IPC) 동작합니다.

• Real Time OS(RTOS): 응용 프로그램의 실시간 성능 보장을 목표로 하는 OS입니다. 정확한 프로그램의 시작과 완료 시간을 보장합니다.
• General Purpose OS(GPOS): 프로세스 실행시간에 미감하지 않고 일반적인 목적으로 사용되는 OS입니다.

---

Scheduling Algorithm

스케줄링 알고리즘이란 어떤 순서대로 프로세스를 실행시키는지를 정의한 것입니다.
프로세스가 저장매체를 읽거나 I/O를 사용하는 작업 없이 CPU를 완전히 사용한다고 가정합니다.
다음과 같이 프로세스 처리 요청이 들어왔다고 가정해봅니다.

3	2	2	2	1	1

FIFO(FCFS) Scheduling

가장 간단한 스케줄러 입니다.(Batch Processing System)
FCFS(First Come First Served) 스케쥴러라고도 합니다.

1	1	2	2	2	3

SJF Scheduling

SJF(Shortest Job First)는 프로세스 실행시간이 짧은 순서로 실행시키는 스케쥴링 방법입니다.

3	1	1	2	2	2

Priority-Based Scheduling

우선순위 기반 스케줄링이라고 합니다.

• 정적 우선순위: 프로세스마다 우선순위를 미리 지정하고 우선순위에 따라 처리합니다.

다음과 같은 프로세스(우선순위) 요청이 들어왔다고 한다면

3(10)	2(20)	2(20)	2(20)	1(1)

각 스케줄러에 따라 다음과 같이 처리됩니다.

입력	3(10)	2(20)	2(20)	2(20)	1(1)
FIFO	1(1)	2(20)	2(20)	2(20)	3(10)
SJF	1(1)	3(10)	2(20)	2(20)	2(20)
우선순위	2(20)	2(20)	2(20)	3(10)	1(1)

Round Robin(RR) Scheduling

시분할 시스템을 위해 설계된 스케줄링법입니다. 선점형 FCFS라고도 합니다.
규정 시간량(Time quantum) 또는 시간 할당량(Time slice)이라는 것은 각 프로세스에 한 번에 할당되는 CPU 시간입니다.
프로세스가 끝나지 않아도 다른 프로세스로 작업을 전환하여 번갈아가며 수행합니다.
일반적으로 평균 대기 시간이 긴 단점이 있고 Time quantum이 Context Switching time보다 길어야합니다.

Process State

• 기본
  
• 상세
  

State

• new state: 프로세스가 막 생성된 상태
• ready state: 프로세스가 CPU에 실행되기 위해 대기하는 상태
• running state: 프로세스에 포함된 명령어가 실행되고 있는 상태
• waiting state: 프로세스가 특정 자원이나 이벤트를 기다리는 상태(파일 읽기 완료, 출력 완료)
• suspended waiting: 프로세스가 대기 상태에서 기억 장치를 잃은 상태
• suspended ready: 프로세스가 기억장치를 제외한 다른 모든 필요한 자원들을 보유한 상태
• terminated state: 프로세스가 실행을 완료한 상태

---

State Transition

• ready->run(dispatch): 우선순위가 높은 프로세스 선정하여 명령어 실행
• run->ready(timer runout): 클럭이 인터럽트를 발생시켜 제어권을 빼앗음(Preemption, 독점 방지)
• run->waiting(block): 프로세서가 입출력, 자원 등을 기다리기 위해 대기로 전환
• waiting->ready(wake up): 입출력이 완료되거나 자원이 할당되어 다시 실행
• swap-out(suspend): 준비(대기) 상태에서 기억 장치를 반납하고 지연 준비(지연 대기) 상태로 전이
• swap-in(resume): 지연 준비(지연 대기) 상태에서 기억 장치를 할당받아 준비(대기) 상태로 전이

---

선점형과 비선점형

• 선점형 스케줄러(Preemptive Scheduling): 하나의 프로세스가 running 중인 다른 프로세스 대신에 프로세서를 차지할 수 있습니다.
• 비선점형 스케줄러(Non=preemptive Scheduling): 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없습니다.

인터럽트(Interrupt)

인터럽트란 CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 또는 예외상황이 발생하여 처리가 필요할 경우에 CPU에 알려서 처리하는 기술입니다.

인터럽트는 이벤트의 일종입니다.

인터럽트 처리 예

• 저장매체에서 데이터 처리 완료시 block state에 있던 프로세스를 ready 상태로 바꿔줘야 합니다. 이런 경우 인터럽트를 발생시켜 알려주게 됩니다.
• 0으로 나누는 것과 같은 예외가 발생할 때 운영체제에 알려줍니다. 그러면 운영체제가 해당 프로세스 실행을 중지하고 에러 표시를 합니다.

내부 인터럽트

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

외부 인터럽트

• HW Interrupt, 주로 하드웨어에서 발생되는 이벤트
  • 전원 이상
  • 기계 이상
  • 키보드 IO관련 이벤트
  • 타이머 이벤트

시스템콜 인터럽트

• 시스템콜 실행을 위해서는 강제로 코드에 인터럽트 명령을 넣어 CPU에게 실행킵니다.

예시)

mov eax, 1
mov ebx, 0
int 0x80

1. eax레지스터에 시스템 콜 번호를 넣고,
2. ebx 레지스터에는 시스템 콜에 해당하는 인자값을 넣고,
3. 소프트웨어 인터럽트 명령을 호출하면서 0x80값을 넘겨줌
   - CPU는 사용자 모드를 커널 모드로 바꿔줍니다.
   - IDT(Interrupt Descriptor Table)에서 0x80에 해당하는 주소를 찾아서 실행합니다.
   - system_call() 함수에서 eax로부터 시스템 콜 번호를 찾아서, 해당 번호에 맞는 시스템콜 함수로 이동합니다.
   - 해당 시스템콜 함수 실행 후, 다시 커널 모드에서 사용자 모드로 변경하고 다시 해당 프로세스 다음 코드를 진행합니다.

   IDT(Interrupt Descriptor Table)에 인터럽트 번호와 실행코드를 가리키는 주소가 미리 정의되어 있습니다. IDT는 컴퓨터 부팅 시 운영체제가 기록하여 놓습니다.

   리눅스의 경우

   • 0~31: 예외 상황
   • 32~47: 하드웨어 인터럽트(주변장치 종류/개수)
   • 128(0x80): 시스템 콜

%eax	kernel function(system call)	%ebx
1	sys_exit	int
2	sys_fork	struct pt_regs
3	sys_read	unsigned int
4	sys_write	unsigned int
5	sys_open	const char*