[OSTEP] 가상화 CH06 - CH07

발표 날짜 2024.10.16 WED 10시a.m.

CH06 제한적 직접 실행 원리 Limited Direct Execution 

CPU를 가상화하기 위해서 운영체제는 여러 작업들이 동시에 실행되는 것처럼 보이도록 물리적인 CPU를 공유한다 

CPU 시간을 나누어 씀으로써 가상화를 구현할 수 있고, 가상화 기법을 구현하기 위해서는 몇 가지 문제를 해결해야 한다 

1) 성능 저하 - 시스템에 과중한 오버 헤드를 주지 않으면서 가상화를 구현할 수 있어야 한다 

2) 제어 문제 - 제어권을 상실하면 한 프로세스가 영원히 실행을 계속할 수 있는 등의 문제가 발생할 수 있다 

6.1 기본 원리 - 제한적 직접 실행 Limited Direct Exectuion 

"직접 실행" - 프로그램을 CPU 상에서 그냥 직접 실행시키는 것 

직접 실행의 문제점  1) 프로그램 입장에서 운영체제가 원치않는 일을 하지 않는다는 것을 보장할 수 없다

2) 프로세스 실행 시 운영체제가 어떻게 프로그램의 실행을 중단하고 다른 프로세스로 전환시킬 수 있는지 

+ 프로세스 전환을 어떻게 유용하게 할까? -> 운영체제가 해준다 

6.2 문제점 1 - 제한된 연산

직접 실행을 하게 되면 프로그램이 하드웨어 CPU에서 실행되기 때문에 빠르게 실행된다는 장점이 있다

그러나 프로세스가 특수한 종류의 연산을 수행하길 원할 때 운영체제가 즉시 반응할 수 없다 

CPU 직접 실행을 보완하기 위해서 아래와 같은 모드가 도입되었다 

사용자 모드 User Mode - 사용자 모드에서 실행되는 코드는 할 수 있는 일이 제한된다

커널 모드 Kernel Mode - 운영체제의 중요한 코드들이 실행된다 

 

사용자 프로세스가 특권 명령어를 실행하고자 할 때를 위해 하드웨어는 시스템 콜 System Call 을 제공하고

시스템 콜을 실행하기 위해 프로그램은 trap 특수 명령어를 실행해야 한다 

이 명령어는 커널 안으로 분기하는 동시에 특권 수준을 커널 모드로 상향 조정한다 

완료되면 특권 수준을 사용자 모드로 다시 하향 조정하면서 호출한 사용자 프로그램으로 리턴한다 

-> 사용자 모드와 커널 모드로 나눈 이유 - 보안을 강화하고 시스템을 보호하기 위해서 

+ 시스템 콜 - 프로세스가 하드웨어 접근 권한을 얻기 위해 사용하는 방법 

+ Trap - 사용자가 커널 모드로 전환하기 위해 사용하는 특별한 명령어

+ 커널 스택에 trap 명령어 실행 전 저장하여 커널 모드로 넘어 가고, 작업이 종료되면 저장한 상태를 복원한다 

+ 그림 6.2 참고하면 좋음 

+ 운영 체제는 부팅 시에 트랩 테이블과 트랩 핸들러를 세팅한다. (터졌을 때의 빠른 대처를 위해서 부팅 시 세팅)

트랩테이블이란?
시스템에서 해당 트랩을 처리하는 핸들러 함수의 주소 저장 데이터 구조 시스템 메모리의 특정 위치에 저장
Why
트랩 핸들러를 호출하기 편하게 하기 위함→ 빠르게 처리 가능
트랩핸들러란?
특정 트랩이 발생했을때 실행되는 함수

부팅 시 초기화 과정 - 1. 트랩 테이블 설정 : 트랩 테이블 초기화해서 각 트랩 번호와 트랩 핸들러 주소를 매핑. 이때 핸들러 함수는 커널 코드 내에서 정의되어야함.

트랩 발생 시 처리 로직

1. 사용자 프로그램에서 trap 명령어 실행 2. CPU 상태 저장 3. 트랩 번호 확인 4. 트랩 테이블에서 핸들러 주소 조회 5. 트랩 핸들러 호출 및 처리 - 예외 처리 또는 시스템 콜 처리 6. CPU 상태 복원 7. 사용자 모드로 복귀

운영체제로 가는 주소는 안 알려주는데 코드는 봐야한대 < P56 중간 참고 

6.3 문제점 2 - 프로세스 간 전환 

프로세스의 전환 - 실행 중인 프로세스를 멈추고 다른 프로세스를 실행하는 것

프로세스가 실행 중이라면 운영체제는 실행 중이지 않는다는 것이고

운영체제가 실행 중이 아니라면, 운영체제는 어떠한 조치도 취할 수 없다 

협조 방식 - 시스템 콜 호출 시까지 대기 

협조 Cooperative 방식은 각 사용자 프로세스가 비정상적인 행동은 하지 않을 것으로 가정한다 

CPU를 장기간 사용해야하는 프로세스들은 다른 프로세스들이 CPU를 사용할 수 있도록 주기적으로 CPU를 반납할 것이리라 믿는다 

CPU를 반납하기 위해서는 운영체제가 해당 프로세스의 실행상태 (각 레지스터값들) 를 저장해야 다시 실행을 계속할 수 있다 

협조방식을 사용하는 운영체제는 yield 시스템 콜을 제공한다, 이 시스템 콜은

운영체제에게 제어를 넘겨 운영체제가 CPU를 다른 프로세스에게 할당할 수 있는 기회를 제공한다 

비협조 방식 - 운영체제가 제어권 확보

협조 방식 운영체제의 경우 프로세스가 무한 루프에 빠졌을 때 재부팅 말고는 방법이 없다 

시스템 콜의 호출이 없더라도 운영체제에게 제어권을 넘길 수 있는 방법은 타이머 인터럽트 Timer Interrupt 이용이다 

인터럽트 발생 시 이를 처리는 것이 운영체제의 가장 중요한 역할 중에 하나이기 때문에 인터럽트가 발생하면

운영체제는 현재 수행 중인 프로세스를 중단시키고 해당 인터럽트에 대한 인터럽트 핸들러 Interrupt Handler 를 실행한다 

+ 타이머 인터럽트를 이용해서 프로세스가 주기적으로 강제 중단되게 하는 방식. OS가 비협조적인 프로세스에 대해 강제로 제어권을 획득할 수 있도록 함.

What : 운영체제에서 특정 주기마다 CPU 제어를 운영체제가 갖는 것
Use
- 프로세스 스케줄링 : 여러 프로세스가 동시에 실행되어 관리된다. 각 프로세스에게 CPU 사용 시간을 할당해서 공정하게 자원을 분배한다.
- 모니터링 : 시간 기반 작업에 이용

+ 협조적인 방식이 가능한 이유는 시스템 콜을 활용하기 때문, 비협조적인 방식은 부팅 시에 타이머 인터럽트를 이용하여 운영체제가 CPU의 제어권 획득한다 

문맥의 저장과 복원 

현재 실행 중인 프로세스를 계속 실행할 것인지 아니면 다른 프로세스로 전환할 것인지의 결정은

운영체제의 스케줄러 Scheduler 라는 부분에 의해 내려진다 

현재 프로세스를 중단시키고 다른 프로세스를 실행하기로 결정을 하면

운영체제는 문맥 교환 Context Switch 를 실행하여 현재 실행 중인 프로세스의 레지스터 값들을 커널 스택 같은 곳에 저장하고 

새로이 실행될 프로세스의 커널 스택으로부터 레지스터 값을 복원한다 

+ 운영체제가 CPU 제어권을 얻고 실행 중인 프로세스 상태를 저장하고 새로운 프로세스 상태를 복원하는 작업.

+ 커널스택이란?
- 운영체제가 커널 모드에서 사용하는 스택 메모리영역
- 프로세스마다 독립적으로 존재 (공유하지 않는다)

6.4 병행 실행으로 인한 문제

인터럽트나 트랩을 처리하는 도중에 다른 인터럽트가 발생할 때의 간단한 해법은

인터럽트를 처리하는 동안에는 인터럽트를 불능화시키는 것이다 

내부 자료 구조가 동시에 접근되는 것을 방지하기 위해 다양한 락 Lock 기법을 개발해 왔고

락의 사용으로 인해 운영체제 전체의 구성과 작동이 매우 복잡해 질 수 있다 (해법은 나중에)

-> 다중 프로세스 환경에서 동시 실행을 지원하기 때문에 충돌을 방지해야 한다 

+ 타이머 인터럽트는 주기적으로 실행된다, 운영체제가 시스템 콜로 CPU를 사용하고 있는데 인터럽트가 발생하면 문제가 생길 수 있으니 인터럽트 불능화를 시키거나 락으로 하드웨어 접근을 막는다 

6.5 요약

운영체제는 CPU 사용에 대한 적절한 안전 장치를 제공한다 

 

CH07 스케줄링 - 개요 

핵심 질문 - 스케줄링 정책은 어떻게 개발하는가
스케줄링 정책을 생각하기 위한 기본적인 프레임워크를 어떻게 만들어야 하는가?
어떤 것들을 가정해야 하는가? 어떤 기준으로 정책을 평가해야 하는가? 초기에는 어떤 기법들이 사용됐는가?

🐣 CPU Scheduling 은 한 프로세스가 CPU 를 사용하는 동안 다른 프로세스가 대기하는 상황에서

CPU 를 효율적으로 활용할 수 있도록 우선순위를 정하고, 프로세스들을 적절하게 배치하는 기술이다 

7.1 워크로드에 대한 가정 

워크로드 Workload - 프로세스가 동작하는 일련의 행위 

적절한 워크로드의 선정은 스케줄링 정책 개발에 매우 중요한 부분이다 

 

우리는 시스템에서 실행 중인 프로세스 혹은 작업 Job 에 대해 다음과 같은 가정을 한다 

1. 모든 작업은 같은 시간 동안 실행된다 

2. 모든 작업은 동시에 도착한다 

3. 작업은 일단 시작하면 최종적으로 종료될 때까지 실행된다 

4. 모든 작업은 CPU만 사용한다 (입출력을 사용하지 않는다)

5. 각 작업의 실행 시간은 사전에 알려져 있다 

7.2 스케줄링의 평가 항목

스케줄링 평가 항목 Scheduling Metric 

반환 시간 : 프로세스가 생성된 시점부터 종료될때까지의 전체 시간
응답 시간 : 사용자가 요청한 시점부터 첫 번째 응답이 도착할 때까지 시간

1) 반환 시간 Turnaround Time 

작업 반환 시간은 작업이 완료된 시각에서 작업이 도착한 시각을 뺀 시간이다 

반환 시간이 짧을수록 해당 프로세스는 빠르게 처리된 것이며, 시스템 성능이 높다고 볼 수 있다 

T turnaround = T completion - T arrival 

 

모든 작업이 동시에 도착한다고 가정했을 때 Taround = 0 이고, Tturnaround = Tarrival 이다 

2) 공정성 Fairness 

각 프로세스가 일정한 자원을 공평하게 할당받는지를 평가하는 항목 

시스템 성능을 균형 있게 유지하고, 모든 프로세스가 차별 없이 자원을 사용할 수 있도록 보장하는 중요한 원칙 

다중 사용자 시스템이나 실시간 시스템에서 중요한 개념 e.g. Jain's Fairness Index [Jai91] 라는 지표 

 

성능과 공정성은 스케줄링에서는 서로 상충된다 ex. 스케줄러는 시스템의 전체 성능을 최적화하기 위해 일부 작업에 대해 실행 기회를 주지 않을 수도 있다 -> CPU를 효율적으로 사용하려고 자주 실행이 끝나는 짧은 작업에 우선권을 주는 경우 공정성이 훼손된다 

7.3 선입선출 FIFO, Fast In Fast Out 

선도착선처리 FCFS, First Come First Served 라고도 불린다 

A, B, C 순서로 도착한 작업이 있을 때, A, B, C 모두 실행 시간이 10초라면 

시스템의 평균 반환 시간은 (10+20+30) / 3 = 20 이지만 

A 의 실행 시간이 100초라면 시스템의 평균 반환 시간이 (100+110+120) / 3 = 110초로 늘어난다

이런 현상을 Convoy Effect [Bla+79] 라고 부른다 

7.4 최단 작업 우선 SJF, Shortest Job First 

앞에서 A, B, C 작업을 B, C, A 순으로 진행한다면 평균 반환 시간이 (10+20+120) / 3 = 50초로 줄어든다 

모든 작업이 동시에 도착한다는 가정 하에 SJF 는 최적 Optimal 의 스케줄링 알고리즘이다 

하지만 가정 2 - 모든 작업은 동시에 도착한다 를 완화하여 A는 0초에 도착하고 B, C는 10초에 도착했을 때

평균 반환 시간은 (100+(110-10)+(120-10)) / 3 = 103.33초이다 

이렇게 현실적으로 생각했을 때 모든 작업은 동시에 도착하지 않으므로 다른 대안을 생각해야 한다 

7.5 최소 잔여 시간 우선 STCF, Shortest Time-to-Completion First 

가정 3 - 작업은 끝날 때까지 계속 실행된다 를 완화하여 작업은 실행 도중에 중단될 수 있다고 하면 

B나 C가 도착했을 때 스케줄러는 하던 일 (A 작업) 을 중지하고 다른 작업으로 스위치가 가능하다 

SJF 는 비선점형 스케줄러이기 때문에, SJF 에 선점 기능을 추가한 스케줄러를

최단 잔여 시간 우선 STCF 또는 선점형 최단 작업 우선 PSJF 라고 한다 

선점형 vs 비선점형 스케줄러
선점형 : 현재 프로세스를 중단하고 다른 프로세스 실행
비선점형 : 현재 프로세스를 중단하지 않고 다 끝난 후 다른 프로세스 실행
+ 선점을 할 수 있다는 건 특권/ 우선순위가 있다는 것 

 

STCF 는 현재 실행 중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행 시간을 비교하여 

잔여 실행 시간이 가장 작업을 스케줄한다 

이전의 예시 A는 0초에 도착하고 B, C는 10초에 도착했을 때 10초에 A의 실행을 중지하고 

B와 C를 끝날 때까지 실행시킨 이후 B와 C가 모두 끝난 후에 A를 다시 실행했을 때

시스템의 평균 반환 시간은 ((12-0)+(20-10)+(30-10)) / 3 = 50초가 된다 

 

작업들이 동시에 도착할 때에만 최적의 결과를 내는 SFJ보다

현실적인 시나리오에서는 작업들이 동시에 도착하지 않고, 작업 시간도 다양하게 분포되어 있기 때문에

STCF가 더 최적의 알고리즘이라고 볼 수 있다 

-> STCF 는 작업 도착 시간의 변동성에 유연하게 대처하고, 대기 시간 감소와 선점을 통해 다양한 작업을 효율적으로 처리 

7.6 새로운 평가 기준 - 응답 시간 

STCF 또한 작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며,

평가 기준이 반환 시간 하나인 경우에만 최적의 알고리즘으로 볼 수 있다 

그러나 시분할 컴퓨터의 등장으로 응답 시간 Response Time 이라는 새로운 평가 기준이 나타났다 

응답 시간은 작업이 도착하는 시점부터 처음으로 스케줄 될 때까지의 시간으로 정의된다 

T response = Tfirstrun - Tarrival 

 

이전의 예시 A는 0초에 도착하고 B, C는 10초에 도착했을 때 각 작업의 응답 시간은 A 0, B 0, C 10 으로 평균 3.33이 된다 

STCF 를 비롯한 비슷한 류의 정책들은 응답 시간이 짧다고 할 수 없기 때문에, 응답 시간을 최소화하는 스케줄러가 필요하다

7.7 라운드 로빈 RR, Round-Robin

응답 시간 문제를 해결하기 위해 라운드 로빈 스케줄링 [Kle64] 을 도입한다 

RR 은 작업이 끝날 때까지 기다리지 않고, 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다 

이 때 작업이 실행되는 일정 시간을 타임 슬라이스 Time Slice 또는 스케줄링 퀀텀 Scheduling Quantum 이라 부른다

타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다

타임 슬라이스의 길이는 RR에게 매우 중요하며, 타임 슬라이스가 짧을수록 응답 시간 기준으로 RR의 성능은 더 좋아진다 

그러나 타임 슬라이스를 너무 짧게 지정하면 문맥 교환 비용이 전체 성능에 큰 영향을 미치게 된다 

문맥 교환 비용을 상쇄할 수 있을만큼 길어야 하지만 그렇다고 응답 시간이 너무 길어지지 않도록, 최적의 상태로 동작할 수 있도록 타임 슬라이스의 길이를 지정해야 한다 

문맥 교환 비용에는 레지스터를 저장/ 복원하는 작업과 CPU 캐시, TLB, 분기 예측 등을 비롯하여 다른 하드웨어에도 프로그램과 관련된 다양한 작업 정보들이 저장되어 있다, 작업이 전환되면 이 정보들은 모두 갱신되어야 하는데, 갱신 작업은 매우 큰 성능 비용을 유발한다 

-> 1) 현재 작업의 모든 레지스터 상태를 저장해야 하고, 새로운 작업의 레지스터 상태를 복원하는 과정이 잦아지면 성능에 큰 영향을 미친다 2) 작업이 전환되면, 현재 캐시가 전환되는 작업의 데이터를 가지고 있지 않을 가능성이 크기 때문에 캐시를 새로 채워야 하는데 이 작업을 "Cache Miss" 라고 하며, 캐시 미스가 발생할 경우 CPU가 메모리에서 데이터를 다시 읽어야 하기 때문에 시간이 오래 걸린다 3)TLB Translation Lookaside Buffer, 가상 메모리 주소를 실제 물리 메모리 주소로 빠르게 변환하는 데 사용되는데 이 과정에서 TLB 미스가 발생하면 주소 변환에 추가적인 시간이 필요하다 4) 분기 예측 Branch Prediction, CPU는 분기 예측을 통해 명령어 실행 흐름을 미리 예측하여 성능을 최적화하는데 작업이 전환되면 이전 작업에서의 분기 예측 정보가 새로운 작업에 적용되지 않으므로, 예측 실패가 발생할 가능성이 커지고, 잘못된 예측은 파이프라인을 비우고 재실행하게 되어 성능 저하를 초래한다 

 

SJF, STCF 는 반환 시간 측면에서는 좋은 성질을 보이지만 응답 시간은 좋지 않다

RR 은 응답 시간 측면에서는 좋지만, 반환 시간 측면에서는 좋지 않다 

두 개 모두 가정 4(작업은 입출력을 하지 않는다) 와 가정 5(각 작업의 실행 시간은 알려져 있다) 처럼 비현실적인 가정을 하고 있다 

7.8 입출력 연산의 고려 

현재 실행 중인 프로세스가 입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행할지를 결정해야 하고, 현재 실행 중인 작업은 입출력이 완료될 때까지 CPU를 사용하지 않는다, 입출력 요청을 발생시킨 작업은 입출력 완료를 기다리며 대기 상태가 되고 입출력이 하드디스크 드라이브에 보내진 경우, 프로세스는 드라이브의 현재 입출력 워크로드에 따라 몇 초 또는 좀 더 긴 시간 동안 블록될 것이기 때문에 스케줄러는 그 시간 동안 실행될 다른 작업을 스케줄해야 한다 

그런 식으로 하나의 프로세스가 입출력 완료를 대기하는 동안, 다른 프로세스가 CPU를 사용하여 연산의 중첩이 가능하면 시스템 사용률을 향상시킬 수 있다 

+ 입출력이 끝나면 끝났다고 신호가 올 때 자동으로 실행 중인 프로그램이 종료되고, 자동으로 CPU가 운영체제로 넘어간대 

+ 인터럽트가 발생하면 CPU가 자동으로 운영체제로 넘어간다, 하드웨어를 건드리면 안 되니까 

7.9 만병통치약은 없다 No More Miracle

아무 사전 지식 없이 SJF/ STCF 처럼 행동하는 알고리즘을 구축할 수 있을까?
응답 시간 개선을 위해서 RR 스케줄러의 아이디어를 도입하는 방법은 없을까? 

7.10 요약

SJF, STCF 와 RR 의 적절한 절충이 필요하다 

프로세서의 미래 동작을 예측함에 있어 과거의 프로세스 동작 이력을 반영하는 방식을 멀티 레벨 피드백 큐 Multi Level Feedback Queue 라고 한다 (8장에서 배울 예정)