뇌를 자극하는 프로그래밍 원리

by 한세경

561 pages, Paperback

First published September 15, 2007

Reviews

[Jaewoo · Rating 4 out of 5]

Structured programming
카노이맵

2진법에서
1의 보수 = 두 수의 합이 1이되는 관계
2의 보수 = 두 수의 합이 0이되는 관계

branch hazard, control hazard
분기문을 만났을때 Pipelining이 깨지는 현상

data hazard
의존 관계의 연산으로 인해 Pipelining이 어려운 상황

data forwarding
의존 관계 연산이 존재 할 경우 메모리에 writeback하지 않고 다음연산의 operand register로 입력

instruction : 기계어로 숫자로 구성됨
어셈블러 : instruction과 1:1로 매칭되는 기호

Dangling Pointer : 유효하지 않은 주소를 가르키는 포인터

프로그램이 실행되면 필요한 메모리 영역을 아래와 같은 Segment로 나누어 할당한다.
Code Segment : 프로그램 Instruction이 저장되는 공간 ( 프로그램 수행 후 메모리 크기 불변 )
Data Segment : 전역변수가 저장되는 공간 ( 프로그램 수행 후 메모리 크기 불변 )
Stack Segment : 지역변수가 저장되는 공간
heap Segment : 동적 메모리가 저장되는 공간

함수 내에서 함수를 더 부를 수 있기 때문에 함수1내에 필요한 변수영역이 할당되고 함수2가 불리면 필요한 메모리 영역에 함수 1영역 위로 쌓이므로 Stack Segment라고 부른다. 지금 사용되는 Stack의 위치가 Stack Pointer(SP)

Intel CPU에서 ebp레지스터는 Stack Frame의 시작점을 나타내고 esp는 스택의 사이즈를 나타낸다.

Heap영역에 여유 공간이 있는지 확인하는 방법은 double Linked List를 활용한다. 먼저 Heap의 시작포인터를 알고 거기에 처음 할당된 Heap 주소를 알아낸다. 그 주소와 현재 주소와의 공간을 계산해보고 공간이 부족하면 그 주소로 이동한다. 그 주소에는 다음에 Heap으로 할당된 주소가 있고 그것을 확인하여 사이에 여유 공간이 있는 지 확인한다.

new, malloc은 Heap 주소 할당 불가
HeapAlloc은 Heap공간 지정가능
GlobalAlloc/LocalAlloc은 Heap 사용 핸들을 반환받고 사용전 GlobalLock을 실행후 Heap 공간을 사용한다.
GlobalAlloc으로 할당받은 주소는 OS가 파편화를 방지하기 위해 계속해서 이동시킨다. 사용 중 이동을 방지하기 위해 Lock이 필요하다.
VirtualAlloc : 하드디스크 스와핑까지 고려한 메모리 할당

스택 프레임 : 스택 세그먼트 내부를 나누는 단위로 함수가 호출될 때마다 그 함수 호출을 위해 할당받는 메모리 덩어리를 의미
==> 함수의 3가지 특징을 구현하기 위해 스택 프레임이 필요하다.
1. 호출 지점으로 복귀
2. 호출하는 코드(Caller), 호출되는 함수(Callee)간의 데이터 교환 가능
3. 함수 안에서 함수 호출 가능

alt + 5 레지스터 정보 alt+6 메모리 정보 alt+8 assembler 창

특별한 명시가 없으면 __cdecl C의 기본 함수 호출규약을 따르며 이 호출 방식은 인자가 차지하는 스택을 해지하는 책임이 호출한 측에 있다. caller는 함수 return을 받은 후 stack pointer를 방금 종료된 함수 인자 크기 만큼 조정해야 한다. 즉 함수가 불릴때마다 assembler 크기 조절 코드가 들어간다.

__stdcall로 명시할 경우 함수내부에서 인자에 대한 스택해지까지 책임을 가진다. callee가 인자에 대한 stack pointer 조절을 하기 때문에 코드 전체의 길이가 줄어들지만 이 함수는 가변인자를 수신할 수 없다. WINAPI는 #define __stacall을 뜻한다.

__fastcall로 명시할 경우 함수 인자의 위치가 stack frame이 아닌 레지스터가 된다. 최대 인자는 2개이다

eax 레지스터에 return 값이 들어간다. main의 return 1 구문은 어셈블러로 mov eax,1로 해석된다.

OS의 개념
OS는 라이브러리의 집합체이다. OS가 시분할 등 스케쥴링을 능동적으로 수행한다고 생각하지만 실제를 그렇지 않다. 실제 어떤 OS에서 프로그램이 수행되려면 OS API혹은 system call을 사용해야 한다. 이것을 통해 프로그램이 만들어지고 프로그램 자체가 스케쥴링을 하면서 작동된다.

HW IO간의 CPU 유휴를 줄이기 위해 Non-Blocked I/O 혹은 Asynchronous I/O를 수행한다. 이것을 위해서는 HW도 지원해야 한다. HW는 Controller가 있어야 하고 CPU는 Controller에 요청을 하고 다른 작업을 한다. Controller가 요청 업무를 마무리 지으면 CPU에 인터럽트를 보내고 CPU는 HW I/O를 마무리 한다. CPU가 인터럽트를 받았을때 지정된 주소로 점프해야하는데 그 주소를 저장해두는 곳이 인터럽트 벡터 테이블이다.

Overlaped I/O
Non-Blocked I/O로 동작되는 방식입니다. ReadFileEx를 이용하여 I/O가 끝나면 동작되는 콜백을 지정해 둡니다. I/O가 끝나면 콜백함수가 저절로 불리는 것입니다. 이것이 일반적인 Async I/O와 다른것은 콜백을 부르는 주체가 ReadFileEx를 수행한 Thread가 된다는 것입니다. 이렇게 되면 콜백을 수행하기 위한 별도 Thread가 없으므로 Context Switch가 줄어들게 됩니다. 이것이 수행되기 위해서는 ReadFileEx를 수행항 Thread는 하고 싶은 일을 끝내고 Wait상태를 선언해야 합니다. 실제 디바이스와 응용프로그램간 주고 받는 데이터도 같은 메모리를 사용하여 데이터 복사시간을 줄일 수 있습니다.

IOCP(I/O Completion Port)
I/O를 처리하는 Thread Pool을 구성하여 Thread Pool을 이용하여 I/O를 처리하는 방식

적재 시간 주소 바인딩( Load Time Address Binding ) : 프로그램이 메모리에 로드 되는 시점에 함수별 메모리 주소가 정해지는 방식

실행시간 주소 바인딩( Excecution Time Address Binding ) : 해당 Instruction 이 수행 될때 메모리 위치가 정해지는 방식 --> 메모리 파편화를 줄이기 위해 메모리 압축을 수행하고 압축이 수행되면 프로그램의 메모리 위치가 바뀌므로 이것을 보완하기 위한 방식. Fetch 때 마다 메모리 위치를 다시 확인 할 수 없으므로 프로그램 시작의 offset 위치가 Relocation register에 저장되고 CPU가 자동으로 Relocation register를 더하여 Fetch 한다.(instruction으로 구현하면 엄청난 연산 손실)

페이징 : 스와핑과 프로그램 압축의 버든을 줄이기 위해 프로그램을 일정 사이즈로 쪼개서 메모리에 올리는 방식( 프로그램이 시간 공간 지역성이 있기에 가능 ).

페이지 폴트 : 페이지 부분이 메모리에 올라오지 않았는데 CPU가 Fetch하려고 상황을 말하고 이렇게 되면 interrupt가 발생하여 OS를 깨운다. 인터럽트를 받은 OS는 필요한 Page를 메모리에 로드한다.

페이징의 장점
1. 메모리를 분할 하여 사용하는 방식보다 많은 프로세스를 동시에 수행 가능
2. 메모리 단편화 미발생

Page Fault는 물리 메모리에 필요 Page가 없는 경우이고 Segmentation Fault는 잘못된 메모리 참조 이다.

TLB( Translation Lookaside Buffer )
일종의 캐쉬 메모리로 가상 메모리 기법을 사용할 경우 인스트럭션 패치를 위해서 페이지 테이블리 있는 메모리를 access하고 그것을 변환하여 물리 주소를 다시 access해야하는 메모리 엑세스 회수를 줄이기 위한 장치이다.

페이징을 통한 프로세스간 메모리 공유
페이징을 이용하면 프로세스간 메모리 공유가 쉽다.
Explorer는 팝업창등 동일한 업무를 프로세스를 이용하여 관리한다.(Thread일 경우 하나의 창이 죽으면 다 죽음) Explorer는 Code Segment부분이 동일하므로 페이징을 주소를 공유하면 메모리 효율을 높일 수 있다. 이런 경우에 동적 연결 라이브러리(DLL)을 사용한다.

PCB(Process Control Block)
문맥 전환을 위해서 레지스터값, 핸들 프로세스 이름등을 메모리에 저장해야 하는데 그 때사용하는 구조체
TCB(Thread Control Block)
Windows에서는 Thread 기반 구조체를 사용한다.

RTOS의 조건
1. 선점형 방식 (Kernel 함수도 선점 가능)
2. 우선순위 스케줄링
3. 인터럽트 지연, 즉 인터럽트가 걸리지 못하는 시간이 일정 해야함.

1. 선점형 방식은 Kernel 함수가 불리더라도 선점이 가능해야함. 이럴 경우 예외처리가 복잡해지므로 Linux와 Windows는 Kernel은 비선점형임. RTLinux는 선점OS커널이 linux Kernel을 Process 형태로 관리하는 구조임
2. 우선순위 스케줄링시 어떻게 해야 Performace향상에 도움이 되는지까지 고려
3. 보통 인터럽트가 발생하면 끝날때까지 다른 인터럽트는 무시된다. 하지만 RTOS는 인터럽트가 일정 지연시간내에 꼭 반응해야하므로 CPU가 인터럽트를 받으면 바로 인터럽트를 종료하고 RTOS에게 할 일을 알려준다. 그러면 RTOS는 인터럽트으로 해야하던 일들을 스케쥴링하여 수행시켜준다.