Pw4ngC0

프로세스의 스케줄링(Scheduling)

CPU는 하나인데 여러개의 프로세스를 동시에 실행할 수 있다. 그 방법은 하나의 CPU가 여러개의 프로세스를 번갈아가면서 실행하는 것이다. 멀티 프로세스 운영체제에서 여러개의 프로세스가 실행되는 것처럼 보이는 이유는 여러개의 프로세스들이 CPU할당 시간을 나누기 때문이다.

스케줄링 기본원리

프로세스의 CPU할당 순서 및 방법을 결정짓는 일을 가리켜 스케줄링(Scheduling)이라 한다. 이때 사용되는 알고리즘을 스케줄링 알고리즘(Scheduling Algorithms)이라 한다. 스케줄링 알고리즘을 적용해서 실제로 프로세스를 관리하는 운영체제 요소(모듈)을 스케줄러(Scheduler)라고 한다.

멀티프로세스는 CPU를 바쁘게 한다.

A,B,C 프로세스를 모두 실행시킨 후 멀티 프로세스 운영체제의 스케줄러에 의해서 프로세스들이 관리하도록 한다. 정해진 순서에 의해서 CPU의 실행시간을 나눠서 할당받아 실행하는 형태이다.

프로그램은 실행되는 과정에서 많은 시간을 I/O(입력 및 출력)에 할당 한다. I/O는 데이터 입출력을 뜻한다. 파일 입출력 뿐만아니라 네트워크로 데이트럴 송수신 하는 것도 I/O에 해당한다. 입출력에 관련된 일을 할 경우 CPU는 아무일도 하지않고 대기하게 된다.

A프로세스가 I/O에 관련된 일을 할 경우, 운영체제는 스케줄러를 통해서 다른 프로세스가 실행되도록 스케줄링한다.

즉 A프로세스가 I/O작업을 하는 동안 B프로세스가 CPU에 의해서 실행을 시킬 수 있다.

프로세스의 상태 변화

여러개의 프로세스들이 돌아가면서 실행되기 때문에, 프로세스 상태는 시간 흐름에 따라 변화한다.

상황 1. S(Start)에서 Ready 상태로의 전이를 보여준다.

S는 프로세스가 생성됨을 의미한다. 프로세스는 생성과 동시에 Ready상태로 들어간다. Ready상태에 있는 프로세스는 CPU에 의해 실행되기를 희망하는 상태이다. 현재 CPU에 의해서 임의의 프로세스가 실행중일 수 있어 바로 Running상태가 되는것이 아니고 Ready상태가 된다.

상황 2. Ready 상태 -> Running

Ready상태에 있는 프로세스들은 스케줄러에 의해서 관리되는 프로세스들이다. 스케줄러는 Ready 상태에 있는 프로세스중 하나를 선택해서 CPU에 의해 실행될 수 있도록 한다.

Ready 상태에 있는 프로세스들 중 스케줄러에 의해 선택된 프로세스는 Running 상태가 되어 실행된다.

상황 3. Running 상태 -> Ready

일의 중요도에 따라 실행순서를 정하기 위해서 프로세스에는 우선순위라는 개념이 존재한다. 프로세스 생성시 중요도에 에 따라 우선순위가 높다면 A프로세스를 Ready상태로 변경하고 B프로세스를 Running 상태로 변경한다.

상황 4. Running 상태 -> Blocked 상태

일반적으로 데이터 입출력에 관련된 일을 하는 경우 프로세스가 실행을 멈추는 상태(Blocked)로 들어간다. 데이터 입출력을 진행 중인 프로세스는 잠시 내려오게 하고(Blocked) Ready상태에 있는 프로세스중 하나를 대신 실행시키는 것이다.

상황 5.Blocked 상태 -> Ready 상태

Ready상태는 스케줄러에 의해 선택되어 바로 Running이 가능한 상태이고 Blocked 상태는 스케줄러에 의해 선택될 수 없는 상태이다. 입출력이 완료된 Blocked 상태에 있는 프로세스는 다시 Ready 상태가 되어 스케줄러의 선택을 기다려야 한다.

컨텍스트 스위칭(Context Switching)

CPU내에 존재하는 레지스터들은 현재 실행 중에 있는 프로세스 관련 데이터들로 채워진다. 즉 실행중인 프로세스가 변경되면 CPU내에 레지스터들의 값이 변경된다. 컨텍스트 스위칭이란 하나의 프로세스를 실행하고 있는 상태에서 다음 우선 순위의 프로세스가 실행되어야 할 때 기존의 프로세스의 레지스터들을 메모리에 저장하고 메모리에 존재하는 다음 프로세스의 정보를 레지스터로 옮기는것이 컨텍스트 스위칭이다.

요즘 운영체제는 "멀티 프로세스(Multi-Process)운영체제" 라고 불린다. 이는 프로세스라는 것이 여러개 존재할 수 있는 운영체제라는 뜻이다.

프로세스란 실행중인 프로그램을 의미한다.

실행파일(.exe)이 더블클릭되면, 프로그램 실행을 위해 메모리(RAM) 할당이 이루어지고, 메모리 공간으로 바이너리 코드가 올라간다.

이순간부터 프로그램은 프로세스라고 불리게된다. 즉 실행중인 프로그램이 프로세스이다.

프로세스를 구성하는 요소

Execution of "C" Program

프로그램이 실행되면 각각 데이터가 특정 영역에 저장된다.

Data 영역 : 전역변수(global), 정적 변수(static), 배열(array), 구조체(structure) 등이 저장된다. 초기화 된 데이터는 data영역에 저장되고, 초기화되지 않는 데이터는 BSS(Block Stated Symbol)영역에 저장된다. BSS는 초기화되지 않은 전역 데이터를 위한 영역이다.

Stack 영역 : 지역 변수 할당과 함수 호출시 전달되는 인자값들의 저장을 위해 존재한다. LIFO(Last in First out)데이터 구조를 가진다.

Heap 영역 : 필요에 의해 동적으로 메모리를 할당할 때 사용. malloc, calloc 함수에 의해 할당된다.

Code 영역 : 프로그램을 실행시키면, 실행파일 내에 존재하는 명령어들이 메모리상에 올라가서 순차적으로 실행되는데 실행파일을 구성하는 명령어들이 올라가는 영역을 Code 영역이라고 한다.

프로그램 실행시 메모리 구조

Register Set

실행파일을 실행하면 실행을 위한 데이터들로 레지스터가 채워진다.

즉 레지스터들의 상태까지도 프로세스의 일부라고 말할 수 있다.

Direct 모드의 문제점과 Indirect모드의 제안

하나의 명령어에 여러 정보를 담다보니 표현하는 데이터 크기에 제한이 따른다는 문제점이 등장 하였다.

예를 들어 LOAD 명령어의 메인 메모리 주소값을 나타내는 source 부분에서 문제가 생길 수 있다.  이 부분에 총 여덟개의 비트 수가 할당되어 0x0000 ~ 0x00ff까지만 표현할 수 있다.

만약에 0x0100번지 값을 참조하고자 한다면 문제가 된다.

위에 설명한 메모리 접근 방법을 Direct모드라 한다.

이러한 Direct모드가 지니고 있는 단점을 해결하기 위해서 Indirect 모드가 등장했다.

Direct 모드는 주소를 직접적으로 표현하는데 반대로 Indirect 모드에서는 지정하는 주소에 저장된 값을 주소로 참조한다.

direct 모드 명령어

Indirect 모드 명령

Indirect 모드 명령어를 보면 피연선자 0x10을 [ ] 기호로 감싸고 있다. 이는 Indirect 모드로 메모리를 참조하는 명령어 구성을 위해서 정의해놓은 기호이다. 즉 [ ] 기호로 주소값을 감싸면 Indirect 모드 연산을 의미한다.

STORE 명령어 에서도 Indirect 모드는 동일하다.

int a= 10;    //0x0010 번지

int b= 20;    //0x0100 번지

int c = 0;    //0x0020 번지

c = a+b 

위 예제의 명령어는

LOAD r1, 0x0010

MUL r0, 4, 4

MUL r2, 4, 4

MUL r3, r0, r2

STORE r3, 0x0030

LOAD r2, [0x0030]

ADD r3, r1, r2

이다.

LOAD & STORE 명령어의 필요성

명령어를 디자인 하는 과정에서 "연산결과를 레지스터에만 저장할 수 있도록 하겠다"는 제한 사항이 있다. 이것은 모든 피연산자에 메인메모리 주소값이 올 수 없다는 제약이다.

그렇기 때문에 지금까지 디자인한 명령어로 아래의 연산을 하지 못한다.

int a= 10;                          //0x10 번지 할당

int b = 20;                         //0x20 번지 할당

int c = 0;                          //0x30 번지 할당

c = a+b;

변수 a,b,c는 메인메모리 0x10번지, 0x20번지, 0x30번지에 할당되었다.

"0x10번지에 저장된 값과 0x20번지에 저장된 값을 더해서 0x30번지에 저장하라" 라는 문제를 해결하기 위해서는

레지스터와 메인메모리 사이에서 데이터를 전송할 수 있는 명령어가 필요하다.

메인 메모리에 저장된 데이터를 레지스터로 이동시키는 명령어 LOAD, 레지스터에 저장된 데이터를 메인 메모리로 이동시키기 위한 명령어 STORE가 필요하다. 각각 명령어는 피연산자가 두개(메인 메모리 정보, 레지스터 정보)면 된다.

LOAD 명령어

destination : 데이터를 저장할 레지스터 정보

source : 데이터를 읽어올 메모리의 주소 정보

LOAD는 이진코드 110으로 정의했다.

ex) LOAD r3, 0x07

위 명령어는 "0x07번지에 존재하는 데이터를 레지스터 r3에 저장하라"이다.

명령어 구조는 아래와 같다.

STORE명령어

source : 데이터를 읽어올 레지스터 정보

destination : 데이터를 저장할 메모리 주소 정보

STORE는 이진코드 111로 정의한다.

ex) STORE r2, 0x08

위 명령어는 "레지스터 r2에 존재하는 데이터를 메인 메모리 0x08번지에 저장하라"는 의미이다. 아래는 이진 명령어 이다.

예제 명령어 구성

int a = 10;         //0x10번지

int b = 20;         //0x20번지

int c = 0;          //0x30번지

c = a + b;

LOAD r1, 0x10

LOAD r2, 0x20

ADD r3, r1, r2

STORE r3, 0x30

피연산자가 레지스터가 되게끔 하기 위해 메모리에 저장된 값을 레지스터에 옮겨다 놓은 후 덧셈연산을 한다.

컴퓨터 디자인

CPU를 구성하는 기본적인 요소는 ALU, 컨트롤 유닛, 레지스터이다. CPU의 특성을 알 필요가 있는 시스템 프로그래머 입장에서 CPU를 보는 관점 대부분이 레지스터에 집중된다.

레지스터 디자인

레지스터를 디자인하는데 있어서 결정해야할 중요한 세가지 요소.

1. 레지스터를 몇 비트로 구성할 것인가.

2. 몇개의 레지스터로 구성할 것인가.

3. 레지스터 각각을 무슨 용도로 사용할 것인가.

이책에서는 16비트 레지스터 8개를 사용한다고 가정한다. 레지스터 이름은 r0~r7이다.

r0~r3은 범용 레지스터이다. 주로 연산에 사용된다.

r4인 ir은 instruction register 이다. 

r5인 sp는 stack pointer이다.

r6인 lr은 link register이다. 

r7인 pc는 program counter 이다.

r4, r5, r6, r7은 각각 특수한 목적으로 사용된다.

명령어 구조 및 명령어 디자인

CPU에게 일을 시키기 위한 명령어 구조 및 명령어 종류를 디자인해야한다.

레지스터와 명령어 상관관계에 주목해야한다.

"레지스터를 디자인 하였으니, 이를 바탕으로 명령어를 디자인 해야한다."

CPU 구성형태(레지스터 구성형태)에 따라서 명령어 구조가 달라진다.

레지스터 크기를 16비트로 결정하였으니 명령어 길이도 16비트로 구성하는 것이 좋다.

CPU에게 일을 시키는 형태

ex)"레지스터 r1에 있는 값과 숫자 7을 더해서 레지스터 r2에 저장하라"

위 명령어를 분석하면 덧셈 대상이 되는 피연산자 r1, 7에 연산결과를 저장하기 위한 피연산자 하나(r2) 그리고 덧셈 연산이 필요하다.

<-----예약-->   <-----연산자-----------> <----저장소--------> <--피연산자1-------------> <-------피연산자2------->

연산에 대한 정보를 나타내는 비트는 세개이다. 즉 우리가 만들 수 있는 연산자의 개수는 여덟개가 된다.

기본적인 덧셈 뺄셈, 곱셈, 나눗셈 의 어셈블리 심볼과 2진코드 정의

      연산자의 의미                 심볼                        2진코드

          덧셈                          ADD                          001

          뺄셈                          SUB                           010

          곱셈                          MUL                          011

          나눗셈                        DIV                           100

각각의 레지스터를 나타내는 코드

r0           000                            r4(ir)                   100

r1           001                            r5(sp)                  101

r2           010                            r6(lr)                   110

r3           011                            r7(pc)                  111

레지스터 코드와 연산자 코드를 넣어 위와같이 명령어가 완성된다.

r1과 7에 해당하는 피연산자가 자리는 저장된 데이터가 숫자인지 레지스터인지 구분할 수 있어야 한다. 이 문제를 해결하기 위해 네개의 비트 중에서 가장 첫번째 비트가 1이면 레지스터정보를 담고 있는것이고, 0이면 숫자 정보를 담은것이라고 정하자.

그럼 아래와 같이 명령어가 완성된다.

지금까지 내용을 종합해보면 심볼 기반 프로그램을 구현한다.

 - 어셈블리 언어 기반의 프로그램

ADD r2, r1, 7

이후 CPU가 인식할 수 있는 2진 명령어 형태로 변환한다.

 - 어셈블러에 의한 바이너리 코드 생성

0000101010010111

위 명령어가 컨트롤 유닛으로 전달되어 의미가 해석되면, CPU의 각 모듈에 명령을 내리고, CPU각 모듈은 이 명령에 따라 적절한 연산을 진행한다.

위 그림 처럼 명령어가 ir(instruction register)에 저장된다. ir은 다음번에 실행하게될 명령어를 미리 가져다 놓는 용도로 사용한다.

컨트롤 유닛은 명령어를 해석하는 일을 맡고 있다. 명령어의 구성과 해석방법을 정확히 알고 있어야만 해석이 가능하다. 명령어의 형태에 따라서 컨트롤 유닛의 논리회로가 디자인 된다.

RISC vs CISC

CISC 구조 CPU

CISC는 "Complex Instruction Set Computer"의 약자로서 복잡한 명령어 체계를 가지는 컴퓨터라는 의미이다.

수백개의 명령어 구성이 가능한 CPU이고, 명령어 종류가 많아 프로그램을 구현하는데 있어서 편리함을 가져다 준다. 수십줄에 걸쳐서 구현해야하는 기능을 단 한줄로 완성할 수 있으며 명령어 길이도 유동적이어서 메모리를 효율적으로 활용할 수 있다.

반면에 명령어 수가 많고, 그 크기가 일정치 않기 때문에 CPU는 복잡해진다.

이러한 복잡한 구조는 성능향상이 어렵다.

RISC 구조 CPU

CISC의 단점을 보완하는 것이 RISC 구조이다. RISC는 CISC 구조 CPU가 전체 명령어 중 사용하는 명령어가 10%정도 밖에 되지않는데서 착안한 구조이다. 명령어 수를 대폭 줄이고, 명령어 길이를 일정하게 디자인해서 RISC 구조를 탄생시킨다.

RISC가 높은 성능을 내는데 유리한 이유는 클럭당 처리할 수 있는 명령어의 개수가 많기 때문이다. RISC는 명령어의 길이가 동일하고 명령어를 처리하는 과정이 일정하기 때문에 클럭당 둘이상의 명령어 처리가 가능하다.(Pipelining 기법에 의해)

strcat을 구현해봤다.

destination 문자열의 '\n'까지 확인하고  '\n'위치부터 source 문자열 데이터를 입력시키는 것이다.

문자열을 1바이트씩 이동시켰다.

위 memcpy는 문자열을 입력받고 복사할 데이터 수를 입력받는다.

입력받은 문자열과 복사할 데이터수만큼 memcpy의 목적 메모리주소에 복사한다.

여기서도 strcpy때와 같이 rep movsb 명령어를 사용했다. ecx에 입력한 데이터 수인 copy_count 값을 넣어주고 rdi에는 복사되야하는 목적 메모리 주소와 rsi에는 복사될 데이터가 있는 메모리 주소를 넣어줬다.

이후 rep movsb 명령어에 의해 한 바이트씩 ecx가 감소하면서 1바이트씩 메모리에 복사하게 된다.

nasm x64 assembly로 strcmp를 구현해 봤다. 

문자열들을 입력받고 1바이트씩 비교하여 strcmp함수를 수행하는 함수이다.

해당 코드는 strcmp(string1,string2)일 경우의 코드이다.

문자가 다를때 string1 에서 string2를 빼주어 strcmp의 결과값이 되도록 했다.(실제 strcmp함수 동작)

sys_read 함수로 문자열을 입력했을 때 마지막에  \n이 들어가기 때문에 \n을 처리해주는 부분을 따로 짜서 0으로 만들어 주는 작업을 했다.