[Parallel Computing] (6) Processes and Threads

 
프로그램 언어는 컴퓨터 프로그램을 작성하는 형식 언어(Formal Language)로 추상화 정도에 따라 High/Low-Level로 나뉠 수 있다. 일반적으로 High-Level Programming language는 Python, Java, C, C++ 같은 언어가 있으며, Low-Level Programming Language는 Assembly language가 있다. Assembly language는 Machine Instruction을 심볼로 표현한다.
(모든 Machine Instruction에 대응되는 심볼이 존재하지 않을 수도 있다.) Assembly language는 Assembler를 통해서 컴퓨터 Machine code instructions으로 변환될 수 있다. 
 
컴파일러(Compiler)는 특정 프로그래밍 언어로 쓰인 문서를 다른 프로그래밍 언어로 변환하는 프로그램을 말한다. 
인터프리터(Interpreter)는 프로그래밍 언어의 소스코드를 바로 실행하는 프로그램을 말한다. 
컴파일러와 인터프리터는 모두 프로그래밍 언어를 기계 코드로 변환하는 동일한 작업을 수행 합한다. 그러나 컴파일러는 프로그램이 실행되기 전에 코드를 기계 코드로 변환한다. 그러나 인터프리터는 프로그램이 실행될 때 코드를 기계 코드로 변환합니다.

컴파일러 & 인터프리터 [1]

 
컴파일을 수행할 때, 전체 코드를 한 번에 수행하는 것이 아니라, 모듈화(Modular programming)하여 각각의 모듈을 컴파일하고 이를 마지막에 연결하여 사용하도록 하는 것이 효율적이다. 

Compiler & Linker [2]

 
수행 가능한 프로그램은 OS Loader에 의해 메인 메모리로 로드되고, 실행 환경을 초기화한다. 프로그램의 시작 포인트를 통해서 컨트롤가능하며, 동작이 완료되면 OS로 컨트롤이 반환된다. 
 
 프로세서는 프로그램의 시작 포인트로부터 동작을 수행한다. 프로세서는 레지스터(Registers)라는 저장공간을 두고 연산을 수행한다. 이 레지스터는 프로세서가 자주 접근하기 때문에 가장 빠르게 동작하는 메모리로 구성된다. 프로세서는 레지스터에 Instruction, 메모리 주소, 계산에 필요한 데이터들을 저장해 두고 사용한다. 일반적으로 하나의 레지스터는 32-bit 혹은 64-bit의 크기를 가진다. 레지스터의 크기는 프로세서가 한 번의 동작으로 처리할 수 있는 데이터의 양을 말하기도 한다.
 
 프로세서에서 사용되는 Instruction 종류에 따라 CISC(Complex Instruction Set Computer)와 RISC(Reduced Instruction Set Computer)로 나뉜다. 간단히 말하면 Instruction 하나가 수행하는 동작이 '많은 가, 적은 가'의 차이에 있다. '많다'는 의미는 Instruction 하나가 표현할 수 있는 동작이 많다는 것을 말하며, 이는 많은 프로그램을 하나의 Instruction으로 표현 가능하는 것이다. 따라서 프로그램 당 Instruction의 수는 적기 때문에, Instruction으로 사용되는 메모리 양은 적다. 반대로 '적다'는 의미는 Instruction 하나가 수행하는 동작이 간단하다는 것을 말하며, 이는 Instruction을 수행하기 위한 Hardware가 상대적으로 간단해질 수 있다는 것을 의미한다. 또한, 프로그램을 Instruction으로 변환하는 과정이 상대적으로 쉬워진다. 
 
현대의 프로세서는 2가지 실행 모드를 지원한다. 하나는 Supervior(Kernel) 모드이고, 또 다른 하나는 User 모드이다. 
 커널 모드에서는 프로세서가 지원하는 모든 Instruction들을 수행할 수 있다. 커널 모드는 시스템의 모든 하드웨어 및 리소스를 제어하고 관리한다. 커널 모드에서 실행 중인 프로세스는 시스템의 모든 리소스에 직접 접근할 수 있다. 따라서 이 모드는 보안 및 안정성을 유지하기 위해 특별한 권한이 필요하다. 
 사용자 모드는 사용자가 작성한 응용 프로그램이 실행되는 모드이다. 사용자 모드에서 실행 중인 프로세스는 시스템 리소스에 직접적으로 접근할 수 없고, 운영 체제의 서비스를 요청해야 한다. 그리고 이 모드에서는 시스템의 리소스에 접근하는 데 필요한 제한적인 권한만 부여된다. 또한 이 모드는 보안을 강화하고 운영 체제의 안정성을 유지하기 위해 사용된다. 
 그런데, 사용자가 kernel mode에서만 수행되는 Instruction을 사용해야 하는 경우도 있다. 이를 OS에서 지원하는 데, System calls이라 한다. System Call은 프로그램이 운영 체제 커널에 직접적으로 액세스 할 수 없는 서비스나 자원을 요청할 때 사용한다. 파일 조작, 입출력 작업, 프로세스 관리, 하드웨어 장치와의 통신 등과 같은 작업을 수행할 때 사용한다. 
시스템 콜은 사용자 수준 프로세스와 커널 간의 인터페이스를 제공합니다. 프로그램이 운영 체제에서 제공하는 서비스를 필요로 할 때, 시스템 콜을 호출하면 사용자 모드에서 커널 모드로 전환한다. 커널 모드에서 운영 체제는 프로그램을 대신하여 요청된 작업을 수행하고, 작업이 완료되면 제어가 다시 사용자 수준 프로세스로 반환한다. 
 
 프로세스(Process)는 컴퓨터에서 현재 실행 중인 프로그램의 인스턴스를 말한다. 각 프로세스는 자체의 메모리 공간을 가지며, 프로그램 코드, 데이터 및 실행 스택을 포함한다. 프로세스는 운영 체제에 의해 관리되며 CPU 시간, 메모리 및 입출력 장치와 같은 리소스를 각 프로세스에 할당한다.
 
Virtual memory는 OS가 물리적 메모리(Physical Memory)를 추상화하는 방법이다. Virtual Memory는 각 프로세스가 독자적인 메모리 공간을 가지고 있다고 생각할 수 있게 하며, 실제 메모리보다 더 많은 공간을 사용할 수 있도록 한다. 이는 RAM과 디스크 저장소를 결합하여 가능하다. 각 프로세스에 할당된 가상 메모리 공간은 페이지로 나뉜다. 각 페이지는 일반적으로 4KB 또는 8KB와 같은 고정 크기의 가상 메모리 부분에 해당한다. 운영 체제는 페이지 테이블이라는 데이터 구조를 사용하여 프로세스가 사용하는 가상 주소를 RAM이나 디스크의 물리적 주소로 매핑한다. 이 메모리 페이지는 필요할 때 물리적 메모리(RAM)로 로드된다. 페이지가 현재 물리적 메모리에 없는 경우 페이지 부재(page fault)가 발생하고, 운영 체제는 디스크에서 필요한 페이지를 물리적 메모리로 가져온다. OS에서 Software적으로 수행하면 매우 느리기 때문에 MMU(Memory Management Unit)과 같이 빠른 주소 변환을 수행하는 Hardware를 두기도 한다. 

Process & Virtual Memory [3]

 
프로세스 간의 통신이 필요할 때가 있다. 이를 수행하기 위하여 공유된 주소 공간(Shared address space)을 사용한다.
또 다른 방법으로는 IPC(Interprocess Communication)이 있는 데, 데이터를 Virtual address space 공유 없이 주고받을 수 있다.

Processes & Shared Address Space [4]

Concurrency(동시성)은 시스템이 여러 작업 또는 프로세스를 동시에 실행할 수 있는 능력을 나타내며, 요새의 모든 컴퓨터는 이 Concurrecy을 지원한다. Concurrency 시스템에서는 작업 또는 프로세스가 독립적으로 시작하고 실행되며, 그 실행은 겹치거나 동시에 발생할 수 있다. 
만약 CPU가 하드웨어의 제약으로 수행할 수 있는 프로세스가 하나라면, 어떻게 여러 프로세스를 동시에 수행할 까? 이는 Context Switch를 통해서 수행한다. 예를 들어 'A'라는 프로세스를 수행하다가, 'B'라는 프로세스를 수행하기 위해 'A' 프로세스의 정보들을 저장해 두고, 'B' 프로세스를 수행하는 것이다. 'B' 프로세스를 수행하다가 'A' 프로세스를 수행하려면, 'B' 프로세스 정보를 저장하고, 'A' 프로세스 정보를 읽어와서 수행한다. OS에서 해당 프로세스가 동작중인지, 준비완료된 상태인지, 특정 이벤트(e.g I/O)로 인하여 막힌 상태(Block)인지를 관리한다.
 여러 프로세스를 동시에 같이 수행하면, 각 프로세스별로 얼마만큼 수행해야 하는지에 대한 문제가 발생한다. 일반적으로 시간 관점에 동일한 시간을 각 프로세서에서 사용할 수 있도록 조절을 수행한다. 
 
 스레드(Threads)는 일반적으로 운영체제에서 스케줄을 수행하는 하나의 프로세스 안에 포함되어 있는 가장 작은 실행 단위이다. 스레드는 독립적인 Independent Fetch/Decode/Execute Loop을 가지고 있으며, 논리적으로 Code/Registers/Stack/Thread-local Data를 가지고 있다. 하나의 프로세스에서 여러 개의 스레드가 동시에 수행될 수 있으며 한 프로세스 내에서 스레드 간에 Code/Data/OS Resources 등의 자원을 공유한다. 하나의 프로세스에서의 스레드들은 기본적으로 논리적 주소(virtual address space) 영역의 일부(Code/Data sections)를 공유한다. 이를 활용하여 스레드 간의 협력 및 조직력은 이 공유된 공간에서 변수들을 읽거나 쓰는 동작을 통해서 수행된다. 

Process & Thread [5]

 
 프로그램을 작성하는 사용자는 API(Application Programming Interface)를 통해서 스레드 생성 및 관리를 수행할 수 있다.  사용자 모드(User-Level) library는 Kernel의 도움 없이 사용자 공간에서 수행된다. 커널 모드(kernel-Lebel) library는 운영체제에서 직접적으로 지원한다. library를 위한 Code 및 Data 구조는 커널 공간(Kernel Space)에 존재한다. 일반적으로 API를 사용하면  System Call를 수행한다. POSIX PThreads는 Thread Library 중 하나로 User-level library를 제공한다.
 
CFS(Completely Fair Scheduler)는 리눅스 커널에서 프로세서와 스레드를 스케쥴링하는 방법 중에 하나다. 이 스케쥴링 방식은 프로세스들과 쓰레들들간의 구분 없이 자원을 배분한다. 여기서 말하는 자원은 수행하는 시간이다. 즉. 프로세스/스레드가 공평하게 프로세서(processor)의 시간을 나눠서 이용하도록 한다. 
 우선, 스케쥴링을 수행하기 위하여 어떤 프로세스들이 동작 가능한 상태인 지를 관리한다. 이를 Run-Queue라고 불리는 데이터 구조를 사용하며, 각 프로세서마다 존재한다. 
 각 프로세스가 얼마만큼의 수행되었는 지를 측정하여 이를 기준으로 스케쥴링을 수행한다. 이때, 실제 수행 시간과 각 프로세스의 중요도(Priority)를 고려하는 Virtual Runtime을 계산한다. 
 프로세스의 중요도(Prioirty)는 각 프로세스마다 weight 값을 표현될 수 있고, 이를 Nice Values라고 한다. Nice Value는 아래와 같이 runtime을 계산하는 데 사용되며, Nice value가 작아지면, Weight(W(t))는 값이 커지고, Weight 값이 커지면, Virtual runtime 값이 작아진다. 예를 들어 nice value 0일 때의 weight(W0)는 nice value 10일 때의 weight(W10) 보다 큰 값을 가지고 있다. 

Virtual Runtime[6]

 
CFS는 Virtual Runtime을 기반으로 실행 가능한 작업을 조직화하기 위해 Red-Black Tree 데이터 구조를 사용한다. Red-Black Tree는 self-balanced tree의 속성을 가지고 있다. Tree 내의 모든 노드(Node)에 대해, 그 왼쪽 하위 트리의 모든 노드는 해당 노드보다 작은 키를 가지고 있으며, 오른쪽 하위 트리의 모든 노드는 해당 노드보다 큰 키를 가지고 있다. CFS에서는 Virtual runtime이 가장 작은 process를 찾기 위해 왼쪽 가장 밑 Leaf Node를 선택한다.
 CFS는 일정 시간마다 스케쥴링을 수행한다. 프로세스가 동작 중일 때, 시간을 측정하여 일정 시간에 도달하면, Virtual Runtime을 다시 업데이트하고, 이를 통해서 다시 프로세스를 선택한다. 
 CFS는 하나의 프로세서 내에서 여러 프로세스를 스케쥴링하기 위해 사용한다. 따라서 하나의 Run-queue를 가지고 있다. SMP(Symmetric Multiprocessing) 스케쥴링은 여러 프로세서들 간에 스케쥴링을 의미하고, 각 프로세서가 가지고 있는 Run-queue의 Load balancing을 수행하는 것이다. 스케쥴링 단위를 각 프로세서가 아니라 프로세서들의 그룹으로 지정하여 수행할 수 있다. load balancing은 특정 시간마다 수행되며, 가장 먼저 현재 태스크의 분배가 적절하게 잘 수행되고 있는 지를 체크한다. 이는 각 프로세서가 가지고 있는 Run-Queue의 Length를 통해서 알 수 있으며, 가장 태스크가 많은 곳에서 적은 곳으로 해당 프로세스들을 이동(Migration)시킨다. Push와 Pull로 표현될 수 있는 데, Push는 프로세스를 보내는 것이고, Pull은 프로세스를 가져오는 것이다. 바쁜 프로세서들은 프로세스를 다른 프로세서로 보낼 수 있고, 현재 놀고 있는 프로세서들은 다른 프로세서로부터 프로세스를 가져올 수 도 있다. 그런데, 자원을 효과적으로 분배하는 것에는 이점이 있지만, 손해를 보는 경우도 있다. 각 프로세서마다 각자의 Cache를 가지고 있는 데, 이 Cache에 전달받거나 가져온 태스크에 관련된 데이터가 존재하지 않는 다면 관련 데이터를 Cache로 모두 가져와야 하는 단점이 존재한다. 

Symmetric Multiprocessing [7]

 
 
 
 
 
 
 
 
[1]: https://www.guru99.com/difference-compiler-vs-interpreter.html

Compiler vs Interpreter – Difference Between Them

[2] : https://fabiensanglard.net/dc/ld.php

Driving Compilers

[3] : https://velog.io/@junttang/SP-8.1-Virtual-Memory-Concepts

SP - 8.1 Virtual Memory Concepts

[4] : https://images.app.goo.gl/2wAd2NZqBo4VYfk37

PPT - Lecture 1: Parallel Architecture Intro PowerPoint ...

[5] : https://velog.io/@jobmania/Thread-%EC%93%B0%EB%A0%88%EB%93%9C

Thread - 쓰레드

[6]: https://images.app.goo.gl/cAUBByxXQtUU71C59

Real-Time Computing and Communications Lab., Hanyang University ...

[7]: https://images.app.goo.gl/Lsjdhhw6i2k8eNzU7

What really happened on Mars?