[5] 프로세스 관리

KOCW - 양희재 교수님 강의를 기반으로 운영체제 정리

프로세스

프로그램 vs. 프로세스

프로세스는 실행 중에 있는 프로그램을 의미합니다. 반면 프로그램은 하드디스크에 저장되어 있는 상태를 의미합니다. 프로그램이 실행 상태가 되면 메인 메모리에 적재되고 CPU는 프로세스를 처리하기 위해 여러 레지스터들도 작동하게 됩니다.

프로세스는 여러가지 상태를 가질 수 있습니다.

• new : 프로그램이 메인 메모리에 올라온 상태

• ready : 메인 메모리에 올라와 모든 초기화를 끝낸 상태

• running : 실제 CPU에 의해서 실행 상태

• waiting : I/O 작업으로 다른 프로세스가 실행되어 기다리는 상태

• terminated : 프로세스가 종료된 상태

Process Control Block (PCB)

PCB는 프로세스에 대한 모든 정보를 담고 있는 자료구조 입니다. PCB는 메모리의 운영체제 프로세스 관리 영역에 저장됩니다.

• Process state : running, ready, waiting ...

• Program counter : 다음에 실행해야할 메모리 주소

• registers : 다양한 레지스터들의 대한 정보

• MMU 정보 : base, limit 정보

• CPU Scheduling Infomation : CPU 점유 시간, 우선 순위, 최종 실행 시간

• Process ID : 프로세스 고유 ID

• Device I/O Status : 프로세스에 할당된 입출력 장치 목록, 열린 파일 목록 등

• Open File List : 프로세스를 위해 열려있는 파일 리스트

Queues

Job Queue

하드디스크에 저장된 프로그램이 메모리에 적재 되기 위한 대기 장소

• 대기 중인 프로그램 중 어떤 것을 메모리에 올려줄지 담당하는 프로그램 : Job scheduler

• Long-term scheduler : 메모리에 공간이 있어야하기 때문에 비교적 긴 간격으로 일어남

Ready Queue

CPU의 서비스를 받기 위한 PCB의 대기 장소

• 대기 중인 프로세스 중 어떤 프로세스를 우선적으로 처리할지 담당하는 프로그램 : CPU scheduler

• Short-term scheduler : 프로세스들 간의 스위칭이 매우 빠르게 일어나기 때문에 짧은 간격으로 일어남

Device Queue

입출력 장치를 사용하기 위한 대기 장소

• 대기 중인 프로세스 중 어떤 프로세스의 입출력 처리를 우선적으로 처리할지 담당하는 프로그램 : Device scheduler

Multi Programming

Multi Programming은 메모리에 여러 프로그램을 적재하는 것을 의미합니다.

• Degree of multi programming : 메모리에 몇 개의 프로세스가 올라와 있는지

• I/O bound process : 입출력 장치 사용이 주를 이루는 프로세스

• CPU bound process : 일기 예보와 같이 CPU 사용이 주를 이루는 프로세스

운영체제는 I/O bound process와 CPU bound process를 적절히 섞어 Job Queue에 올리는 기능도 가지고 있다.

• Medium-term scheduler : Swapping

  • Swap-out : 메모리에 올라와 있는 프로세스를 메모리에서 빼는 작업 (더 중요한 프로세스가 있거나 CPU를 사용하고 있지 않거나 등의 상황)

  • Swap-in : Swap-out된 프로세스를 다시 메모리로 올리는 작업

  • 메모리에서 뺀 프로세스는 보조기억장치(backing store, swap device)에 저장한다.

• Context switching

  • scheduler

  • dispatcher : 현재 프로세스의 정보를 PCB에 저장하고, 다음 프로세스의 PCB를 가져오는 작업을 하는 프로그램

  • context switching overhead : 스위칭이 일어날때 일어날 수 있는 부담

CPU Scheduling

선점 vs 비선점

• 선점(preemptive) 스케줄링 : 한 프로세스가 실행되고 있을 때, 다른 프로세스가 현재 프로세스를 중지시키고 CPU를 차지할 수 있는 스케줄링. 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 유용

• 비선점(non-preemptive) 스케줄링 : 한 프로세스가 실행되고 있으면, 프로세스가 끝나거나 I/O 작업을 만나기 전까지 CPU를 빼앗을 수 없는 스케줄링. 일괄 처리 시스템에 적합

스케줄링의 기준

• CPU Utilization (CPU 이용률, %)

• Throughput (처리율, jobs/sec)

• Turnaround time (반환시간, sec)

• Waiting time (대기시간)

• Response time (응답시간)

• 기타

CPU Scheduling Alogorithms

First-Come, First-Served (FCFS)

Ready queue에 도착한 순서대로 CPU를 할당하는 스케줄링으로 비선점 스케줄링입니다.
스케줄링의 척도를 AWT(Average waiting time)으로 계산할 경우 최악의 대기시간으로 CPU를 할당할 수 있습니다. 예를 들어, A 프로세스가 24초, B 프로세스가 3초, C 프로세스가 3초의 시간이 걸린다고 했을때 CPU를 A-B-C순으로 할당하면 AWT는 17초가 걸리게 됩니다. 하지만 C-B-A(B-C-A) 순서로 CPU를 할당할 경우 AWT는 3초 밖에 걸리지 않게 됩니다. 이처럼 실행 시간이 긴 프로세스가 Job queue의 앞에 위치한 경우 그 뒤의 프로세스는 아무것도 못하고 기다리는 현상을 Convoy Effect(호위효과)라고 합니다.

Shortest Job First (SJF)

AWT를 줄이기 위해 실행 시간이 짧은 프로세스에 먼저 CPU를 할당하는 방법입니다. 이 방법의 가장 큰 문제점은 현실적이지 않다는 점입니다. 정확한 프로세스 실행 시간이 얼마나 걸리는지 알 수 없기 때문에 예측을 해야하고 이 예측은 정확하지 않고 과거의 이력들을 가지고 있어야 하기 때문에 오버헤드가 일어날 수 있습니다.
SJF는 비선점/선점 두가지 방식으로 모두 구현이 가능합니다.

• 비선점 : 실행중인 프로세스가 끝나고 실행 시간이 가장 짧은 프로세스 실행

• 선점 : 실행중인 프로세스보다 짧은 수행시간이 있다면 현재 프로세스를 중지하고 우선순위 프로세스 실행 (Shortest-Remaining-Time-First)

Priority Scheduling

프로세스에 우선순위를 정적/동적으로 부여하여 우선순위가 높은 순서대로 처리하는 방법입니다.
우선순위는 내부적으로 실행 시간, 메모리 요구량, I/O 이용시간 ... 과 외부적으로 사용을 위한 금액, 정치적 요소 등을 고려할 수 있습니다.
해당 프로세스의 대표적인 문제점으로 starvation(기아)현상이 있습니다. 하나의 프로세스가 지속적으로 우선순위에 뒤쳐져 실행되지 않는 상태를 의미합니다. 이 문제를 해결하기 위해 ready queue에서 오래 기다릴수록 우선순위를 점진적으로 높이는 aging 방식을 사용합니다.
Priority Scheduling도 비선점/선점 두가지 방식으로 모두 구현이 가능합니다.

Round-Robin (RR)

Time-sharing system에서 많이 사용되는 스케줄링 방법입니다. 어떤 시간축이 있다면 시간을 양자화(Time Quantum, Time Slice, 10~100 msec)하여 프로세스의 같은 크기의 CPU 시간을 할당하는 스케줄링 방법으로 선점 스케줄링입니다. 이때 Time Quantum을 무한대로 설정할 경우 FCFS와 같은 스케줄링으로 작동하게 되고 반대로 0으로 설정할 경우 context switching이 매우 빈번하게 발생하게 되고 이는 오버헤드를 발생시키게 됩니다.

Multi-level Queue

프로세스들도 어떠한 기준에 따라 그룹을 이룰 수 있습니다.

• System processes : 운영체제가 담당하는 프로세스

• Interactive processes : 사용자와 대화하는 프로세스(게임)

• Interactive editing processes : 워드와 같은 상호작용을 통해 편집을 하는 프로세스

• Batch processes : 대화형이 아닌 일괄적으로 처리하는 프로세스

• Student processes

위와 같은 다양한 프로세스 그룹 중 우선순위를 매길 수 있습니다. 이처럼 특징이 다른 프로세스를 하나의 큐에 줄을 세우는 것이 비효율적이라는 생각을 할 수 있습니다. 따라서 Multi-level Queue는 Ready Queue를 하나만 두는 것이 아닌 여러개를 둬서 프로세스를 스케줄링하는 방법입니다. 이 방식은 여러개의 Queue에 절대적 우선순위를 적용하고 독립된 알고리즘을 적용할 수 있습니다.

Multi Feedback Queue

Multi-level Queue와 비슷하나 모든 프로세스는 하나의 Queue에 넣고 일정시간이 지나도 처리되지 않으면 다른 Queue로 이동시키는 스케줄링 방법입니다. 기아 상태를 고려하여 우선순위가 높은 Queue로 이동시키는 방법을 사용합니다.

프로세스의 생성과 종료

프로세스 생성

프로세스는 프로세스에 의해 만들어집니다. 컴퓨터가 부팅되어 운영체제가 메모리에 적재되면 운영체제는 초기의 프로세스를 만들어 냅니다. 운영체제 마다 다르지만 보통 init 프로세스라고 하고 이 프로세스에 의해서 자식 프로세스가 만들어집니다. 또한 이 자식 프로세스도 부모 프로세스가 되어 또 다른 자식 프로세스를 만들어내는 구조로 마치 트리 구조를 띄게 됩니다.

프로세스에도 식별하기 위해 Process Identifier(PID)가 부여됩니다. 해당 프로세스의 부모 프로세스의 식별자를 Parent PID(PPID)라고 말합니다. fork() system call에 의해 부모 프로세스를 복사하여 새로운 프로세스를 생성하게 됩니다. 또한 exec() system call에 의해 통해 실행 파일을 새로운 프로세스로 가져오게 됩니다.

프로세스 종료

exit() system call을 통해 현재 프로세스를 종료하고 SIGCHLD 시그널이 부모 프로세스에 전달되어 waiting 상태의 부모 프로세스는 자식 프로세스가 종료된 것을 알 수 있고 다시 ready queue에 들어가 실행될 준비를 하게 됩니다. 종료가 되면 자식 프로세스에 할당된 모든 자원이 운영체제에 의해 반환됩니다.