대학원부터 시작한 첫번째 블로그

디버깅 작업 또는 프로그램의 안전성을 검사할 때 디버거를 잘 쓰면 꽤 많은 시간을 절약할 수 있습니다. 대부분 개발자들이 GDB를 써서 디버깅을 하고 있지만, GDB가 가지고 있는 강력한 기능들을 거의 쓰지 못하고 있기 때문에, 이 글에서는 자주 쓰이지는 않을 지언정, 알면 매우 도움이 되는 기능들을 위주로 살펴보겠습니다.

먼저, 이 글을 읽는 분들이 GDB의 기본적인 사용 방법 (특히 break, run, continue, file, backtrace, print 등)을 알고 있다고 가정하겠습니다. 기본적인 사용 방법을 모르신다면 Emacs/GDB/etags/cscope나 기타 GDB manual을 참고하기 바랍니다.

Breakpoints

break 명령은 대개 다음과 같이 쓸 수 있다는 것은 이미 알고 계실 것입니다:

(gdb) break                # 현재 줄에 breakpoint 설정

(gdb) break 31             # 현재 파일 31번째 줄에 breakpoint 설정

(gdb) break foo            # 함수 foo에 breakpoint 설정

(gdb) break list::next     # list 클래스 next 멤버 함수에 설정

(gdb) break hello.c:main   # hello.c 파일의 main 함수에 설정

(gdb) break util.c:300     # util.c 파일의 300번째 줄에 설정

특히 C++의 경우, 한 클래스의 모든 멤버 함수에 breakpoint를 설정하고 검사할 필요가 있는데, 이 경우, 정규 표현식(regular expression)으로 breakpoint를 설정하는 rbreak 명령을 쓰면 편리합니다. 예를 들어 보면:

(gdb) rbreak f*o           # "f*o"를 만족하는 심볼 전체에 대해 설정

(gdb) rbreak list::        # "list::.*"를 만족하는 심볼 전체에 대해 설정

특히 위 두번째 예제를 보시면 ".*"이 항상 default로 따라 온다는 것을 알 수 있습니다. 사실 rbreak 명령에 "foo"를 준 경우 사용되는 정규 표현식은, 정확히 말하면 ".*foo.*"가 됩니다. 따라서 "foo"로 시작하는 함수 전체에 대해 breakpoint를 설정하고 싶다면, 다음처럼 쓰면 됩니다:

(gdb) rbreak ^foo

breakpoint를 설정하면, 해당 breakpoint마다 번호(BNUM)가 주어지고, 이 번호를 써서 다양한 작업을 수행할 수 있습니다. 예를 들어, 전체 breakpoint 목록을 보고 싶다면:

(gdb) info b

Num Type           Disp Enb Address    What

1   breakpoint     keep y   0x08066b44 in eventShow() at menubar.cpp:1017

        breakpoint already hit 3 time

2   breakpoint     keep y   0x080b06f4 in Play() at thumbview.cpp:416

3   breakpoint     keep y   0x08066e7e in ActPlay() at menubar.cpp:1085

4   breakpoint     keep y   0x08059cd3 in Play_SS(int, int) at widgets.cpp:2183

(gdb)

첫번째 컬럼(Num)은 각 breakpoint에 대한 고유번호(BNUM)를 나타냅니다. 그리고 두번째 컬럼(Type)은 breakpoint인지 watchpoint인지 catchpoint인지를 나타냅니다. (watchpoint와 catchpoint는 다음에 설명..) 그리고 세번째 컬럼(Disp)은 이 breakpoint의 특징을 나타냅니다. (다음에 설명). 네번째 컬럼(Enb)는 현재 이 breakpoint가 활성화되어 있는지를 나타냅니다. 비활성화(n)로 표시된 breakpoint는 동작하지 않습니다. 활성화/비활성화는 'enable br [BNUM]' 또는 'disable br [BNUM]'으로 변경할 수 있습니다. 예를 들어 1번 breakpoint를 비활성화하고 싶다면:

(gdb) disable br 1

전체 breakpoint를 활성화하고 싶다면:

(gdb) enable br

2번, 4번 breakpoint를 비활성화하고 싶다면:

(gdb) disable br 2 4

2번부터 5번까지 breakpoint를 활성화 하고 싶다면:

(gdb) enable br 2-5

등으로 할 수 있습니다.

때때로, 딱 한 번만 쓸 breakpoint가 필요한 경우가 있습니다. 이 경우 쓸 수 있는 명령은 enable br once [BNUM] 또는 enable br delete [BNUM]을 쓸 수 있습니다. 예를 들어 아래 명령은 1번, 3번 breakpoint를 활성화하고, 사용된 경우 바로 비활성화시킵니다:

(gdb) enable br once 1 3

아래 명령은 4번 breakpoint를 활성화하고, 사용된 경우, 이 breakpoint를 삭제합니다:

(gdb) enable br delete 4

쓸모있는 기능 중 하나가 바로 breakpoint에 조건을 지정하고, 해당 조건을 만족할 경우에 멈추도록 하는 것입니다. 예를 들어 다음과 같은 코드가 있다고 가정해 봅시다:

int i = 0;


/* do something #1 */


for (i = 0; i < 1000; i++) {

  /* do something #2 */

  /* do something #3 */

}

이상하게도 i가 456일때 반복문 안에서 프로그램이 이상하게 동작한다고 가정해 봅시다. 이 때 "do something #2" 부분에 breakpoint를 걸었다면 (이 breakpoint의 번호는 8번이라고 가정합시다), 반복할 때마다 계속 프로그램 실행이 멈출 겁니다. 정확히 1000번 멈추겠죠. 456번까지 진행한다는 것은 매우 귀찮은 일입니다. 이 경우, 다음과 같이 조건을 지정할 수 있습니다:

(gdb) cond 8 i == 456

즉, 8번 breakpoint는 i == 456을 만족할 때에만 멈추도록 지정합니다. 조건식에는 단순한 상수 비교 이외에, 복잡한 함수 호출도 가능합니다. 예를 들면 다음과 같습니다:

(gdb) cond 8 foo(i) > bar(rand())

앞에서 예로 든 코드는 단순 반복문이기 때문에, 처음 456 - 1번에 발생하는 breakpoint는 무시하라고 지정할 수도 있습니다. 처음 N번 발생하는 breakpoint를 무시하라는 명령은 다음과 같습니다:

(gdb) ignore 8 455

즉, 8번 breakpoint는 455번 동안 무시됩니다.

또, 다음과 같은 코드를 가정해 봅시다:

int i = 0;

int j, k;

long l;


while (1) {

  j = rand();

  k = some_funtion(j, time());


  /* do something #1 */

  l = j & 0xFF00 + (int)(log(k) * 3.2108) - ...;


  if (some_condition)

    break;

}

위 코드는 j와 k가 실행할 때마다 값이 변합니다. 그리고 이상하게도 j < k 일때 변수 l이 이상한 결과를 가지는 것 같지만, 확실하지는 않습니다. 우리가 확신할 수 있는 것은 j < k일 경우, l은 항상 양수이어야 한다는 것입니다. 그래서 l의 값이 전체 반복을 끝낼 동안 어떤 값을 가지고 있는지 검사해보고 싶습니다. 이 경우 해당 breakpoint에서 멈출 때, 특정 명령을 수행하도록 하는 GDB 명령인 commands를 쓰면 됩니다.

일단 "l = j & 0xFF00..." 부분에 breakpoint를 걸고 (9번 breakpoint라고 가정), 다음 명령을 내립니다:

(gdb) commands 9

Type commands for when breakpoint 9 is hit, one per line.

End with a line saying just "end".

>silent

>if j < k

 >printf "l is %d\n", l

 >end

>cont

>end

대충 눈치가 빠른 분은 아시겠지만 'commands [BNUM] ... end'는, BNUM breakpoint에서 멈췄을 때, "..."에 지정한 GDB 명령들을 수행합니다. 일단 silent 명령으로 명령 자체가 출력되지 않도록 한 다음, GDB printf 명령으로 변수 l 값을 출력합니다. 그리고 continue 명령으로 계속 프로그램을 진행하도록 합니다. 그 결과, 프로그램을 실행할 경우, breakpoint에서 멈추고 l 값을 출력한 다음 프로그램을 자동으로 진행합니다. 이 과정은 반복문이 끝날 때까지 계속되기 때문에, 다음과 같은 비슷한 출력을 얻을 수 있습니다.

(gdb) continue

l is 3

l is -2

l is 2

l is 1

l is -3

앞에서 j < k일 때, l은 항상 양수여야 한다고 말했습니다. 위 결과를 보고 우리는 l 값이 때때로 잘못된다는 것을 쉽게 알 수 있습니다.

commands에 쓸 수 있는 GDB 명령어 형태는 다음 기회에...

가끔 next나 step으로 실행 과정을 따라 가다가 반복문을 만날 경우, 반복문 끝난 부분으로 바로 건너뛰거나, 현재 함수의 실행을 정상적으로 끝내고 상위 함수로 돌아가야할 경우가 있습니다. 예를 들어:

for (i = 0; i < 1000; i++) {

  /* do something #1 */

  /* do something #2 */

}

/* do something #3 */

현재 "/* do something #2 */" 부분까지 실행했고, 이 반복문에 이상이 없다고 판단되면, 반복문 다음까지 빠르게 진행하고 싶을 겁니다. 이 경우, until 명령이나 advance 명령을 쓰면 편리합니다.

until 명령을 쓰면, 반복문이 아닌 경우에는 next 명령과 똑같이 동작합니다.

(gdb) until

반복문일 경우, 현재 스택 프레임 (즉, 현재 함수) 안에서, 현재 줄 다음 줄에 올 때까지 프로그램을 실행합니다. 쉬운 말로, 루프를 진행하고 빠져 나오는 순간까지 실행한 다음 "(gdb)" 프롬프트를 보여줍니다.

advance 명령은 continue 명령과 마찬가지로 프로그램을 주욱 실행시키는 대신, 지정한 곳에 코드 흐름이 오면 바로 멈춥니다. 예를 들어 위 코드의 "/* do something #3 */" 부분의 줄 번호가 34였다면, until 명령 대신 다음과 같이 실행할 수도 있습니다:

(gdb) advance 34

advance 명령은 스택 프레임에 대한 제한이 없기 때문에, 현재 함수가 아닌, 아무 곳이나 설정할 수 있으며, 위치 지정은 줄 번호 뿐만 아니라, break 명령에 쓰는 모든 형식을 다 지원합니다.

네트워크로 서비스 요청 데이터를 전송받아 분석하고, 적절한 기능을 수행하고, 그 결과를 돌려주는 서버 프로그램을 생각해 봅시다. 그리고 다음과 같은 꼴로 되어 있다고 가정해 봅시다:

#define PACKET_MAX      10


int

fetch(void)

{

  int packet_received = 0;

  int received[PACKET_MAX];


  while (1) {

    if (!packet_received) {

      if (recv_data(received, PACKET_MAX) == 0)

        packet_received = 1;

    }


    /* do work here */


    process_packet(received, PACKET_MAX);

  }

  return 0;

}

이 프로그램은 평소에는 정상적으로 잘 동작하지만, 특정 패킷을 받으면 이상하게 동작한다고 가정합시다. 그리고 이 패킷은 아주 가끔 들어온다고 가정해 봅시다. 원하는 대로 패킷을 보내주는 프로그램을 따로 작성해 두지 않았다면, 이 프로그램을 디버깅하기 위해서, 문제를 일으키는 패킷이 올 때까지 하염없이 기다려야할 지도 모릅니다. 실제 코드는 다음과 같습니다:

만약 원하는 패킷이 recv_data()를 통해 들어왔다고 가정합시다. 이 때 packet_received는 1이 되고, 그에 따라 처리 작업이 이상하게 동작할 것입니다. 이 때, received의 내용을 저장하기 위해, 다음 명령을 쓸 수 있습니다:

(gdb) dump binary value buggy.dat received

위 명령을 수행하면 배열 received의 내용을 파일 buggy.dat에 저장합니다. 만약 시작 주소와 끝 주소를 알고 있다면 다음 명령을 쓸 수 있습니다:

dump binary data buggy.dat START-ADDR END-ADDR

이 때, START-ADDR는 시작 주소를, END-ADDR는 끝 주소를 나타냅니다. 즉, 앞 received 배열의 경우, 다음과 같이 쓸 수 있습니다.

(gdb) dump binary memory buggy.dat received received+10

어느 방법을 썼든지, 현재 디렉토리에는 buggy.dat이라는 파일로, 배열 received의 내용이 저장될 것입니다. 이는 메모리 내용을 그대로 dump시킨 것이므로 od(1)와 같은 툴을 써서 그 내용을 직접 볼 수 있습니다. received 배열은 int 배열이므로 다음과 같이 확인 가능합니다:

$ od -td buggy.dat 

0000000         163         151         162          85

0000020          83         190         241         252

0000040         249         121

0000050

$ _

만약, 바로 디버깅을 성공적으로 끝냈다면, 사실 위와 같은 기능은 큰 역할을 발휘하지 못합니다. 하지만, 계속해서 디버거를 실행해서 여러번 디버깅을 해야 한다면 꽤 쓸모있다는 것을 알 수 있습니다.

일단, 새로 GDB를 띄워 디버깅을 시작했다고 합시다.

    if (!packet_received) {

위 코드를 실행할 때, 강제로 packet_received를 1로 만들어, 패킷을 받는 부분을 건너뜁니다. 변수의 값 변경은 print 명령으로 쉽게 할 수 있습니다:

(gdb) p packet_received = 1

그리고 나서, received 배열을 아까 저장해 두었던 buggy.dat에서 다음과 같이
불러올 수 있습니다:

(gdb) restore buggy.dat binary received

Restoring binary file buggy.dat into memory (0xbfeda890 to 0xbfeda8b8)

이 외에도, GDB는 타 디버거에 비해 강력한 기능들을 많이 제공합니다. 다음 기회에 좀 더 알아보겠습니다.

core dump file이 발생하였을 경우 이것을 가지고 디버깅 하는 방법을 소개하고자 한다.

간단한 소스 코드를 보자.

#include <stdio.h>

int main(int argc, char* argv[]) {
char buffer[16];

buffer[80000] = 3;

return;
}

gcc -g -o main main.c

ps: -g 옵션은 디버그 정보를 넣어서 컴파일을 해 주는데, 이게 없으면 core 파일을 분석 할 수 없다.

frank@tightrope:~/tmp/gdbtest$ ./main
Segmentation fault

core dump file이 생성되지 않을 경우는 막아 놓았기 때문인데, ulimit 를 사용해서
이것을 풀어줄 수 있다.

ulimit -c 1024 (core file 용량을 정해준다.)

frank@tightrope:~/tmp/gdbtest$ ./main
Segmentation fault (core dumped)

frank@tightrope:~/tmp/gdbtest$ ls -als core
72 -rw------- 1 frank frank 147456 2006-01-13 21:19 core

분석을 해 보도록 하겠다.

frank@tightrope:~/tmp/gdbtest$ gdb ./main ./core
GNU gdb 6.3-debian
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "i486-linux-gnu"...
Using host libthread_db library "/lib/tls/i686/cmov/libthread_db.so.1".

Core was generated by `./main'.
Program terminated with signal 11, Segmentation fault.

warning: current_sos: Can't read pathname for load map: Input/output error

Reading symbols from /lib/tls/i686/cmov/libc.so.6...done.
Loaded symbols for /lib/tls/i686/cmov/libc.so.6
Reading symbols from /lib/ld-linux.so.2...done.
Loaded symbols for /lib/ld-linux.so.2
#0 main (argc=1, argv=0xbfca9944) at main.c:6
6 buffer[80000] = 3;
(gdb)

이걸 보고 우리는 main 함수에서 Segmentation fault로 종료되었다는 것을 알 수 있다.
함수 이름과 매개변수 값, 몇 번째 줄에서 segmentation fault가 났는지 보여준다.

이제는 조금 더 복잡한 소스를 디버깅해 보도록 해 보자.

#include <stdio.h>

int main(int argc, char* argv[]) {

// notice the erroneous "=", the coder meant "=="
if(argv = 0) return;

printString(argv);

return;
}

컴파일 하고 실행해 보자.

frank@tightrope:~/tmp/gdbtest$ gcc -g -o main main.c

frank@tightrope:~/tmp/gdbtest$ ./main
Segmentation fault (core dumped)

frank@tightrope:~/tmp/gdbtest$ ls -als core
68 -rw------- 1 frank frank 147456 2006-01-13 21:53 core

이제 디버깅을 해 보도록 하자.

frank@tightrope:~/tmp/gdbtest$ gdb ./main ./core
GNU gdb 6.3-debian
Copyright 2004 Free Software Foundation, Inc.

...

#0 0x08048396 in printString (string=0x0) at main.c:14
14 sprintf(string, "This is a test.\n");

#0 줄을 보면 string 이 널 포인터라는게 분명하다. 그런데 우리는 이게 어디서 왔는지
모른다. 단서는 파일 main.c에 14번 째 줄이라는 것과 main 에서 에러가 발생하지
않았다는 것이다. 그래서 우리는 backtrace를 할 것이다.

(gdb) backtrace
#0 0x08048396 in printString (string=0x0) at main.c:14
#1 0x0804837c in main (argc=1, argv=0x0) at main.c:8

'backtrace' 명령어는 함수를 연대기순으로 나열해 준다. 맨 위에 줄이 segmentation fault
가 발생한 소스이다. 저걸 보면 main.c:8 에서 main.c:14를 호출한 것을 알 수 있다.
더 많은 정보를 얻기 위해 'frame' 명령을 사용하도록 하자. 'frame' 명령은 'backtrace'
명령 실행으로 나온 항목들에 대해 더 많은 정보를 보여준다.

(gdb) frame 0
#0 0x08048396 in printString (string=0x0) at main.c:14
14 sprintf(string, "This is a test.\n");
(gdb) frame 1
#1 0x0804837c in main (argc=1, argv=0x0) at main.c:8
8 printString(argv);

이것을 보면 이미 main.c:8 에서 argv가 0으로 값이 넘어간 것을 알 수 있다.

*잡다한 tip
스레드를 사용해서 프로그래밍을 할 때 threadsafe 함수를 사용해야 한다. 예를 들어서 localtime
함수는 언젠가 프로그램과 충동할 것이다. 그 대신에 localtime_r 함수를 쓰는게 좋다. localtime_r
함수는 threadsafe 함수이다.

유선과 무선 환경의 차이

• 노드 사이의 명시적인 링크가 존재하지 않음
  • 라디오의 전송 범위 내에 노드들이 위치하면 통신 가능
• 무선상에서는 MAC 기술이 아주 중요
  • NS2 유선 시뮬레이션 환경은 MAX이 존재하지 않음
• 무선상에서 노드는 이동성이 존재
• 라우팅
  • 유선상에서는 특별히 라우팅을 설정하지 않아도 링크 설정관계를 통해서 최단 경로가 선택
  • 무선에는 반드시 라우팅이 존재해야 함
• 주소
  • 유선에서는 flat address
  • 무선만 존재하면 flat address
  • 유무선 연동인 경우는 hierarchical address

NS2에서의 유선과 무선의 차이

• C++ 상에서의
  • 유선 : class Node
  • 무선 : class MobileNode
• 노드 생성은 유무선 모두 $ns node로 하지만 무선에서는 node-config라는 추가 작업이 필요
• Trace
  • $ns/common 에서
    • 유선 : trace.{h, cc}
    • 무선 : cmu-trace.{h, cc}
• 이동성
  • 무선에서는 이동성을 지원
  • 위치 정보가 중요
    • 유선에서는 연결 구조가 중요, 노드의 배치는 중요하지 않음
    • 무선에서는 위치에 따라서 전송 범위 내에 있는지 여부가 결정
• 그 외에는 유무선 모두 같은 네트워크 컴포넌트를 사용

node-config

• -adhocRouting : 라우팅 프로토콜 설정
  • DSDV, AODV, TORA,, FLOODING,...
• -llType : 링크 레이어 설정
  • LL
• -macType : 맥프로토콜 설정
  • Mac/802_11, Mac/SMAC
• -propType : 경로손실타입
  • Propagation/twoRayGround, Propagation/FreeSpace, Propagation/Shadowing,...
• -ifqType : 큐타입
  • Queue/DropTail/PriQueue,...
  • 애드혹라우팅 프로토콜이 DSR인 경우 반드시 CMUPriQueue로 해야 함
• -ifqLen : 큐길이
  • 패킷 개수
• -phyType : 피지컬레이어타입
  • Phy/WirelessPhy,...
• -antType : 안테나 타입
  • Antenna/OmniAntenna
• -channel : 현재는 없어짐
  • Channel/WirelssChannel
• -topoInstance : 전체 영역
  • $topo
• -agentTrace : 트레이스 설정
  • ON or OFF
• -routerTrace : 트레이스 설정
  • ON or OFF
• -macTrace : 트레이스 설정
  • ON or OFF
• -movementTrace : 트레이스 설정
  • ON or OFF

NS2 무선환경 시뮬레이션 스크립터

 Max/802_11 Bandwidth

• basic rate, data rate 두가지 존재
  • basic reate : RTS, CTS, ACK 을 전송하는 속도
  • data rate : 실제 데이터를 전송하는 속도
• 설정하는 방법
  • Mac/802_11 set basicRate_ 1Mb
  • Mac/802_11 set dataRate_ 1Mb
  • 기본값은 둘다 1Mbps

범위 설정

• 전송 범위 : 데이터가 성공적으로 수신되는 범위
• 캐리어 감지 범위 : 데이터를 성공적으로 수신하지는 못하지만 신호만 감지하는 범위 -> CSMA/CA 프로토콜의 CA
• 전송 범위와 캐리어 감지 범위는 수신 노드에서 받는 전파세기와 쓰레쉬홀드에 의해서 결정
• $ns/tcl/lib/ns-default.tcl

• 다른 설정은 변경하지 않고 위 두개의 threshold만 변화시켜 범위 조절 가능
• $ns/indep-utils/propagation/threshold.cc
  • 컴파일 후 threshold -m <경로손실모델> <범위> ->threshold

Teodor Zlatanov
프로그래머, Gold Software Systems
2002년 1월

보다 나은 펄(Perl) 프로그래밍을 위한 완벽한 가이드를 제공하고 있다. 이번에는 객체 지향 프로그래밍(OOP, Object Oriented Programming)에 대해 설명한다. 객체 지향 프로그래밍이 무엇이고, 언제 쓰이며, 펄에서는 어떻게 작용하는지를 설명할 것이다.

객체 지향 프로그래밍(Object Oriented Programming, OOP)
OOP는 프로그래밍 방식 또는 문제를 해결에 쓰이는 일반적인 접근방식이다. 절차적 프로그래밍과 함수 프로그래밍 방식과는 연관성이 적고, 그들과 잘 맞지 않는다.

이 글에서는 펄에서 OOP와 함수적/절차적 프로그래밍의 기초를 다루겠다. 그리고 펄 프로그램과 모듈에서 OOP를 사용하는 방법을 설명하겠다. 이 글은 요약에 그칠것이라는 것을 명심하라. 펄 OOP의 모든 부분을 설명하는 것은 무리이다. 그와 같은 것을 다루는 책이 많이 나와있으며 이미 여러차례 다루어졌다.(참고자료).

OOP가 정확히 무엇인가?
OOP는 객체를 사용하여 문제를 해결하는 기술이다. 프로그래밍 용어에서 객체(object)란 속성(property)과 동작(behavior)이 문제 해결에 주요하게 작용하는 엔터티(entity)이다. 정의를 좀 더 자세하게 내려야 하겠지만, 오늘날의 컴퓨터 산업에서 OOP 접근방식의 엄청난 다양성 때문에 불가능하다.

펄 프로그래밍에서, OOP는 필수적인 것은 아니다. Perl version 5 이상 버전은 OOP를 장려하지만 필요한 것은 아니다. 모든 펄 라이브러리는 모듈이다. 적어도 OOP의 기초를 사용한다는 것을 의미한다. 게다가 대부분의 펄 라이브러리는 객체로서 구현된다. 모듈을 사용하는 사람은 특정 작동과 속성을 지닌 OOP 엔터티로서 그들을 사용해야 한다.

기본적인 OO 프로그래밍 언어 특징
일반적으로, OO 프로그래밍 언어에 있어서 기본적인 세 가지의 특징이 있다. 상속(inheritance), 다형성(polymorphism), 캡슐화(encapsulation)가 바로 그것이다.

펄은 상속을 지원한다. 상속(Inheritance)은 하나의 객체(child)가 시작 포인트(parent)로서 다른 것을 사용하고 그런다음 필요할 경우에 속성과 동작을 변경할 때 적용된다. 이러한 자식-부모 관계는 OOP에 있어서 필수적이다. 재사용(reuse)은 OOP의 이점 중 하나이며 프로그래머들도 이러한 특징에 만족한다.

상속에는 두 가지 유형이 있다. 단일 상속(Single inheritance)은 자식이 단 하나의 부모를 가져야 한다. 반면 다중 상속(multiple inheritance) 은 좀 더 자유롭다. 실제로 둘 이상의 부모를 보게 될 경우는 드물지만 펄은 다중 상속을 지원한다.

다형성(Polymorphism)은 한 객체를 다른 것처럼 보이도록 만드는 기술이다. 펄에서, 다형성은 완벽히 지원된다. 펄 프로그래머들은 상속된 동작을 변경하는 것보다는 객체 속성을 가진 일반적인 작동을 변경하는 것을 더욱 선호하기 때문에 빈번하게 사용되는 것은 아니다. 234 포트의 UDP 패킷 리셉션과 트랜스미션에, 80 포트의 TCP 패킷 리셉션에, 1024 포트의 TCP 패킷 트랜스미션을 위해 세 개의 IO::Socket::INET 객체를 만드는 코드를 기대한다는 것을 의미한다. 첫 번째 경우에는 IO::Socket::INET::UDPTransceiver 를, 두 번째의 경우 IO::Socket::INET::TCPReceiver를, 세 번째의 경우 IO::Socket::TCPTransmitter를 사용하는 코드를 기대하기 보다는 말이다.

OOP 순수주의자들은 모든것이 적절하게 구별되어 한다고 느끼지만, 펄 프로그래머들은 순수주의자가 결코 아니다. 그들은 OOP 규칙에 대해 융통성을 발휘하고 있다.

캡슐화(Encapsulation)는 객체 작성자가 액세스를 허용하기를 원치 않는다면 사용자에게 액세스를 불가능하게 하는 방식으로 객체 작동과 속성을 인클로징한다는 것을 의미한다. 그러한 방식으로 객체 사용자들은 하지 못하도록 정해진 일을 수행할 수 없으며, 액세스 할 수 없도록 지정된 것에 액세스 할 수 없다(Listing 1).

왜 OOP가 강력한 방식인가?
어떻게 OOP가 강력한 방식이 될 수 있었는지 생각해보자. OOP에는 절차적/함수 프로그래밍 (PP/FP)에 적용하기에 까다로운 여러 주요 개념들이 있다는 것을 알았다. 우선, 무엇보다도, PP나 FP 모두 상속이나 클래스 다형성 개념이 없다. PP와 FP에는 클래스가 없기 때문이다. PP와 FP에서 캡슐화는 존재한다. 하지만 단지 절차적 레벨에서 존재하는 것 뿐이다. 결코 클래스나 객체 속성으로서 존재하는 것은 아니다. 따라서 프로그래머는 호환되지 않는 방식들을 섞는 것보다 전체 프로젝트에 OOP를 고수하는 것이 낫다.

OOP는 절차적 프로그래밍 방식과 함께 잘 작동하지 않는다. 왜냐하면 OOP는 객체에 집중하고 절차 프로그래밍은 프로시져(procedure)에 기반하기 때문이다. 마치 메소드(method)와 같은 프로시져는 사용자에 의해 호출되는 함수이지만 그 둘 사이에는 차이점이 없다.

프로시져는 객체 데이터를 가지고 있지 않다. 그들은 매개변수 리스트에 있는 데이터로 전달되거나 범위내에서 데이터를 사용해야 한다. 프로시져는 호출 시 이것으로 전달된 모든 데이터나 글로벌 데이터에 액세스 할 수 있다. 메소드는 오직 그들의 객체 데이터에만 액세스 해야한다. 실제로, 메소드용 함수 범위는 메소드를 포함하고 있는 객체이다.

프로시져는 글로벌 데이터를 사용하여 찾는다. 단, 절대적으로 필요할 때만 수행되어야 한다. 글로벌 데이터를 사용하는 메소드는 가능하면 빨리 다시 작성되어야 한다. 프로시져는 다른 매개변수들을 가진 다른 프로시져들을 호출한다. 메소드는 단지 몇 개의 매개변수만을 가지고 있어야 하며 다른 프로시져들 보다 자주 다른 메소드들을 호출한다.

함수 프로그래밍(FP)은 여러가지 이유로 OOP와 잘 섞이지 않는다. 가장 중요한 이유는 FP는 문제를 해결하는 데 있어서 세부적인 함수 접근방식에 기반을 두고 있고, OOP는 개념을 표시하기 위해 객체를 사용한다. FP 프로시져들은 어느 곳에서나 사용될 수 있지만, OOP 메소드는 그것을 보유하고 있는 객체내에서만 사용될 수 있다.

이제는 펄이 OOP, FP, PP 방식들을 섞는 최상의 언어인지를 설명할 수 있다.

펄에서 OOP를 절차적/함수 프로그래밍과 섞는 방법
펄은 프로그래머가 원하는 무엇이든 할 수 있도록 하기위해 길이를 한없이 늘일 수 있다. 이는 Java와 C++ 같은 언어들과는 극명하게 대조된다. 예를 들어, 펄에서 프로그래머는 이전에 선언되지 않는 변수를 자동으로 만들수 있다.

따라서 펄은 여러 방법들을 남용하기에 적합한 언어이다. 내부 객체 데이터에 액세스하고, 클래스를 변경하고, 메소드를 재 정의하는 것이 모두 가능하다. 펄의 규칙은 프로그래머들이 코딩, 디버깅, 실행 효율성에 맞게 규칙을 파괴할 수 있다. 작업을 수행하는데 도움이 된다면 괜찮다. 따라서, 펄 그 자체는 프로그래머에게 베스트 프랜드가 될 수도 최악의 적이 될 수도 있다.

규칙을 위반하는 것임에도 왜 사람들은 OOP, FP, PP를 섞기를 원하는가? 다시 근본적인 문제로 되돌아가 보자. OOP, FP, PP는 무엇인가? OOP, FP, PP는 툴이고 모든 프로그래머들이 하는 첫 번째 작업은 그들의 툴을 이해하는 것이다. 만일 프로그래머가 해시를 소팅할 때 FP Schwartzian 변형을 사용하지는 못하는데 Sort::Hashtable을 작성할 수 있거나 또는 Sys::Hostname 모듈의 재사용을 실패했지만 대신 시스템의 호스트네임을 얻기 위해 절차 코드를 작성한다면, 그 프로그래머는 시간, 노력, 돈을 낭비한 것이 되고, 코드 품질과 신뢰성도 깎인다.

프로그래밍 팀은 최상이라고 믿고 있는 툴에 만족할 수 있다. 이것은 그들에게 일어날 수 있는 최악의 일이다. 프로그래머는 효율성을 증대시키고, 더 나은 코드를 만들 수 있으며, 팀을 더욱 혁신적으로 만들수 있는 방법이 무엇이든지 그 방법을 섞을 수 있어야 한다. 펄은 이러한 태도를 인정하고 장려한다.

OOP의 효용성
OOP의 효용성을 이 글에서 설명하기에는 너무나 많다. 또한 앞서 언급했듯이 이 주제를 다루는 책들이 많이 있다.

OOP는 기본적인 클래스와 객체에 의존하기 때문에 OO 코드를 재사용한다는 것은 필요할 때 클래스를 임포팅한다는 것을 의미한다. 코드 재사용은 OOP를 사용하기 위한 가장 중요한 이유이고, OOP가 오늘날의 산업에서 중요성과 대중성을 얻을 수 있는 이유이다.

단점도 있다. 예를 들어, 이전 문제에 대한 솔루션이 현재 상황에도 이상적으로 적용되지 않을 수도 있고 형편없이 문서화 된 라이브러리는 이해하고 사용하기가 힘들어 오히려 다시쓰는 편이 더 나을 때도 있다. 시스템 아키텍트의 임무는 이러한 단점을 보완하는 것이다.

코드 품질은 OOP를 이용하여 향상된다. 캡슐화는 데이터 오염문제를 없애기 때문이다. 상속과 다형성은 새로 작성되어야 하는 코드의 복잡성을 줄인다. 코드 품질과 프로그래밍 혁신 사이에는 미묘한 균형이 있고 각 팀은 팀의 목적에 맞게 이것을 활용해야 한다.

OOP의 상속과 재사용은 코드의 일관성있는 인터페이스를 가능하게 한다. 모든 OO 코드가 일관성있는 인터페이스를 갖추어야 한다는 의미는 아니다. 프로그래머는 일반적인 아키텍쳐를 고수해야 한다. 예를들어, 확장이 가능하고 사용하기 매우 편리한 모듈식의 인터페이스를 통해 에러 기록을 위한 포맷과 인터페이스에 팀은 합의를 해야한다. 그때야 비로소 모든 프로그래머는 에러가 많은프린트 문장 대신 인터페이스를 사용한다.

적응성(adaptability)은 프로그래밍을 할 때 다소 막연한 개념이다. 개인적으로는 이것을 환경과 사용 변화의 수락과 예견으로 정의하고 싶다. 모든 소프트웨어는 진화하기 때문에 적응성은 중요하다. 잘 작성된 소프트웨어는 발전해야 한다. OOP는 모듈식의 디자인, 향상된 코드 품질, 일관성있는 인터페이스를 이용하여 새로운 오퍼레이팅 시스템이나 새로운 리포트 포맷이 핵심 아키텍쳐에 급진적 변화를 주어야하는 필요성을 감소시킨다.

펄에서 OOP 사용하기
믿거나 말거나 지만 :) 펄에서 OOP는 초급 이나 중급 레벨이 어렵지가 않다. 고급 레벨의 사용도 복잡하지 않다. 펄은 프로그래머들에게 몇 가지 제한을 둔다.

첫 번째 단계는 펄 패키지를 이해하는 것이다. 패키지는 C++ 과 Java 라이브러리에 있는 네임스페이스(namespace) 같은 것이다. 펄 패키지는 프로그래머에게 자문역할을 한다. 기본적으로 펄은 패키지들 간에 데이터 교환을 제한하지 않는다.

#!/usr/bin/perl

# note: the following code will generate warnings with the -w switch, 

# and won't even compile with "use strict".  It is meant to demonstrate

# package and lexical variables.  You should always "use strict".

# pay attention to every line!

# this is a global package variable; you shouldn't have any with "use strict"

# it is implicitly in the package called "main" 

$global_sound = "

";

package Cow;                              # the Cow package starts here

# this is a package variable, accessible from any other package as $Cow::sound

$sound = "moo";

# this is a lexical variable, accessible anywhere in this file

my $extra_sound = "stampede";

package Pig;                              # the Pig package starts, Cow ends

# this is a package variable, accessible from any other package as $Pig::sound

$Pig::sound = "oink";                     

$::global_sound = "pigs do it better";    # another "main" package variable

# we're back to the default (main) package

package main;

print "Cows go: ", $Cow::sound;           # prints "moo"

print "\nPigs go: ", $Pig::sound;         # prints "oink"

print "\nExtra sound: ", $extra_sound;    # prints "stampede"

print "\nWhat's this I hear: ", $sound;   # $main::sound is undefined!

print "\nEveryone says: ", $global_sound; # prints "pigs do it better"

파일 범위의 어휘 변수인 $extra_sound 는 세 패키지 ("main", "Pig", "Cow")액세스 할 수 있다. 이 예제에서 같은 파일 안에서 모두 정의되었기 때문이다. 일반적으로 각 패키지는 각자의 파일 안에서 정의되고 어휘 변수들은 패키지에 속하게 된다. 따라서 캡슐화가 가능하다. ( "perldoc perlmod"를 실행해보라.)

다음에는 패키지들을 클래스에 결부시켜야 한다. 펄에서의 클래스는 단지 형식적인 패키지이다. (그와는 반대로 객체는 bless() 함수로 특별하게 만들어졌다). 펄은 OOP 규칙을 융통성있게 적용하여 프로그래머는 규칙에 제약을 받지 않는다.

new() 메소드는 클래스 컨스트럭터용 이름이다. 클래스가 객체로 인스턴스화 될 때마다 호출된다.

#!/usr/bin/perl -w

package Barebones;

use strict;

# this class takes no constructor parameters

sub new

{

  my $classname = shift;  # we know our class name

  bless {}, $classname;   # and bless an anonymous hash

}

1;

Listing 2에 있는 코드를 Barebones.pm 파일에 놓고 디렉토리에서 다음을 실행시켜서 테스트 할 수 있다:

perl -I. -MBarebones -e 'my $b = Barebones->new()'

예를 들어, print 문을 new() 메소드 안에 두어 $classname 변수가 무엇을 포함하고 있는지를 볼 수 있다.

Barebones->new()대신 Barebones::new()을 호출하면 클래스 이름은 new()로 전달되지 않을 것이다. 다시말해서, new() 는 컨스트럭터가 아닌 평범한 함수로서 작동한다.

Y$classname가 왜 전달되어야 하는지 궁금할 것이다. bless {}, "Barebones";라고 부르지 않는가? 상속이라는 것 때문에 이 컨스트럭터는 Barebones에서 상속되는 클래스에 의해 호출되지만 Barebones라고 하지는 않는다.

모든 클래스는 멤버 데이터와 new()와는 다른 메소드를 필요로 한다. 이를 정의하는 것은 몇 개의 프로시져를 작성하는 것 만큼 쉽다.

#!/usr/bin/perl -w

package Barebones;

use strict;

my $count = 0;

# this class takes no constructor parameters

sub new

{

  my $classname = shift;  # we know our class name

  $count++;               # remember how many objects

  bless {}, $classname;   # and bless an anonymous hash

}

sub count

{

  my $self = shift;       # this is the object itself

  return $count;

}

1;

이 코드를 다음을 이용하여 테스트 할 수 있다:

perl -I. -MBarebones -e 'my $b = Barebones->new(); Barebones->new(); print $b->count'

그러면 결과 '2'를 얻는다. 컨스트럭터는 두 번 호출되고 Barebones 객체 범위가 아닌 Barebones 패키지 범위로 한정된 어휘 변수($count)를 수정한다. 객체 데이터는 객체 그 자체로 저장되어야 한다. 메소드가 호출될 때 마다 객체에 액세스 할 수 있는 이유는 객체로의 레퍼런스는 그러한 메소드에 전달된 첫 번째 매개변수이기 때문이다.

DESTROY()와 AUTOLOAD()같은 특정 메소드가 있는데 이것은 특정 조건에서 펄에 의해 자동으로 호출된다. AUTOLOAD()는 동적 메소드 이름을 허용하는데 사용되는 메소드이다. DESTROY()는 객체 소멸자(destructor) 이지만, 정말로 필요한 경우가 아니라면 사용하지 말아야 한다. 펄에서 소멸자를 사용하는 것은 C/C++ 프로그래머로서 자신을 생각하고 있다는 의미가 된다.

상속에 대해 살펴보자. 펄에서 이것은 @ISA 변수를 변경하여 수행된다. 클래스 이름 리스트를 그 변수에 할당하면 된다. 그것으로 충분하다. @ISA 에 무엇이든 둘 수 있다. 클래스를 Satan의 자식으로 만들 수 있다. 펄은 상관하지 않는다.

#!/usr/bin/perl -w

package Barebones;

# add these lines to your module's beginning, before other code or

# variable declarations

require Animal;                      # the parent class

@ISA = qw(Animal);                   # announce we're a child of Animal

# note that @ISA was left as a global default variable, and "use

# strict" comes after its declaration.  That's the easiest way to do it.

use strict;

use Carp;

# make your new() method look like this:

sub new

{

  my $proto = shift;

  my $class = ref($proto) || $proto;

  my $self  = $class->SUPER::new();  # use the parent's new() method

  bless ($self, $class);             # but bless $self (an Animal) as Barebones

}

1;

이것은 펄 OOP의 기본이다. 다른 많은 언어들도 연구해야 한다. 이를 주제로 다룬 책들도 많다. 참고자료 리스트도 꼼꼼히 살펴보기 바란다.

h2xs
펄 클래스를 작성하고 문서 (POD) 스켈레톤(skeleton)을 작성할 툴이 있다면 더욱 행복해질 것 같지 않은가? 펄에는 이러한 종류의 툴이 있다: h2xs.

"-A -n Module" 플래그는 중요하다. 기억하기 바란다. 이것을 이용하여, h2xs는 유용한 파일로 가득찬 "Module" 이라는 스켈레톤 디렉토리를 만든다:

• Module.pm, 이미 작성된 스켈레톤 문서를 가진 모듈.
• Module.xs, 모듈을 C 코드로 연결하는데 사용.
• MANIFEST, 패키지용 파일 리스트.
• test.pl, 스크립트를 테스트하는 스켈레톤.
• Changes, 모듈의 변경 기록.
• Makefile.PL, makefile 생성자(generator).

이 모든 파일을 사용할 필요는 없지만 이와 같은 것이 존재하고 있다는 것을 알아두는 것이 낫다.

참고자료

• 1장 (코드 가이드라인), 2장 (코드 주석), 3장 (루프 신택스), 4장 (함수 프로그래밍): 보다 나은 프로그래밍으로 가는 길 시리즈.
  
  
• Object Oriented Perl: Damian Conway (Manning Publications, 2000).
  
  
• Perldoc.com.
  
  
• comp.object Object FAQ.
  
  
• Programming Perl, Third Edition: Larry Wall, Tom Christiansen, Jon Orwant (O'Reilly & Associates, 2000).
  
  
• developerWorks "Cultured Perl" 시리즈:
  • 프로그래머의 Linux 지향 설정
  • Perl로 애플리케이션 구성
  • Perl을 이용하여 UNIX 시스템 관리 자동화하기
  • 쉬운 Perl 디버깅 (US)
  • "JAPH"
  • Perl의 유전자 알고리즘
  • One-liners 개론
  • C와 Java 프로그래머를 위한 Perl
  • Perl로 Excel 파일 읽기/쓰기
  • "Programming Perl" the 3rd Edition
  • Perl의 데이터 저장 기술 (US)
  
  

친구가 인공지능, 검색, 게임등에 공통적으로 쓰일 수 있는 가장 요긴한 알고리즘을 알려달라고 부탁하더군요. 뭐 가장 처음 떠오르는 것이 바로 이 A* 알고리즘이더군요. 컴퓨터쪽 전공자 또는 게임쪽 전공자라면 누구나 한번쯤은 거쳐갔을 알고리즘이죠.

A* 알고리즘은 기본적으로 트리구조에서 많이 쓰이고 Best First Search의 방법을 쓰기 때문에 효율성도 갖추면서 코드도 깔끔히 만들 수 있는 장점이 있죠. 특히 휴리스틱(Heuristic)  접근법이라 제한된 시간과 제한된 컴퓨팅 리소스로 최적의 해답과 근접한 만족할 만한 솔루션을 찾아낼 수 있으면서도 그다지 복잡하지 않다는 것이 매력적인 점입니다.

아주 간단히 알고리즘으로 표현하면 다음과 같습니다. 알고리즘으로 표현한 것이기 때문에 구현은 어떤 언어로든 가능하죠. 교육용이니 아카데믹 한 면이라고만 생각 할수도 있지만 실제 코드로 만들어도 g,h function만 잘만들면 놀라운 성능을 보이죠.

기본적으로 Data Structure의 큐(Queue) 개념과 알고리즘을 읽고 이해할 수 있는 능력, 그리고 recursive function에 대한 거부감이 없어야 이해하기 쉬울 듯 하네요...

1. 주요 함수

(출처는 제가 대학다닐때 썼던 교재입니다 : (Russell, Stuart, and Peter Norvig. Artificial Intelligence. New Jersey: Prentice Hall, 1995)

Evaluation,기본 함수 개념

f (n) = g(n)+h(n)

g(n) = 루트부터 현재의 노드 까지의 웨이트 값

             **** 거리를 찾는 소프트웨어라면 출발지부터 현재 지점까지의 자동차 미터에 찍힐 값

h(n) = 현재 노드부터 목표점까지의 최선의 선택으로 갔을때 가질 수 있는 웨이트 값.

             **** 가장 핵심적인 함수로 목적에 따라자알~ 정해야 합니다.

             **** 거리로 말하자면 현재 지점에서 목적지까지의 직선거리라 할 수 있겠죠. 주의할점은 절대로 실제 나올값 보다 큰 값을 가질수 있는 함수로 만들면 안됩니다. Admissible Heuristic이라고 불리우는데 예를들면 A 지점부터 B지점의 실제 도로상 주행 거리가 10km라고 할때 h(n)으로 estimate한 값이 절대로 10km보다 크면 안된다는 이야기죠. 그래서 거리를 측정하는 소프트웨어에서는 h(n)=직선거리 로 쓰는 것입니다.

Queueing-Fn : 언제나 그렇듯 병렬컴퓨팅이 아니라면 순차적으로 문제를 풀어야 겠죠. 그래서 큐에 문제를 푸는 순서를 정해 넣습니다. A*의 경우 위의 f(n)이 그 순서를 정하게 되죠. 뭐 데이터 구조까지 설명은 안하겠습니다. 데이터 구조론(Data Structure)시간에 최소한 큐는 배웠을테니깐요. 큐의 형성은 최초에 General-Search 함수에서 Make-Queue에서 형성되고 loop 안에서 각 노드마다 child노드를 f(n)에 의거하여 큐에 추가시킵니다.

알고리즘 함수

function A*-SEARCH(problem) returns a solution or failure

    return BEST-FIRST-SEARCH(problem, g+h)

(Russell 97)

function BEST-FIRST-SEARCH(problem,EVAL-FN) returns a solution sequence

    inputs: problem, a problem

                EVAL-FN, an evaluation function

    Queueing-Fn <- a function that orders nodes by EVAL-FN

    return GENERAL-SEARCH(problem, Queueing-Fn)

(Russell 93)

function GENERAL-SEARCH(problem,QUEUING-FN) returns a solution, or failure

    nodes<- MAKE-QUEUE(MAKE-NODE(INITIAL-STATE[problem]))

    loop do

        if nodes is empty then return failure

        node<- REMOVE-FRONT(nodes)

        if GOAL-TEST[problem] applied to STATE(node) succeeds then return node

        nodes <- QUEUING-FN(nodes, EXPAND(node, OPERATORS[problem]))

    end

(Russell 73)

위의 함수들만으로는 거의 패닉상태에 빠져들 것 같아 간단히 그림으로 설명하도록 하겠습니다. 그림의 출처는 저(bgyuh)입니다.

** 각 노드는 도시들입니다.

** 붉은색 h= 에 적힌 값은 현재 도시에서 목적지까지의 직선거리입니다.

** 붉은색 g= 에 적힌 값은 출발지에서 현재 노드도시의 자동차 미터거리를 나타냅니다.

** 붉은 색 선은 도시 사이의 길이 있음을 표시합니다. 선위에는 도시사이의 실제적인 자동차 미터 거리를 나타냅니다.

** 도시 뒤의 d는 노드의 depth (깊이)입니다.

** 서치의 목적은 출발지부터 목적지까지 최단 주행거리를 가지는 경로를 찾는 것입니다.

간단히 프로그램이 서치과정에서 노드를 선택하는 과정을 보면 출발점에서는 당연히 도시 1 d 1를 선택하겠죠. Eval 함수 f(n) = g(n)+h(n)=110+300 = 410으로 2 d 1의 560보다 더 짧으니깐요. 그다음은 3가지 선택(11,12,13) 중에서 f 값 즉 총 거리의 Estimate 값이 가장 작은 도시 13 d 2를 선택 할 겁니다. 그다음은 물론 목적지라 직선거리 0인 131 도시를 선택하고 검색을 종료하겠죠.

좀더 자세히 들여다 보면

1. 루트에서 출발해서 첫번째 선택과정에서 보면 알 수 있듯이 노드 자체에 모든 값이 저장이 되어 있지는 않습니다. (즉 루트에서는 모든 브랜치 노드의 정보를 알 수 없고 바로 밑 자녀들의 정보만 알 수 있죠)

h값은 실시간으로 계산되는 estimate 값이고 단지 루트(출발도시)와 도시 1, 2간의 거리만이 실제값이 저장이 되어있죠.  만약에 모든 데이터를 저장해놓고 검색한다면 가장 정확하고 빠른 결과 (hash테이블처럼)를 얻을 수 있겠지만 경우의 수는 b^depth (예:바이너리트리의 경우 2^depth) 가 되므로 거의 무한정의 리소스가 필요합니다. g(n)은 물론 조금만 머리쓰면 쉽게 계산할 수 있죠.

정리해 보자면 각 노드에 저장된 정보는 도시의 좌표, 도시 이름, 각 인접 도시간의 도로와 그 도로로 갈 경우 인접도시간 거리 정도가 됩니다. 물론 더 고급기술로 가면 인덱싱을 이용하여 서치시간을 팍 단축시킬수도 있지만 생략하도록 하겠습니다.

2. 도시 13 d 2와 12 d 2를 비교할 경우 g값은 12 d 2가 더 작지만 h값을 더한 f값이 13 d 2가 더 작으므로 프로그램은 13 d 2를 선택하게 됩니다. 확실한 선택이었나를 따진다면 컴퓨터는 모르죠. 12 d 2의 노드를 검색 하지 않았기 때문입니다. 그러나 최적값에 가까운 값을 얻는 것이 목적이므로 그정도의 오차는 허락 할 수 있는 문제에 A* 알고리즘 사용해야 겠죠.

따라서 A* 알고리즘을 사용할 경우 Heuristic Function인 h(n)을 얼마나 잘 만드는 가에 따라 성능이 좌우됩니다.

3. f 값이 가장 작은 노드를 따라가더라도 목적지 (h=0)인 곳에 도착하지 못한다면 failure 를 return 하고 위 노드로 거슬러 올라가 다음으로 가능성이 높은 노드들을 따라 갑니다.

4. f (n) = g(n) + h(n) 값이 출발점부터 목적지까지의 자동차 미터거리를 Estimate한 값인데 노드가 진행될수록 커져야만 합니다. Admissible Heuristic 조건 때문이죠. Russell 교수님의 책에 이 조건이 왜 필요하고 A*가 왜 Optimal한가를 수학적으로 증명해 놓았는데 관심있으신분은 책을 사서 보셔도 좋을 듯 합니다.  

5. 도시 132 d 3의 경우 h값이 더 커졌는데 뭔가 돌아가게 된다는 암시가 되겠죠. Make-Node Function에 아예 이런 노드를 제거해서 큐에 안들어가게 하면 그만큼 시간이 절약되겠지만 굉장히 특이한 경우 산에 가로막혀서 반드시 돌아가는 외길만 존재한다면 제거하기도 뭐하죠. 그러니 특수케이스를 만들어 실험해 봐야 합니다. 솔루션이 존재하는데 프로그램이 찾아내지 못하면 그것 또한 버그죠.

위의 검색과정은 단순하고 가장 이상적인 적용례이지만 실제 적용과정에서 고려해야만 할 점들은 훨씬 많고 다양하죠

가장 흔하게 겪을 수 있는 버그들의 예입니다.

1. 갔던 노드를 또 가게 될 경우 무한 순환의 오류에 빠질 수 있으니 꼭 위에 알고리즘에서 그 부분을 추가 해 줘야죠.

2. 만약 h값이 작은 노드들로 서치하다가 어느순간 h 값이 Parent 노드보다 커진다면 의심해 보아야 합니다. 실제로 현재노드에서 목적지까지 절벽, 바다등으로 가로막혀서 목적지까지 돌아가야만 하는 경로만이 존재하고 부모나 그위의 노드에서 다른 경로를 선택할 경우 더 짧은 경로를 찾을 수 있었다면 최적의 솔루션과 상당히 동떨어진 결과를 얻을 수도 있겠죠. 그래서 h값이 부모노드보다 커진다면 부모노드나 그 윗 노드에서 재검색을 하여 더 나은 솔루션이 있나 찾아보는 것도 나쁘지는 않을 것입니다.

이 밖에도 실제 적용을 할때에는 수많은 테스트를 케이스를 만들어 고쳐가면서 해야지 그냥 덥석 알고리즘만 코드로 만들다가는 이놈의 네이버처럼 글쓰는데 한글변환도 잘 안되던가 사진올리다 포스트 날아가는 버그들을 양산하게 되겠죠.

친구의 부탁으로 자료를 좀 만들다가 그냥 심심해서 포슷에 끄적거려 봤습니다. 몇시간만에 예제를 만든거라 혹시 오류나 오타가 있을지도 모르겠네요. 책에 있는 예제도 좋은데 특수케이스들을 설명하기 뭐해서 새로 만들어 봤습니다.

저자: 한동훈(traxacun)

이 글은 리눅스 커널을 처음 공부하는 분들에게만 적합하며, 이미 잘 알고 계시는 분들에게는 적합하지 않을 수도 있습니다. 본 기사에서는 다음 주제들을 다룰 것입니다.

1. Memory Model
2. i386 CPU에서의 메모리 관리
3. 리눅서 커널에서의 메모리 관리
4. 커널에서의 코드

메모리 모델

예를 들어서, 1M 메모리를 가진 시스템이 있습니다. 이 시스템에서 메모리를 300k 사용하는 프로그램 A가 있고, 500k를 사용하는 프로그램 B가 있습니다. 그런데, 프로그램 A는 데이터가 많아질수록 더 많은 메모리를 사용하게 되어 있어서 600k의 메모리를 사용하게 되었습니다. 이런 경우에는 메모리가 프로그램 A와 B가 서로 충돌하게 되어 더 이상 프로그램을 실행할 수 없게 될 것입니다. 프로그램을 작성하면서 계산기 프로그램이 내 프로그램의 메모리 영역을 침범하면 안되는데라고 고민하면서 프로그램을 작성하지는 않을 것입니다. 이와 같이 다양한 프로그램들이 메모리를 사용할 수 있게 하기 위해 OS는 메모리를 관리합니다.

http://network.hanbitbook.co.kr/view.php?bi_id=1113

메모리 모델의 종류

메모리를 관리하는 방법은 세그먼트(Segment) 기법과 페이징(Paging) 기법이 있습니다. 우리가 흔히 보는 책은 페이지를 매기는 방법이 두 가지가 있습니다. 예를 들어, 1,000 페이지짜리 책이 있을 때 페이지를 1번부터 1,000번까지 모두 매겨놓은 책이 있는가하면, 책을 챕터별로 나누어서 각 챕터에서 몇번째 페이지라고 표기하는 방법이 있습니다. 선형적으로 일괄되게 페이지를 매기는 방법을 페이징이라 하고, 각 챕터별로 책을 나누고, 챕터에서 몇번째 페이지(Offset)라고 나누어 관리하는 방법을 세그먼트라고 합니다.

현대 운영체제는 정확하게 세그먼트와 페이징으로 나누어 관리하기 보다는 이 두가지를 적절하게 혼합된 형태를 사용합니다.

여기까지는 메모리를 관리하는 방법을 이론적으로 나눈 것이고, CPU에서 메모리를 관리하는 것은 다릅니다. 즉, OS에서 메모리를 관리하는 방법은 OS를 제작하는 사람이 마음대로 정할 수 있는 것이지만 실제로 CPU와 데이터를 주고 받을 때는 CPU에 맞춰서 데이터를 주고 받아야 합니다. 우리가 사용하는 x86 CPU는 리얼 모드(Real Mode)와 보호 모드(Protected Mode)를 사용합니다. 리얼 모드는 예전에 도스(DOS)를 사용하던 시절에 사용하던 모드로 1M 까지의 메모리를 사용할 수 있습니다. 보호 모드에서는 메모리를 0-4G까지 사용할 수 있습니다. 요즘에는 모두들 512M 이상의 램을 장착해서 사용하는 것이 보편적이니 리얼 모드는 몰라도 되지 않아라고 생각할 겁니다. 그러나, 시스템이 처음 전원이 들어가고, 부팅이 될 때는 리얼 모드로 실행되고, 그 이후에 보호 모드로 넘어가게 됩니다. 그렇게 때문에 커널을 학습하는 사람들은 CPU에서 메모리를 관리하는 방법이 리얼 모드일때와 보호 모드일 때 다르다는 것을 알아야 합니다. 이에 대해서는 뒤에서 보다 자세히 설명하도록 하겠습니다.

커널의 메모리 모델

리눅스 커널이 생각하는 메모리 모델은 크게 두 가지 뿐입니다. 하나는 물리 메모리(Physical Memory)이고, 다른 하나는 가상 메모리(Virtual Memory)입니다.

많은 분들이 들어보았을 이야기는 프로세스 하나당 4GB까지의 메모리 공간을 가진다는 것입니다. 즉, 스타크래프트도 4GB의 메모리 공간을 사용한다고 생각하고, 인터넷 익스플로러도 4GB의 메모리 공간을 사용한다고 생각합니다. 잠깐만요! 저는 PC에 램이 512M 밖에 없는데요? 라고 생각할 수 있습니다.

잠시 생각하면 알 수 있는 것처럼 모든 프로그램은 4G라는 메모리를 모두 사용하는 것이 아닙니다. 실제로는 매우 작은 일부만 사용할 뿐입니다. 그러니 사용하지 않는 부분은 무시하고, 사용하는 부분만 메모리에 갖고 있으면 됩니다.

프로세스는 4G의 공간이 전부 자기것이라고 생각하고, OS는 프로세스가 실제로 사용하는 부분만 실제 메모리에 올려놓으면 됩니다. 즉, 가상 공간과 실제 메모리 공간을 연결할 수 있는 변환 테이블이 하나 있으면 되겠네요!


그림1. 프로세스 A의 가상 공간과 실제 메모리

그림에서 볼 수 있는 것처럼 프로세스 A는 페이지 1, 4, 7번을 사용하고 있습니다. 그리고 이들 각각은 실제 메모리 프레임 5, 3, 1에 저장되어 있습니다. 이와 같은 방법을 사용하기 때문에 각 프로세스는 각자가 4G의 공간을 사용하고 있다고 생각하고, 다른 프로그램이 사용하는 메모리 공간에 대해 염려하지 않고 프로그램을 작성할 수 있는 것입니다.

x86 아키텍처의 메모리 모델

CPU는 연산을 위해 메모리와 데이터를 주고 받습니다. 즉, CPU가 메모리를 어떻게 이용하는지 알고 있어야합니다. CPU마다 메모리를 이용하는 방법은 각기 다르지만, 여기서는 가장 흔하게 사용되는 x86 CPU에 대해서 살펴볼 것입니다.


그림2. x86 CPU의 메모리 모델

x86 CPU는 32bit 환경이라고 얘기합니다. 즉, 메모리도 32bit에 해당하는 2의 32승 = 4G까지 사용할 수 있습니다. 각 페이지를 4096 바이트로 나누어서 관리하고 있습니다. 즉, 2^12 = 4096입니다. 따라서, 12 비트는 각 페이지의 위치를 가리키기 위해서 사용됩니다.

4G의 공간을 4096 페이지 크기로 나누면 1,048,576이고, 이 숫자의 의미는 4G의 메모리 공간을 4k 크기의 페이지로 나누어 관리하기 위해서는 페이지 테이블이 1,048,576개나 필요하다는 의미가 됩니다. 즉, 2^20 = 1,048,576이고, 1개의 PTE는 4 바이트이기 때문에 페이지 테이블이 차지하는 메모리의 크기는 1,048,576 * 4 = 4M가 됩니다. 즉, 하나의 프로세스가 4G의 메모리 공간을 관리하는 페이지 테이블을 유지하기 위해서는 4M가 필요하다는 것입니다. 프로세스 1개 생성에 4M를 무조건 사용한다는 것은 꽤나 큰 낭비입니다.

20 bit table인 경우: 2^20 = 1,048,576 = 1M
1M * 2^12(4096) = 4G
PTE = 4 bytes, 1M * 4 = 4M each process

그렇다면, 20비트를 한꺼번에 이용하는 대신에 10비트씩 나누어서 사용하면 어떨까요?
2의 10승은 1024개이고, 한 항목은 4 바이트를 차지하므로 1024 * 4 = 4096 = 4k를 사용하게 되고, 4k는 메모리에서 1 프레임만 차지합니다.
그래서 그림2와 같이 페이지 디렉토리에 10비트, 페이지 테이블에 10비트를 사용합니다.

Page Directory = 1024개 * 4 bytes = 4k = 1 page
Page Table = 1024개 * 4 bytes = 4k = 1 page

간단하게 C언어의 정의대로 적어보면 다음과 같습니다.

unsinged int table[1024*1024];
unsigned int directory[1024], table[1024];

첫번째는 20비트를 사용했을 때의 배열 선언이고, 두번째는 10비트씩 나누어서 디렉토리, 테이블로 사용할 때의 선언입니다. 물론, 리눅스 커널의 선언이 이렇게 되어 있다는 것은 아닙니다.

첫번째 배열 선언이 차지하는 크기를 생각해보면 4M이고, 두번째 배열 선언이 차지하는 크기는 8k입니다.

0xC1234567이라는 논리 주소가 주어졌을 때 실제로 CPU에서 어떻게 실제 메모리를 찾아가는지 살펴보겠습니다.


그림3. 논리 주소

0xC1234567이라는 16 진수를 2진수로 풀어서 쓰면 11000001001000110100010101100111이며, 이를 각각 10, 10, 12 비트씩 끊으면 위 그림과 같다.

그림2에 나온 것처럼 CPU에는 CR3 레지스터가 있으며, 이 레지스터는 메모리 관리를 위한 페이지의 출발지 정보를 갖고 있다. 따라서 CR3 레지스터의 값을 읽어서 페이지 디렉토리가 시작하는 위치를 알아내고, 상위 10비트  1100 0001 00 번째에 해당하는 위치로 디렉토리에서 이동하는 것이다. 16진수로는 0x304이며, 10진수로는 772가 된다. 772라는 의미는 페이지 디렉토리의 1024개 중에서 772번째 항목을 의미한다. 실제로는 773번째지만, PC에서는 값을 0부터 세어나가기 때문에 혼동하지 않게 0번째, 1번째, 2번째, 처럼 772번째라고 하겠다. 한 항목이 4바이트이므로 772 * 4 = 3088 로 이동해야한다. 여기서 읽어들인 값은 다시 페이지 테이블의 시작주소를 가리킨다. 페이지 테이블에 저장된 값 1000 1101 00 = 0x234 = 567이므로, 567번째 항목으로 이동해야 한다. 마찬가지로 각 항목이 4바이트 이므로 567 * 4 = 2256 위치로 이동해서 물리 프레임의 메모리 주소를 알아낸다. 마지막 오프셋은 여기서 알아낸 메모리 주소 값에 대한 상대위치를 나타내는 값이기 때문에 값을 단순히 더하기만 하면 된다.

2256위치에서 읽어들인 값이 0x40000이고, 오프셋의 값이 1383이면 실제 메모리 주소의 위치는 0x41383이 된다.

리눅스 커널의 메모리 모델

리눅스 커널은 64비트 선형 주소를 사용한다. 커널에서 64비트 주소를 사용하는 이유는 Alpha CPU와 같이 64비트 주소를 사용하는 시스템을 지원하기 위해서이다.


그림4. 리눅스 커널의 메모리 모델

리눅서 커널도 x86 CPU와 마찬가지로 메모리 관리의 효율성을 위해 페이지 디렉토리를 글로벌 디렉토리와 미들 디렉토리로 나누어서 관리한다. 즉, x86 CPU에서 2단계 페이징을 사용한다면 커널에서는 3단계 페이징을 사용하는 것이 차이점이다.
글로벌 디렉토리는 pgd_t, 미들 디렉토리는 pmd_t, 페이지 테이블은 pte_t로 나타내며, 오프셋은 상대위치이기 때문에 따로 나타낼 필요는 없다.

x86에서는 2단계를 사용하고, 리눅스 커널에서는 3단계를 사용한다면 커널은 x86 환경에서는 어떻게 해야할까? x86 CPU를 지원하기 위해 별도로 2단계 페이징을 만들어야 할까? 라고 생각할 수 있는데 실제로 커널은 위 구조를 그대로 유지하면서 2단계 페이징을 지원하는 방법을 택했다. 즉, 미들 디렉터리를 1개만 사용하는 것이다. 이렇게 하면 커널의 코드를 크게 변경하지 않으면서 64비트 환경과 32비트 환경을 쉽게 지원할 수 있다.

각 시스템마다 메모리 관리를 위해 사용하는 비트수는 다르기 때문에 위 그림에서 몇 비트씩 사용하는지 명시하지 않았다. 물론, 특정 플랫폼마다의 비트수를 적는다면 적을 수 있지만 여기서는 그렇게 하지 않았다.

x86 CPU와 커널에서 메모리를 찾는 방법을 보면 먼저 CR3 레지스터에서 글로벌 디렉터리의 시작 주소를 알아내고, 글로벌 디렉토리에서 몇번째 위치인지 알아낸다고 했다. 여기에 쓰이는 함수가 pgd_offset()이다. 마찬가지로 미들 디렉토리에서의 위치를 알아내는 것은 pmd_offset, 페이지 테이블에서의 위치를 알아내는 것은 pte_offset이다. pgd_offset, pmd_offset, pte_offset은 모두 2개의 인자를 갖는다.

pgd_offset(mm, address)인데 mm은 메모리 관리를 위한 구조로 각 프로세스마다 1개씩 갖고 있다. 즉, 페이지 글로벌 디렉토리의 시작 위치가 되며, address는 페이지 글로벌 디렉터리에서 몇 번째 위치라는 것을 나타낸다. 마찬가지로 pmd_offset의 첫번째 인자는 페이지 미들 디렉토리의 시작위치를, 두번째 인자는 페이지 미들디렉토리의 몇번째 페이지를 인자로 받는다. pte_offset도 동일하다. Redhat 9에 포함된 커널 2.4.20-8 버전에서는 pte_offset 대신에 pte_offset_kernel을 사용하면 된다. 상위 버전의 커널에서는 pte_offset으로 이용할 수 있다.
이들 함수(정확히는 매크로)를 이용하면 프로세스가 실제로 이용하고 있는 물리 메모리를 알아낼 수 있다. 이들 매크로는 arch/asm-i386/pgtable.h, pgtable-3level.h에서 찾아볼 수 있다. 참고로 실제로 존재하지 않는 페이지 글로벌 디렉토리, 미들 디렉토리 등을 액세스하려하면 중대한 커널 오류가 발생할 수 있다. 따라서, 페이지를 액세스하기 전에 각각 pgd_present, pmd_present, pte_present를 사용해서 실제 페이지가 있는지 확인하고 사용해야 한다.

프로세스에서 바라본 메모리

프로세스마다 4G의 가상 공간을 사용한다고 얘기했다. 그리고, 프로세스마다 메모리 관리를 하기 위해 페이지 글로벌 디렉토리, 페이지 테이블과 같은 구조를 갖고 있다고 했다. 프로세스를 나타내는 구조체는 task_struct이며, 여기에는 메모리 구조를 나타내는 mm_struct mm이 있다. mm은 메모리 관리를 위한 구조체이며, pgd_t* pgd는 페이지 글로벌 디렉토리의 시작 위치를 가리킨다. 즉, pgd가 가리키는 값과 CR3 레지스터가 가리키는 값이 같다. 그 이후부터는 앞에서 설명한 것처럼 각 페이지별로 주소를 찾아서 실제 메모리상의 프레임을 찾아간다.


그림5. 프로세스에서 바라본 메모리

이를 자세하게 표현하면 그림6과 같습니다. 각각의 프로세스는 task_struct 구조체로 표현되며, 이를 간단히 PCB(Process Context Block, 컨텍스트 문맥)이라고 이야기한다. 커널에는 프로세스 ID로 해당 PCB를 찾아내는 함수가 있는데 이 함수가 find_task_by_pid(pid)이다. 이 함수는 프로세스 ID, PID를 인자로 넘겨 받으면 task_struct에 대한 것을 반환해준다.

물론, 현재 프로세스는 current로 접근할 수 있지만, 다른 프로세스에 대한 task_struct를 얻어오려면 find_task_by_pid를 사용해야 한다. task_struct에는 mm이 있고, 이 mm이 mm_sturct 자료구조를 가리킨다.

그림1을 생각해보면 프로세스는 연속적인 가상 메모리를 할당 받는 것도 아니라 여러 개의 가상 메모리 블록을 할당받는다. 즉, 연속적으로 할당 받을 수도 있고, 따로따로 할당 받을 수도 있다는 얘기다. 이를 위해서 mm_struct에 보면 각각의 가상 메모리 블록을 관리하는 vm_area_struct 구조체가 있다. 그리고 vm_area_struct에는 각각 vm_start와 vm_end가 있는데 이는 가상 메모리 공간에서의 시작 위치와 마지막 위치를 가리킨다. 또한 vm_area_sturct* vm_next는 자신과 같은 형태의 구조체를 다시 가리키고 있는데, 이는 다른 가상 메모리 블록을 가리킨다. 즉, 단일 연결 리스트(Singly Linked List)로 연결되어 있다. vm_next를 따라 프로세스가 사용하는 전체 가상 메모리 공간을 알아낼 수 있다. 만약, vm_next가 NULL인지 아닌지를 알아내면 가상 메모리 블록의 끝을 알아낼 수 있다.


그림6. 프로세스에서 바라본 메모리 관리

마지막으로 task_struct에는 mm_struct로 선언된 변수가 두 가지가 있다. 하나는 mm이고, 다른 하나는 active_mm이다. mm은 프로세스가 사용하는 메모리 공간을 나타내고, active_mm은 CPU에 의해 현재 제어중인 주소공간을 가리킨다. 프로세스 A에게 있어서 mm과 active_mm은 같다. 즉, A->mm == A->active_mm이다. 그러나, 커널 스레드에서는 mm은 NULL이며, 커널 스레드가 사용중인 메모리는 active_mm으로 표현된다.
Linux 커널의 아버지인 Linus는 메모리 공간을 실주소공간(Real Address Spaces)과 익명주소공간(Anonymous Address Spaces)로 나눈다. 사용자 프로세스가 사용하는 주소 공간을 실주소공간아리하고, 커널 스레드가 사용하는 공간을 익명주소공간이라 하는 것이다.

모든 커널 스레드는 익명주소공간을 사용하며, 사용자 프로세스가 사용하는 실주소공간에 대해서는 관여하지 않는다.

foo라는 프로세스 A를 실행한다고 하자. 이 경우 A->mm == A->active_mm = foo일 것이다. 이때 커널 스레드 B에 의해 선점당한 경우 B->mm = NULL이지만, A->active_mm = foo를 여전히 가리키게 된다. 즉, 커널 스레드는 실주소공간을 신경쓰지 않지만, 작업 A가 다시 로드되었을 때 mm을 다시 로드하지 않기 위해 active_mm을 사용하는 것이다.

스왑

실제 메모리 사용량보다 더 큰 메모리가 필요한 프로그램을 실행할 수 있는 것은 가상 메모리 덕분이다. 앞에서는 가상 메모리에 대해서 살펴보았는데, 사용중이지 않은 부분은 스왑으로 저장해서 메모리에 여유공간을 확보하는 것이 스왑의 역할이다.

앞의 그림5에서 살펴본 것처럼 스왑을 한다는 것은 실제 메모리의 프레임을 디스크로 저장하는 것을 의미한다. 실제 메모리 프레임을 찾기 위해서는 페이지 테이블의 위치를 알아야하고, 페이지 테이블의 위치를 알기 위해서는 페이지 미들 디렉토리의 위치를 알아야한다. 마찬가지로, 페이지 미들 디렉토리의 위치를 알기 위해서는 페이지 글로벌 디렉토리의 위치를 알아야 한다. 이들 프로세스는 가상 메모리로 관리되고 있으니 가상 메모리 구조를 찾아봐야하고, 다시 실제 메모리 공간도 찾아봐야 한다. 즉, swap_out 함수는 이러한 순서들을 찾아가며 실제 메모리 프레임을 찾아가는 역할을 하고, 메모리 프레임을 디스크에 저장하는 것은 try_to_swap_out 함수의 역할이다.


그림7. 스왑의 흐름

kswapd 함수는 daemonize 함수를 호출해서 자신을 데몬으로 등록시키고, 무한 루프를 돌면서 kwapd_can_sleep 함수를 호출한다. 이 함수는 지금 스왑 작업을 해도 되는지 아닌지를 판별하며, 이를 판별하기 위해서는 다시 kswapd_can_sleep_pgdat를 호출해서 페이지 글로벌 디렉토리에서 스왑이 필요한 페이지가 있는지 없는지를 판별한다. 스왑이 필요한 페이지가 하나라도 있으면 kswapd_balance를 호출한다. kwapd_balance는 메모리의 균형을 맞춰준다. 마찬가지로 이 함수도 kswapd_balance_pgdat를 호출하여 페이지 글로벌 디렉토리를 확인한다. try_to_free_pages 함수에서 try_to_free_pages_zone을 호출해서 사용할 수 있는 페이지 영역을 찾아보고, 사용할 수 있는 페이지가 부족한 경우에는 필요한 페이지를 확보하기 위해 shrink_caches를 호출한다. shrink_caches는 캐시들을 돌아다니며 비울 수 있는 캐시인지 판별하기 위해 shrink_cache 함수를 사용한다.

전체적인 흐름은 이렇게 되어 있으며, 각 프로세스에서 사용중인 스왑 공간은 task_struct의 swap_address로 알 수 있다.

스왑 정책

커널의 스왑 정책에서 사용할 수 있는 방법은 여러가지가 있지만, 리눅스 커널에서는 LRU(Least Recently Used) 정책을 사용한다고 알려져 있다. LRU는 가장 적게 사용된 페이지를 스왑으로 대체시키는 것이다.

메모리 페이지를 LRU 정책에 따라 스왑시키려면 해당 메모리 페이지가 액세스 된 적이 있는지 알아낼 수 있는 방법이 있어야 한다. 각 페이지가 액세스 된 시간을 기록해서, ‘아, 이 페이지는 1시간 전에 액세스했고, 이 페이지는 5분전에 액세스했네’라는 사실을 이용할 수도 있을 것이다. 단, 이렇게 한다면 액세스 될 때마다 시간을 기록하고, 각 페이지의 시간을 기록하고 유지하는 것만으로도 굉장히 높은 작업부하가 걸릴 것이라고 예상할 수 있을 것이다. 이런 스왑 정책은 OS가 단독으로 하기엔 어려운 부분이다. CPU에서는 이를 위해 액세스 비트(Access Bit)를 제공한다. 이 비트는 이 페이지가 접근된 적이 없으면 0, 있으면 1로 설정된다. 그림8에서 A가 액세스 비트를 나타낸다. 액세스 비트는 페이지에 접근할 때 CPU에서 자동으로 1로 설정하지만, CPU가 이를 다시 0으로 설정할 수는 없다. 0으로 설정할 수 있는 것은 오직 커널 뿐이다.


그림8. 페이지 엔트리

U/S는 사용자 프로세스가 접근할 수 있으면 1이고, 커널만 접근할 수 있으면 0으로 설정된다. R/W는 0이면 읽기만 가능하고, 1이면 읽기/쓰기가 모두 가능하다. P는 Present Bit라는 것으로 페이지가 메모리상에 존재하는지를 나타낸다. 즉, 페이지가 디스크로 스왑 되었으면 0이 된다. 프로세스가 이 페이지를 접근하려하면 P 비트가 0이기 때문에 페이지 폴트 인터럽트 #14가 발생하고, 디스크에서 다시 메모리로 이 페이지를 읽어들이고, P 비트를 1로 설정하게 된다.

메모리 관리와 관련된 부분은 OS가 독단으로 결정할 수 있는 것이 아니며, CPU와 OS가 서로 조화를 이루어가며 관리하는 부분이다.

코드로 보는 리눅스

8086 시스템은 과거에 20개의 어드레스 핀을 가진 16비트 시스템이었다. 즉, 2^20 = 1M까지 사용할 수 있는 시스템이었다. 이 의미는 1M 이상의 메모리를 사용할 수 없다는 것이다. 1M + 1번째를 접근하려 하면 1번째로 접근하게 된다. 이는 마치 프로그래밍 언어에서 만나는 정수 오버플로우와 같다. 1M + 1 = 1로 만들려면 어떻게 하면 될까? 2^20은 16진수로 0x100000이고, 2진수로는 100000000000000000000이다. 1M를 넘어가는 비트가 공교롭게도 가장 맨 앞의 비트이다. 즉, 맨 앞의 1을 0으로 만들어 주기만 하면 된다. 11111111111111111111 + 1을 하면 100000000000000000000이 되어야 하는데 20번째 비트를 0으로 만들면 결과 값은 0이 된다. +2를 하면 결과값은 1이 될 것이다.

이를 위해 8086 시스템에서는 20번째 핀을 키보드 인터럽트 핸들러인 8042와 AND 게이트로 연결해 놓았다. 20번째 핀이 켜지지 않으면 사용자는 항상 저 주소를 이용할 수 없다.

펜티엄 4에서 DOS용 응용 프로그램을 실행할 수 있다는 의미는 하위 호환성이 좋다는 의미이기도 하지만, 위와 같은 단점도 고스란히 물려받았다는 의미가 된다.

요즘과 같이 512M 램을 사용하는데, 저걸 알아서 뭐해요? 라고 되물을수도 있다. 그러나 A20을 켜주지 않으면 20번째 비트가 항상 0이 되기 때문에 1M = 0이 되고, 3M = 0이 된다. 즉, 1M에 해당하는 메모리 주소를 CPU가 액세스하려하면 0번째를 가리키게 된다. 사용자는 1, 3, 5, 7…과 같이 홀수번째 메모리를 전혀 사용할 수 없게 된다. 그렇게 때문에 부팅 과정에서 CPU가 리얼 모드에서 보호 모드로 넘어가기전에 반드시 A20 게이트를 켜야한다.



리눅스 커널의 소스 코드를 보면 그런 부분이 있다. movb $0xDF, %al이 있고, 옆에는 주석으로 A20 게이트를 켠다고 되어 있다. 이 부분의 값은 몰라도 된다. 저것은 CPU 매뉴얼에 있는 특정한 명령어인 것이다.



여기서는 lgdt gdt_48을 볼 수 있다. lgdt 명령어는 전체 커널 소스에서 단 한번만 사용된다. CPU는 리얼 모드에서 보호 모드로 넘어가기전에 글로벌 디스크립터(Global Descriptor)를 작성해야 한다. 즉, 4G에 해당하는 메모리를 어떻게 사용하겠는가를 설계하는 명세서와 같은 역할을 한다. 코드 세그먼트 디스크립터, 데이터 세그먼트 디스크립터, 비디오 세그먼트 디스크립터등을 지정할 수 있다. gdt_48은 명령어가 아니라 이러한 디스크립터를 적어놓은 곳으로 C언어의 struct와 같은 것이다.

리얼 모드에서 보호 모드로 넘어가는 순서는 1. 디스크립터를 정의한다. 2. lgdt 명령어로 디스크립터를 로드하고 보호모드로 전환한다. 이다.
CPU에는 명령어를 실행하는 부분이 3가지로 나누어져 있다. 첫번째는 명령어를 읽어들이는 부분, 두번째는 명령어를 해석하는 부분, 세번째는 명령어를 실행하는 부분이다.

즉, lgdt 명령어를 실행하게 되는 순간에 읽기 유닛, 해석 유닛에 이미 2개의 명령어가 들어가 있다. 보호모드로 전환된 다음에 리얼 모드에서 들어가 있던 명령어가 실행되면 안되니까 최소한 읽기, 해석 유닛의 명령을 무시하기 위해 두 스텝을 쉬어줄 필요가 있다. 따라서, lgdt 명령어를 실행한 다음에 어셈블리로 nop(No Operation: 아무일도 하지마!)를 2번 실행해주는 것이 관례다. 그런데, 커널 소스에선 nop 대신에 call delay를 사용하는 것 같다고 나름대로 추측할 수 있었다. nop 명령어를 커널에선 사용하지 않는다.

다음으로 첫번째 줄을 보면 lidt 명령이 있다. 이것은 인터럽트 디스크립터를 로드한다. 즉, Devide By Zero(인터럽터 0번)이라든가, 페이지 폴트(인터럽터 14번) 같은 인터럽트가 발생했을 때 이를 처리할 루틴의 위치를 지정하는 부분이 idt_48이고, lidt는 이를 메모리에 로드해주는 것이다.

굳이 이렇게 GDT를 꺼내든 이유는 <<리눅스 커널의 이해>>의 2장 메모리 관리 부분의 처음 1/2 정도가 전부 이 GDT 구조를 설명하는데 할애되어 있다고 느꼈기 때문이다. 책만 펼치면 잠이 쏟아질 만큼 졸린데, 이는 어셈블리와 CPU 구조에 대한 이해조차 없이는 책을 이해하기 어렵기 때문이라 생각했다. 즉, 내공이 부족한 내가 보기엔 어려운 책이다.

이들 어셈블리 코드는 arch/i386/boot에 있으며, 비디오 디스크립터는 video.S에 정의되어 있다.



위 코드처럼 0xC0000000가 3G 영역을 가리킨다. 커널이 3G위의 영역을 사용한다는데 실제로 그 값이 있는지 확인해 본 부분이다.



여기서는 앞에 CR4 레지스터가 보인다. CPU에는 CR0-CR4까지의 레지스터가 있다. 이중에서 CR3는 페이지 글로벌 디렉토리의 위치를 가리키며, CR4 레지스터는 PAE 확장을 사용할 것인가를 설정한다. 펜티엄 프로 이후에는 어드레스 핀이 4개가 더 추가되어서 4G가 아니라 64G까지 사용할 수 있게 해준다. 따라서, 이 값이 설정된 경우에 CR4 비트를 1로 설정해서 PAE 확장을 사용하게 설정해 주는 부분이다.



movl %eax, %cr3에서 페이지 테이블이 시작하는 위치를 CR3 레지스터에 저장하고 있다.(GAS, GNU Assembler는 AT&T 스타일을 따르고 있어서 어셈블리 명령어 인자 위치가 서로 반대다. mov a, b는 B의 값을 A에 넣는다이지만 AT&T 스타일에서는 A의 값을 B에 넣는다가 된다)

마치며

아직은 커널을 잘 알지 못하고 커널을 공부하는 입장에서 준비된 글입니다. 국내에 나와있는 다양한 커널 책들을 많이 참고했습니다. 아직 다루지 못한 부분들이 많습니다. 커널 소스에 대한 세세한 설명보다는 커널의 전체적인 흐름을 다루는 것이 세미나에는 더 적합하다고 판단해서 전체적인 흐름을 다루는데 중점을 두었습니다. kmalloc과 vmalloc의 차이점을 다루는 것 보다는 전체적인 흐름이 더 중요하다고 생각했습니다. 흐름에 대한 이해를 바탕으로 소스 코드를 살펴보는 것이 이해에 더 도움이 된다고 생각합니다.

레퍼런스

각각의 책마다 같은 부분을 보아도 설명이나 보여주는 부분이 다릅니다. 결국, 저자가 커널을 바라보는 방식에 대해 생각해보는 기회도 되고, 책을 가이드삼아 커널을 직접 찾아보며 전체를 바라볼 수 있는 안목을 기르는 것은 자신의 몫이라 생각됩니다. 주로 리눅스 커널 프로그래밍을 많이 참고했으며, 리눅스 커널 심층 분석은 커널 API 이해에 많은 도움이 되었습니다. Operating System Concepts는 운영체제가 시스템을 관리하는 다양한 방법과 알고리즘에 대한 해설이 중심이고 이를 토대로 리눅스 커널이 채택한 방법을 살펴보는 데 좋은 참고가 됩니다. 리눅스 커널의 어셈블리 코드 부분은 만들면서 배우는 OS 커널의 구조와 원리에서 많은 부분을 참조했습니다.

• 리눅스 커널의 이해, 2판, 한빛미디어
• 만들면서 배우는 OS 커널의 구조와 원리, 한빛미디어
• 리눅스 커널 프로그래밍, 교학사
• 리눅스 매니아를 위한 커널 프로그래밍, 교학사
• 리눅스 커널 심층 분석, 에이콘
• 리눅스 커널 분석 2.4, 가메
• Operating System Cencepts, 6판, 홍릉