1. 제한적 직접 실행 원리(Limited Direct Execution)
CPU를 가상화하기 위해서 운영체제는 여러 작업들이 동시에 실행되는 것처럼 보이도록 물리적인 CPU를 공유한다. 프로세스 여러개를 잠깐씩 실행하는 CPU 시분할(time sharing)을 통해 가상화를 구현할 수 있다.
제한적 직접 실행기법의 "직접 실행"이라고 하는 부분은 간단하다. 그냥 프로그램을 CPU 상에서 직접 실행시키는 것이다. 이 간단한 방식에는 크게 두 가지 문제점이 있다.
(1) 프로그램을 직접 실행시키면 프로그램이 운영체제가 원하지 않는 일을 하지 않는 것을 보장할 수 없음
(2) 프로세스 실행 시 운영체제가 어떻게 프로그램의 실행을 중단하고 다른 프로세스로 전환시킬 수 있는지, 즉 시분할을 어떻게 구현할 수 있는가
1.1 첫 번째 문제점 해결방안: 제한된 연산
파일에 대한 접근을 허용하기전에 접근 권한을 검사하는 파일 시스템을 구현하는 것을 예로 들어보자. 프로세스가 디스크에 대해 입출력하는 것을 제한하지 않으면 검사하는 기능은 아무 의미가 없다. 이 때문에 사용자 모드(user mode)라고 알려진 새로운 모드가 도입되었다. 예를 들어, 프로세스가 사용자 모드에서 실행 중이면 입출력 요청을 할 수 없도록 설정한다. 이 때 입출력 요청을하면 프로세서가 예외를 발생시키고, 운영체제는 해당프로세스를 제거한다. 커널 모드(kernel mode)는 사용자 모드와 대비되는 모드로서 운영체제의 중요한 코드들이 실행된다. 디스크 입출력 요청이나 CPU 또는 메모리 같은 시스템 자원에 대한 추가할당 같은 특수한 명령어를 포함하여 모든 작업을 수행할 수 있다.
그렇다면 사용자 프로세스는 제한명령을 실행할 수 없나? 직접적으로는 불가능 하지만 시스템 콜을 통해 운영체제에 작업을 요청할 수 있다. 시스템 콜을 실행하기 위해 프로그램은 trap 특수 명령어를 실행해야 한다. 이 명령어는 커널 안으로 분기하는 동시에 특권 수준을 커널모드로 상향 조정 한다. 운영체제가 해당 명령어 수행을 마치면 return-from-trap 특수 명령어를 호출하여 특권수준을 사용자모드로 다시 하향 조정한다.
주의해야할 점은 운영체제가 트랩을 처리하기전에 현재 프로세스의 상태인 레지스터들을 저장해야 한다. 이 역할은 하드웨어가 한다. x86에서는 프로그램 카운터, 플래그와 다른 몇 개의 레지스터를 각 프로세스의 커널 스택(kernel stack)에 저장한다. return-from-trap 명령어가 이 값들을 스택에서 팝(pop)하여 사용자 모드 프로그램의 실행을 다시 시작한다.
trap이 운영체제 코드의 어디를 실행할지 어떻게 알 수 있을까? 커널은 부팅시에 트랩 테이블(trap table)을 만들고 이를 이용하여 시스템을 통제한다. 컴퓨터가 부트될 때는 커널 모드에서 동작하기 때문에 하드웨어를 원하는 대로 제어할 수 있다. 운영체제가 하는 초기 작업 중 하나는 하드웨어에게 예외 사건이 일어났을 때 어떤 코드를 실행해야 하는지 알려주는 것이다. 프로그램이 시스템 콜을 호출하면 무슨 코드를 실행해야 할까? 운영체제는 특정 명령어를 사용해 하드웨어에게 트랩 핸들러(trap handler)의 위치를 알려준다. 하드웨어는 이 정보를 전달 받으면 해당 위치를 기억하고 있다가 어느 코드로 분기할지 결정할 수 있다. 트랩 핸들러는 운영체제의 일부분이다. 운영체제는 시스템 콜 번호를 읽어 사용자가 명시한 시스템 콜 번호가 유효한 시스템 콜에 해당하는지를 먼저 파악한다.
각 시스템 콜의 코드위치는 운영체제만 알고 있다. 사용자 프로그램은 시스템 콜 코드의 정확한 위치를 모른다. 만약 알고 있다면 사용자 프로그램이 그 위치로 점프하여 커널 코드를 실행하는 경우도 있을 것이다. 일종의 보안기법이다.
1.2 두 번째 문제점 해결방안: 프로세스 간 전환
프로세스간 전환은 협조 방식, 비협조 방식이 있다. 협조 방식은 운영체제가 시스템콜 호출시 까지 대기하는 방식이다. 대부분의 프로세스는 시스템콜을 자주 호출하는 것으로 알려져 있다. 시스템 콜을 호출하면 자연스럽게 운영체제의 코드가 실행되며, 제어권이 운영체제로 넘어가게 되어있다. 협조방식을 사용하는 운영체제는 yield 시스템콜을 제공한다. 응용 프로그램이 비정상적인 행위를 하면 운영체제에게 제어가 넘어간다. 만약 프로그램이 허가되지 않은 메모리에 접근한다면 운영체제로 트랩이 일어난다. 트랩을 통해 CPU를 얻은 운영체제가 해당 프로세스를 종료할 수 있다. 협조 방식의 스케줄링 시스템은 근본적으로 수동적이다. 만약 프로세스가 무한루프에 빠져 시스템콜을 호출할 수 없다면? 문제다.
비협조 방식은 타이머 인터럽트(timer interrupt)를 이용하여 운영체제가 시스템콜 없이 제어권을 가질 수 있다. 하드웨어의 도움을 받는 것이다. 인터럽트가 발생하면 운영체제는 현재 수행 중인 프로세스를 중단시키고 해당 인터럽트에 대한 인터럽트 핸들러를 실행한다. 인터럽트 핸들러는 운영체제의 일부분이다.
협조 방식이든 비협조 방식이든 운영체제가 제어권을 다시 획득하면 현재 실행중인 프로세스를 계속 실행할 것인지 다른 프로세스로 전환할 것인지 결정해야 한다. 이 결정은 운영체제의 스케줄러(scheduler)가 담당한다. 현재 프로세스를 중단하고 다른 프로세스를 실행하기로 결정하면 운영체제는 문맥 교환(context switch)라 불리는 코드를 실행한다. 문맥 교환은 현재 실행 중인 프로세스의 레지스터 값들을 커널 스택 같은 곳에 저장하고 새로이 실행 될 프로세스의 레지스터 값을 커널 스택으로 복원하는 것이다. 이는 주로 실행속도를 높이기 위해 어셈블리 코드를 사용해 구현한다. 운영체제는 현재 실행 중인 프로세스의 범용 래지스터, PC뿐 아니라 현재 커널 스택 포인터를 저장한다.
문맥교환의 과정이 아래 그림에 나와있는데 주의해야 할 점은 커널스택에 현재 프로세스의 레지스터가 저장되는 것이고 커널 영역에서 실행되는 문맥인 레지스터는 프로세스 구조체(PCB)에 저장된다. 즉, 시스템콜 혹은 타이머인터럽트가 발생하면 커널스택에 현재 프로세스의 레지스터를 저장하는 것이고 운영체제에서 문맥교환이 발생하면 프로세스 구조체에 레지스터를 저장하는 것이다. (핀토스에서 fork 시스템콜 호출할 때 자식프로세스 레지스터를 현재 프로세스 구조체에서 읽어들이다가 삽질을 많이 했었다)
만약 시스템 콜을 처리하는 도중에 타이머 인터럽트가 발생하면 어떻게 해야할까? 또는 하나의 인터럽트를 처리하고 있을 때 다른 인터럽트가 발생하면? 이 부분은 병행성 부분에서 다루게 될 건데. 락(lock)을 이용해 커널 내부의 각종 자료구조들을 보호하여 다수 작업들이 동시에 진행되는 것이 가능하다.
이번 파트에서는 CPU 가상화를 실행하는 기법들을 다루어보았다. 이런 기법들을 제한적 직접 실행이라고 통칭한다. 아이디어를 요약하면 원하는 프로그램을 실행하고 하드웨어를 적절히 설정하여, 프로세스가 할 수 있는 작업을 제한하고, 중요한 작업을 실행할 때에는 운영체제를 거치도록 한다.
2. 스케줄링
1.1 스케줄링 평가항목
1. 반환시간 = Tturnaround = Tcompletion − Tarrival
2. 공정성
3. 응답시간 = Tresponse = Tf irstrun − Tarrival
응답시간은 나중에 나온 평가기준이다. 바로 시분할 컴퓨터가 등장하면서 시스템과 상호작용이 원활한 성능을 요구하게 된 것이다. 예를 들면 SJF 스케줄링의 응답시간 문제를 해결하기 위해 라운드 로빈 스케줄링 방식이 나온 것이다.
1.2 선입선출(FIFO)
FIFO의 장점은 단순하고 구현이 쉽다는 점이다. 다만 문제가 있다. 아래와 같은 상황이라면 작업 B,C는 CPU를 잠깐 사용하는 반면 긴 시간을 사용하는 A를 기다려야만 한다.(= convoy effect) 평균 반환 시간으로 정량적으로 안좋아진 정도를 확인할 수 있다.
1.3 최단 작업 우선(SJF)
SJF(Shortest Job First)는 convoy 문제를 해결할 수 있다. 세 작업이 동시에 도착한다면 작업이 짧은 B와 C에 먼저 CPU를 할당할 것이다. 하지만 A가 조금이라도 일찍도착한다면? 똑같은 문제가 발생한다.
1.4 최소 잔여시간 우선(STCF)
SJF의 문제를 해결하기 위해선 작업을 실행도중에 중단할 수 있도록 해야한다. 즉 짧은 작업의 B와 C가 A가 실행중일 때 들어온다면 인터럽트가 발생하여 A를 중지(선점)시키고 짧은 B와 C를 실행시킨뒤 남은 부분을 끝나고 실행시키는 것이다. 이렇게 하는게 STCF(Shortest time-to-Completion First)이다. 다른 말로 선점형 최단 작업 우선(PSJF)라고도 한다. 위의 두 스케줄러와의 차이는 선점형이냐 비선점형이냐 이다.
1.5 라운드 로빈(RR)
응답시간 문제해결을 위해 라운드로빈 스케줄링 알고리즘이 도입되었다. 라운드 로빈은 작업이 끝날때 까지 기다리지 않고 타임 슬라이스(time slice) 혹은 스케줄링 퀀텀이라 불리는 일정 시간동안 실행하게 한다. 타임 슬라이스의 길이를 제대로 결정하는 것은 중요하다. 타임 슬라이스가 짧을 수록 응답 시간 성능은 올라가지만 컨텍스트 스위치 비용이 올라가는 trade-off가 발생한다.
1.6 입출력 연산의 고려
아래 STCF를 확인해보면 프로세스 A가 입출력 작업요청에 대기하는 동안 B가 실행된다. 이것이 가능한 이유는 프로세스 A 전체가 아닌 각 10msec 작업을 독립적인 작업으로 간주하기 때문에 B가 실행되고있는동안 A의 입출력 작업요청이 끝나면 바로 A가 다시 선점할 수 있는 것이다. 이런식으로 CPU 버스트를 하나의 작업으로 간주함으로써 대화형 프로세스가 더 자주 실행되는 것을 보장할 수 있다.
3. 또 다른 스케줄링 방식들
1.1 멀티레벨 피드백 큐(MLFQ)
MLFQ(Multi-level Feedback Queue)가 해결하려고 하는 기본적인 문제는 두 가지이다 첫 번째는 짧은 작업을 먼저 실행시켜 반환시간을 최적화 하는 것이 필요하다. SJF나 STCF 같은 알고리즘은 작업의 실행 시간 정보를 필요로 하지만, 운영체제는 이 실행 시간을 미리 알 수 없다. 두 번째는 대화형 사용자에게 응답이 빠른 시스템을 제공하기 위해 응답 시간을 최적화 하는 것이 필요하다. RR의 경우 이 응답시간이 짧지만 반환시간이 좋지 않다. 문제를 종합하면 운영체제는 실행 시간을 미리 알수 없는데 반환 시간을 어떻게 최적화 할 수 있으며 동시에 응답시간 또한 어떻게 최적화 할 수 있을까?
MLFQ는 아래 그림과 같이 여러 개의 큐로 구성되며, 각각 다른 우선순위가 배정된다. 같은 우선 순위 안에 여러개의 프로세스 큐가 들어갈 수 있으며 같은 우선순위를 가진 각각의 프로세스는 라운드로빈 스케줄링이 사용된다. 프로세스는 라운드로빈 만큼의 시간을 작업하고 우선순위가 바뀔 수 있다. 규칙을 참고하자.
규칙 1. Priority(A) > Priority(B) 이면, A가 실행된다. (B는 실행되지 않는다. 이규칙에 대한 예로 아래 그림을 보면 우선순위가 높은 A와 B만 실행되고 C, D는 실행되지 않을 것이다)
규칙 2. Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.
규칙 3. 프로세스가 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다.
규칙 4a. 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
규칙 4b. 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
규칙 4는 CPU burst time이 짧고 IO burst가 긴 것을 만족하는, 즉 IO burst가 높은 대화형 사용자에게 응답이 빠른 프로세스에게 높은 우선순위를 제공할 수 있게 한다. 참고로 CPU burst time이 높은 프로세스를 CPU bound process라고 하는데, 공학용 계산기 같은 프로그램을 예로 들면 어떨까 싶다. 순수 계산하는데에 CPU를 많이 사용하기 때문에 계산 프로그램은 CPU bound process일 것이다. 반면 파일을 다운로드 하는 작업이나 외부와의 상호작용이 많은 웹애플리케이션, 채팅프로그램 이런 것들을 IO bound process의 예로 볼 수 있을 것 같다.
예를 들어 보자. 아래와 같이 검은색으로 표현된 프로세스A가 들어온다. 프로세스 A는 CPU bound process이다. 무조건 처음에는 높은 우선순위로 들어오는데 주어진 실행시간을 CPU burst로 사용하면 우선순위가 Q1, Q0로 내려간다.
그리고 회색으로 표현된 프로세스 B가 중간에 들어온다. 프로세스 B또한 CPU bound process지만 프로세스 A가 처음에 그랬듯 처음에는 높은 우선순위로 배정받고 밑으로 한 번 강등당한다. 그러고 주어진 작업시간을 다 사용하고 프로세스가 종료된다. 이 예시를 통해 MLFQ가 짧은 반환시간을 만들어 낼 수 있음을 볼 수 있다. 핵심 아이디어는 스케줄러는 짧은 작업인지 긴 작업인지 알 수 없기 때문에 일단 처음에 높은 우선순위를 줘서 짧은 작업은 알아서 밑으로 많이 강등되기 전에 종료되도록 하는 것이다. 이러한 방식으로 SJF를 근사할 수 있다.
마지막 케이스로 검정색으로 표현된 CPU bound process가 먼저 큐에 들어오고 중간에 회색으로 표현된 IO bound process가 들어온다고 가정하자. 그러면 아래 그림과 같이 실행될 것이다. 회색으로 표현된 IO bound process는 가장 높은 우선순위에 계속 남아있는 것을 볼 수 있다. 자주 입출력을 수행하는 대화형 작업에게 응답시간을 최적화 할 수 있다.
MLFQ에도 문제점이 있다. 첫째로 기아상태(starvation)이 발생할 수 있다. 너무 많은 대화형 작업이 존재한다면 낮은 우선순위의 작업은 CPU를 할당받지 못할 것이다(굶어 죽는다). 두 번째로 특성을 악용할 수 있다. 자신이 원하는 프로세스를 일부로 조금만 IO burst가 섞이게 만들면 계속해서 높은 우선순위에서 CPU를 독점하는 프로그램을 만들 수 있다. 세 번째로 프로그램은 시간에따라 특성이 바뀔 수 있다. CPU위주 작업이 대화형 작업으로 바뀔 수도 있는 것이다.
첫 번째 문제 기아상태를 해결하기 위해 우선순위 상향 조정(boost)을 도입한다. 주기적으로 모든 작업의 우선순위를 상향조정하는 것이다.
규칙 5. 일정 시간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.
새 규칙은 첫 번째와 세 번째 문제를 해결한다. 물론 적절한 상수 S값 결정이 필요할것이다. (a.k.a 부두상수) S가 너무 크면 긴 실행 시간을 가진 작업은 굶을 수 있으며 너무 작으면 대화형 작업이 적절한 양의 CPU 시간을 사용할 수 없다. 두 번째 문제는 어떻게 해결할까? CPU 총 사용시간을 도입하는 것이다. CPU를 양도하는게 중요한게 아니라 주어진 사용시간을 소진하느냐 하는게 중요하다.
규칙 4(new): 주어진 단계에서 시간 할당량을 소진하면 (CPU를 몇 번 양도하였는지 상관 없이), 우선순위는 낮아진다 (즉, 아래 단계의 큐로 이동한다).
아래 예시를 통해 확인해보자. 새 규칙을 적용하기 전에는 대화형 작업인 회색 프로세스가 CPU를 거의 독점한다. 하지만 새로운 규칙 하에서는 회색 프로세스는 주어진 시간을 소진하는 순간 강등되며 나중에는 CPU 독점이 불가능해지는 것을 확인할 수 있다.
또 다른 쟁점들은 적절할 변수의 값을 결정하는 문제다. 큐는 몇개를 설정해야하는가? 타임슬라이스 크기는? 우선순위 상향 빈도는? 이런것들은 쉽게 대답하기 힘든 질문이며 워크로드에 대해 충분히 경험하고 계속 조정해 나가면서 균형점을 찾아야 한다. 예를 들어, 대부분의 MLFQ 기법들은 큐 별로 타임 슬라이스를 변경할 수 있다. 아래 그림처럼 우선순위가 높은 큐는 보통 짧은 타임 슬라이스가 주어진다.
핀토스 MLFQ의 우선순위 공식을 보면 nice, load avarege, recent cpu time 값을 사용한다. 이 부분을 제대로 이해못하고 넘어갔는데 정리해보자.
1.2. 추첨 스케줄링(lottery scheduling)
비례 배분(Proportional Share) 혹은 공정 배분(fair share)이라 불리는 스케줄러이다.
1.3. 리눅스 CFS(Completely Fair Scheduler)
오 레드블랙 트리를 쓴다.
내용 요약
1. 컨텍스트 스위치란 무엇인가요?
꼬리질문
컨텍스트가 저장되는 곳이 두 군데(PCB, 커널 스택)인데 무슨차이가 있나요?
(링크)https://stackoverflow.com/questions/67955845/during-a-context-switch-does-the-os-use-pcb-or-kernel-stack-to-restore-register
PCB는 어디있나요?
프로세스의 상태는 뭐가있나요?
멀티프로세스란?
동시성과 병렬성의 차이는?
PCB에는 어떤것들이 저장되나요?
2. 프로세스 스케줄링 방식에 대해서 종류와 함께 설명해 주세요
