Jins' Dev Inside

Context Switching 은 면접에서 지원자의 기본기를 검사할 목적으로 단골로 등장하는 질문이자, CS의 중요한 기본 지식이기도 하다.

Context Switching 이란 CPU가 한 개의 Task(Process / Thread) 를 실행하고 있는 상태에서 Interrupt 요청에 의해 다른 Task 로 실행이 전환되는 과정에서 기존의 Task 상태 및 Register 값들에 대한 정보 (Context)를 저장하고 새로운 Task 의 Context 정보로 교체하는 작업을 말한다.

여기서 Context란, CPU 가 다루는 Task(Procee / Thread) 에 대한 정보로 대부분의 정보는 Register 에 저장되며 PCB(Process Control Block) 으로 관리된다.

여기서 Process 와 Thread 를 처리하는 ContextSwitching 은 조금 다른데, PCB는 OS에 의해 스케줄링되는 Process Control Block이고, Thread 의 경우 Process 내의 TCB(Task Control Block) 라는 내부 구조를 통해 관리된다.

Task 의 PCB 정보는 Process Stack, Ready Queue 라는 자료구조로 관리가 되며, Context Switching 시 PCB 의 정보를 바탕으로 이전에 수행하던 작업 혹은 신규 작업의 수행이 가능하게 된다.

PCB는 주로 다음과 같은 정보들을 저장하게 된다.

(1) Process State : 프로세스 상태

(2) Program Counter : 다음에 실행할 명령어 Address

(3) Register : 프로세스 레지스터 정보

(4) Process number : 프로세스 번호

Context Switching 시, Context Switching 을 수행하는 CPU 는 Cache 를 초기화하고 Memory Mapping 을 초기화하는 작업을 거치는 등 아무 작업도 하지 못하므로 잦은 Context Switching 은 성능 저하를 가져온다. 

일반적으로 멀티 프로세스를 통해 PCB를 Context Switching 하는 것보다 멀티 쓰레드를 통해 TCB 를 Context Switching 하는 비용이 더 적다고 알려져있다.

주로 Context Switching 은 Interrupt 에 의해 발생되는데, Hardware 를 통한 I/O 요청이나, OS / Driver 레벨의 Timer 기반 Scheduling 에 의해 발생한다.

더 자세한 참조 링크 : 

https://stackoverflow.com/questions/7439608/steps-in-context-switching/7443719

https://nesoy.github.io/articles/2018-11/Context-Switching

캐시란 데이터를 임시로 저장해두는 장소를 말한다. 임시로 저장하여 사용하는 데이터의 종류는 제한이 없기 때문에 작게는 메모리에서 크게는 Logic 혹은 그 이상을 저장할 수 있다.

Cache 의 목적은 로직을 처리하는 데 있어서 빠른 접근성을 제공하는 것이며, 단순히 수동적으로 보관하는 것에 그치지 않고 이를 응용해서 작업의 결과를 저장함으로써 해당 로직의 불필요한 수행을 줄여주는 능동적인 역할까지 수행한다.

캐시가 될 수 있는 것은 일반적으로 로컬 메모리부터 별도의 디스크 볼륨까지 다양하지만 Cache 로 사용하기 위한 가장 중요한 요건은 데이터로의 접근성이다.

Cache 에 대한 접근성은 어떤 경우에도 로직 상에서 원하는 데이터에 직접 접근하거나 만들어내는 비용보다 저렴해야 한다. 그래야만 캐시로서의 의의가 있는 것이다.

그렇기 때문에 Cache 는 접근성이 빠른 공간(Space)에 빠른 자료구조를 사용한다.

캐시서버로 이용되는 서버들은 I/O 에 최적화된 공간이 사용되며 당연히 이에 대한 접근성에 있어서 효율적인 REST 등의 방법을 사용한다. 

컴퓨터 내에서 사용되는 캐시는 RAM보다 빠른 L1,L2 레지스터를 캐시로 사용하고, 프로그램 내에서 구현된 Software Cache 라면 접근에 용이한 Map 과 같은 자료구조에 인메모리(Inmemory)로 저장한다.

다음은 캐시를 이해하는 데 중요한 용어들이다.

 - origin : origin 혹은 origin server 는 캐시에 저장할 실 데이터가 존재하는 공간이다. 웹 캐시라면 DB 서버일 수도 있고, SW 내에서라면 파일 혹은 실행 함수 그 자체일 수도 있다.

 - cache expire : 프로세스 내에서 사용하는 인메모리 캐시나 영구히 상주해야하는 정보를 가진 캐시가 아니라면 Cache 는 Expire Date 를 갖고 있으며 해당 시간이 지나면 상한(Stale) 상태가 된다.

 - cache freshness : 캐시가 만료되지 않은 경우를 fresh 한 캐시라 하고 만료된 경우 stale cache 라 한다.

 - cache hit : 참조하려는 데이터가 캐시에 존재할 때 해당 캐시를 조회하는 걸 Cache hit 이라 한다.

 - cache miss : 참조하려는 데이터가 캐시에 존재 하지 않는 경우

 - cache hit ratio : 적중률로 전체 참조 횟수 대비 Cache hit 된 비율을 의미한다. 실질적으로 캐시의 설계는 Cache hit Ratio 를 높이는 데 초점을 둔다.

다음은 캐시의 동작에 대한 정책들이다.

 Cache Read : 

 - Cache-aside 방식 : 데이터를 참조 하기 전에 참조하고자 하는 값이 캐시에 존재하는지 확인한다. 여기서 값을 직접 비교하기 보다는 키를 이용해서 캐시에 접근한다. 

 Cache에 존재한다면 Cache에서 데이터를 가져온다. 만약 Cache에 존재하지 않는다면 origin에서 데이터를 가져오고 이를 캐시에 저장한다.

 - RT/WT/Write back 방식 : 캐시를 Main Data Source 로 사용하기 때문에 캐시에서만 데이터를 조회한다.

 RT/WT 방식(Read Through / Write Through) 은 Read Scalability 가 가장 뛰어나다.

 Cache Write :

 - Cache-aside 방식 : 캐시를 Application Level 에서 직접 갱신시켜준다. 개발자가 Flow 를 이해하고 Update / Evict 시켜줘야 하며, 그렇지 않으면 Cache 데이터와 DB 데이터가 불일치하는 Stale 현상이 발생한다.

 - Read Through / Write Through 방식 : 데이터의 쓰기시 캐시와 실제 저장공간의 데이터 둘다 최신화 시키는 작업이다. 

 캐시를 메인 Database 로 사용하는게 특징적이며, 캐시에 데이터를 먼저 업데이트하고 캐시에서 Main Database 를 즉시 갱신시킨다.

 양쪽의 데이터를 동일하게 유지할 수 있지만, 쓰기 시에 추가 부하가 생긴다는 단점이 있다.

 - Write Back 방식 : 데이터의 쓰기시 캐시의 데이터만 최신화 하고 해당 Cache 를 Evict 시켜놓는다. 이 후 RT/WT 방식처럼 캐시 값을 마킹된 기준으로 origin 으로 직접 반영(Write) 하는데, 캐시가 별도의 큐를 이용해서 Database Source를 비동기로 Update 시켜준다.

 Write Performance 와 DB Scalability 에 있어서 가장 뛰어나다.

 쓰기 작업이 Cache 에서만 발생하지만, Cache 가 만료되는 시점까지 Origin 에 Write Failure 가 발생한다면 데이터를 영구 손실할 위험이 존재한다. 

 Cache Replacement : 

  웹 캐시의 경우 자동 expire 하거나 명시적으로 cache 를 지워주는 동작을 해주지만, 캐시를 Scheduling 에 사용하는 컴퓨터나 알고리즘의 경우 Replicement Policy 를 갖는다.

 다음은 몇가지 대표적인 알고리즘들이다.

  - FIFO(First In First Out) : 오래된 캐시를 먼저 비우고 새로운 캐시를 추가하는 방식이다.

  - LIFO(Last In First Out) : 가장 최근에 반영된 캐시가 먼저 지워진다.

  - LRU(Least Recently Used) : 가장 최근에 사용되지 않는 순서대로 캐시를 교체한다. 가장 오랫동안 사용되지 않은 캐시가 삭제되며 일반적으로 사용되는 방식이다.

  - MRU(Most Recently Used) : 가장 최근에 많이 사용되는 순서대로 캐시를 교체한다. 휘발성 메모리를 이용해야 하는 특수한 상황에 사용된다.

  - Random : 말그대로 랜덤으로 캐시를 교체한다.

 운영체제를 배웠다면 페이지 교체 알고리즘이 Cache Replacement 정책을 사용한다는 것을 알 수 있을 것이다.

본 포스팅에서는 넓은 범위의 Cache 의 정의와 목적, 정책들에 대해 정리해보았다.

이론적인 부분이고 웹 캐시와는 조금 다르기도 하지만 중요한 기본 개념은 잘 숙지해두자.

참조 : 

https://en.wikipedia.org/wiki/Cache_replacement_policies

https://codeahoy.com/2017/08/11/caching-strategies-and-how-to-choose-the-right-one/

https://gomguard.tistory.com/115

https://onecellboy.tistory.com/260

https://dzone.com/articles/using-read-through-amp-write-through-in-distribute

컴퓨터는 CPU에서 tick 을 발생시키며 1970년 1월 1일부터 발생된 tick 의 수를 계산해서 시간을 측정한다.

이 시작점을 UNIX 계열에서는 POSIX time 혹은 Epoch time 이라 하며, 1970년 1월 1일 00:00:00 UTC 이고, 

이때부터 경과 시간을 초로 환산해서 사용한다.

이런 방식에는 몇가지 문제가 있는데, 먼저 윤초(예를 들어 1998년 12월 31일 23:59:60)는 표현할 수 없이 무시된다.

현재 32비트 운영체제에서 초 시간을 지정하는 time_t 자료형은 32비트 Integer 이기 때문에, 

2038년이 되면 overflow 문제가 발생한다.

이를 2038 Years Problem 이라 하며 2038년 1월 19일 03:14:07 UTC 가 되면 오버플로우가 발생해서 

32비트 유닉스 시스템의 시간은 음수가 되어버린다.

그렇기 때문에 현재 int32 를 int64 로 바꾸는 노력을 계속하고 있고, 지속적으로 수정이 진행되고 있다.

컴파일 과정은 사람이 이해할 수 있는 High Level Programming Language 로 구성된 소스코드를 기계가 이해할 수 있는 Lower Level Language 로 바꾸는 과정이다.

컴파일러는 다음과 같은 과정을 통해 컴파일을 수행한다.

[출처 : https://www.programcreek.com/2011/02/how-compiler-works/]

위의 그림은 컴파일의 단계를 간략하게 설명한다. 다음은 그림에 대한 설명이다.

(1) Lexical Analysis 

소스코드를 Token 으로 분할한다. 모든 키워드와 Parenthesis, 변수들 및 괄호들을 분리해낸다.

(2) Syntax Analysis

앞선 단계에서의 스캔으로 만들어진 토큰들(Token Stream)의 문법을 분석하기 위한 자료구조료 변형한다.

이렇게 만들어지는 자료구조를 Parse Tree 라고 한다.

이 단계에서는 Token 이 Valid 한지 검출하지 못하며, Token 이 사용되기 이전에 정의 또는 초기화되어있는 지 등 정적분석은 불가능하다.

또한 이단계에서 파싱이 일어난다. Parsing 작업은 Top-Down, Bottom-Up 두가지 방식으로 나뉜다.

Top-Down Parsing 은 Parse Tree 의 윗쪽부터 파싱을 수행하며, Bottom-Up Parsing 은 트리의 아래쪽부터 파싱이 수행된다.

유명한 파서의 종류로 Top-Down 방식의 Non-Backtracking Predictive Parser 인 LL Parser와 Bottom-Up 방식의 LR Parser 가 존재한다.

(3) Semantic Analysis

각 기호들 및 구문들을 의미있는 값들로 변경한다. 가령 기호 < 는 bool 을 Return 하는 Operand 함수로,

While 과 같은 키워드는 반복 구조를 이루는 void 함수로, 각 변수는 메모리로 치환한다.

이 단계에서 Type 의 Mismatch 나, 변수의 미정의, 파리미터 미정의 등 문법적 요소들이 검증된다.

(4) IR Generation

구문 분석으로 이루어진 자료를 중간 언어로 변경하는 작업을 수행한다.

IR 은 Intermediate Representation 의 약어로 소스코드에 근접한 기계어인 High Level IR, 타겟 머신에 종속적으로 디자인된 Low Level IR 이 존재한다.

컴파일러는 소스코드를 High Level IR -> Low Level IR 로 변경한 뒤 Target Machine Code 로 해석한다.

(5) IR Optimization

중간 언어를 최적화한다. 불필요한 루프를 없애거나, 사용하지 않는 변수의 정리 등이 수행된다.

(6) Code Generation

Syntax Analyzer 및 Semantic Analyzing 된 출력값을 Low level Code 로 해석한다.

이 단계를 거쳐서 Assembly Code 등의 Object Code 로 번역된다.

이 단계에서 수행되는 작업들은 다음과 같다.

 - Instruction Selection : 어떤 명령어를 사용할 것인지

 - Instruction Scheduling : 어떤 명령어를 먼저 실행할지 (최적화)

 - Register Allocation : 변수들을 프로세서 레지스터에 할당

 - Debug data generation : 디버그 모드인 경우 디버그를 위한 코드를 생성

(7) Optimization

위의 과정에서 생성된 코드를 한단계 더 최적화한다.

이 단계의 최적화는 두단계로, Machine 에 종속되지 않은 일반적인 형태의 최적화와 Machine 에 종속된 최적화가 이루어진다.

이 과정을 거치면서 중복 제거, 메모리 확보, 코드 정리, 루프 최적화, Control Flow 개선이 일어난다.

위의 단계들을 거치면 High Level Source Code 는 Machine Code 로 변환된다.

Generating 되는 코드는 대게 머신별로 다르게 되며, 세부로직 및 최적화의 과정 역시 컴파일러에 따라 차이가 존재하게 된다.

본 포스팅은 컴파일러에 대한 간략한 소개를 다루고 있으며 더 자세한 내용은 다음 링크들을 참조한다.

(이해해야할 분량이 많다.)

참조

https://www.tutorialspoint.com/compiler_design/index.htm

https://www.programcreek.com/2011/02/how-compiler-works/