제한적 직접 실행 원리

CPU를 가상화하기 위해서 운영체제는 여러 작업들이 동시에 실행되는 것처럼 보이도록
물리적인 CPU를 공유한다. 기본적인 아이디어는 간단하다. 한 프로세스를 잠시 동안
실행하고 다른 프로세스를 또 잠깐 실행하고, 이런 식으로 계속해서 잠깐씩 실행시키면
된다. 이러한 방식처럼 CPU 시간을 나누어 씀으로써 가상화를 구현할 수 있다.

• Issue
  1. 성능 저하 (Performance)
  시스템에 과중한 오버헤드를 주지 않으면서 가상화를 구현할 수 있을까?

2. 제어 문제(Control)
   CPU에 대한 통제를 유지하면서 프로세스를 효율적으로 실행시킬 수 있는 방법은 무엇인가?

운영체제의입장에서는 자원 관리의 책임자로서 특히 제어 문제가 중요하다.
제어권을 상실하면 한 프로세스가 영원히 실행을 계속할 수 있고 컴퓨터를 장악하거나 접근해서는 안 되는 정보에 접근하게 된다.
제어권을 유지하면서 성능 저하가 없도록 하는 것이 운영체제를 구축하는 데 핵심적인
도전 과제이다.

기본 원리: 제한적 직접 실행¶

제한적 직접 실행(Limited Direct Execution): 프로그램을 CPU 상에서 그냥 직접 실행

운영체제가 프로그램을 실행하기 시작할 때 프로세스 목록에 해당 프로세스 항목을 만들고 메모리를 할당하며 프로그램 코드를 디스크에서 탑재하고 진입점 (예, main() 루틴 혹은 유사한 무엇)을 찾아 그 지점으로 분기하여 사용자 코드를 실행하기 시작한다.

프로그램 실행에 제한을 두지 않으면 운영체제는 어떠한 것도 제어할 수 없으며 따라서 단순한 라이브러리일 뿐이다.

• Direct Execution의 절차
  1. OS에서 프로세스 리스트에 엔트리를 생성
  2. OS에서 프로그램 메모리 할당
  3. OS에서 메모리로 로드
  4. OS에서 argc/argv를 사용해서 스택 설정
  5. OS에서 레지스터 클리어 후 main문 실행
  6. 프로그램에서 main문 실행
  7. OS에서 프로세스 메모리 해제 및 프로세스 리스트에서 제거

직접 실행의 장점은 빠르게 실행된다는 것이다.
기본적으로 프로그램이 하드웨어 CPU 에서 실행되기 때문이다.

그러나 CPU에서 직접 실행시키면 CPU를 가상화함에 있어 몇 가지 문제를 일으킨다.

첫 번째는 프로그램을 직접 실행시킨다면 프로그램 /운영체제가 원치않는 일을 하지 않는다는 것을 어떻게 보장할 수 있는가?

두 번째 문제는 프로세스 실행 시, 운영체제는 어떻게 프로그램의 실행을 중단하고 다른 프로세스로 전환시킬 수 있는가?
즉, CPU를 가상화하는 데 필요한 시분할(time sharing) 기법을 어떻게 구현할 수 있는가
(가상화 오버헤드, 중간에 인터럽트 발생할 때마다 OS는 어떻게 제어할 수 있는가)

아래에서 이와 같은 질문에 답하면서 CPU를 가상화하는 데 필요한 사항을 더 잘 이해하게 될 것이다.
이러한 기법을 발전시키는 과정 중에 “제한적”이라는 이름이 어디서 비롯되었는지 보게 될 것이다.

Direct Execution의 단점을 해결할 두 가지 해결방안이 있다.

1. 유저모드와 커널모드를 구분한다. 모드를 변경할 때 trap 명령을 사용한다. ^53e86f
2. 자원과 관련된 요청이 오면 OS가 개입한다.(system call을 통해)

핵심 질문 : 제한 연산을 수행하는 방법
프로세스는입출력 연산을 비롯한 다른 제한된 연산을 수행해야 한다. 그러나, 프로세스는 시스템에 대한 권한이 있기 때문에 제한된 연산을 수행할 수 있다. 이 일을 위해 운영체제와 하드웨어가 할 일은 무엇인가?

팁 : 보호된 제어 양도
하드웨어는 두 가지 실행 모드를 제공하여 운영체제를 돕는다. 사용자 모드(user mode)에서 응용 프로그램은 하드웨어 자원에 대한 접근 권한이 일부 제한되어 있다.
운영체제는 컴퓨터의 모든 자원에 대한 접근 권한을 커널 모드(kernel mode)에서 가진다. 이를 위하여 커널 모드로 진입하기 위한 trap명령어와 사용자 모드로 돌아가기 위한 return-from-trap 명령어가 제공된다. 또한, 운영체제가 하드웨어에게 트랩 테이블 (trap table)의 메모리 주소를 알려주기 위한 명령어도 함께 제공된다.

privilege of user = privilege of os in direct execution.

• Issue 1: protect system

  • User can do wrong thing.
  • What if?
    
    C

    int *i; // 포인터 정의  
    i = 0 // 주소 0 지정  
    *i = 1; // 해당 주소에 1 저장  
    

    
    포인터 까먹음
    controlling the memory access

• Issue 2: control the execution

  • Getting the control back from CPU is not easy.
  • What if?
    
    C

    i = -1;  
    while (i < 0) { // infinite loop  
        // do something;  
    }  
    

문제점 1: 제한된 연산 (Limit the execution):¶

유저 모드와 커널 모드¶

프로세스가 다음과 같은 제한된 연산 요청을 수행하기를 원한다면?

• 디스크입출력 요청
• CPU 또는 메모리와 같은 시스템 자원에 대한 추가할당 요청

더 예를 들자면,
최신 Android 운영체제에서 SD카드 사용 시에는 SD카드에 생성된 Android 폴더에 아무나 접근하지 못한다. 해당 폴더는 각 앱이 SD카드에 저장할 데이터를 담는 공간이므로, 다른 앱이 데이터를 변조하여 보안 문제로 이어질 수도 있기 때문이다. 가령, 리디나 알라딘 전자책 앱은 전자책을 해당 폴더에 저장하므로 DRM을 해독할 수 있는 능력만 있다면 전자책을 추출하여 등록하지 않은 기기에서도 볼 수 있다.

그런데 이 SD카드를 Windows, macOS, Ubuntu, Fedora 등 다른 운영체제에서 열어보면 아무런 제약 없이 Android 폴더에 접근할 수 있다. 이는 파일 시스템이 아닌 운영체제가 걸어 둔 제약사항이어서 다른 운영체제에서는 막을 이유가 없기 때문이다. 만약 같은 운영체제 안에서조차 직접 실행을 했다는 이유로 이렇게 보안 상의 이유로 막아둔 접근이 무력화된다면 제한을 둔 의미가 없어질 것이다.

디스크 입출력 요청, 시스템 자원 추가 할당 등 특수한 종류의 연산은 접근 권한 등의 문제로 시스템의 제어를 받아야 할 필요가 있다.
그래서 프로세스가 자유롭게 다룰 수 있도록 하는 것은 적절하지 않다.

Solution 1: Grant everything.
Solution 2: Use protected control transfer

• User mode: Applications do not have full access to hardware resources.
• Kernel mode: The OS has access to the full resources of the machine

Allow the kernel to carefully expose certain key pieces of functionality to user program, such as..

• Accessing the file system: read, create
• Creating and destroying porcesses: fork()
• Communicating with other processes: signal
• Allocating more memory: sbrk()

파일에 대한 접근을 허용하기 전에 접근 권한을 검사하는 파일 시스템을 구현하는 경우 프로세스가 디스크에 대하여 입출력하는 것을 제한하지 않으면 프로세스는 전체 디스크를 읽고 쓸 수 있기 때문에 접근 권한을 검사하는 기능이 아무런 의미가 없다.

이 때문에 사용자 모드(user mode)라고 알려진 새로운 모드가 도입 되었다.
사용자 모드에서 실행되는 코드는 할 수 있는 일이 제한된다.
예를 들어, 프로세스가 사용자 모드에서 실행 중이면 입출력 요청을 할 수 있도록 설정한다.
이때 입출력 요청을 하면 프로세서가 예외를 발생시키고, 운영체제는 해당 프로세스를 제거한다.

커널 모드(kernel mode)는 사용자 모드와 대비되는 모드로서 운영체제의 중요한 코드들이 실행된다.
이 모드에서 실행되는 코드는 모든 특수한 명령어를 포함하여 원하는 모든 작업을 수행할 수 있다.

그러나 우리에겐 아직 해결해야 할 한 가지 문제가 남아 있다.
사용자 프로세스가 디스크를 읽기와 같은 특권 명령어를 실행해야 할 때는 어떻게 해야 하는가?

Trap 명령 (System call)¶

What Is the Difference Between Trap and Interrupt? | Baeldung on Computer Science
읿반적인 응용 프로그램은 사용자 모드에서 실행되며, 시스템 콜을 사용하여 커널로 trap해서 운영체제의 서비스를 요청함.

이런 제한 작업의 실행을 허용하기 위하여 거의 모든 현대 하드웨어는 사용자 프로세스에게 시스템 콜을 제공한다.
Atlas [Kil+62; Lav78]와 같은 커널은 시스템 콜을 통하여 자신의 주요 기능을 사용자 프로그램에게 제공한다.
이러한 기능에는 파일 시스템 접근, 프로세스 생성 및 제거, 다른 프로세스와의 통신 및 메모리 할당 등이 포함된다. 대부분의 운영체제는 수백 개의 시스템 콜을 제공한다.

초기 Unix 시스템은 약 20개 정도의 시스템 콜을 제공하였다.

Trap instruction: int n
시스템 콜을 실행하기 위해 프로그램은 trap 특수 명령어를 실행해야 한다.
이 명령어는 커널 안으로 분기하는 동시에 특권 수준을 커널 모드로 상향 조정한다.
커널 모드로 진입하면 운영체제는 모든 명령어를 실행할 수 있고 이를 통하여 프로세스가 요청한 작업을 처리할 수 있다.

trap은 trap table(a.k.a. IDT, Interrupt Descriptor table)을 사용해서 발생시킨다.
trap table은 trap handler들로 구성이 된다.
trap handler엔 system call handler, div_dy_zero handler, segment fault handler 등이 있다.
부팅 시간에 초기화 된다.

• Raise the privilege level to kernel mode
• Save registers at the kernel stack. (eip, cs, eflags, esp, ss)
• Locates the destination in the kernel
• Jumps to the destination.
• Interrupt number for system call: 0x64 @xv6, 0x30 @Pintos
  • e.g. int 0x64

예를 들어, system call의 처리 절차는 다음과 같다.

1. 프로그램(유저 모드)에서 system call trap을 호출
2. 하드웨어 단에서 kernel stack에 register 값들을 저장하고, 커널 모드로 이동하고, trap handler로 점프
3. OS 단(커널 모드)에서 trap을 제어하고, system call을 수행한 뒤 다시 되돌아 감

Return-from-trap instruction
작업이 완료되면 운영체제는 return-from-trap 특수 명령어을 호출한다.
이 명령어는 특권 수준을 사용자 모드로 다시 하향 조정하면서 호출한 사용자 프로그램으로 리턴한다.

여담 : 왜 시스템 콜은 프로시저 콜과 비슷하게 보일까
open() 또는 read()와 같은 시스템 콜을 호출하는 형태는 C 프로그램의 전형적인 프로시저 호출의 형태와 똑같다. 즉, 만약 프로시저 호출과 똑같다면 운영체제는 시스템 콜을 어떻게 구분할 수 있으며 그에 맞는 작업을 할 수 있는가?
간단한 이유 : 진짜 프로시저 호출이지만 유명한 trap 명령어가 그 안에 감추어져 있다.
더 정확하게 설명하면, 예를 들어, open()을 호출할 때, C 라이브러리의 프로시저 호출을 수행하고 있는 것이다. open()(다른 시스템 콜들도 마찬가지이다)이 호출되면, 라이브러리는 커널과 약속된 호출 규약을 사용하여 open에게 전달할 인자와 시스템 콜 번호를 지정된 장소 (스택 또는 특정 레지스터)에 저장한다.

그런 다음 trap 명령어를 실행한다. 그 다음에 반환 값을 정리하고 시스템 콜을 호출한 프로그램에게 제어를 넘긴다. 이를 위해서 C 라이브러리에서 시스템 콜을 호출하는 부분의 코드는 어셈블리어로 작성된다.

인자의 반환 값을 올바르게 처리하고, 하드웨어마다 다른 trap 명령어를 실행하기 위해 꼭 필요한 일이다.
자 이제 운영체제로 진입하기 위해서 어셈블리 코드 작업을 직접할 필요가 있다는 것을 알았다. 어셈블리 코드는 이미 만들어져 있다.

• What code to run in trap?
  Sources of trap
  1. Completion of disk IO
  2. Keyboard interrupt
  3. System call

trap handler: the code to run for each interrupt number (trap number)

Trap table

1. The address of the trap handlers.
2. Hardware Informs the location of the trap table to OS when booting.
3. The instruction to inform the location of the trap table is also privileged instruction.
4. You cannot execute this instruction in user mode.

하드웨어는 trap 명령어를 수행할 때 주의가 필요하다. 호출한 프로세스의 필요한 레지스터들을 저장해야 한다. 운영체제가 return-from-trap 명령어 실행 시 사용자 프로세스로 제대로 리턴할 수 있도록 하기 위함이다.

예를 들면, x86에서는 프로그램 카운터, 플래그와 다른 몇 개의 레지스터를 각 프로세스의 커널 스택(kernel stack)에 저장한다.
return-from-trap 명령어가 이 값들을 스택에서 팝 (pop)하여 사용자 모드 프로그램의 실행을 다시 시작한다. (Intel systems manual [Int11]을 참조)
다른 하드웨어 시스템은 다른 규약을 사용하긴 하지만 기본적인 개념은 모두 비슷하다.

현재까지의 논의에서 다루지 않은 중요한 사항이 있다. 그것은 trap이 운영체제 코드의 어디를 실행할지 어떻게 아느냐는 것이다. 호출한 프로세서는 분기할 주소를 명시할 수 있다. 주소를 명시한다는 것은 커널 내부의 원하는 지점을 접근할 수 있다는 것이기 때문에 위험하다. 커널이 임의의 코드를 실행하기 위해서는 접근 권한 검사가
끝난 후 분기해야 한다 [Sha07]. 이러한 문제 때문에 커널은 trap 발생 시 어떤 코드를 실행할지 신중하게 통제해야 한다.

커널은 부팅 시에 트랩 테이블(trap table) 을 만들고 이를 이용하여 시스템을 통제한다. 컴퓨터가 부트될 때는 커널 모드에서 동작하기 때문에 하드웨어를 원하는 대로 제어할 수 있다. 운영체제가 하는 초기 작업 중 하나는 하드웨어에게 예외 사건이 일어났을 때 어떤 코드를 실행해야 하는지 알려주는 것이다.

예를 들어, 하드 디스크 인터럽트가 발생하면, 키보드 인터럽트가 발생하면, 또는 프로그램이 시스템 콜을 호출
하면 무슨 코드를 실행해야 하는가? 운영체제는 특정 명령어를 사용하여 하드웨어에게 트랩 핸들러(trap handler)의 위치를 알려준다. 하드웨어는 이 정보를 전달받으면 해당 위치를 기억하고 있다. 따라서 시스템 콜과 같은 예외적인 사건이 발생했을 때 하드웨어는 무엇을 해야 할지 (즉, 어느 코드로 분기하여 실행할지) 알 수 있다.

마지막 하드웨어에게 트랩 테이블의 위치를 알려주는 것은 매우 강력한 기능이다.
당연히 이 역시 특권 명령어이다. 사용자 모드에서 이 명령어를 실행하려고 하면 실행할 수 있고, 어떤 결과가 올지 알고 있을 것이다.

숙고해 볼 주제: 만약 당신이 자신의 트랩 테이블을 설치할 수 있다면, 시스템에 어떤 황당한 일이 일어날까? 컴퓨터를 장악할 수 있는가?

Trap Table¶

trap의 중요한 자료구조.

• 트랩 핸들러의 주소를 가지고 있고, 부팅 시에 OS에게 하드웨어가 트랩 테이블 위치를 알려준다.
• 트랩 테이블의 위치를 알려주는 명령어도 권한이 필요한 명령어. (즉, 유저 모드에서는 얻어낼 권한이 없음)

그림 9.2는 이 메커니즘을 요약해서 나타내고 있다.
연대표는 시간의 흐름에 따라 아래 방향으로 진행된다. 프로세스는 커널 스택을 각자 가지고 있다. 커널 모드로 진입하거나 진출할 때 하드웨어에 의해 프로그램 카운터와 범용 레지스터 등의 레지스터가 저장되고 복원되는 용도로 사용된다.

LDE 프로토콜은 두 단계로 진행된다. 전반부에서 (부팅 시) 커널은 트랩 테이블을 초기화하고 CPU는 나중에 사용하기 위하여 테이블의 위치를 기억한다. 커널은 이러한 작업을 커널 모드에서만 사용할 수 있는 명령어를 이용하여 수행한다 (이러한 명령어는 굵게 강조하였다).

후반부에서 (프로세스를 실행할 때) return-from-trap을 이용하여 사용자 프로세스를 시작할 때 몇 가지 작업을 수행한다. 새로운 프로세스를 위한 노드를 할당하여 프로세스 리스트에 삽입하고, 메모리를 할당하는 등의 작업이 포함된다. return-from-trap 명령어는 CPU를 사용자 모드로 전환하고 프로세스 실행을 시작한다. 프로세스가 시스템 콜을 호출하면 운영체제로 다시 트랩된다. 운영체제는 시스템 콜을 처리하고 return from-trap 명령어를 사용하여 다시 제어를 프로세스에게 넘긴다. 프로세스는 이후 자신의 할 일을 다하면 main()에서 리턴한다. 이때 일반적으로 스텁 코드로 리턴하고 스텁 코드가 프로그램을 종료시킨다. 종료시킬 때 exit() 시스템을 호출하고 다시 운영체제로 트랩된다. 이 시점에 운영체제는 정리 작업을 하게 되어 모든 일이 완료된다.

Interrupt Descriptor Table (IDT, a.k.a Interrupt Vector Table)¶

Q. trap 명령어가 실행되면, 운영체제의 어떤 코드를 실행할지 어떻게 알까?
운영체제가 trap을 처리하기 위해서 trap table을 사용한다. 이 테이블은 부팅 시에 초기화가 이루어지며, 소프트웨어적 사건들을 처리하기 위한 함수 (trap handler) 들이 들어 있다.
각 함수에는 시스템 콜 넘버 (system call number)라는 번호가 정의되어 있고, 운영체제만 해당 위치를 기억 하고 있다. 이제 유저 프로세스가 trap 명령어를 호출하면, 전달 받은 시스템 콜 번호를 확인한 후 유효한 경우 이를 테이블에서 검색 후 실행한다. (사용자 프로그램은 시스템 콜의 위치를 모른다! 일종의 보안 기법이다.)

운영체제 시스템 콜에서 중요한 자료구조. 각각의 인터럽트(= 예외)는 개별적인 인터럽트 핸들러(= 트랩 핸들러)와 맞물려 돌아간다.

※ IDT라는 표현은 x86 및 x86_64 아키텍처에서만 사용하고, ARM의 경우에는 Exception Vector Table이라는 표현을 사용한다. 대부분의 프로세서는 Interrupt Vector Table을 갖고 있다고 한다. (출처: 영문 위키백과, 추가 출처 없음)

시스템콜에서 IVT에 있는 인터럽트를 명시하면, 이 자료구조를 참조하여 어떤 코드를 실행할지 결정한다.

인터럽트의 번호 (리눅스)
인터럽트마다 고유의 번호

• 0 ~ 31 : 예외상황 인터럽트 | 대부분 소프트웨어(내부) 인터럽트
  일부는 정의가 되지 않은 채로 남겨져 있다.
• 32 ~ 47 : 하드웨어 인터럽트
  주변장치의 정류 혹은 개수에 따라 변경이 가능하다.
• 128 : 시스템 콜
  0x80(16진수)를 10진수로 전환하면 128이다.

Recap: Process Creation¶

Load a program code into memory, into the address space of the process.

• Programs initially reside on disk in executable format.
• OS perform the loading process lazily.
  • Loading pieces of code of data only they are needed during program execution.

The program’s run-time stack is allocated.

• Use the stack for local variables, function parameters, and return address.
• Initiallize the stack with arguments → argc and the argv array of main() function

The program’s heap is created.

• Used for explicitly requested dynamically allocated data.
• Program request such space by calling malloc() and free it by calling free().

The OS do some other initialization tasks.

• Input/Output (I/O) setup
  • Each process by default has three open file descriptors.
  • Standard input, output and error

Start the program running at the entry point, namely main().

• The OS transfers control of the CPU to the newly-created process.

문제점 2: 프로세스 간 전환¶

핵심 질문 : 운영체제는 어떻게 CPU를 다시 획득하여 프로세스를 전환할 수 있는가?

직접 실행의 두 번째 문제점은 프로세스 간 전환을 할 수 있어야 한다는 점이다.
운영체제는 실행 중인 프로세스를 계속 실행할 것인지, 멈추고 다른 프로세스를 실행할 것인지를 결정해야 한다.

CPU에서 프로세스가 실행 중이라는 것은 운영체제는 실행 중이지 않다는 것을 의미한다. 운영체제가 실행하고 있지 않다면 어떻게 이런 일들을 할 수 있을까?
CPU에서 실행하고 있지 않다면 운영체제는 어떠한 조치도 취할 수 없다.

이를 해결하기 위해서는 2가지 방법이 존재한다.

• A cooperative Approach: Wait for system calls
• A Non-Cooperative Approach: The OS takes control

협조 방식: 시스템 콜 기다리기¶

협조(cooperative) 방식으로 알려진 방법은 과거의 몇몇 시스템에서 채택되었던 방식이다.

• 시스템 콜 (System Call)
  예를 들어, Macintosh 운영체제의 초기 버전 [Mac11], 또는 오래 전 Xerox Alto 시스템 [Alt79]이 채택했던 방식이다.

프로세스가 운영 체제의 서비스를 요청하기 위해 커널의 함수를 호출하는 경우 발생하는 인터럽트

각 프로세스가 비정상적인 행동은 하지 않고, 오래 연산할 프로세스는 다른 프로세스들이 cpu를 사용할 수 있도록 주기적으로 cpu를 반납할 것이라고 가정한다.

또한, 너무 오랫동안 실행할 가능성이 있는 프로세스는 운영체제가 다른 작업을 실행할 결정을 할 수 있도록 주기적으로 CPU를 포기할 것이라고 가정한다.
대부분의 프로세스는 주기적으로 시스템 콜을 호출하여 CPU의 제어권을 운영체제에게 넘겨준다.

예를 들어, 파일을 열고 읽는 작업을 한다거나 다른 컴퓨터에게 메시지를 송신하거나 또는 새 프로세스를 생성하는 등의 시스템 콜을 호출한다.
이런 유형의 운영체제는 yield 시스템 콜을 제공하는데, 이 시스템 콜은 운영체제에게 제어를 넘겨 운영체제가 다른 프로세스를 실행할 수 있게 한다.

yield 같은 시스템 콜을 사용하여 오래 걸릴 작업 중 주기적으로 CPU 사용을 포기하여 OS가 제어할 수 있도록 프로세스가 ‘협조’하는 방식. 이 방식에서도 비정상적인 행위(0으로 나누기, 접근 불가능한 메모리 영역에 접근 시도 등)를 하거나 그 밖의 시스템 콜을 발생시키면 운영체제로 제어권이 넘어간다. 그러나 기본적으로는 프로세스의 작동을 신뢰하는 것을 전제로 하는 방식이다.

이 방식에서 무한 루프가 발생하면 시스템을 사용자가 직접 재부팅하는 수밖에 없다.

팁 : 응용 프로그램의 오작동 처리하기
운영체제는 종종 오작동 프로세스를 처리해야 한다. 오작동하는 프로세스란 악의적으로 설계되었거나 실수로 인한 버그 때문에 해서는 안 될 무언가를 하려는 프로세스를 말한다. 현대 시스템에서 운영체제가 그러한 부정 행위를 처리하는 방법은 단순히 행위자를 종료시키는 것이다.
만약 메모리에 불법적으로 접근하거나 불법적인 명령어를 실행할 때 운영체제가 취할 수 있는 일은 무엇이 있을까?

• 예외 상황 (Exception)
  프로그램이 허용되지 않은 연산을 수행하려고 할 때 자동적으로 발생하는 인터럽트 (운영체제로의 트랩이 발생)
• 응용 프로그램이 어떤 수를 0으로 나누는 연산을 실행
• 접근할 수 없는 메모리에 접근
  그러면 운영체제는 다시 CPU 를 획득하여 해당 행위를 하는 프로세스를 종료할 수 있다.
  협조 방식의 스케줄링 시스템에서 운영체제는 시스템 콜이 호출되기를 기다리거나 불법적인 연산이 일어나기를 기다려서 CPU의 제어권을 다시 획득한다.

프로세스가 시스템 콜을 호출하기를 거부하거나 실수로 호출하지 않아 운영체제에게 제어를 넘기지 않을 경우 하드웨어의 추가적인 도움없이는 운영체제가 할 수 있는 일은 거의 없다.
협조적 방법에서 악의적이든 버그로 인한 것이든 프로세스가 무한 루프에 빠져 시스템 콜을 호출할 수 없을 때에는 리부팅을 해야만 한다.

비협조 방식: OS 개입¶

• Timer interrupt and Context switch

핵심 질문 : 협조 없이 제어를 얻는 방법
프로세스가 비협조적인 상황에서도 CPU의 제어를 획득하는 방법은 무엇인가?
악의적인 프로세스가 컴퓨터를 장악하지 않도록 보장하기 위하여 운영체제는 무엇을 할 수 있을까?

Timer Interrupt 사용¶

해결책은 타이머 인터럽트(timer interrupt)를 이용하는 것이다.

• 운영 체제에서는 각 프로그램들이 공평한 시간 동안 CPU를 할당 받을 수 있도록 세팅된 시간 동안 CPU를 사용하고, 사용시간이 종료되면 인터럽트를 발생시킨다.

1. 부팅 중 운영체제가 타이머를 시작한다.
2. 타이머는 주기적으로(ms 단위) 인터럽트를 발생한다.
3. 실행 중인 프로세스는 일시정지, 프로세스의 상태는 저장되며 미리 설정된 인터럽트 핸들러가 실행된다.

타이머 장치는 수 밀리 초마다 인터럽트를 발생시키도록 프로그램 가능하다.
인터럽트가 발생하면 현재 수행 중인 프로세스는 중단되고 미리 구성된 운영체제의 인터럽트 핸들러(interrupt handler)가 실행된다.
이 시점에 운영체제는 CPU 제어권을 다시 얻게 되고 자신이 원하는 일을 할 수 있다.
현재의 프로세스를 중단하고 다른 프로세스를 실행시키는 작업 등이 해당된다.

팁 : 제어를 다시 획득하기 위해 타이머 인터럽트 사용하기
타이머 인터럽트 기능을 추가하면 운영체제는 프로세스가 비협조적으로 행동하는 상황에서도 CPU 상에서 실행될 수 있는 능력을 가지게 된다.
타이머 인터럽트 하드웨어 기능은 운영체제가 컴퓨터의 제어를 유지하는 핵심적인 기능이다.

process A 실행 중 디스크에서 어떤 데이터를 읽어오라는 명령을 받았다고 가정해보자.

• process A는 system call을 통해 인터럽트를 발생시킨다.
• CPU는 현재 진행 중인 기계어 코드를 완료한다.
• 현재까지 수행중이었던 상태를 해당 process의 PCB(Process Control Block)에 저장한다.
  (수행중이던 MEMORY주소, 레지스터 값, 하드웨어 상태 등…)
• PC(Program Counter, IP)에 다음에 실행할 명령의 주소를 저장한다.
• 인터럽트 벡터를 읽고 ISR 주소값을 얻어 ISR(Interrupt Service Routine)로 점프하여 루틴을 실행한다.
• 해당 코드를 실행한다.
• 해당 일을 다 처리하면, 대피시킨 레지스터를 복원한다.
• ISR의 끝에 IRET 명령어에 의해 인터럽트가 해제 된다.
• IRET 명령어가 실행되면, 대피시킨 PC 값을 복원하여 이전 실행 위치로 복원한다.

운영체제는 하드웨어에게 타이머 인터럽트가 발생했을때 실행해야 할 코드를 알려주어야 한다.
부팅될 때 운영체제가 이런 준비를 한다.
부팅 과정 진행 중에 운영체제는 타이머를 시작한다. 타이머가 시작되면 운영체제는 자신에게 제어가 돌아올 것이라는 것을 알고 부담 없이 사용자 프로그램을 실행할 수 있다.
또한, 타이머는 특정 명령어를 수행하여 끌 수도 있다. (병행성 관련 추가 학습함.)

인터럽트 발생 시 하드웨어에게도 약간의 역할이 있다.
인터럽트가 발생했을 때 실행 중이던 프로그램의 상태를 저장하여 나중에 return-from-trap 명령어가 프로그램을 다시 시작할 수 있도록 해야 한다.
이러한 일련의 동작은 시스템 콜이 호출되었을 때 하드웨어가 하는 동작과 매우 유사하다.
다양한 레지스터가 커널 스택에 저장되고, return-from-trap 명령어를 통하여 복원된다.

• Scheduler makes a decision:
  Whether to continue running the current process, or switch to a different one.
  If the decision is made to switch, the OS executes context switch.

Context Switch¶

A low-level piece of assembly code

• Save a few register values for the current process onto its kernel stack.
  • General purpose registers
  • PC
  • kernel stack pointer
• Restore a few for the soon-to-be-executing process from its kernel stack.
• Switch to the kernel stack for the soon-to-be-executing process.

Context switch(문맥 교환): Context save and restore

• Context switch의 흐름:
  1. Process A 실행
  2. Process B 도입: A의 context를 저장하고 B의 context를 올림.
  3. B 종료
  4. B의 context를 저장하고 저장했었던 A의 context를 다시 로드.

context switch(문맥 교환) 은 선점 되었을 때 프로세스의 마지막 상태를 기억한다.

Context save: 메모리에 있는 PCB에 CPU register를 담는다.
Context restore: CPU register들에 PCB를 로딩한다.
switching하는 동안은 유용한 일을 못하는 overhead가 발생한다.

시스템 콜을 통하여 협조적으로 하던, 또는 타이머 인터럽트를 통하여 약간은 강제적으로 하던, 운영체제가 제어권을 다시 획득하면 중요한 결정을 내려야 한다.
즉, 현재 실행 중인 프로세스를 계속 실행할 것인지 아니면 다른 프로세스로 전환할 것인지를 결정해야 한다.
이 결정은 운영체제의 스케줄러(scheduler)라는 부분에 의해 내려진다.

다른 프로세스로 전환하기로 결정되면 운영체제는 문맥 교환(context switch) 이라고 알려진 코드를 실행한다.
문맥 교환은 개념적으로는 간단하다.

운영체제가 해야 하는 작업은

1. 현재 실행 중인 프로세스의 레지스터 값을 커널 스택 같은 곳에 저장하고
2. 곧 실행될 프로세스의 커널 스택으로부터 레지스터 값을 복원한다.
   그렇게 함으로써 운영체제는 return-from-trap 명령어가 마지막으로 실행될 때 현재 실행 중이던 프로세스로 리턴하는 것이 아니라 다른 프로세스로 리턴하여 실행을 다시 시작할 수 있다.

프로세스 전환을 위하여 운영체제는 저수준 어셈블리 코드를 사용하여 현재 실행 중인 프로세스의 범용 레지스터, PC뿐 아니라 현재 커널 스택 포인터를 저장한다.

그리고 곧 실행될 프로세스의 범용 레지스터, PC를 복원하고 커널 스택을 이 프로세스의 커널 스택으로 전환한다.
이로써 운영체제는 인터럽트된 프로세스 문맥에서 전환 코드를 호출하고, 실행될 프로세스 문맥으로 리턴할 수 있다.
운영체제가 마지막으로 return from-trap 명령어를 실행하면 곧 실행될 프로세스가 현재 실행 중인 프로세스가 된다.

그래서 문맥 교환이 마무리 된다.

x86 아키텍처 기준으로, 커널 스택은 프로세스마다 생성되며 사용자 모드로 돌아가기 위한 정보 중 일부를 저장하는데 사용하며, 커널 모드 안에서 함수 호출 시 해당 함수의 지역변수도 여기에 할당된다.

프로세스 하나가 4GB의 가상 공간을 할당받을 때, 0~3GB 영역까지는 응용 프로그램이, 3~4GB 영역은 커널이 사용하며 이때 커널이 사용하는 영역 안에 커널 스택이 존재한다.

시스템 콜, 인터럽트 핸들러(타이머 인터럽트 포함) 등이 발생 시 현재 사용 중인 프로그램의 커널 스택 등을 사용. 이는 문맥 교환이 부하가 크기 때문이다.

이 모든 과정의 연대표가 그림 9.3에 나와 있다.

이 예에서 프로세스 A가 실행 중이고 타이머 인터럽트에 의해 중단된다. 하드웨어는 A의 레지스터를 커널 스택에 저장하고 커널 모드로 진입한다.

타이머 인터럽트 핸들러에서 운영체제는 프로세스 B로 전환하기로 결정한다.

이 시점에 switch() 루틴을 호출한다. 이 루틴이 A의 레지스터의 현재 값을 A의 프로세스 구조체에 저장하고 B의 프로세스 구조체에서 B의 레지스터를 복원한다.

그런 후에 A의 커널 스택이 아니라 B의 커널 스택을 사용하도록 스택 포인터를 바꾸어서 문맥 교환을 수행한다. 마지막으로 운영체제는 return-from-trap을 수행하여 B의레지스터를 복원하고 실행을 시작한다.

이 과정이 실행되는 동안 두 번의 레지스터의 저장/복원이 일어난다는 것에 주의하자.

첫 번째는 타이머 인터럽트가 발생했을 때 일어난다.

이 경우 실행 중인 프로세스의 사용자 레지스터가 하드웨어에 의해 암묵적으로 저장되고 저장 장소로 해당 프로세스의 커널 스택이 사용된다.
두 번째는 운영체제가 A에서 B로 전환하기로 결정했을 때 일어난다.
이 경우 커널 레지스터는 운영체제에 의하여 해당 프로세스의 프로세스 구조체에 저장된다.

이것은 운영체제가 A가 아닌 B로부터 커널로 트랩된 것처럼 만든다.

Xv86 문맥 교환 예시 코드¶

이러한 문맥 교환이 어떻게 일어나는지 잘 이해할 수 있도록 xv6의 문맥 교환 코드를 그림 9.4에 보이고 있다.
우선 이해할 수 있는지 살펴보기 바란다.
물론 xv6와 x86에 관한 얼마간의 지식을 가지고 있어야 한다.
context 구조체 old와 new는 구 프로세스와 새 프로세스의 프로세스 구조체 안에 위치해 있다.

병행성 관련 이슈¶

여담 : 문맥 교환하는 데 걸리는 시간은 얼마인가
떠올릴 수 있는 자연스러운 질문은 문맥 교환과 같은 작업의 처리 소요 시간이다.

혹은 시스템 콜의 처리 소요 시간은? 호기심 많은 당신을 위해 lmbench [MS96]라는 도구가 있다.
이 도구는 언급한 그러한 작업의 시간을 정확하게 측정할 뿐 아니라 연관된 다른 성능 수치도 측정한다. 결과는 시간이 지나면서 대략 프로세서의 성능개선 추이와 비슷하게 점점 좋아졌다.

예를 들어, 1996년에 200 MHz P6 CPU에서 실행되는 Linux 1.3.37의 경우 시스템 콜은 4마이크로초 그리고 문맥 교환에는 대략 6마이크로초가 소요되었다 [MS96].

현대 시스템에서는 자릿수가 달라질 정도로 성능이 좋아져서 2 또는 3 GHz 프로세서의 경우 1마이크로초 미만이 소요된다. 운영체제의 모든 동작이 CPU 성능에 따라 좋아지는 것이 아니라는 것에 주의하자.
Ousterhout가 발견한 것처럼 운영체제의 많은 연산은 주로 메모리를 접근하는 연산이며 메모리의 대역폭은 프로세서 속도가 발전하는 것만큼 극적으로 향상되지 않았기 때문 이다 [Ous90].
사용한 워크로드의 특성에 따라 최신의 좋은 프로세서를 구매하더라도 운영체제의 속도가 기대만큼 증가하지 않을 수 있다.

What happens if, during interrupt or trap handling, another interrupt occurs?
OS handles these situations:

• Disable interrupts during interrupt porcessing
• Use a number of sophisticated locking schmes to protect concurrent access to internal data structures.

시스템 콜을 처리하는 도중에 타이머 인터럽트가 발생하면 어떤 일이 발생하는가?
하나의 인터럽트를 처리하고 있을 때 다른 인터럽트가 발생하면 어떤 일이 생기는가?
커널에서 처리하기 더 어려워지는 것은 아닌가 → 그렇다

운영체제는 인터럽트 또는 트랩을 처리하는 도중에 다른 인터럽트가 발생할 때 어떤 일이 생기는가에 대해 신중하게 고려할 필요가 있다. (이후 병행성 파트에서 자세히 배움)

운영체제가 할 수 있는 간단한 해법은 인터럽트를 처리하는 동안 인터럽트를 불능화시키는 것이다.
이럴 경우 하나의 인터럽트가 처리되고 있는 동안 다른 어떤 인터럽트도 CPU에게 전달되지 않는다.
물론, 운영체제는 이 작업을 신중하게 해야 한다. 인터럽트를 너무 오랫동안 불능화시키면 인터럽트를 놓치게 되고 기술적으로도 좋지 않다.
운영체제는 또한 내부 자료 구조에 동시에 접근하는 것을 방지하기 위해 많은 정교한 락(lock) 기법을 개발해 왔다.
이 잠금 기법은 커널 안에서 동시에 다수의 활동이 진행될 수 있게 허용한다.
이 책의 병행성에 관한 부분에서 살펴보겠지만 이런 잠금 기법은 복잡해질 수 있으며 그로 인해 흥미로우면서도 발견하기 힘든 버그를 만들어 낸다.

요약¶

팁 : 리부팅은 유용하다
협조적 선점 모드에서 무한루프와 같은 행동의 유일한 해결책은 컴퓨터를 리부팅하는 것이다. 단순 무식한 방법이지만, 연구가들은 리부팅이나 소프트웨어를 다시 시작하는 방법이 강건한 시스템 구축에 있어 매우 유용하다는 것을 보였다 [Can+04].
1. 리부트는 소프트웨어를 이미 알려진 상태 그리고 검증된 상태로 되돌리기 때문에 유용하다.
2. 리부트는 오래된 자원 또는 제어를 벗어난 자원을 시스템에 반환한다. 이러한 자원은 반환하지 않으면 처리하기 곤란하다.
3. 리부트는 자동화하기 쉽다.
이러한 이유들 때문에 시스템 관리 소프트웨어를 위한 대규모 클러스터 인터넷 서비스에서는 컴퓨터 일부를 리셋시키기 위하여 주기적으로 리부팅하는 것이 흔한 일이다.
이렇게 함으로써 앞서 언급한 모든 이점을 얻을 수 있다. 따라서 리부팅한다고 해서 그것이 단순무식한 방법은 아니다.
오히려 컴퓨터 시스템의 동작을 향상시키기 위하여 충분히 검증된 방법을 사용하고 있는 것이다.

CPU 가상화를 위한 기본 개념
인터럽트 그리고 프로세스와 스케줄러
인터럽트는 고유의 번호가 있다.
그리고 해당 번호에 해당하는 코드들이 있으며 해당 코드들은 운영체제에 존재합니다. 그리고 그러한 코드와 번호들에 대한 정보가 IDT에 들어가 있다. 그래서 인터럽트가 발생하면 IDT를 참조해서 코드를 실행한다.

프로세스
프로세스와 인터럽트를 정리하자면 인터럽트가 발생하면 프로세스는 실행을 중단한다.
그리고 커널 모드로 변경한 뒤에 위에 얘기한대로 IDT를 찾아가 해당 인터럽트에 해당하는 코드를 커널 모드에서 실행한다.
그리고 실행이 끝나면 다시 사용자 모드로 변경됩니다.

스케줄러 (선점형)
스케줄러와 인터럽트를 정리하자면 하드웨어에서 일정 시간마다 타이머 인터럽트를 운영체제에게 알려줍니다. 그러면 운영체제는 해당 인터럽트 정보를 가지고 카운트등을 해서 누적시켜 가지고 있겠죠. 그 뒤에 인터럽트의 카운트가 스케줄러가 정해놓은 어떠한 규칙과 일치한다면 현재 프로세스를 다른 프로세스로 교체하게 된다.

우리는 CPU 가상화를 구현하기 위한 핵심적인 저수준 기법에 관해 설명하였다.
이런 기법들을 묶어서 제한적 직접 실행이라고 부른다. 기본적인 아이디어는 간단하다.

CPU 에서 실행하고 싶은 프로그램을 실행시킨다. 그러나 운영체제가 CPU를 사용하지 못하더라도 프로세스의 작업을 제한할 수 있도록 하드웨어를 셋업해야 한다.

운영체제는 CPU에 안전 장치를 준비해 놓을 수 있다.
우선 부팅할 때 트랩 핸들러 함수를 셋업하고 인터럽트 타이머를 시작시키고 그런 후에 제한된 모드에서만 프로세스가 실행되도록 한다.

이로써 운영체제는 프로세스를 효율적으로 실행할 수 있다.
또한 특별한 연산을 수행할 때, 즉 프로세스가 CPU를 독점하거나, 다른 프로세스로 전환해야 할 때만 개입한다.

다음에 배울 개념: 스케줄러
→ 특정 시점에 어떤 프로세스를 실행시켜야 하는가

• Context Switching Cost
  Context Switching이 발생하게 되면 많은 Cost가 소요된다.
  1. Cache 초기화
  2. Memory Mapping 초기화
  3. Kernel은 항상 실행되어야 합니다. (메모리의 접근을 위해서..)

• Process vs Thread
  Context Switching 비용은 Process가 Thread보다 많이 듭니다.
  1. Thread는 Stack 영역을 제외한 모든 메모리를 공유하기 때문에
  2. Context Switching 발생시 Stack 영역만 변경을 진행하면 됩니다.

참고 자료¶

OS공부 - 제한적 직접 실행 | JW’s Blog
[OS기초] 인터럽트 제대로 이해하기
#3 인터럽트의 원리 - 운영체제와 정보기술의 원리
#7 운영체제 | 인터럽트는 무엇이고 왜 필요한가
운영체제(Operating System) 핵심 개념 정리 (3) - Process – Jang
같은 스터디원분이 정리한 자료
Context Switching이란?