« Previous : 1 : 2 : 3 : 4 : Next »

오늘은 기초 전산학/컴공 상식을 좀 복습해 보고자 한다.

※ 지금과 같은 컴퓨터의 근간이 갖춰진 과정

1. 순 전자식

이로써 인간이 발명한 계산 기계는 엔진 달린 주판 수준을 넘어서 자신의 모든 내부 상태를 전자 신호만으로 광속으로 표현할 수 있게 됐다. 에니악이 순 전자식 컴퓨터로서는 거의 최초 원조라 여겨진다. 이거 이후로 컴퓨터는 진공관, 트랜지스터, IC, (V)LSI 회로 순으로 그야말로 엄청난 공간 워프를 거듭하면서 작아지고 빨라지기 시작했다.

전자식이 아니라면? 컴퓨터도 엔진이나 모터가 달린 채로 만들어졌을 것이다. 19세기에 영국의 수학자 찰스 배비지는 '프로그래밍 가능한 보편적인 계산 기계'인 '해석 기관'이라는 걸 제안하고 만들려 했다. 시대를 아득히 앞서 간 물건이었는데, 그걸 가동하기 위해서 무려 증기 기관을 접목할 생각까지 했었다. 지금 같은 눈부신 전자 공학 기술이 없던 시절이니 당연히 기계식밖에 선택의 여지가 없었던 것이다.

그리고 1940년대 초에 에니악 이전에 등장했던 '하버드 마크 1'이라는 기계는 '전자식 계산기'라기보다는 '전동식 계산기'에 더 가까웠다. 복잡한 배선과 릴레이뿐만 아니라 4마력짜리 모터가 달려 있었다. 이건 냉각팬 모터가 아니며 하드디스크 같은 기계식 보조 기억장치용 모터도 아니고, CPU의 실제 계산 동작을 위한 모터였다..;;

2. 2진법 기반

사람이나 열 손가락이 달려 있으니 10진법이 편하지, 기계는 단순한 2진법이 더 편하다. 컴퓨터가 전자식으로 바뀐 뒤부터는 그 차이가 더욱 두드러졌다.
하지만 극초창기에는 숫자 진법을 변환하는 것조차 쉬운 작업이 아니었고, 정수가 아닌 부동소수점으로 가면 숫자를 표현하는 난이도가 더 올라갔다. 더구나 컴퓨터는 처음부터 포탄 탄도 예측, 풍동 실험, 일기예보 시뮬, 모의 핵실험처럼 천상 실수 연산이 잔뜩 필요한 과학 영역에서 쓰였다.

그러니 에니악 같은 컴퓨터는 10진법 기반으로 만들어졌다. 4비트를 한 자리로 묶어서 0~9를 표현하는 BCD 코드 기반이었지 싶다. 하지만 10진법 숫자를 처리하기 위해서 어차피 2진법 기반의 각종 논리 연산 회로를 구현해야 했을 것이고, 후대의 컴퓨터들은 얼마 가지 않아 native 2진법 기반으로 다 바뀌었다.

3. 튜링 완전

프로그램이 하드코딩된 고정된 변수가 아니라 메모리에 기록된 값을 토대로 또 임의의 위치의 메모리를 읽고 쓸 수 있고(= 배열, 포인터 등을 이용한 복합 자료형. 공간 확장),
런타임 때 결정되는 값의 조건에 따라 반복과 분기가 가능하다면 (= 시간 확장)
그런 계산 모델은 Turing-complete하다고 여겨진다. 즉, 단순 계산기를 넘어 뭔가 본격적으로 프로그래밍이 가능해진다는 것이다.
그 열악한 에니악조차도 설계 구조는 튜링 완전한 형태였다고 한다.

4. 프로그램 내장형

컴퓨터에게 시킬 작업을 변경하기 위해 매번 회로 배선을 뜯어고치고 바꾸는 게 아니라, 한 메모리에서 코드와 데이터를 일체로 내장시킨다. 이 개념까지 정립됨으로써 비로소 컴퓨터는 정말 유연하고 무한한 확장성을 지닌 물건으로 변모했으며, 컴퓨터에서 하드웨어와 별개로 '소프트웨어'라는 것이 존재할 수 있게 됐다.
또한, 메모리가 컴퓨터의 성능에서 차지하는 비중이 아주 커졌다. 프로그램을 메모리에다 처음으로 입력시킬 때는 과거엔 천공 카드 같은 불편한 매체가 쓰였지만, 나중에는 더 간편한 키보드로 대체됐다.

저 아이템들 하나하나가 그야말로 병아리가 알을 깨고 세상으로 나오는 급의 대격변이고 혁신이었다.
인류 역사상 이런 네 조건을 모두 만족하는 컴퓨터가 발명되고 등장한 지 아직 100년이 채 지나지 않았다. 자동차와 비행기의 역사는 100년을 넘었지만 컴퓨터는 아직 그렇지 않고 오히려 2차 세계 대전 이후 냉전 때부터 발전해 왔다.
그 짧은 기간 동안 컴퓨터가 인류 역사상 유례가 없이 세상을 바꿔 놓은 걸 보면.. 정말 전율이 느껴지지 않을 수 없다.

※ 메모리 계층

컴퓨터는 모름지기 정보를 다루는 기계이다. 그리고 앞서 언급했던 프로그램 내장 방식의 특성상, (1) 실행할 코드와 (2) 그 코드가 처리할 데이터가 모두 메모리에 담겨 있어야 한다. 쉽게 말해 정보를 담을 그릇이 필요하다.
그런데 컴퓨터가 취급하는 메모리라는 게 여러 종류가 있고, 이들은 속도와 용량, 단위 용량당 가격이 극단적으로 반비례하는 관계이다. 그렇기 때문에 종류별로 일종의 '메모리 계층'이 존재한다.

1. 레지스터(수십~수백 byte)

CPU 구성요소의 일부이다. 당연히 CPU 차원에서 최고속으로 직통으로 값을 읽고 쓸 수 있다.
현재 프로그램이 실행되고 있는 지점(메모리 위치), 수만 번씩 실행되는 for 문 loop 변수, C++ 함수의 경우 this 포인터, 산술 연산 명령에 쓰이는 피연산자와 연산 결과 같은 정~말 원초적인 값들이 이곳에 저장된다.
실행되는 스레드의 context가 바뀌면 레지스터의 값도 자기 상태의 것으로 바뀐다.

2. 캐시 메모리(수백 KB~수 MB)

CPU 자체는 아니지만 여전히 CPU의 연장선 격이며 접근 속도가 매우 빠르다. CPU가 사람 두뇌이고 레지스터가 손의 손가락이라면 캐시는 의수 정도는 된다.
얘는 CPU 속도와 메모리 속도의 격차가 커지면서 메모리로 인한 병목을 줄이기 위한 버퍼 차원에서 도입되었다.

캐시도 레벨 1, 레벨 2로 나뉘긴 하는데, 인텔 x86 CPU에서 제일 원초적인 L1 캐시는 80486 때 8K짜리가 도입된 것이 최초이다. 반대로 펜티엄 2이 나왔던 시절에 셀러론 프로세서는 L2 캐시를 제거하거나 용량을 팍 줄인 저가형 모델이었다.

3. 일반 메모리(수십 GB)

CPU의 외부에 있기 때문에 위의 것들보다는 느리지만, 그래도 보조 기억장치보다는 여전히 훨씬 빠르다. 이들 메모리는 전원이 끊어지면 내용이 다 지워지는 휘발성 메모리이다. 이제 신체 접근성으로 치면 의수를 넘어서 핸들과 버튼으로 따로 조작하는 로봇 팔과 비슷하다고 볼 수 있겠다.

4. 하드디스크(수 TB)

디스크부터는 보조 기억장치이기 때문에 이건 CPU의 명령만으로는 직접 접근조차 할 수 없다. 운영체제라는 소프트웨어가 구현해 놓은 파일 시스템에다 해당 운영체제 API를 통해 요청해야만 데이터를 읽고 쓸 수 있다. 파일 시스템은 열고 닫는 상태를 따로 보관하고 관리해야 하며, 프로그램의 입장에서는 여는 작업이 실패하는 상황에 대한 대비가 필요하다.
사람으로 비유하면 내 손으로 뭔가를 직접 조작하는 게 아니라, 남에게 말로 부탁을 해서 간접적으로 뭔가를 요청하고 움직이는 형태가 된다.

그 대신 보조 기억장치는 전원이 끊어진 뒤에도 기록을 남기고 보존할 수 있다. persistency를 보장하려다 보니, 하드디스크는 컴퓨터에서 전자식이 아닌 기계식으로 동작하는 얼마 안 되는 부품 중 하나가 돼 있다. 플래시 메모리는 '일반 메모리'의 성격에 더 근접해 있는 기억장치이지만, 가격과 용량 문제 때문에 하드디스크를 완전히 대체하는 구도는 못 된다.

캐시 메모리에서 캐시 미스가 나서 더 느린 일반 메모리까지 내려가서 데이터를 가져오는 게, 아래의 운영체제의 가상 메모리 체계에서 페이지 폴트가 발생해서 디스크의 페이지 파일에서 데이터를 가져오는 것과 비슷한 구도이다. 메모리 공간 자체가 CPU의 일부는 아니지만, 보호 모드 가상 메모리 구현을 위한 주소 변환은 CPU 차원의 지원을 따로 받아서 이뤄진다.

메모리가 비싸고 귀하고 부족하던 옛날에는 가상 메모리라는 게 디스크를 메모리 보충분처럼 사용하는 메커니즘이기도 했다. 비록 속도는 안드로메다로 가 버리지만, 그래도 아예 안 돌아가는 것보다는 나으니 better late than never이다. 요즘 운영체제들은 memory mapped file이라고 디스크를 반쯤 메모리 다루듯이 포인터로 접근시켜 주는 API를 제공하는데, 가상 메모리를 구현하면서 내부적으로 구현된 기능을 사용자도 적절하게 활용하라고 떼어 준 것에 가깝다.

또한, 가상 메모리와는 별개 개념으로.. 레지스터와 메모리 사이에 '캐시 메모리'가 있듯이, 메모리와 디스크 사이에 '디스크 캐시'라는 계층이 존재한다. 이게 잡아먹는 메모리 양이 만만찮지만 도스 시절에 smartdrv 유틸로 수백 KB~2MB 남짓만 캐시를 잡았어도 체감 성능 향상 효과가 장난이 아니었다. 이거 없이 곧이곧대로 찔끔찔끔 디스크에 접근해서는 오늘날의 방대한 컴퓨터 시스템이 돌아가질 못한다. 그만치 메모리와 디스크 사이의 속도 격차 병목이 엄청나다는 뜻이다.

5. 자기 테이프(수백 TB~수 PB)

아주 극단적인 보조 기억장치이다. 느리고 랜덤(임의 위치) 접근이 안 된다는 엄청난 단점이 있지만, 용량이 가히 압도적이고 가격이 저렴하다. 그렇기 때문에 서버 전체 내지 매일 생성되는 방송국 동영상 같은 엄청난 양의 데이터를 오로지 백업· 보존만 할 목적으로 일부 연구소나 기업에서 테이프가 여전히 사용되고 있다. 마치 국제 화물 운송에서 선박이 차지하는 위상(느리지만 엄청난 수송량)과 비슷하고, 프린터계에서 도트 프린터의 먹끈 카트리지(원시적이지만 타의 추종을 불허하는 저렴함)와 비슷하다.

메모리야 컴퓨터 프로그램들이 맨날 하는 짓이 저걸 건드리는 것이고, 보조 기억장치는 파일을 읽고 쓰는 운영체제 API를 통해 사용 가능하다.
레지스터의 경우, C/C++ 언어에는 특정 정수 변수를 가능한 한 저기에 얹어 달라고 컴파일러에게 요청하는 register이라는 키워드가 있다. 함수에 inline이 있다면 변수는 저게 있는 셈이다. for문 loop 변수가 레지스터에 올라가면 좋다.
물론, inline 함수는 재귀호출을 해서는 안 되며, 레지스터 등재 변수는 주소 참조(단항 & 연산자)를 해서는 안 된다.

이렇게 타 메모리나 디스크나 레지스터와는 달리, 캐시 메모리만은 적중률을 올리기 위해 소프트웨어가 직접 접근하고 개입하는 방법이 딱히 존재하지 않는다. 멀티코어 병렬화를 위해서는 CPU 직통 명령인 인트린식 같은 것도 있는데 캐시는 활용 방식이 소프트웨어가 아닌 오로지 CPU의 재량인가 보다.
이렇게 존재감이 없음에도 불구하고 캐시 메모리의 양과 성능은 클럭 속도 다음으로 컴의 속도에 직접적인 영향을 끼치는 요인이다.

※ 인텔 x86

인텔 x86은 전세계의 PC 시장을 완전히 석권한 기계어 아키텍처이다. 애플 맥 진영이 x86으로 갈아탄 지 이미 10년이 넘었고, 슈퍼컴퓨터조차도 Cray 같은 슈퍼컴 전용 아키텍처가 진작에 다 망하고 x86이 코어 수를 늘려서 야금야금 파고들고 있다.

하지만 x86은 CPU를 만들던 기술과 방법론이 지금과 같지 않던 초창기, 특히 메모리 가격이 왕창 비싸던 시절을 기준으로 기반이 설계되었으며 16, 32, 64비트로 올라가는 과정에서도 하위 호환성을 잘 유지하고 있다. 그래서 넘사벽급의 범용성과 시장 경쟁력은 확보했지만, 내부 구조가 갈수록 왕창 지저분해지고 스마트폰용 ARM 같은 후대의 최신 CPU들의 유행과는 영 동떨어진 형태가 됐다.

  • 범용 레지스터 수가 유난히 매우 적음. R## 이렇게 수십 개씩 번호가 붙는 게 아니라 EAX EDX ESI EBP 등 꼴랑 8개로 끝인 건 x86이 예외적이고 특이하기 때문이다. 함수에다가 매개변수를 올리는 주 방식도 x86은 당연히 레지스터가 아닌 스택 기반이다. 이 때문에 컴파일러 백 엔드를 개발하는 방법론이 x86 타겟 계열과 타 아키텍처 계열은 서로 완전히 다르며, x86은 오늘날 컴공과에서 컴파일러 제작 교육용 교보재로 쓰이기에는 영 좋지 못한 타겟 아키텍처이다.
  • 메모리를 조밀하고 compact하게 쓰는 대신에, 디코딩이 복잡하고 더 어려운 CISC 가변 길이 방식으로 명령어를 기술한다. 한 인스트럭션으로 연산에다 메모리 조작까지 몽땅.. 이런 식으로 많은 지시를 함축하고 있는 편이다. 자동차 엔진으로 치면 회전수가 낮은 대신 실린더의 스트로크가 긴 디젤처럼..
  • machine word align이 맞지 않은 메모리 주소의 값을 fetch하는 것을 굉장한 비효율(여러 클럭수 소모)을 감수하고라도 CPU 차원에서 아무 문제 없이 잘 처리해 준다. 요즘 CPU 같았으면 그냥 예외 날리고 끝이었을 텐데.. 이 역시 메모리를 아끼기 위한 조치이다.

레지스터가 부족하면 나중에라도 더 보충하면 되지 않냐고?
레지스터는 추가로 더 꽂기만 하면 되는 메모리가 아니라 CPU 그 자체이다. 그걸 뒤늦게 확장한다는 건 CPU의 아키텍처, 세부 설계와 생산 라인이 다 바뀐다는 뜻이다. 컴파일러도 그에 맞춰 바뀌고 프로그램도 몽땅 다시 빌드되어야 추가된 레지스터 덕을 볼 수 있다. 사람으로 치면 가방 크기를 더 키우는 게 아니라 생물의 유전자 차원에서 손의 크기, 손가락 개수를 더 키우고 늘리는 것과 같은 엄청난 변화이다.

x86이 너무 지저분하다는 건 제조사인 인텔도 누구보다 잘 알고 있었기 때문에 과거 2000년대 초, 64비트 CPU를 내놓는 김에 애플처럼 하위 호환성을 싹 버리고 현대적인 디자인 트렌드를 따라 과감한 물갈이를 하려 했다.
마소 역시 새천년 Windows 2000에 맞춰 64비트 에디션을 당당히 내놓으려고 벼르고 있었다. Windows SDK 헤더 파일에서 INT_PTR, INT64 이런 typedef가 등장하고 GetWindowLong이 GetWindowLongPtr로 감싸진 게 이 시기의 준비 작업이었다.

하지만 모두의 예상을 깨고 IA64 Itanium라는 새 아키텍처는 CPU와 컴파일러 개발이 제대로 되지 않고 호환성도 안습했기 때문에 철저히 망하고 실패했다.
결국 지금은 기존 x86을 그대로 수용하면서 Itanium보다 훨씬 더 현실과 절충한 x86-64라는 다른 아키텍처를 기반으로 64비트 컴퓨터가 쓰이게 됐다. 이 아키텍처는 인텔이 아니라 경쟁사인 AMD가 최초로 개발했다.

Windows 2000은 과거 NT 3~4 시절에 지원했던 한물 간 구형 CPU들의 지원은 다 끊었고(Alpha, PowerPC, MIPS 등), IA64는 베이퍼웨어이고, 지금 같은 ARM이나 x64는 아직 안 나왔다 보니 NT로서는 이례적으로 사실상 x86 전용으로만 출시되어야 했다.

그런데.. 인텔 x86이 저렇게 메모리 아끼려고 CPU 본연의 효율까지 희생하면서 헝그리하게 설계된 건 과거 PC의 역사를 살펴보면 충분히 이해가 된다.
32비트 80386 CPU가 이미 1985년에 개발됐는데도 Windows NT, OS/2 같은 이상적인 32비트 운영체제의 도입과 보편화가 10년 가까이 너무 늦었고 Windows 9x 같은 요물이 몇 년간 쓰여야 했던 이유는 32비트 가상 메모리를 운용하고도 남을 정도로 컴의 메모리가 충분치(못해도 수~십수 MB) 못했기 때문이다. (CPU 말고 그래픽 카드는 1987년에 VGA가 개발되자 못해도 2~3년 안으로 프로그램들이 다 지원하기 시작함)

64비트로 넘어갈 때도 마찬가지다. IA64가 개발되던 1990년대 말엔 아직 가정용 컴의 메모리는 100~200MB대에 불과했다. 32비트를 벗어나야 할 이유가 전혀 없었다. 64비트 CPU는 대용량 데이터 처리 분야에서 속도가 좀 더 올라갈지는 모르지만, 같은 명령과 데이터를 수행하더라도 메모리 소모가 훨씬 더 많아지는 건 피할 수 없었다. 이러니 가정용 PC에서 64비트의 대중화는 Windows 2000/XP 시기는 어림도 없고, 본격적으로 램 용량이 4GB를 넘어선 2000년대 후반 Vista/7급은 돼서야 이뤄지게 됐다.

Posted by 사무엘

2017/12/11 08:31 2017/12/11 08:31
, ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1436

Trackback URL : http://moogi.new21.org/tc/trackback/1436

Comments List

  1. 비밀방문자 2017/12/11 18:28 # M/D Reply Permalink

    관리자만 볼 수 있는 댓글입니다.

    1. 사무엘 2017/12/13 00:42 # M/D Permalink

      우와.. 펫졸드 아저씨가 Windows 프로그래밍 책만 썼는 줄 알았는데,
      역시 올드 타이머 프로그래머답게 컴퓨터라는 기계가 밑바닥에서 처음부터 만들어져 온 과정을 고찰한 입문서도 몇 년 전에 썼구나?
      아주 흥미로운 내용일 것 같고 나도 책 내용이 궁금해진다? 우와아앙??

  2. 경헌 2017/12/12 19:17 # M/D Reply Permalink

    윗 댓글의 책이 뭘지 저도 알 것 같군요 ㅎㅎ
    오랜만에 생각난 김에 다시 한 번 읽어봐야 겠습니다.

    레지스터 - 캐시 - 메모리 - 디스크의 메모리 계층에서, 반드시 가격만이 용량을 결정한 요소인가 하는 의심이 들더군요.
    레지스터나 캐시의 경우에는 필요 이상으로 크게 만들면 어쩔 수 없이 속도가 떨어지게 되는 구조상 문제도 있지 않을까 싶어요.

    그리고 최근 들은 세미나에서, 미래의 아키텍처에서는 3. 일반 메모리와 4. 하드디스크의 경계가 희미해져 갈 것이라는 이야기를 들었습니다. SSD 에서 시작해서 비휘발성 메모리가 점점 싸고 빨라지고 있기 때문인데, 굳이 프로그램을 휘발성 고속 메모리에 올리고 실행할 필요 없을 정도로 빨라지고 나면 OS 수준에서 많은 것들이 달라지게 되지 않을까 이야기 하더군요.

    1. 사무엘 2017/12/13 00:49 # M/D Permalink

      하하! 경헌 님도 대단하십니다. ^^
      레지스터와 캐시는 제가 그 정도 본질까지 논할 수 있는 실력이 못 됩니다만, 일반 메모리와 하드디스크는.. 흥미롭네요. 일반 메모리의 속도와, 하드디스크의 비휘발성에서 일장일단이 아니라 두 토끼를 다 잡는 메모리가 나온다면 두 계층 구분이 당연히 사라지겠죠.
      SSD 때문에 전통적인 조각 모음이라는 게 의미가 없어졌듯이, 그런 미래의 모델에서는 memory-mapped file이라든가 디스크 캐시라는 것도 개념이 재정립될 듯합니다.

Leave a comment

컴퓨터 프로그램이 뻗는 방식을 분류하면 크게 다음과 같이 정리된다.

1. 아무 뒤끝 없이 그냥 뻗음(crash)

제일 단순하고 흔한 형태이다. 코딩을 잘못해서 잘못된 메모리에 접근하다가 튕긴 것이다. 그 예로는 null 포인터(null로부터 유도된 인근의 잘못된 주소 포함), 초기화되지 않은 포인터, 초기화되지 않은 배열 첨자 인덱스, 이미 해제된 메모리 포인터 등 참 다양하다.
혹은 애초에 메모리를 할당하는데 할당량에 엉뚱한 값이 들어와서 뻗은 것일 수도 있다. 가령, 음수만치 할당은 저 문맥에서는 대체로 부호 없는 정수로 바뀌면서 도저히 감당 불가능한 엄청난 양의 메모리 요청으로 바뀌기 때문이다.

2. CPU 사용 없는 무한루프

단독으로 돌아가는 프로그램이 제발로 이렇게 되는 경우는 잘 없다. 이건 스레드 내지 프로세스 간에 서로 아귀가 안 맞는 상호 대기로 인해 deadlock에 걸려서 마취에서 못 깨어난 상황이다. 그러니 엄밀히 말해 무한루프보다는 무한대기에 더 가깝겠다.
굳이 커널 오브젝트를 직접 취급하지 않고 윈도우 메시지를 주고받다가도 이렇게 될 수 있다. 가령, 스레드 A가 타 프로세스/스레드 소속의 윈도우 B에다가 SendMessage를 해서 응답을 기다리고 있는 중인데, B는 또 스레드 A가 생성한 윈도우에다가 SendMessage를 했을 때 말이다. 요 데드락을 해소하려고 ReplyMessage라는 함수가 있다.

3. CPU 쳐묵과 함께 무한루프

종료 조건을 잘못 명시하는 바람에 loop에서 빠져나오지 못하는 경우이다. 부호 없는 정수형으로 변수를 선언해 놓고는 while(a>=0) a--; 이런 식으로 코딩을 해서 무한루프에 빠지는 경우도 있다. 얘는 그래도 다행히 메모리 관련 문제는 없는 상황이다.

4. stack overflow와 함께 뻗음

이건 단순 뺑뺑이가 아니라 재귀호출을 종료하지 못하고 비정상적으로 반복하다 이 지경이 된 것으로, 컴에 메모리가 무한하다면 3번 같은 무한루프가 됐을 상황이다. 하지만 현실에서는 물리적인 자원의 한계가 있고, 또 컴이 취급 가능한 메모리 주소 자릿수 자체도 무한하지 않기 때문에 언젠가는 뻗을 수밖에 없다.

재귀호출도 반드시 A-A-A-A-A... 이렇게 단일 함수만 쌓이는 게 아니라 마치 유리수 순환소수처럼 여러 함수 호출이 주기적으로 쌓이는 경우도 있다.
스택은 다음에서 다룰 heap 메모리와는 달리, 그래도 그 정의상 할당의 역순으로 회수되고, 회수가 반드시 된다는 보장은 있다.

5. 메모리 쳐묵과 함께 뻗음

이건 heap memory의 leak을 견디다 못하고 프로그램이 뻗은 것이다. loop 안에서 계속해서 leak이 발생하면 꽤 골치아프다. 또한, 금방 발견되는 leak은 그나마 다행이지, 프로그램을 몇 주, 몇 달째 돌리다가 뒤늦게 발견되는 것은 더 답이 없고 잡기 어렵다. 프로그램이 뻗은 지점이 실제로 문제가 있는 지점과는 전혀 관계 없는 곳이기 때문이다. 뭔가 컴파일 에러와 링크 에러의 차이와도 비슷한 것 같다.

요약하면, 메모리 쪽 문제는 가능한 한 안 마주치는 게 낫고, 마주치더라도 프로그램이 곧장 뻗어 주는 게 디버깅에 유리하다. 1과 5는 포인터를 대놓고 취급하지 않는 C/C++ 이외의 언어에서는 프로그래머가 직접 볼 일이 드물다.
요즘은 그래도 디바이스 드라이버 급이 아닌 평범한 양민 프로그램이라면 메모리 문제로 뻗는 경우 전적으로 혼자만 뻗지, 컴퓨터 전체를 다운시키는 일은 없으니 세상 참 좋아졌다. 이게 다 가상 메모리와 보호 모드 덕분이다.

Posted by 사무엘

2017/10/03 19:34 2017/10/03 19:34
, , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1412

Trackback URL : http://moogi.new21.org/tc/trackback/1412

Leave a comment

C/C++, 자바, 파이썬 등 프로그래밍 언어를 하나 배워서 초보 딱지를 뗄 정도가 되면, 프로그래밍을 할 줄 모르던 때보다 컴퓨터를 훨씬 더 유용하고 창의적으로 활용할 수 있게 된다. 초보 딱지를 뗐다는 건 한 변수로부터 복수 개 + 다중 계층 형태로 된 숫자나 문자열에 접근하는 '복합 자료형(composite type)'을 다룰 수 있고, 함수와 반복문과 재귀호출로 반복 절차를 구현할 수 있음을 의미한다. 거기에다 Windows API에 대한 약간의 지식이 필요하다.

뭐, C/C++보다 더 고수준 언어를 쓴다면 날포인터(raw pointer)를 써서 수동 메모리 관리까지 직접 다룰 일은 없겠지만, 거기는 거기 고유한 방식으로 리스트나 시퀀스처럼 복합 자료형을 제공하는 게 있을 것이다. 복합 자료형과 실행 시간 조건부 반복 및 분기가 튜링 완전한 계산 모델의 본질이며, 자연어로 치면 그냥 Hello world나 I am a boy를 넘어서 길고 복잡한 안은 문장과 이어진 문장을 자유자재로 구사하는 것과 같다.

모든 사람이 전산학과 코딩을 전공으로 삼아 생업 수준으로까지 할 필요는 전혀 없다. 굳이 번듯한 GUI 갖추고 제3자가 쓸 만한 번듯한 소프트웨어를 개발하는 경지에 이르지는 않아도 된다. 그냥 일상생활에서 내가 당면한 문제를 코딩으로 스스로 해결하는 '자가용' 프로그래밍 스킬만으로 충분하다. 원하는 웹사이트 내용을 크롤링 해서 텍스트를 추출하거나, 방대한 무슨 데이터 파일을 내 입맛에 맞게 변환· 가공하거나, 특정 시간대에나 주기적으로 컴퓨터로 하여금 특정 작업을 수행하게 하는 게 대표적인 예이다.

물론 프로그래밍을 공부하는 대신, 그런 일을 수행해 주는 유틸리티(특히 매크로 같은..)를 찾아서 사용법을 익히는 것도 방법이 될 수 있다. 그러나 본인의 경우는 간단한 건 그냥 직접 만들어 쓴다. 그게 더 빠르다.
옛날 직장에 다니던 시절엔 이튿날 아침 9시 3분 전에 회사 인트라넷에 접속해서 출근 도장을 자동으로 찍게 하는 프로그램을 짜 놓고 퇴근 후, 정작 나는 다음날 느긋하게 출근하기도 했었다. 이 정도 잔머리야 뭐 직업 프로그래머라면 완전 껌(piece of cake)일 것이고, 반대로 회사에서 작정하고 오토의 부정 사용을 단속하려 한다면 키보드 드라이버 차원의 보안 프로그램들로 직원들의 컴을 도배시켜 놓겠지만 말이다.

잡다한 서론이 좀 길어졌으니 본론으로 들어가도록 하겠다. 컴퓨터 프로그래밍에는 저렇게 고정된 입력에 대해서 언제나 고정된 답만 출력하는 작업 말고 의외로 재미있고 유용한 분야가 있는데, 바로 난수(random number) 생성을 이용한 시뮬레이션, 무작위 표본 추출 등이다.

이 글은 난수 생성 방법 자체에 대해 다루지는 않을 것이다. 그래도 말이 나왔으니 잠시 언급하자면, 난수란 그 정의상 등장 패턴을 예측할 수 없으면서(혹은, 몹시 어렵고) 각 숫자들의 등장 빈도에 치우침이 없어야 할 것이다. 파이나 자연상수 같은 유명한 무리수가 파면 팔수록 끝없이 생성하는 소수점들은 난수의 범주에 든다고 볼 수 있으려나 모르겠다.

품질 좋은 난수를 값싸고 빠르게 많이 생성하는 알고리즘에 대한 수요는 매우 많으며, 이건 정수와 관련된 응용 수학에서 매우 중요하게 다뤄지는 분야이다. 옛날에 CACM에서 Random numbers: good ones are hard to find라는 논문을 봤던 기억이 나는데... 거기는 그 정도 퀄리티의 논문이 그야말로 상상도 할 수 없을 정도로 옛날에(1988년!) 이미 게재되었다는 게 전율이 느껴진다.
시뮬레이션도 좋고 각종 게임도 좋지만 추첨 역시 단순 유흥이 아니라 그야말로 사람의 인생과 진로를 결정하는 매우 사무적이고 크리티컬한 분야에 쓰인다.

추첨의 가장 간단한 형태는 A명의 사람에게 B개의 물건을 무작위로 배분하거나(단, A>B) 그냥 B명을 무작위로 답정너 선발하는 것이다. 그리고 이를 일반화하면 단순히 "당첨 B개 vs 꽝 A-B개"라는 이분법적인 상태를 넘어서 3개 이상의 상태를 배분하는 것도 생각할 수 있다.
이런 추첨을 종이와 연필만으로 수행하는 대중적인 방법 중 하나는 사다리 게임이다. 이 정도 추첨이야 언제 어디서든 필요할 때 하라고 사다리를 무작위로 생성해 주는 스마트폰 앱도 진작에 나와 있다.

그러나 현실에서는 이보다 더 복잡한 조건을 주고 추첨을 해야 할 때도 있다. 조 추첨이 대표적인 예인데, 각 조별로 인원과 성별이 비록 조의 수로 나눠 떨어지지 않더라도 최대한 균일하게 유지돼야 하며, 그 밖에 구성원들별로 다른 내부 속성도 최대한 균일하게 유지돼야 한다.
본인은 고등학교 시절에 반 내지 학교 행사 때 테이블별 인원 추첨을 컴퓨터 프로그램을 짜서 실시한 적이 있다. 하긴, 반 편성 자체도 일단 컴퓨터가 뒤섞어 놓은 결과에다가 각 반 담임들이 보정을 해서 뽑는다고 들었다. 가령, 문제아들은 한 반에 몰리지 않고 최대한 서로 다른 반에 찢어지게 말이다.

그 뒤 본인은 최근에는 교회 청년부의 소그룹 기도 모임의 인원을 분기별로 새로 추첨해 주는 프로그램을 작성했다.
이 역시 기본적으로 조별 인원과 성별부터 균등하게 맞추지만, 거기에다가 모임에 활발히 참여하는 사람과 그렇지 않은 사람도 나눠서 특정 성향의 사람이 한 조에 너무 몰리지 않고 최대한 분산되게 하는 조건을 추가했다.
그리고 또 중요한 것으로, 동일 집안의 친형제· 친자매· 친남매는 같은 조에 결코 걸리지 않게 했다. 흥미롭지 않은가?

처음에 인원과 성별은 무조건 균등하게 나오게 틀을 먼저 짜서 했다. 그러나 나머지 필터링은 알고리즘으로 구현한 게 아니라 무식한 방법을 썼다. 추첨 결과가 조건을 전체 만족하는지 검사해서 안 그러면 그냥 빠꾸 시키고 될 때까지 추첨을 다시 한다. 그러니 이건 프로그램의 실행 종료와 성공 여부를 전적으로 난수 생성 알고리즘의 품질에다 맡기는 셈이다.

물론 이렇게만 해도 소규모 인원의 조편성 결과쯤이야 운이 나빠 봤자 몇십 번 정도 뺑뺑이 만에 답이 즉시 잘 튀어나온다. 허나, 진지한 프로그램이라면 추첨 결과에 anomaly가 존재하면 조의 인원을 무작위하게, 적절하게 교환하고 보정을 해서 그걸 해소해야 할 것이다. 난수 생성 결과와 무관하게 수행이 유한 시간 만에 끝난다는 게 보장되는 알고리즘으로 말이다.

더 나아가면 이렇게 추첨이라는 computation을 위한 범용적인 '로직 선언형 프로그래밍 언어'를 생각할 수 있을 것 같다. 어찌 보면 SQL처럼 select A from B where 같은 문법 구조를 가질 수도 있겠다. 10명의 인원에다 무엇을 배당하되 무엇과 무엇에는 무엇이 같아서는 안 되고..
마치 "A와 B의 사이에는 C가 있지 않다. C의 오른쪽에는 D가 있다." 이런 단서들 주고 나서 "A~D의 가능한 정렬 순서는 무엇인가?" 이런 문제를 풀듯이 추첨 조건을 쫙 명시할 수 있다.

모든 조건의 충족이 불가능하다면 무식하게 무한 루프에 빠지는 게 아니라 저 조건들만 분석해 보고는 일찌감치 "성립 불가능, 답 없음"이라고 에러가 깔끔하게 튀어나와야 한다.
조건들 중에는 일단 추첨 뒤에 사후 보정을 해야 하는 것도 있겠지만, 여러 가지 속성 변수들을 균등하게 분할하는 것은 변수의 개수만큼 n차원 공간을 만들어서 거기에다가 차곡차곡 무작위로 숫자들을 채워 넣는 선형대수학 같은 방법론을 동원해서 구현할 수도 있을 것 같다. 아무튼 추첨· 배분과 관련된 수학 패키지나 프로그래밍 언어 솔루션이 있는지 궁금하다.

그리고 다음으로.. 컴퓨터 추첨은 추첨 알고리즘에 인위적인 조작이 없다는 걸 어떻게 보장하느냐고 결과에 대한 불신이 있을 수 있다.
이걸 해소하기 위해서는 제3자 참관인을 두는 게 바람직할 듯하다. 그래서 1부터 N회 중 가추첨을 몇 번 할지를 결정하게 한 뒤, 그 횟수를 공언한다. 그리고 그 횟수만큼 그 사람이 실제로 추첨을 돌리고 N회째의 결과를 최종 결과물로 선택하는 것이 모두에게 공정할 것 같다.

프로그램을 개발하는 사람 입장에서는 몇 회째에 조작된 결과를 내놓아야 할지 알 수 없으며, 참관인은 자기가 원하는 추첨 결과가 나왔을 때가 아니라, 먼저 약속했던 횟수만큼만 가추첨을 돌리다가 최종 결과에는 승복해야 한다. 그리고 가추첨의 결과도 계속 공개되므로 각 가추첨의 결과가 충분히 무작위하지 않고 이상하다면 이의 제기가 가능하다.

빵 같은 걸 두 사람이 먹게 반으로 나눌 때, 한 사람은 칼로 빵을 나누고 다른 한 사람은 나눠진 결과물 중 원하는 것(= 더 큰 것)을 취사선택하게 한다면 그야말로 두 사람이 모두 만족하는 결과가 나올 수밖에 없을 것이다. 이와 비슷한 시스템을 구현하는 것으로 논란을 잠재우는 게 합리적이어 보인다.

Posted by 사무엘

2017/07/29 19:33 2017/07/29 19:33
, , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1387

Trackback URL : http://moogi.new21.org/tc/trackback/1387

Comments List

  1. 경헌 2017/07/30 05:05 # M/D Reply Permalink

    > 더 나아가면 이렇게 추첨이라는 computation을 위한 범용적인 '로직 선언형 프로그래밍 언어'를 생각할 수 있을 것 같다. 어찌 보면 SQL처럼 select A from B where 같은 문법 구조를 가질 수도 있겠다. 10명의 인원에다 무엇을 배당하되 무엇과 무엇에는 무엇이 같아서는 안 되고..
    > 마치 "A와 B의 사이에는 C가 있지 않다. C의 오른쪽에는 D가 있다." 이런 단서들 주고 나서 "A~D의 가능한 정렬 순서는 무엇인가?" 이런 문제를 풀듯이 추첨 조건을 쫙 명시할 수 있다.

    이거 프롤로그 언어가 딱일거 같은데요? ㅎㅎ

    흔히 아인슈타인 문제라고 하는 것 https://ko.wikipedia.org/wiki/%EC%95%84%EC%9D%B8%EC%8A%88%ED%83%80%EC%9D%B8%EC%9D%98_%ED%8D%BC%EC%A6%90

    이런걸 말 그대로 저 정보를 그대로 선언해서 풀 수 있으니까..
    조건을 몇 개 덜 주면 말씀하신대로 조건을 만족하는 모든 조합을 출력하는 식으로도 쓸 수 있을거 같네요.

    1. 사무엘 2017/07/30 14:44 # M/D Permalink

      네, 정확한 말씀이십니다. ^^ 프롤로그 언어 자체를 저렇게 추첨 내지 조합 나열식으로 활용할 수 있으려나 모르겠어요.
      답을 딱 구하는 건 방정식을 푸는 것이고, 조건을 덜 줘서 모든 조합 출력하는 건 부등식을 푸는 것과 비슷할 테니까요~
      아인슈타인의 퍼즐은 아마 아인슈타인 본인이 만든 문제는 아닌 것 같지만 그래도 유명하지요. 여기 홈페이지에도 제가 15년 넘게 전에 만들었던 백트래킹 문제 풀이 소스가 있습니다. http://moogi.new21.org/src4.htm

  2. 허국현 2017/07/30 15:42 # M/D Reply Permalink

    1. 폰 노이만은 이런 랜덤 관련 연구를 별로 안 좋아했다고 하네요. 도박의 느낌이 많아 나서인 것 같다는 평이 지배적입니다.

    2. 난수 관련 문제는 아니지만, 예전에 게임 개발에 한참 관심 있을 때, 그래픽 관련 논문들 출처 연도를 보다 보면 1970 같은 숫자도 나와서, "도대체 컬러 TV도 없을 것 같은 시절에 왜 그런 알고리즘에 관심을 가진 사람이 있었던 거지?"라는 생각을 해 본 기억이 납니다.

    3. Keyboard Hook을 쓰는 것보다는 훨씬 편하기 때문에 Python 등과는 별개로 Autohotkey는 배워 둘만 하다는 느낌이 들더라고요.

    1. 사무엘 2017/07/30 19:59 # M/D Permalink

      반갑습니다. ^^

      1. 폰 노이만은 인간 컴퓨터 괴수인 데다 순수 수학보다는 응용 수학의 달인이었는데.. 그러면 간단한 xor과 비트 rotation 연산만으로 아스트랄하게 펼쳐지는 암호화· 난수· 해쉬 함수 같은 바닥에서도 흥미를 갖고 펄펄 날았을 것 같은데 그건 좀 의외의 취향과 행적이네요. ^^
      하긴, 뉴턴도 직접 도박까지는 아니고 뭐 투자 잘못해서 돈 왕창 날리고 나서는 "과학 법칙은 복잡하더라도 분석과 파악이 되지만 사람 심리는 도저히 노답이다.." 학을 뗐다는 일화도 전해지죠.

      2. 3차원 그래픽 테크닉이라든가 Doom, Quake에서 사용하는 BSP 맵 자료구조 같은 것도 이론은 다 그 까마득한 옛날에 이미 연구된 것들이죠. 기계값이 서민들이 도저히 범접할 수 없을 정도로 비쌌던 그 시절에 그런 걸 연구한 사람들이 진정한 선구자들입니다.

      3. Windows 3.x 시절에 있었던 레코더 생각이 나네요. 개인적으로 키· 마우스 매크로 자동화는 마치 화면 캡처 기능만큼이나 운영체제 차원에서 유틸리티가 제공돼야 한다고 생각합니다만.. 오늘날 운영체제는 그런 기능이 빈약한 게 좀 아쉽습니다.

Leave a comment

오늘날 Windows에서 실행되는 모든 프로그램들.. exe, dll 따위는 잘 알다시피 portable executable이라는 형식으로 만들어져 있다. 하지만 이 파일 포맷도.. 처음 만들어지던 당시에 여전히 컴퓨터에서 현역이던 도스와 최소한의 호환성을 유지할 필요가 있었기 때문에, 맨 앞에 MZ로 시작하는 16비트 도스 헤더를 여전히 갖추고 있다.

호환성이란 게 딴 게 아니고, 도스에서 Windows용 프로그램이 실행됐을 때 컴퓨터가 다운되는 게 아니라 "이 프로그램은 도스용이 아닙니다" 같은 짤막한 에러 메시지라도 뜨게 하는 것 말이다.

옛날에 Win32s가 제대로 설치되지 않은 상태에서 32비트 프로그램을 Windows 3.1에서 실행했더니.. "상위 버전에서 실행해 주십시오 / Win32s를 다시 설치해 주십시오" 이런 말이 메시지 박스 형태로 뜨는 게 아니라 황당하게 This program cannot be run in DOS mode라고.. 지금 시스템이 아예 Windows가 아닌 듯한 자비심 없는 메시지가 도스창에 떴다. 20여 년 전에 그 인상이 무척 강렬했었다. 요즘은 32비트 OS에서 64비트 exe의 실행을 시도해도 에러 메시지가 그 정도로 막나가는 형태는 아니다.

Windows용 프로그램들은 빌드할 때 그렇게 도스에서 잘못 실행됐을 때를 대비해 짤막하게 대신 실행해 줄 도스용 일명 "stub" 프로그램을 링크 옵션으로 지정할 수 있다. 이름하여 /STUB. 이걸 지정하지 않으면 아까 같은 저런 짤막한 에러 메시지 한 줄만 찍는 기본 stub 프로그램이 들어간다.
16비트 시절에 Visual C++ 1.5x를 보면 그 예제 stub 프로그램 자체가 winstub.exe라고 있었다. 하지만 그 이후부터는 디폴트 stub 프로그램은 그냥 링커 내부에 내장되어 버렸는지 그런 게 따로 있지는 않다.

프로그램을 특수하게 빌드하면 그런 stub을 아예 전혀 집어넣지 않는 것도 가능하다. 맨 앞에 MZ, 그리고 0x3C 오프셋에 PE 헤더가 있는 지점만 들어있으면 되고 나머지 칸은 몽땅 0으로 채움. 심지어 PE 헤더가 0x3C 오프셋보다도 전에, 도스 EXE 헤더가 있어야 할 지점에서 바로 시작하는 것도 가능하다.

미래에 마소에서 빌드하는 EXE/DLL들은 번거로운 This program cannot be ... 메시지를 떼어내고 이렇게 만들어져 나올지도 모른다. 물론 이런 프로그램은 Windows 환경에서 실행하는 건 문제 없지만 만에 하나 어느 레트로 변태 덕후가 그걸 굳이 도스에서 실행해 보면 컴퓨터가 어찌 되는지 책임 못 지는 상태가 될 것이다.

반대로 기본 stub 대신에 꽤 규모 있는 16비트 프로그램을 집어넣어서 동일 EXE가 도스에서도 그럭저럭 기능을 하고 Windows에서도 GUI를 띄우며 제대로 실행되는 프로그램을 만든 경우가 있다. Windows 9x 시절엔 레지스트리 편집기가 그러했다. 이건 Windows에서 보기 드문 하이브리드 universal binary 형태의 프로그램인 것 같다.
16비트 프로그램이 자기 자신 EXE를 열어서 PE 헤더를 파싱해서 리소스 같은 걸 읽어들이는 코드가 같이 빌드되었다면.. 도스 파트가 나중에 합쳐진 Windows 파트와 더불어 한 리소스를 공유하는 형태로 실행될 테니 이 역시 무척 흥미로울 것이다.

이 시점에서 문득 궁금해졌다.
링커가 얹어 주는 기본 stub 프로그램은 명령어가 겨우 몇 바이트밖에 되지 않는다. 얘들은 무슨 의미를 갖고 있는지, 혹시 옛날 16비트 NE 시대와 지금의 PE 시대에 stub 프로그램에 차이가 있는지..?
그래서 오랜만에 도스 API와 8086 어셈블리 명령어 레퍼런스까지 찾아서 stub 프로그램을 분석해 봤다.

stub 프로그램의 코드는 이게 전부이다.

(1) 0E        PUSH CS
(2) 1F        POP DS
(3) BA 0E 00  MOV DX,000E
(4) B4 09     MOV AH,09
(5) CD 21     INT 21
(6) B8 01 4C  MOV AX,4C01
(7) CD 21     INT 21
"문자열"


(1), (2) 맨 앞의 PUSH와 POP은 데이터 세그먼트를 코드 세그먼트의 값과 맞추는(DS=CS) 일종의 초기화이다. 스택에다가 CS 값을 넣은 뒤 그걸 DS로 도로 가져오는 거니까.
지금 이 프로그램은 화면에다 찍을 에러 메시지도 기계어 코드와 정확하게 같은 영역에 있으므로 저건 수긍이 가는 조치이다.

(3) 그 다음으로 DX 레지스터에다가 16진수로 0xE, 즉 14를 기록한다. 저 stub 프로그램은 길이가 정확하게 14바이트이다. 이 값은 프로그램의 시작 지점을 기준(0)으로 해서 그로부터 14바이트 뒤에 있는 문자열을 가리킨다.

(4) AX 레지스터의 high byte에다가 9를 기록한다.

(5) 이렇게 기록된 AX와 DX 레지스터 값을 토대로 0x21 인터럽트를 날려서 도스 API를 호출한다. 도스 API 중 9는 DX가 가리키는 주소에 있는 문자열을 화면, 정확히는 표준 출력에다가 찍는 기능을 수행한다.
그런데 굉장히 기괴한 점이 있는데.. 얘가 받아들이는 문자열은 null-terminated가 아니라 $-terminated여야 한다!

믿어지지 않으면 아무 Windows용 EXE/DLL이나 헥사 에디터로 열어서 앞부분의 에러 메시지 텍스트가 무슨 문자로 끝나는지를 확인해 보시기 바란다.
왜 그렇게 설계되었는지 모르겠다. 파일이나 디렉터리 이름을 받는 도스 API들은 당연히 null-terminated 문자열인데 말이다.

(6) 그 다음, AX 레지스터에다가 0x4C (high)와 0x1 (low)을 기록하고..

(7) 또 도스 API를 호출한다. 0x4C는 프로그램을 종료하는 기능을 하며, 종료와 동시에 low byte에 있는 1이라는 값을 에러코드로 되돌린다. 정상 종료는 0인데 1은 뭔가 오류와 함께 종료되었음을 나타낸다.
사실, 도스 API 레퍼런스를 보면 AH 값으로 0도 프로그램을 종료시키는 역할을 하는 듯하다(도스 1.0때부터 최초). 하지만 모종의 이유로 인해 그건 오늘날은 사용이 별로 권장되지 않으며 0x4C가 원칙이라 한다(도스 2.0에서부터 추가됨).

이렇게 분석 끝. 정말 간결 단순명료하다.
참고로 도스 EXE에서 헤더를 제끼고 기계어 코드가 시작되는 부분은 0x8~0x9 오프셋에 있는 unsigned short값에다가 16을 곱한 오프셋부터이다. 가령, 거기에 04 00 이렇게 적혀 있으면 0x40 오프셋부터 디스어셈블링을 해 나가면 된다. EXE는 헤더에 고정 길이 구조체뿐만 아니라 가변 길이인 '재배치 섹션'이 나오고 그 뒤부터 코드가 시작되기 때문이다.

그럼 과거 16비트 Windows에서 쓰이던 stub은 어떻게 돼 있었을까?
거의 차이가 없긴 한데, 문자열이 들어있는 위치와 얘의 주소를 전하는 방법이 달랐다.

(1) E8 53 00  CALL 0056
"문자열"
20 20 20 20 .. padding 후
(2) 5A        POP DX
(3) 0E        PUSH CS
(4) 1F        POP DS
(5) B4 09     MOV AH,09
(6) CD 21     INT 21
(7) B8 01 4C  MOV AX,4C01
(8) CD 21     INT 21


(1) 맨 먼저 JMP도 아니고 웬 CALL 인스트럭션이 나온다. 기계어로 표기할 때는 인자값이 0x53이어서 3바이트짜리 자기 자신 인스트럭션 이후에 0x53바이트 뒤로 가라는 뜻이 되는데, 영단어로 바꿔서 표기할 때는 자기 자신 원래 위치 기준으로 0x56바이트 뒤가 된다. 이 위치는 그냥 바로 다음 (2) 명령이 있는 곳과 같다.

(2) 함수 호출을 했는데 RET를 하는 게 아니라 스택을 pop하여 DX 레지스터에다 가져온다. 그렇다. 아까 그 call에 대한 복귀 주소에 문자열이 담겨 있으니, 아까 같은 하드코딩이 아닌 요런 방식으로 문자열 주소를 얹었다.

(3) (4) 이제부터는 아까처럼 DS = CS 해 주고,

(5)~(8) 아까와 동일. 문자열을 찍은 뒤 프로그램을 종료한다.

이런 초간단 초미니 프로그램은 exe가 아니라 com 형태로도 만들지 말라는 법이 없어 보인다. com은 그 어떤 헤더나 시그니처도 없이 첫 바이트부터 바로 기계어 코드와 데이터를 써 주면 되는.. 정말 원시적이기 그지없는 바이너리 덤프일 뿐이기 때문이다. 빌드 날짜, 버전, 요구하는 아키텍처나 운영체제 등등 그 어떤 부가정보도 존재하지 않는다.

요즘 프로그래밍 언어들이 기본 제공하는 런타임들의 오버헤드가 너무 크다 보니, 이에 대항하여 세상에서 제일 작은 "Hello world" 프로그램 이런 것에 집착하는 덕후들이 있다. Windows 프로그램의 경우 프로그램을 특수하게 빌드하여 CRT 라이브러리는 당연히 떼어내고, 코드와 데이터도 한 섹션에다 우려넣고, 거기에다 후처리까지 해서 단 몇백 바이트만으로 MessageBoxA(NULL, NULL, "Hello, world!", 0) 하나만 호출하는 프로그램을 만든 예가 있다.

그러나 이런 것들도 com 앞에서는 몽땅 버로우 타야 한다. 얘는 아예 파일 포맷 자체가 없으니까. 이 이상 더 줄일 수가 없다. com 형태로 만든 Hello world 프로그램은 겨우 20몇 바이트가 전부이다.
무슨 명령어를 내렸는지 기억은 안 나지만 컴퓨터를 재시작시키는 com 파일이 있었는데, 얘는 크기가 겨우 2바이트에 불과했다.

(1) BA 0C 01  MOV DX,010C
(2) B4 09     MOV AH,09
(3) CD 21     INT 21
(4) B8 01 4C  MOV AX,4C01
(5) CD 21     INT 21
그 뒤에 "Hello, world!$" 같은 문자열. 따옴표는 제외하고.


com은 exe처럼 코드/데이터 세그먼트 DS=CS 따윈 전혀 신경 쓸 필요 없이, 바로 본론부터 들어가면 된다. 그 대신 com은 16비트 단일 세그먼트 안에서 코드와 데이터 크기 한계가 모두 64K라는 치명적인 한계를 갖는다. 메모리 모델로 치면 그 이름도 유명한 tiny 모델 되겠다. 애초에 exe가 16비트 CPU에서 저 한계를 극복하고, 또 멀티태스킹에 대비하여 재배치도 가능하게 하려고 만들어진 포맷이기도 하다.

아, 아주 중요한 사항이 있다. com에서는 첫 256바이트, 즉 0x100 미만의 메모리 주소는 시스템용으로 예약되어 있어서 사용할 수 없다. 내 코드와 데이터는 0x100부터 시작한다. 그렇기 때문에 저 프로그램의 코드 크기는 12바이트이고, 문자열은 0xC 오프셋부터 시작하긴 하는데 거기에다가 0x100을 더해서 DX에다가는 0x10C를 써 줘야 한다.

Windows PE에다 비유하자면 0x100이 고정된 base address값인 셈이다. 그리고 DX의 값은 그냥 VA이지 RVA가 아니다.
과거에 굴러다니던 exe/com 상호 변환 유틸리티들이 하던 주된 작업 중 하나도 이런 오프셋 재계산이었다. 그리고 com에서 exe라면 모를까 더 넓은 곳에서 좁은 곳으로 맞추는 exe -> com은 아무 exe에 대해서나 가능한 게 물론 아니었다. (단일 세그먼트 안에서만 놀아야..) 과거 도스에 exe2bin이라는 외부 명령어가 있었는데 걔가 사실상 exe2com의 역할을 했다.

아무튼, 저 바이너리 코드와 문자열을 헥사 에디터를 이용해서 입력한 뒤, 파일을 hello.com이라고 명명하여 저장한다. 이걸 도스박스 같은 가상화 프로그램에서 도스 부팅하여 실행하면 신기하게도 Hello, world!가 출력될 것이다.
고급 언어를 사용하지 않고 컴파일러 나부랭이도 전혀 동원하지 않고 가장 원초적인 방법으로 나름 네이티브 실행 파일을 만든 것이다. 사용 가능한 코드와 데이터 용량이 심각하게 작다는 것과, 요즘 64비트 Windows에서는 직통으로 실행조차 할 수 없다는 게 문제이긴 하지만. (네이티브 코드라는 의미가 없다~!)

이런 식으로 컴퓨터에 간단히 명령을 내리고 램 상주 프로그램이나 바이러스 같은 것도 만들기 위해 옛날에는 debug.com이라는 도스 유틸리티가 요긴하게 쓰였다. 간단한 어셈블러/디스어셈블러 겸 헥사 에디터로서 가성비가 뛰어났기 때문이다. edlin 에디터의 바이너리 버전인 것 같다.

오늘날 어셈블리어라는 건 극소수 드라이버/컴파일러 개발자 내지 악성 코드· 보안· 역공학 같은 걸 연구하는 사람들이나 들여다보는 어려운 물건으로 전락한 지 오래다. 하지만 이것도 알면 디버깅이나 코드 분석에 굉장한 도움이 될 듯하다.
디스어셈블리 자체는 주어진 규칙대로 바이트 시퀀스를 몇 바이트씩 떼어서 명령어로 분해해 주는 비교적 간단한 작업일 뿐이다. 파서(parser)가 아니라 스캐너(scanner) 수준의 작업만 하면 된다.

하지만 디스어셈블리가 골치 아프고 귀찮은 이유는 코드의 첫 실행 지점을 정확하게 잡아서 분해를 시작해야 하며, 그래도 어느 게 코드이고 어느 게 데이터인지가 프로그램 실행 문맥에 의해 시시각각 달라지고 무진장 헷갈리기 때문이다. 데이터는 백 날 디스어셈블링 해 봤자 아무 의미가 없고, 오히려 코드의 분석에 방해만 된다. 이런 역공학을 어렵게 하기 위해서 디스어셈블러를 엿먹이는 테크닉도 보안 분야에는 발달해 있다.
하긴, 코드와 데이터가 그렇게 경계 구분 없이 자유자재로 변할 수 있는 게 "폰 노이만 모델 기반의 튜링 기계"가 누리는 극한의 자유이긴 하다.

Posted by 사무엘

2016/12/17 08:34 2016/12/17 08:34
, , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1306

Trackback URL : http://moogi.new21.org/tc/trackback/1306

Leave a comment

오옷, 지금까지 내 블로그에서 데이터베이스에 대한 얘기가 거의 없었던 것 같다.
오늘날 정보화· 컴퓨터 세상의 근간을 담당하는 핵심 소프트웨어 기술을 꼽자면 (1) 운영체제(!!), (2) 컴파일러(컴퓨터에서 돌아가는 모든 프로그램들을 생성..), (3) 손실/무손실 압축 알고리즘, 그리고 (4) DB엔진이지 싶다. 딱히 무순으로 나열한 것임.

요즘은 전국민의 신분 근황, 학생들의 모든 학적 정보, 카드 거래 내역, 병원 진료 내역 등등등~ 모든 기록과 행적이 전산화됐다.
그리고 저기서 전산화라는 건 곧 DB화를 의미한다. DB 엔진 없이는 이 복잡한 세상이 돌아갈 수 없는 지경이 된 지 오래다. 또한 key-value 개념부터 시작해 삼라만상의 정보들을 다 표와 표를 융합해서 구축한다는 '관계형'이라는 모델, 그리고 정규화 계층 같은 DB 이론도 깊이 들어가면 생각보다 굉장히 심오하고 복잡하다.

똑같이 총이라 해도 권총부터 시작해 소총, 중기관총, 대포까지 다양한 크기가 있듯이 DB 엔진이라는 것도 스케일이 생각보다 매우 다양하다.
네트워크를 통해 들어오는 수백~수만~수백만 건의 동시 접속 트랜잭션을 소화하면서 방대한 양의 데이터를 극도의 안정성(그 대신 성능 오버헤드도..)을 보장하면서 처리하는 대형 DB 엔진이 있다.
이런 건 일반 사용자가 개인용 PC에서 돌릴 일은 없는 물건이다. 오라클 내지 MS SQL Server 같은 프로그램의 제일 고급 에디션이 이 범주에 해당할 것이며 이런 건 가격도 왕창 비싸다.

MySQL은 저 정도로 방대한 스케일은 아니지만 원격· 다중 접속을 지원하고 로컬 내지 중소규모 웹 서버에서 굴리는 용도로 가성비가 아주 좋다. 게시판이나 블로그 엔진들이 컨텐츠를 얘를 기반으로 구축하곤 한다.

MS Office에 포함돼 있는 Access 정도로 가면 다중 접속은 이제 없고, 서버가 아닌 클라이언트 지향 DB가 된다. 개인용 컴퓨터에서 엑셀로 처리하기엔 좀 방대한 양의 데이터를 엑셀보다 더 프로그래밍 지향적으로 전문적으로 처리하는 도구로 격이 더 낮아진다. 예전에 Visual C++ 책을 봐도 DB 관련 API는 꼭 한 챕터가 할당돼 있었으며, ODBC는 큰 DB, DAO는 좀 작은 DB라고 봤었다.

개인적으로는 성경을 DB로 구축하니 좋았다. 성경은 신구약 전체가 31000구절쯤 되고 역본을 10여 개 갖고 있으면 구절 수가 몇십만 개에 달한다. 그리고 내가 원하는 구절만 쿼리를 날려서 찾는 건 아무래도 스프레드 시트보다는 응당 DB가 제격이다.

또한, 먼 옛날에 컴퓨터 학원에서 dBase III+를 배우던 추억이 떠오른다. 얘도 그 당시로서는 Access에 준하는 체급의 개인용 DBMS라 볼 수 있겠다. SQL이 아닌 독자적인 문법 기반이었고, 명령 프롬프트 모드도 있고 메뉴를 띄워서 DB 파일을 관리하는 assist 모드도 있어서 UI가 독특했다. 또한 dBase가 생성하던 DBF 파일은 도스 시절에 아래아한글도 전화번호부에서 사용하고 DB Viewer를 제공할 정도로 옛날에 꽤 대중적인 파일 포맷이었다.

여느 워드 프로세서나 스프레드 시트와는 달리, DB 프로그램에서는 각 데이터에 속하는 속성들을 자료형과 크기까지 꽤 까다롭게 미리 지정해 놓고 데이터를 넣어야 한다. 프로그램 코딩을 할 때 말고 '자료형'이라는 개념을 따지고 생각해야 하는 분야는 아마 DB밖에 없지 싶다.

사실은 프로그래밍 언어 중에도 자료형이 엄격하지 않고 귀걸이 코걸이 식으로 변할 수 있는 언어가 있다. 그리고 DB 자료형은 엔진에 따라 다르긴 하지만 프로그래밍 언어의 그것과는 달리 딱히 기계 친화적으로 지정하지 않아도 되는 경우가 있다. 숫자형의 표현 범위를 2진법이 아닌 10진법 기준 자릿수로 지정하는 것처럼 말이다.
전화번호는 절대로 숫자형으로 지정하지 말고 문자열형으로 지정해서 넣어야 한다고 학원 선생님에게서 들은 기억이 남아 있다.

"명령줄 기반 + UI + 반쯤 절차형 프로그래밍 환경"이라는 점에서는 이런 DB 프로그램은 매쓰매티카 같은 수학 패키지와도 구조가 비슷한 구석이 있는 것 같다. 아무나 함부로 접근하기는 어렵다는 공통점도 있고 말이다.

그에 비해 엑셀은 어떤가? 대용량 데이터를 취급하는 성능은 DBMS보다 뒤쳐지고, 수식 계산은 수학 패키지에, 비주얼과 레이아웃 기능은 워드 프로세서에 밀린다. 엑셀은 심벌 연산이나 임의 자릿수 계산 기능이 없으며(수학 패키지), 성능을 위해 위지윅(워드 프로세서)도 포기했다.

그럼에도 불구하고 엑셀은 이들 이념을 어중간하게 절충해서 얻은 접근성과 성능, 가성비 덕분에 일반 사용자에게 최고의 업무 처리 앱이 되었다고 볼 수 있다. 일종의 포지셔닝을 잘해서 승리자가 됐다. 한 값이 바뀌었을 때 관련된 셀의 값들이 연달아 쫙 바뀌는 동적인 문서를 손쉽게 만들 수 있는 게 최고의 강점인 듯하다. 또한 피벗테이블/차트는 SQL 같은 거 하나도 몰라도 SELECT 쿼리에서 특히 GROUP BY를 적절하게 구현해 줬다고 볼 수 있다.

DBMS는 굳이 사람만 쓰는 건 아니고 다른 컴퓨터 프로그램이 로컬에서 내부적으로 사용하기도 한다. 에.. 그러니까, 사람이 관리하는 데이터 말고 프로그램이 자기 혼자만 취급하는 데이터를 관리할 목적으로 말이다. 이런 데에 미들웨어 컴포넌트처럼 쓰이는 DB 엔진은 덩치가 더욱 작고 백업· 응급 복구 같은 안전 기능이 없는 대신, 크기· 성능 오버헤드가 더욱 작고 빠르다.

예전에 파일 포맷에 대해서 글을 쓴 적이 있었다. 내 프로그램이 테이블 형태이고 수정이 빈번한 몇백만 개의 대용량 데이터를 다루는데, 파일 포맷을 새로 만들기는 심히 귀찮고 그렇다고 단순 선형적인 바이너리/텍스트 컨테이너 포맷을 쓰기에는 성능이 우려된다면, 범용성으로 인한 약간의 오버헤드를 감수하고라도 저런 내장형 소형 DB를 얹는 게 좋은 선택이 될 수 있다.

괜히 파일 내부에서 골치 아픈 청크가 어떻고 헤더가 어떻고 데이터를 바이너리 비트 수준에서 신경 쓸 필요 없이, 그냥 테이블 스키마.. 이건 프로그래밍 언어로 치면 C/C++ 쓰던 게 아주 고수준 언어로 바뀐 것과도 같다. DB 구조 자체가 일종의 파일 시스템에 대응하니까.

특히 데이터 전체를 무식하게 메모리에 다 올려서 작업하는 형태가 아니라면 DB의 가성비가 더욱 올라간다. 요즘 시대에 다 차려져 있는 밥상인 검증된 오픈소스 솔루션을 놔두고 개발자가 B+ 트리 같은 거 일일이 구현하면서 삽입 삭제 수정 케이스를 일일이 테스트 할 이유가 없기 때문이다.

이런 컴퓨터지향적인 DB는 DB가 하는 본연의 작업에다가 비교/정렬/데이터 변형 알고리즘 같은 일부 핵심 작업만 내가 custom으로 작성한 함수로 대체할 수 있어서 대단히 강력하고 편리하다. 당연히 C/C++로 작성하여 네이티브 코드로 빌드한 함수로 말이다. 파이썬이나 Lua처럼 C/C++ glue에 뛰어난 고급 언어가 있듯, glue에 최적화된 DBMS도 응당 있다.

Visual Studio의 경우 인텔리센스 엔진이 ncb 자체구현 DB를 쓰던 것이 2010부터는 자사의 SQL Server "Compact Edition" DB 기반으로 바뀐 것으로 유명하다. 그런 건 DB를 사용하기 꽤 적절한 용례로 보인다. C++ 문법이란 건 앞으로 또 뭐가 생기고 어떻게 변할지 모르는데 그런 것에 대응하는 것도 파일보다는 DB 지향이 더 유리하겠다.

MS 것 말고도 이 바닥의 유명한 오픈소스 소형 DBMS로는 SQLite가 있다. 리처드 힙이라는 아저씨가 만들었는데, 그냥 오픈소스로도 모자라 골치아픈 LGPL, MIT 라이선스 그딴 것조차 거부하고 소스를 걍 public domain으로 뿌렸다..;;; 그러면서 "님이 받은 만큼 님도 남에게 베풀어 주세요"를 저작권 notice랍시고 적은 게 전부이고.. 천재에다 신자이고 굉장한 대인배이신 듯하다.

The author disclaims copyright to this source code. In place of a legal notice, here is a blessing:
- May you do good and not evil.
- May you find forgiveness for yourself and forgive others.
- May you share freely, never taking more than you give.


모질라 재단의 이메일 클라이언트 유틸인 ThunderBird는 워낙 대용량 편지함을 관리하다 보니 내부 파일이 SQLite DB인 듯하며, 안드로이드 OS에서도 얘를 적극 활용 중이라고 한다. 그러고 보니 소형 DB들은 MS것과 오픈소스 모두 제품명에 compact, lite라는 '꼬마'를 나타내는 단어는 꼭 들어가 있다.

본인도 회사에서 SQLite를 좀 다룰 일이 있었다.
SQLite는 코드가 다양한 플랫폼에서 다양한 문자 인코딩(UTF-8, UTF-16 빅/리틀/디폴트)에 대비하여 API가 굉장히 세심하게 설계된 게 인상적이었다. 하긴, 인코딩에 따라 한글 같은 건 글자 수가 달라져 버리니 정보량에 매우 민감한 DB에서 그걸 민감하게 다루지 않을 수가 없다. 간단하게 단일 문자열로 통합· 추상화가 가능하지 않다는 얘기다.

콜백 함수는 자신이 받고 싶은 문자열의 형태를 지정해 줄 수 있으며, 콜백 함수 자체의 인자는 char도, wchar_t도 아닌 const void*로 돼 있다.
그리고 DB 내부에서 사용하는 문자열뿐만 아니라 열고 싶은 DB 파일을 지정하는 것도 16비트 문자열형 버전이 따로 있는데, 이건 Windows처럼 16비트 문자열을 네이티브로 쓰는 OS에서 CreateFileW 같은 W API를 쓰면서 제 성능을 낼 수 있게 한 배려로 보인다.

다음은 DB와 관련된 여러 문자열 처리 관련 잡설들이다.

1. 정렬

프로그래밍 언어들이 제공하는 문자열 비교는 정말 단순무식하게 숫자 비교의 연장선으로서 각 문자들의 코드값 비교 그 이상도 이하도 아니다. 허나 실생활에서는 오름차순/내림차순부터 시작해 대소문자 구분, 언어 정보를 고려한 비교 같은 복잡다양한 옵션이 필요하다.

대중적이고 자주 쓰이는 옵션은 SQL에서도 언어 차원에서 (1) 옵션을 제공한다. 하지만 좀 더 복잡한 정렬을 위해서는 값을 그대로 비교하는 게 아니라 (2) 사용자가 변조한 값을 비교한다거나 (3) 아예 비교 함수 자체를 customize할 수 있어야 한다.
물론 (3)만 있어도 (1)과 (2)는 다 처리가 가능하니 C 언어의 qsort 함수는 비교 함수만 인자로 받는다. 그러나 파이썬의 정렬 함수는 (1)~(3)까지 다양한 방식으로 운용 가능하다. SQL은 collation이라는 개념으로 정렬 알고리즘 자체를 customize할 수 있다.

2. 토큰화

구분자를 사이에 두고 여러 문자열들이 뭉쳐 있는 문자열을 토큰화해서 문자열(단어)들의 리스트로 뽑아내는 건 탈출문자 인코드/디코드만큼이나 이 바닥에서 굉장히 흔하게 행해지는 작업인 것 같다. 파이썬의 경우 split이라는 메소드가 있다.

그런데 토큰화라는 게 두 부류가 있다. 하나는 구분자가 whitespace 부류이기 때문에 "A    B"나 "A B"나 똑같이 A와 B로 분간되는 것이다. A와 B 자체는 빈 문자열이 될 수 없다.
다른 하나는 구분자가 콤마나 세미콜론 같은 부류이며, 한 구분자가 정확하게 한 아이템만을 분간한다. A,,,B라고 쓰면 A와 B 사이에 빈 문자열이 두 개 더 걸려 나온다..

C가 제공하는 오리지널 strtok는 컨텍스트를 받는 인자가 없어서 (1) 토큰 안에서 또 토큰 구분을 할 수 없으며 멀티스레드 환경에서 사용하기에도 위험하다. 그뿐만이 아니라 얘는 (2) whitespace형 토큰화만 지원하기 때문에 콤마형 토큰화에는 사용할 수 없다는 것도 단점이다. 그래도 뭔가 문자열을 또 복사하고 생성하는 게 없고 성능 하나는 나쁘지 않기 때문에 컨텍스트 인자만 추가해 주면 여전히 유용한 구석은 있다.

DB를 텍스트 형태로 덤프 백업하면 그냥 csv 형태로만 뱉는 게 아니라, 그대로 SQL을 실행만 하면 DB의 재구성이 가능하게 INSERT INTO xxx VALUES가 붙은 형태로 백업되는 것도 많다. DB 스키마는 그냥 CREATE TABLE ... 형태가 될 것이고.
코드와 데이터의 경계가 모호하다. DB 백업도 뭔가 JSON 같은 포맷과 연계 가능하지 않을까 하는 생각이 잠시 들었다.

3. 검색어의 전처리

SQL로 문자열을 검색하고 싶으면 그 이름도 유명한 LIKE 연산자를 쓰면 된다. 어지간한 프로그래밍 언어라면 함수 형태로 구현되었을 기능이 SQL에서는 연산자이다.
얘는 정규 표현식과 같지는 않은데 반쯤은 정규 표현식을 닮은 문법을 지원하여, A LIKE B는 A가 B라는 패턴을 만족하는지 여부를 되돌린다. 0개 이상의 임의의 문자열을 뜻하는 와일드카드가 *가 아니라 %이다. XXX로 시작하는 문자열, 끝나는 문자열, 중간에 XXX가 포함된 문자열 같은 게 다 이걸로 커버 가능하다.

그런데 탈출문자/와일드카드가 존재하는 모든 문자열 체계가 그렇듯이 그 탈출문자 자체는 어찌 표현하느냐가 또 문제가 된다. 이를 위해 SQL에서는 A LIKE B 다음에 ESCAPE C라고, '필요한 경우' 탈출문자를 사용자가 지정해 줄 수 있다. 그래서 \%, \_ 이런 식으로 와일드카드 자체를 표현할 수 있다. 탈출문자 자체는 역시 그 탈출문자를 두 번 찍으면 표현 가능.
탈출문자로는 C/C++처럼 역슬래시를 써도 되지만, 다른 걸 지정해 줘도 된다. SQL은 의외로 이런 데에 유도리가 있다. LIKE는 뒤의 ESCAPE와 합쳐져서 삼항 연산자 역할도 한다고 생각하면 되겠다.

다음으로, SQL에서 문자열 상수(리터럴)는 작은따옴표 또는 큰따옴표로 모두 표현 가능하다. 문자열 내부에 작은따옴표가 있으면 큰따옴표로 둘러싸면 되고, 그 반대의 경우를 사용해도 된다. 그런데 고약하게 문자열 내부에 두 종류의 따옴표가 모두 존재한다면 그 따옴표 자체는 따옴표를 두 번 찍어서 표현하면 된다. 이건 LIKE 연산자가 아니라 SQL 파서 자체에서 인식하는 탈출문자이므로 LIKE 연산자가 인식하는 탈출문자와는 성격이 다르다. C/C++로 비유하자면 위상이 \ 탈출문자와 printf % 탈출문자와의 관계와도 같다.

쿼리 내부에서 따옴표 탈출문자의 처리는 매우 철저하게 해야 한다. 안 그러면 이건 SQL injection이라는 보안 취약점이 되기 때문이다. SELECT ... WHERE id='A' 이런 식으로 쿼리를 작성했는데 A 내부에 또 작은따옴표가 존재해서 문자열 상수를 종결해 버리고, 사용자가 입력한 문자열이 쿼리의 실행에 영향을 줄 수 있다면.. WHERE 절을 언제나 true로 만들 수 있고 DB 내용을 몽땅 유출할 수 있기 때문이다. 이런 사건이 대외적으로는 '해킹' 내지 '개인정보 유출'이라고 보도된다.

Posted by 사무엘

2016/12/11 08:38 2016/12/11 08:38
,
Response
No Trackback , 2 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1304

Trackback URL : http://moogi.new21.org/tc/trackback/1304

Comments List

  1. 허국현 2016/12/16 11:39 # M/D Reply Permalink

    저작권 문구가 정말 인상적입니다.

    비슷한 성경 구절들이 연상될 정도네요.

    1. 사무엘 2016/12/16 12:26 # M/D Permalink

      네~ 정말 대단하지요. ^^ 개인 홈페이지를 찾아가 보면 알겠지만, 저분은 소수 민족 언어 성경 번역에도 관심이 있을 정도로 실제로 신자이기도 합니다.

Leave a comment

등산 이야기만 몇 콤보로 계속되는 와중에 오랜만에 또 프로그래밍 얘기를 좀 하겠다.

본인은 예전에 열차나 건물(대표적으로 영화관)에서 좌석 배당 알고리즘이 어떻게 될까 궁금해하면서 이와 관련된 썰을 푼 적이 있다. 그리고 이와 비슷한 맥락에서, 점을 최대한 균등하게 순서대로 뿌리는 ordered 디더링의 가중치, 다시 말해 흑백 음영 단계 테이블은 어떻게 만들어지는 것일까 하는 의문을 제기했다. 그 당시엔 의문 제기만 하고 더 구체적인 해답을 얻지는 못했다.

그래픽 카드가 천연색을 표현할 수 있게 되면서 이제 컴퓨터에서 선택의 여지가 없는 '생존형'(?) 디더링의 필요성은 전무해졌다. 비디오보다는 아주 열악한 네트워크 환경에서 그래픽의 용량을 극도로 줄일 필요가 있을 때에나 특수한 용도로 제한적으로 쓰이는 듯하다. 색상뿐만 아니라 해상도도 왕창 올라가면서 이제는 글꼴의 힌팅조차 존재감이 많이 위태로워졌을 정도이니 세상이 참 많이도 변했다.

하지만 ordered 디더링이라는 건 점을 평면이나 공간에 최대한 골고루 질서정연하게 뿌리는 순서를 구하는 문제이다 보니, 계산 알고리즘의 관점에서는 실용적인 필요성과는 별개로 굉장히 흥미로운 문제인 것 같다.

사용자 삽입 이미지
(이제는 이런 무늬 패턴을 볼 일 자체가 거의 없어졌다..)

컴퓨터에는 아예 글꼴 차원에서 이런 음영 무늬를 나타내는 문자가 있다.
과거의 아스키 코드 시절은 말할 것도 없고, 유니코드에도 cp437 코드 페이지를 계승하여 25%, 50%, 75% 음영을 나타내는 U+2591, U+2592, U+2593이 있다. (?▒?)

그리고 과거의 아래아한글은 반각 기호 영역에 무려 5단계짜리 음영이 있었으며, 같은 흑백 50% 음영도 작은 점으로 찍은 것과 더 큰 점으로 듬성듬성 찍은 것 바리에이션까지 제공했다. 겨우 8*16 크기의 흑백 비트맵이라는 극도로 제한된 공간에서도 이 정도로 창의적인 무늬를 표현할 여지가 있었다.

사용자 삽입 이미지
(한컴 2바이트 코드 기반인 <날개셋> 편집기 2.x를 꺼내서 찍은 스크린샷.)

비트맵이 아니라 윤곽선 글꼴로 음영을 표현하는 건 대략 난감해진다. 윤곽선 글립과 도트 노가다 무늬는 거의 상극인 표현 방식이니까 말이다.
아래아한글이 제공하는 특수문자 글꼴은 도트 하나를 정사각형으로 대응시켜서 비트맵의 형태를 있는 그대로 윤곽선화했다.

하지만 Windows가 제공하는 글꼴은(정확한 이름은 모름) U+2591~2593 모두 작은 동그라미들로 도트를 표현한다. 그리고 진한 음영으로 갈수록 그 동그라미의 크기가 조금씩 더 커진다. 마치 출판물에서 볼 수 있는 하프톤 디더링처럼 말이다. 이런 글꼴에도 아래아한글과 Word에는 차이가 존재하는 셈이다.

그럼 다시 본론으로 돌아와, 디더링 내지 음영 테이블을 생성하는 방식에 대해 알아보자.
흑과 백이 정확하게 반반씩 있는 50% 경우를 생각해 보면, 당연한 말이지만 흑과 백은 대각선으로 엇갈린 형태로 존재한다. 수평선이나 대각선 형태가 아니다. ▤나 ▥가 아니라 ▩에 가까운 것이다.

그러므로 아주 간단한 2*2 크기의 음영이라면
(1 4)
(3 2)

가 된다. 수평선인 (1 2)(3 4)나 수직선인 (1 4)(2 3)이 아니라, (1 4)(3 2)라는 것이다.
그러니 태극기의 괘는 패턴이 (3 5)(4 6)이기 때문에 수직선에 가깝다. 그리고 이거 무슨 승용차에서 운전사가 있을 때와 없을 때, 좌석의 위치별로 상석에서 말석 순서 테이블과 비슷하다는 느낌도 든다.. -_-;;

시작점인 1은 언제나 좌측 상단으로 고정해서 생각해도 일반성을 잃지 않는다. 그럼 다음 2의 위치는 1에서 가장 멀리 떨어진 대각선이므로 역시 자동으로 결정된다.
그럼 (1 4)(3 2) 대신 (1 3)(4 2)는 불가능한 방향이 아니긴 하지만, 관례적으로 2 다음에 위쪽이 아니라 왼쪽에다가 3을 찍는 걸 선호하는 듯하다.

자, 그럼 얘를 조금 더 키워서 4*4 음영은 어떻게 될까?

(1 ? 4 ?) - (1 ? 4 ?) - (1 13 4 16)
(? * ? *) - (? 5 ? 8) - (9 5 12  8)
(3 * 2 ?) - (3 ? 2 ?) - (3 15 2 14)
(? * ? *) - (? 7 ? 6) - (11 7 10 6)

테이블의 크기가 딱 두 배로 커지면 새로운 숫자들은 언제나 기존 테이블의 틈바구니에 삽입된다. 그래야 균형이 유지될 수 있다.
각각의 틈바구니에 대해서 원래 칸의 대각선 아래 (+1, +1), 그리고 바로 아래 (0, +1), 바로 옆 (+1, 0)의 형태로 (5~8), (9~12), (13~16)이 매겨진다. 그랬더니 무슨 짝수 마방진 같은 복잡난감한 퍼즐이 채워졌다.

컴퓨터그래픽에서 실용적으로 가장 많이 쓰이는 음영은 8*8 크기이다. 모노크롬/16색 시절에 단색 패턴 채우기 함수들은 전부 8*8 패턴을 사용했다. 그러므로 얘는 음영을 64단계까지 표현할 수 있다.

8*8 패턴은 역시 4*4 패턴의 틈바구니에 삽입된다. 16 다음에 17이 들어가는 위치는 어디일까? 1과 2 사이에 5가 삽입되었던 것처럼 1과 5의 사이에 17이 삽입된다. 그리고 패턴 크기의 절반인 4픽셀 단위로 n, n+1, n+2, n+3이 (x,y), (x+4,y+4), (x,y+4), (x+4,y)의 순으로 번호가 매겨지는 건 변함없다.

거의 난수표 수준의 복잡한 테이블이 완성됐다. 규칙성이 뭔가 감이 오시는지? 그래픽 라이브러리들은 마치 삼각함수 테이블만큼이나 미리 계산된 디더링 테이블을 내장하고 있다.
그런데 이런 식으로 16*16 256단계 음영 테이블은 어떻게 만들 수 있을까?
각 구간을 순서대로 각개격파하는 게 아니기 때문에 분할 정복이나 재귀호출은 아닌 것 같다.

이런 숫자를 생성하는 코드를 작성하기 위해, 먼저 다음과 같은 변수들을 클래스나 전역변수 형태로 정의하자.

int mtrix[N][N]; int cs, ce;
static const POINT PTR[4] = {
    {0,0}, {1,1}, {0,1}, {1,0}
};

void Draw(int y, int x, int delta)
{
    for(int i=0;i<4;i++)
        mtrix[y+PTR[i].y*delta][x+PTR[i].x*delta]=ce++;
}

Draw는 특정 지점에서 n 간격으로 (0,0), (n,n), (0,n), (n,0)의 순으로 ce부터 ce+3까지 번호를 매겨 주는 역할을 한다.
이를 이용하면 2*2의 경우는 Draw(0, 0, 1)을 통해 간단히 만들 수 있다.

void Case2()
{
    cs=2; ce=1; memset(mtrix, 0, sizeof(mtrix));
    Draw(0, 0, 1);
}

앞서 살펴보았던 4*4는 이런 형태가 되고..

void Case4()
{
    cs=4; ce=1; memset(mtrix, 0, sizeof(mtrix));
    for(int a=0;a<4;a++)
        Draw( PTR[a].y, PTR[a].x, 2 );
}

더 복잡한 8*8은 Draw를 어떤 순서대로 호출해야 할지 따져보면 결국 규칙성이 도출된다.
그렇다. 2중 for문이 만들어지며, 16*16은 3중 for문이 될 뿐이다.

void Case8()
{
    cs=8; ce=1; memset(mtrix, 0, sizeof(mtrix));
    for(int a=0; a<4; a++)
        for(int b=0; b<4; b++)
            Draw(PTR[a].y + PTR[b].y*2, PTR[a].x + PTR[b].x*2, 4);
}

void Case16()
{
    cs=16; ce=1; memset(mtrix, 0, sizeof(mtrix));
    for(int a=0; a<4; a++)
        for(int b=0; b<4; b++)
            for(int c=0; c<4; c++)
                Draw(PTR[a].y + (PTR[b].y<<1) + (PTR[c].y<<2),
                    PTR[a].x + (PTR[b].x<<1) + (PTR[c].x<<2), 8);
}

사용자 삽입 이미지

바로 이것이 우리가 원하는 정답이었다. 식을 도출하고 보니 규칙은 허무할 정도로 너무 간단하다. n중 for문을 재귀호출이나 사용자 스택 형태로 정리하는 건 일도 아닐 테고.
이 정도면 평면이 아니라 3차원 공간을 점으로 촘촘하게 채우는 것도 생각할 수 있다. PTR 테이블은 (0,0,0), (1,1,1)부터 시작해서 정육면체의 꼭지점을 순회하는 순서가 되므로 크기가 8이 될 것이다.

그리고 참고로 8*8 음영 행렬은 아래의 코드를 실행해서 생성할 수도 있다.

int db[8][8];
for (int y = 0; y < 8; y++)
    for (int x = 0; x < 8; x++) {
        int q = x ^ y;
        int p = ((x & 4) >> 2) + ((x & 2) << 1) + ((x & 1) << 4);
        q = ((q & 4) >> 1) + ((q & 2) << 2) + ((q & 1) << 5);
        db[y][x] = p + q + 1;
    }

내가 처음에 for문을 써서 작성한 코드는 함수로 치면 일종의 매개변수 함수이다. (t에 대해서 x(t)는 얼마, y(t)는 얼마)
그런데 저건 그 매개변수 함수를 y=f(t) 형태로 깔끔하게 정리한 것과 같다. 식이 뭘 의미하는지 감이 오시는가?

이런 걸 보면 난 xor이라는 비트 연산에 대해 뭔가 경이로움, 무서움을 느낀다.
덧셈이야 "니가 아무리 비비 꼬아서 행해지더라도 까짓거 덧셈일 뿐이지. 결과는 다 예측 가능해" 같은 생각이 드는 반면, xor에다가 비트 shift 몇 번 하고 나면 도저히 예측 불가능한 난수 생성 알고리즘이 나오고 암호화/해시 알고리즘이 만들어지기 때문이다. 지극히 컴퓨터스러운 연산이기 때문에 속도도 왕창 빠르고 말이다.

2002년에 우리나라에서 열렸던 국제 정보 올림피아드에서도 'xor 압축'이라는 제출형 문제가 나온 적이 있다. 임의의 비트맵 이미지가 주어졌을 때, 이걸 사각형 영역의 xor 연산만으로 생성하는 순서를 구하되, 연산 수행을 최소화하라는 게 목표이다.

한 점에 대해서 가로/세로로 인접한 점 3개를 추가로 조사하여 흑백 개수가 홀수 개로 차이가 나는 점을 일종의 '모서리'로 간주하여 각 모서리들에 대해 plane sweeping하듯이 xor을 시키면 그럭저럭 괜찮은 정답이 나온다. 단, 이것이 이론적인 최적해와 동일하다는 것은 보장되지 않는다. 그렇기 때문에 문제가 제출형으로 출제된 것이다.

재미있는 것은 모서리 판정도 xor로 하면 간단하게 해결된다는 것이다.
(pt[x][y]==1)^(pt[x+1][y]==1)^(pt[x][y+1]==1)^(pt[x+1][y+1]==1) 같은 식. 이유는 조금만 생각해 보면 알 수 있다.

난 Bisqwit이라는 필명을 쓰는 이스라엘의 무슨 괴수 그래픽 프로그래머의 코딩 동영상에서 저 코드가 흘러가는 걸 발견하고 가져왔다. 흐음..;; Creating a raytracer for DOS, in 16 VGA colors 뭐 이런 걸 올려서 시청자들을 경악시키는 분이긴 한데, 물론 레알 16비트 도스용 Turbo C나 QuickBasic 컴파일러로 저런 걸 돌린다는 소리는 아니다. 그건 알파고 AI를 개인용 데스크톱 컴퓨터로 돌리는 것만큼이나 불가능한 일이니 너무 쫄지 않아도 된다. (VGA 16색인 건 맞지만 메모리와 속도는 그 옛날 기계 기준이 결코 아님.)

엑셀에다가 저 16*16 음영 테이블을 입력한 뒤, 수식을 이용해서 숫자 n을 입력하면 그에 해당하는 음영이 생성되게 워크시트를 만들어 보니 재미있다. 이번에도 흥미로운 덕질을 했다.

 

사용자 삽입 이미지

Posted by 사무엘

2016/06/26 08:33 2016/06/26 08:33
, , ,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1242

Trackback URL : http://moogi.new21.org/tc/trackback/1242

Leave a comment

지금 와서 가만히 생각해 보니, 컴퓨터 알고리즘을 동원하여 푸는 문제들은 다음과 같은 세 범주로 나눌 수 있는 것 같다. 뒤로 갈수록 설명이 길어진다.

1. 최적해를 다항 시간 만에 구할 수 있으며, 직관적인 brute-force 알고리즘과 뭔가 머리를 쓴 알고리즘이 시간 복잡도 면에서 충분히 유의미한 차이를 보이는 문제

간단한 발상의 전환으로 인해서 속도가 드라마틱하게 빨라질 수 있고, 알고리즘에 대한 정량적인 분석도 어렵지 않게 다 되는 경우이다. 요런 게 알고리즘 중에서는 가장 무난하다. 정보 올림피아드에도 이런 부류가 가장 많이 나온다.
가장 전형적인 예는 시간 복잡도 O(n^2)가 O(n log n)으로 바뀐다거나, 지수함수 복잡도가 O(n^2)로, 혹은 O(n^3)이 O(n^2)로 바뀌는 것이다. 물론 시간 복잡도를 줄이기 위해서는 공간 복잡도가 시공간 trade-off 차원에서 추가되는 경우가 대부분이다. 중간 계산 결과들을 모두 저장해 놓는 다이나믹 프로그래밍 문제가 대표적인 예이다.

정렬, common subsequence 구하기, 그래프에서 최단거리 찾기 같은 깔끔하고 고전적인 문제들이 많다. 기하 분야로 가면 convex hull 구하기, 거리가 가까운 두 점 구하기도 있다. 하지만 세상에 산적한 문제들 중에는 이 1번 부류에 속하지 않는 것도 많다.

2. 최적해를 다항 시간 만에 구하는 것이 가능하지 않은 (것으로 여겨지는) 문제

P에는 속하지 않지만 NP에는 속하는 급의 문제이다. 이건 다항 시간 만에 원천적으로 풀 수 없는 문제를 말하는 게 아니며 개념과 관점이 사뭇 다르다. 비결정성 튜링 기계라는, 실물이 없는 이론적인 계산 기계에서는 그래도 다항 시간 안에 풀 수 있다는 뜻이다.

입력 데이터의 개수 n에 비례해서 상수의 n승 내지 n 팩토리얼 개수의 가짓수를 일일이 다 따져야 하는 문제라면 다항 시간 만에 풀 수가 없다. 그런데 실생활에는 이런 무지막지하게 어려운 문제가 은근히 많이 존재한다. 진짜 말 그대로 n!개짜리 뺑이를 쳐야 하는 외판원 문제가 대표적이고, 그래프에도 '해밀턴 경로 문제'처럼 이런 어려운 문제가 산적해 있다. 이런 분야의 문제는 소위 말하는 NP-complete, NP-hard이기도 하다.

요런 문제는 brute force 알고리즘으로는 대용량 데이터를 도저히 감당할 수 없고 그렇다고 다항 시간 최적해 알고리즘이 있는 것도 아니기 때문에, 이런 문제는 100% 최적해는 포기하고 그 대신 95+n%짜리로 절충하고 시간 복잡도는 O(n^2)로.. 뭔가 손실 압축스럽게 tradeoff를 하게 된다.
국제 정보 올림피아드에는 이런 문제가 많이는 안 나오지만 전혀 안 나오는 건 아니다. 출제된다면 답은 최적해와의 비율로 점수가 매겨지며, 프로그램 실행이 아닌 그냥 제출형으로 출제되기도 한다.

P와 NP 사이의 관계는 전산학계에서 만년 떡밥이다. 현실에서는 마치 장기간 실종자를 법적으로 사망한 것과 마찬가지로 간주하듯이 P와 NP는 서로 같지 않다고 여겨지고 있다. 이를 전제로 깔고 발표된 연구 논문들도 수두룩하다. 하지만 그게 정말로 딱 그러한지는 전세계의 날고 기는 수학자들이 여전히 완벽하게 규명을 못 하고 있다.

엔하위키에는 P!=NP임을 증명하는 사람은 전산학 전공 서적에 이름이 실릴 것이고, P=NP임을 증명하는 사람은 아예 초등학생 위인전에 등재될 것이라고 얘기를 했는데... 적절한 비유인 것 같다. 지수함수 brute force 말고는 답이 없는 문제가 좀 있어야 암호와 보안 업계도 먹고 살 수 있을 텐데..!

3. 최적해를 다항 시간 만에 구할 수 있음이 명백하고, naive 알고리즘도 실생활에서 그럭저럭 나쁘지 않은 결과가 나오지만, 그래도 미시적· 이론적으로는 최적화 여지가 더 있는 심오한 문제

말을 이렇게 어렵게만 써 놓으면 실감이 잘 안 가지만 이 그룹에 속하는 문제의 예를 보면 곧장 "아~!" 소리가 나올 것이다. 이 분야에도 어려운 문제들이 은근히 많다.

(1) 문자열 검색
실생활에서는 그냥 단순한 알고리즘이 장땡이다. 원본 문자열을 한 글자씩 훑으면서 그 글자부터 시작하면 대상 문자열과 일치하는지 처음부터 일일이 비교한다. 실생활에서 텍스트 에디터는 대소문자 무시, 온전한 단어 같은 복잡한 옵션들이 존재하며 각 글자들의 변별성도 높다(대상 문자열과 일치하지 않는 경우 첫 한두/두세 글자에서 곧바로 mismatch가 발생해서 걸러진다는 뜻). 그 때문에 그냥 이렇게만 해도 딱히 비효율이 발생할 일이 없다.

하지만 문자열 검색이라는 건 실무가 아닌 이론으로 들어가면 생각보다 굉장히 심오하고 난해한 분야이다. 원본과 대상 문자열이 자연어 텍스트가 아니라 오로지 0과 1로만 이뤄진 엄청 길고 빽빽하고 아무 치우침이 없는 엔트로피 최강의 난수 비트라고 생각하자. 그러면 예전에 패턴이 어디서부터 어긋났는지를 전혀 감안하지 않은 채 오로지 1글자씩만 전진하는 방식은 효율이 상당히 떨어진다. 이제야 좀 더 똑똑한 문자열 검색 알고리즘이 필요해진다.

퀵 정렬의 중간값(pivot) 선택 알고리즘을 의도적으로 엿먹이는 '안티' 데이터 생성 알고리즘만큼이나..
특정 문자열 검색 알고리즘을 엿먹여서 언제나 최악의 경우로 한 글자씩만 전진하게 만드는 문자열 데이터를 생성하는 안티 알고리즘도 있을 것이다.

(2) 팬케이크 정렬
a1부터 a_n까지 임의의 수 배열이 존재하는데, 우리가 이 수열에 대해 취할 수 있는 동작은 여느 정렬 알고리즘처럼 임의의 두 원소끼리의 교환이 아니다. 1~2, 1~3 또는 1..m (m<=n)처럼 첫째부터 m째의 원소들을 모조리 역순으로 뒤집는 것만 가능하다. 1 7 4 2였으면 2 4 7 1로 바꾼다는 것. n개의 임의의 수열이 있을 때 수열을 정렬하기 위해 필요한 이론적인 최대 뒤집기 횟수는 정확하게 얼마나 될까? 한꺼번에 몇 개를 뒤집건 한번 뒤집는 데 걸리는 시간은 무조건 상수라고 가정하고, 뒤집기 자체 외에 다른 계산의 비용(가령, 현 구간에서 maximum 값을 찾는 것)은 전혀 고려하지 않아도 된다.

본인은 아주 어렸을 때 GWBASIC 교재에서 이 팬케이크 정렬 문제와 같은 방식으로 수열을 뒤집어서 "사람으로 하여금 문제를 풀게 하는" 프로그램을 본 기억이 있다. 프로그램의 이름이 REVERSE였다.
이 문제는 마치 선택 정렬과 비슷한 방식으로 명백한 해법이 존재한다. 가장 큰 수가 m째 원소에 존재한다면 m만치 뒤집어서 가장 큰 수가 맨 처음에 오게 한 뒤, 판 전체를 뒤집어서(n만치) 그 수가 맨 뒤로 가게 하면 된다. 이 과정을 그 다음 둘째, 셋째로 큰 수에 대해서 계속 적용하면 된다.

그렇게 명백한 해법의 계산 횟수는 최대 2*n-3으로 알려져 있다. 하지만 이것은 그렇게 뒤집은 여파가 다음으로 큰 수들을 정렬하는 데 끼치는 영향이 감안되어 있지 않다. 물론 여기서 좀더 머리를 써 봤자 2n이던 계수가 1.xx 정도로나 바뀌지 그게 n 내지 심지어 log n급으로 확 바뀌지는 못한다. 비록 O(n) 표기상으로는 동일하지만 그렇게 상수 계수를 조금이라도 줄이는 최적화이다 보니, 알고리즘이 더 까다롭고 머리가 아프다.

마이크로소프트의 창립자인 그 빌 게이츠가 1979년에 바로 이 문제의 계산 횟수를 최적화하는 알고리즘을 (공동) 연구하여 이산수학 학술지에다 투고했었다. 이 사람의 기록은 그로부터 거의 30년이 지난 2008년에야 더 정교한 알고리즘이 나옴으로써 깨졌다. 이것은 빌이 단순히 비즈니스맨이기만 한 게 아니라 엔지니어 기질도 얼마나 뛰어났고 수학 쪽으로도 얼마나 천재였는지를 짐작케 하는 대목이다. 학부 중퇴 학력만으로도 이미 전산학 석· 박사급의 걸출한 리서치를 했으니 말이다.

(3) 행렬의 곱셈
갑자기 팬케이크 정렬 얘기가 좀 길어졌는데 다음 항목으로 넘어가자면.. 계산 관련 알고리즘도 이런 급에 속한다. 대표적으로 행렬.

일반적으로야 두 개의 n*n 정방행렬끼리 곱셈을 하는 데 필요한 계산량, 정확히 말해 두 수 사이의 곱셈 횟수는 정확하게 O(n^3)에 비례해서 증가한다. 그러나 거대한 행렬을 2*2 형태의 네 개로 쪼개고, 덧셈을 늘리는 대신 곱셈을 줄이는 방식으로 최적화를 하는 게 가능하다. 게다가 쪼개진 행렬이 여전히 크다면 그걸 또 재귀적으로 쪼갤 수 있다.
a+bi와 c+di라는 복소수의 곱셈을 위해서 통상적으로는 ab, ac, bc, bd라고 곱셈이 총 4회 필요하다고 여겨지지만 실은 덧셈을 더 하는 대신에 곱셈은 ac, bd와 (a+b)*(c+d)로 3회로 줄일 수 있지 않은가? 그런 식으로 줄인 것이다.

그렇게 해서 O(n^3)보다 이론상 작은 시간 복잡도가 최초로 제안된 게 1969년에 나온 슈트라센 알고리즘이다. 대략 O(n^2.8). 정확하게 2.8인 건 아니고 지수 자체가 로그 n 이런 형태로 떨어진다. 프랙탈의 차원 수가 로그로 표현되는 것처럼 말이다.
여기서 2.8x의 정확한 의미는 log[2] 7이다. 원래 2*2 행렬 두 개를 곱하기 위해서는 상수 곱셈이 8회 필요한데, 중간 과정의 공식들을 궁극의 캐사기 테크닉을 동원하여 변형했다. 어마어마한 양의 우회 연산을 통해 덧셈은 횟수가 왕창 늘었지만 곱셈이 8회에서 7회로 딱 1회 줄었다! (도대체 무슨 약 빨고 연구해서 이런 걸 생각해 냈을까? ㄷㄷ) 이 여파가 분할 정복법의 특성상 재귀· 연쇄적으로 적용된 덕분에 전체 시간 복잡도가 감소한 것이다.

그리고 이 바닥도 발전에 발전을 거듭한 덕분에 오늘날은 무려 O(n^2.4)대까지 곤두박질쳤다. 덧셈과는 달리 곱셈은 이런 최적화의 여지가 존재한다는 사실 자체가 아주 신기하지 않은가? 크기가 서로 다른 행렬들의 최소 곱셈 횟수를 구하는 다이나믹 프로그래밍 문제하고는 완전 별개의 영역이다.

아래의 그림을 보자(움짤임). RGB라는 세 대의 차량이 서로 부딪치지 않고 G는 그대로 위로, R과 B는 서로 좌우가 엇갈리게 빠져나가려면 어떻게 하면 좋을까? 아래의 중앙은 길이 막혔기 때문에 횡단을 할 수 없다.
결국 가운데 G는 곧이곧대로 위로 나가서는 안 되며, R과 B의 경로를 피해서 몇 배나 더 긴 우회를 해야 한다. 하지만 그래도 RGB 모두 신호 대기가 없이 서로 엇갈리는 방향으로 술술 소통이 가능하다.

사용자 삽입 이미지

자연에는 관성이라는 게 존재하니, 다리가 아니라 바퀴가 달린 자동차나 열차에게는 우회를 하더라도 이게 훨씬 더 나은 방법인 것이다.
행렬도 덧셈이라는 우회가 아무리 몇 배로 더 늘어 봤자, 아주 큰 행렬(차량 소통이 엄청 많을 때)에 대해서는 곱셈이 눈꼽만치라도 줄어드는 게 도로로 치면 신호 대기가 없어지는 것에 맞먹는 이익이 될 수 있다는 생각이 든다.

물론 행렬의 곱셈 시간 복잡도가 O(n^2)보다 더 낮아질 리는 없으며, 저런 알고리즘들은 지수를 줄이는 대신 공간 복잡도(스택 사용..) 같은 다른 오버헤드가 왕창 커졌다는 점을 감안해야 한다. 크기가 몇십~몇백 정도 되는 초대형 행렬에서 두각을 발휘하지, 그냥 3차원 그래픽용으로나 간단히 쓰이는 3*3이나 끽해야 4*4 행렬에서 적용할 만하지는 않다.

Posted by 사무엘

2016/01/12 08:30 2016/01/12 08:30
, , ,
Response
No Trackback , 9 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1181

Trackback URL : http://moogi.new21.org/tc/trackback/1181

Comments List

  1. Lyn 2016/01/12 21:48 # M/D Reply Permalink

    전 Genius oriented algorism 을 사용합니다.

    1. 사무엘 2016/01/13 08:08 # M/D Permalink

      오잉, 그건 무슨 분야의 어떤 알고리즘인가요??

    2. Lyn 2016/01/17 17:36 # M/D Permalink

      모든분야에 다 적용되는 알고리즘인데... 천재들이 만들어둔걸 그냥 갖다쓰는 방법입니다.

    3. 사무엘 2016/01/18 09:20 # M/D Permalink

      아아.. 제일 확실한 방법이군요. ㅠㅠ ^^

    4. Lyn 2016/01/31 10:23 # M/D Permalink

      파인만 알고리즘에 맞먹습니다.

  2. 박한철 2016/01/14 03:12 # M/D Reply Permalink

    재밌는 글 잘 보았습니다. 이런 게 수학이죠. P!=NP 는 과연 풀릴 날이 올까요 -_-

    1. 사무엘 2016/01/14 09:35 # M/D Permalink

      알고리즘 서적들이 보통은 분할 정복, 다이나믹 같은 방법론별로.. 혹은 정렬, 그래프, 문자열 같은 주제별로 알고리즘을 분류하는 편이죠. 그런데 최적화 양상으로 분류하면 저렇게 세 그룹으로 나뉜다 싶은 생각이 개인적으로 들어서 정리해 봤습니다.
      그 까마득한 옛날에 저런 걸 30대 나이 때 벌써 P와 NP라는 걸 생각해 내고 떡밥을 던지다니~ 스티븐 쿡 아저씨의 위대함을 실감합니다. ㅜ.ㅜ

  3. 박한철 2016/01/14 14:56 # M/D Reply Permalink

    저는 수학을 공부하는 입장인데 부끄럽게도 스티븐 쿡이라는 이름을 이제사 처음 들어 봤습니다 ㅠㅠ 수학과 계산과학이 겹치는 부분이 많은데 커리큘럼이 나눠져 있어서... 주로 조합수학combinatorics 쪽에서 많이 겹치는 것 같더군요.

    1. 사무엘 2016/01/15 08:55 # M/D Permalink

      아유 수학이 원래 분야가 왕창 넓어서 주 연구 분야가 아니면 교수라도 잘 모르지 않나요? ^^
      수학을 전문으로 공부하는 분들 개인적으로 참 대단하고 부럽습니다. 저도 그냥 이것저것 주워 들었을 뿐이죠. ㅎㅎ

Leave a comment

※ 메모리 단편화

컴퓨터에서 무작위 읽기/쓰기가 가능한 모든 기억장치.. 즉 RAM, 파일 시스템, 데이터베이스 따위에는 모두 구조적으로 단편화라는 문제가 존재한다.
메모리를 10바이트씩 찔끔찔끔 요청했는데 최소 할당 단위 제약 때문에 실제로는 수백 바이트 단위로 성큼성큼 용량이 짤려 나간다거나(내부 단편화),
전체 남은 용량은 1000바이트인데 한 600바이트 정도 연속된 구간이 없어서 메모리 할당이 실패하는 외부 단편화가 모두 존재한다.

메모리라는 게 1차원적인 공간이기 때문에 이건 뭐 어쩔 수 없다.
그래서 컨텐츠가 실제로 차지하는 용량보다 전체 소모 용량이 더 커지게 되고, 이런 걸 관리하는 프로그램이나 유틸리티에는 조각 모음(defrag), shrink, compact 같은 동작을 강제로 수행하는 기능이 있다. (뭐, 디스크 중에서 SSD는 예외적으로 조각 모음이 필요하지 않은 구조라고는 하지만.)

디스크는 애초부터 파일 시스템의 지배 하에 있으며 그 시스템이 제공하는 방식대로 디렉터리와 파일 이름을 통해서만 내용에 접근 가능하다. 일반적인 응용 프로그램이 디스크를 무슨 실린더 번호 x, 트랙 y, 섹터 z 같은 형태로 무식하게 접근하는 경우는 거의 없다. 그런 방식은 오늘날의 운영체제에서는 더욱 금기시되고 있다.

그렇게 파일명이라는 고수준 추상 계층이 있는 덕분에 디스크는 내부적으로 막 조각 모음을 해도 딱히 파일을 못 찾는 일이 발생하지는 않는다. 저수준 처리는 운영체제의 파일 시스템이 알아서 다 처리해 준다. 또한 디스크 정도면 물리적으로 액세스를 하는 데서 발생하는 병목이 소프트웨어적인 추상화 계층을 거치는 시간보다 훨씬 더 길기도 하고 말이다. 사용자에게는 외부 단편화보다는 클러스터 최소 단위로 인한 내부 단편화가 현실적으로 더 와 닿는다.

그런데 RAM은 디스크와는 사정이 다르다. 단편화를 예방한답시고 함부로 컨텐츠들을 재배치하면 memcpy 오버헤드는 둘째치고라도 그 메모리 주소를 직접 가리키고 있던 수많은 포인터들이 작살이 나 버린다.
메모리 자원이 극도로 가난하고 열악하던 16비트 Windows 시절에는 운영체제의 global/local heap으로부터 메모리를 할당받고 나면 곧바로 포인터가 돌아오는 게 아니라 핸들 하나만이 돌아왔다. 이 핸들이 가리키는 메모리는 운영체제의 사정에 따라 수시로 재배치될 수 있는데, 메모리를 실제로 사용할 때만 lock을 걸어서 위치를 고정시킨 뒤, 포인터를 얻어와서 메모리를 참조하곤 했다. 사용이 끝나면 다시 unlock을 해 줘야 한다.

이것이 바로 GlobalAlloc - GlobalLock - GlobalUnlock - GlobalFree 사이클이다. 재배치를 하는 이유는 당연히 메모리 단편화를 극복하고, 연속된 긴 메모리 공간을 언제나 확보하기 위해서이다. 16비트 시절에 메모리 블록이나 리소스 같은 데에 discardable, resident, non-resident 같은 속성이 달려 있던 이유는, 수시로 재배치 내지 재로딩 같은 빡센 메모리 관리에 대응하기 위해서이다.
운영체제가 자동으로 무슨 garbage collect를 해 주는 것도 아니고, 저런 일을 해야만 했다는 게 참 안습하다.

여기서 우리가 알 수 있는 점은, 32비트 정도 되는 주소 공간에서 가상 메모리가 제공되는 게 프로그래머의 관점에서 얼마나 축복이냐 하는 것이다. 4기가바이트 정도 넉넉한 공간이 있으면, 단편화 문제는 주소빨로 어느 정도, 상당 부분 극복이 가능해진다. 어지간히 단편화가 심한 상태라 해도, 또 대용량 메모리 요청이 들어오면 걍 다음 주소를 끌어다가 물리 메모리에다 대응시켜 쓰면 되기 때문이다.

그 연속된 가상 메모리 주소를 실제로는 여기저기 흩어졌을 가능성이 높은 지저분한 물리 메모리로 대응시키는 건 운영체제와 CPU의 몫이다. 물리 메모리가 부족하면 하드디스크 스와핑까지 알아서 해 준다. 가상 메모리 덕분에 프로세스간에 보안이 더 향상된 것도 덤이고 말이다.

이것이 RAM과 디스크의 차이이다. 디스크에 파일명이 있다면 RAM에는 가상 메모리 메커니즘이 있다. 한 주소 공간 안에서 스레드가 여러 개 있는 경우 가상 메모리의 필요성은 더욱 커진다.
물론, 세상에 공짜는 없으니, 가상 메모리는 메모리를 관리하기 위한 추가적인 메모리도 적지 않게 소요하는 테크닉인 걸 알아야 한다. 물리적인 메모리뿐만이 아니라 가상 메모리 주소 영역 자체도 떼먹는다.
오늘날 64비트 운영체제라 해도 어마어마하게 방대한 공간인 64비트 전체를 사용하는 게 아니라 40비트대 정도만 사용하는 것도 이런 이유 때문이다.

※ 옛날 이야기

옛날의 프로그래밍 언어나 소프트웨어 플랫폼을 살펴보면, 메모리와 관련하여 오늘날 당연한 기본 필수라고 여겨지는 요소가 대놓고 빠진 것들이 적지 않아 놀라게 된다.

(1) 예를 들어 옛날에 포트란 언어는 함수 호출은 가능하지만 초기에는 동일 함수에 대한 중첩/재귀 호출이 가능하지 않았다. 세상에 뭐 이런 언어가 다 있나 싶다..;; 함수 안에서 지역 변수의 사용이 스택 기반으로 되어 있지 않고 늘 고정된 주소로만 접근하게 돼 있어서 그랬던 모양이다.

오늘날의 프로그래밍 언어에서야 지역 변수는 스택의 기준 주소로부터 상대적인 위치를 건드리게.. 일종의 position independent code 형태로 접근된다. 재귀 호출 지원뿐만 아니라 코드 실행 주체가 증가하는 멀티스레드 환경에서는 각 스레드가 또 독립된 스택을 갖고 있으니 절대 고정 주소가 더욱 의미를 상실하기 때문이다. 멀티스레드는 thread-local이라는 일종의 새로운 scope까지 만들었다.

(2) 한편, 프로그래밍 언어 쪽은 아니지만, Win32의 구현체 중에 제일 허접하고 불안정하고 열악하던 Win32s는..
멀티스레드도 없고 각 프로세스마다 독립된 주소 공간이 없는 건 그렇다 치는데... DLL은 자신이 붙는 각 프로세스별로 자기만의 독립된 데이터 공간마저도 보장받지 못했다. 16비트 DLL과 다를 바가 없다는 뜻.

옛날에 아래아한글 3.0b는 윈도 95나 NT 말고 3.1 + Win32s에서 돌아갈 때는 무슨 자기네 고유한 메모리 서버 프로그램을 먼저 실행한 뒤에야 실행 가능했다. 이제 와서 다시 생각해 보니, 그 메모리 서버가 하는 일이 바로 DLL별로 고유한 기억장소를 할당하는 것과 관련이 있지 않았나 싶다. 아래아한글의 소스를 모르는 상태에서 그냥 개인적으로 하는 추측이다.

아시다시피 16비트 Windows는 가상 메모리 같은 게 없다 보니, 콜백 함수의 실행 context를 레지스터에다 써 주는 것조차 소프트웨어가 수동으로 해야 할 정도로 진짜 가관이 따로 없었다.

※ 쓰레기(다 쓴 메모리) 수집

끝으로 garbage collector 얘기다.
heap으로부터 할당하는 메모리는 너무 dynamic한지라 언제 얼마만치 할당해서 언제 해제되는지에 대한 기약이 없다. 그걸 소스 코드만 들여다보고서 정적 분석으로 완벽하게 예측하는 건 원천적으로 불가능하다.

하지만 정해진 scope이 없는 동적 메모리를 잘못 건드려서 발생하는 소프트웨어 버그는 마치 자동차의 교통사고처럼 업계에서 상당히 심각한 문제이다.
memory leak은 당장 뻑이 나지는 않지만 프레임 단위 리얼타임으로, 혹은 수 개월~수 년간 지속적으로 돌아가는 소프트웨어에서는 치명적이다. 또한 다른 메모리/포인터 버그도 단순히 혼자만 뻑나는 걸로 끝나면 차라리 다행이지, 아예 악성 코드를 실행시키는 보안 문제로까지 상황을 악화시킬 수 있다.

이 동적 메모리 관리를 사람에게 수동으로 맡겨서는 안전하지 못하니, 메모리 자원 회수를 프로그래밍 언어 런타임 차원에서 자동으로 보장되게 하는 기법이 연구되어 왔다.
고전적인 reference counting 테크닉은 C++의 생성자/소멸자 패러다임과 맞물려서 일찍부터 연구되어 왔으며 smart pointer 같은 구현체도 있다.

이건 원리가 아주 간단하며, 언어 차원에서 포인터의 scope가 벗어나는 족족 메모리가 칼같이 회수되는 게 컴파일 시점에서 보장된다. 그래서 깔끔한 것 하나는 좋다.
허나 이 기법은 생각보다 비효율과 단점도 많다. 대표적인 논리적 결함인 순환 참조는.. 서로 다른 두 객체가 상대방을 서로 참조하여 똑같이 참조 횟수가 1보다 커지고, 따라서 둘이 메모리가 결코 해제되지 않아서 leak으로 남는 문제이다.

즉, 레퍼런스 카운팅이 잘 동작하려면, 참조를 받은 피참조자는 자신을 참조하는 놈을 역참조하지 말아야 한다. 이걸 어기면 객체간의 레퍼런스 카운트가 꼬여 버린다.
문제는 이걸 일일이 조심하면서 코드를 작성하는 게 상황에 따라서는 차라리 걍 메모리 자체를 수동으로 관리하는 게 나을 정도로 효율이 떨어질 수 있다는 것이다. 게다가 고리가 어디 A-B, B-A 사이에만 생기겠는가? A-B, B-C, C-A 같은 식으로 더 골치 아프게 생길 수도 있다. 참조 관계는 정말로 cycle이 없이 tree 형태로만 가야 한다.

그러니 이 문제는 예상 외로 굉장히 심각한 문제이다. 멀티스레드에서의 '데드락'하고 다를 바가 없다! 서로 뭔가 꼬여서 끝이 안 난다는 점, 잡아 내기가 극도로 어렵다는 점이 공통점이다.
성능을 더 희생하고라도 메모리 leak 문제를 완전히 다른 방식으로 접근한 전용 garbage collector가 괜히 등장한 게 아니었겠다 싶다.

가비지 컬렉터라고 해서 무슨 용 빼는 재주가 있는 건 아니다. 기본적으로는 당장 접근 가능한 메모리로부터 출발해서 그 메모리로부터 추가로 접근 가능한 메모리 블록을 줄줄이 순회하여 표시를 한 뒤, 표시가 없는 메모리를 죄다 해제한다는 아이디어를 기반으로 동작한다. 동적으로 할당받은 메모리 내부에 또 동적 할당 메모리의 포인터가 있고, 그게 또 이상하게 얽히고 배배 꼬인 걸 어떻게 일일이 다 추적하는지 더 구체적인 방법은 잘 모르겠지만.

어찌 보면 단순무식하다. 주인 없이 주차장에 장기간 방치되어 있는 폐자전거들을 일괄 처분하기 위해 모든 자전거에 리본을 달아 놓은 뒤, 일정 날짜가 지나도록 리본이 제거되지 않은 자전거를 갖다 버리는 것과 개념적으로 비슷하다! 혹은 기숙사의 공용 냉장고에서 주인에게로 접근(?)이 안 되는 장기 방치 식품을 주기적으로 제거하는 것과도 비슷한 맥락이다. 단지 좀 더 성능을 올리기 위해, 메모리 블록들을 생존 주기별로 분류를 해서 짬이 덜 찬 메모리가 금방 또 해제될 가능성이 높으므로 거기부터 살펴보는 식의 관리만 하는 정도이다. 자바, .NET의 가상 머신들도 이런 정책을 사용한다.

이건 즉각 즉각 자원이 회수되는 게 아니며, 리얼타임 시스템에서는 적용을 재고해야 할 정도로 시공간 오버헤드도 크다. 그러나 한번 수집이 벌어질 때 랙이 있다는 말이지, 매 대입 때마다 시도 때도 없이 카운터 값을 변화시키고 그때 스레드 동기화까지 해야 하는 레퍼런스 카운팅도 성능면의 약점은 상황에 따라 피장파장일 수 있다.

언어 차원에서 이런 가비지 컬렉터가 제공되어서 delete 연산자와 소멸자 자체가 존재하지 않는 언어가 요즘 추세이다. 자바나 C#처럼. 하지만 메모리는 그렇게 자동으로 수집되지만, 파일이나 다른 리소스 핸들은 여전히 수동으로 해제를 해야 할 텐데 무작정 소멸자가 없어도 괜찮은지는 잘 모르겠다. 본인은 그런 언어로 대규모 프로그램을 작성한 경험이 없다. C++ 이외의 언어에서는 RAII 개념이 아예 존재하지 않는 건지?

Posted by 사무엘

2015/09/20 08:28 2015/09/20 08:28
, ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1140

Trackback URL : http://moogi.new21.org/tc/trackback/1140

Comments List

  1. 김재주 2015/09/20 09:37 # M/D Reply Permalink

    일반적인 응용 프로그램이 디스크를 무슨 실린더 번호 x, 트랙 y, 섹터 z 같은 형태로 무식하게 접근하는 경우는 거의 없다. 그런 방식은 오늘날의 운영체제에서는 더욱 금기시되고 있다.


    - 저희 연구실 차기 연구분야랑 어느정도 관련이 있는 이야기인데요. 요즘 SSD로 저장장치의 대세가 넘어가면서 오히려 반대로 돌아가려는 움직임이 있습니다.

    낸드플래시 특성상 쓰기는 페이지 단위, 지우기는 블록 단위로 일어나기 때문에 논리적 주소가 같더라도 메모리 상의 다른 위치에 쓰이게 되죠. 이 때 논리 주소와 실제 물리 주소 사이를 연결하는 테이블을 관리하는 소프트웨어가 FTL입니다...만, SSD 펌웨어 내부에서 동작하는 FTL 입장에서는 자기가 저장하는 데이터가 어떤 데이터인지 모르기 때문에 최적의 위치에 넣는다고 넣겠지만 실제 최적의 활용과는 거리가 있죠.


    그래서 요즘은 Software-defined flash라고 해서, 플래시메모리의 구조(채널 수라던지, 블록 사이즈라던지)를 운영체계에 오픈해 두고, 데이터베이스나 키밸류 스토어 응용프로그램에서 저장할 데이터의 특성 등을 고려하여서 가장 잘 들어맞는 위치에 저장할 수 있도록 하는 방법이 쓰이고 있습니다. 주로 데이터센터나 클라우드 서버처럼 높은 I/O 성능이 필요한 곳에서 사용하죠.



    후자는 예전에 이 블로그 포스트에서도 본 적이 있지만, RAII 패턴과 Move sementic을 언어 차원에서 강제하는 것이 Rust죠. 가비지 컬렉터 없이 메모리 문제를 해결한 (현재로서는) 유일한 솔루션이 아닌가 합니다. 물론 프로그래머가 작정하고 타입 시스템의 빈틈을 노리고 악용한다면 답이 없겠지만요.

    그리고 제 기억엔 C#에는 소멸자와 비슷한 역할을 하는 IDisposable이라는 인터페이스가 있습니다. 파일 핸들 같은 걸 가지고 있는 객체는 이 인터페이스를 상속해서 Dispose 메서드를 재정의하면 자원 해제를 제어할 수 있죠. 자바는 아마 그런 장치는 없고 수동으로 예외 처리를 해야 했던 걸로 기억합니다.

    1. 사무엘 2015/09/20 23:24 # M/D Permalink

      도스 시절엔 디스크에 굉장히 저수준으로 접근을 하는 노턴 유틸리티의 diskedit, NDD, unerase 같은 프로그램들이 있었지요.
      다만 플래시 메모리는 확실히 전통적인 비휘발성 보조 기억장치에 대한 패러다임을 확 바꿔 놓은 기술이긴 합니다.

      Rust에 대해서는 1년쯤 전에 오픈소스 얘기와 함께 다룬 적이 있습니다.
      이것저것 다양한 보충 설명에 감사드립니다. ^^

  2. 김진 2015/10/19 00:22 # M/D Reply Permalink

    자바7부터는 try-with-resources 구문이 있어서 try(AClass a = new AClass()) {} 하면 블록이 끝날 때 a.close()가 호출됩니다. AClass는 AutoCloseable이라는 인터페이스를 구현해야 하고요. C#에서 IDisposable 구현하고 using 구문으로 묶는 것과 갈습니다.

    1. 사무엘 2015/10/19 11:38 # M/D Permalink

      소멸자라는 게 태생적으로 가상 함수와 비슷한 형태이니,
      언어 차원에서 소멸자를 지원하지 않는 언어에서는 결국 소멸자는 특정 인터페이스를 구현하는 형태로 가는군요. 자동 호출이 필요한 곳에서만 try-with-resources 구문을 써 주고..;; 재미있네요~!

Leave a comment

본인이 인터넷에서 굉장히 고맙게, 유용하게 잘 열람하는 정보 중 하나는 지도이다.
참 대단하지 않은가? 항공 사진, 길거리 사진, 길 찾기, 실시간 대중교통 연계와 도로 상황 안내 등... 정말 혀를 내두르는 수준이다. 이젠 도대체 얼마나 더 똑똑해질 거리가 남아 있는 걸까?

아울러, 지도의 일종인 차량용 내비게이션 소프트웨어도 도대체 어떤 천재가 만들었나 싶은 생각이 든다. 도로 상황을 감안해서 길을 찾는 건 당연한 소리이고, 그걸로도 모자라서 길 가는 중에 실시간으로 “해당 경로에 사고가 발생했습니다. 우회 경로를 재탐색할까요?”까지도 튀어나온다.

2013년엔 구글 회장이 한번 방북을 하고 났더니 구글어스가 평양을 중심으로 북한의 세부 지리 정보(단순 항공 사진은 예전부터 제공했음)를 제공하기 시작했다. 얘를 시작으로 2014년 하반기부터는 국내 지도 사이트들도 북한 정보를 제공하기 시작했다.
고무적인 현상이다. 물론 구글어스도 그 자체는 처음부터 구글이 개발한 게 아니라 타 업체 솔루션을 인수한 것이긴 하지만 말이다.

본인이 예전에 인터넷 지도에 대해 썼던 글은 이 모든 기능이 별도의 응용 프로그램이 아니라 웹에서 웹 표준 기술만으로 바로 구현 가능해진 것이 신기하다는 요지였다.
이번에는 다른 분야에서 대단히 신기하게 느껴지는 것에 대해 이야기를 늘어놓아 보겠다. 바로 이미지 가공 기술이다.

지도 사이트들이 제공하는 평면 항공 사진은 (1) 넓디넓은 영역을 한결같이 위에서 아래를 내려다보는 단일 각도로 본 이미지이다. 그런데 이거 정말 가공을 많이 했겠다는 생각이 들지 않는가?
이미지에서 원근감이라는 걸 완전히 제거하고 건물들이 마치 스타크래프트 맵처럼 보이게 해야 한다. 중심에서 먼 곳의 건물일수록 모양이 왜곡되어 보이는 카메라 렌즈의 오차를 보정해야 한다.

물론 엄청 높은 곳에서 촬영을 하면 건물 자체의 높이로 인해 발생하는 원근감은 상당수 없어지지만 이번엔 반대로 고층 건물도 높이가 전혀 표현되지 않게 되며, 또 사진의 화질이나 해상도, 그리고 구름으로 인한 시야 가려짐 같은 기술적인 문제도 커진다. 게다가 지구 자체도 근본적으로 평면이 아니라 둥근 구이니, 이로 인한 평면의 왜곡은 카메라의 위치가 높아질수록 더욱 부각되어 보일 것이다.

이런 항공 사진은 전세계의 것을 동시에 촬영하기란 불가능할 테니 여러 사진, 혹은 연속적으로 촬영된 사진을 파노라마 사진 만들듯이 연결해야 할 것이고 이 사진들은 촬영 시간대도 최대한 일치해야 할 것이다(광량의 차이). 또한, 주행 중이어서 시시각각 위치가 변하는 자그마한 자동차나 열차의 모습은 어떻게 보정을 하면 좋을까?
이런 것들을 다 극복하고 전국· 전세계의 항공 사진을 최대한 일관성 있는 색조와 각도로 엮는 것은.. 그 어려움과 복잡함이 정말 말도 못 할 것 같다. 비행기에서 아래를 내려다보고 사진만 팡팡 찍는다고 해서 구현 가능한 게 아니다.

사용자 삽입 이미지
(사진으로 나타난 63 빌딩의 높이와, 그림자의 길이를 비교해 보자.;; 각도가 뭔가 자연스러운 것 같지는 않다. 보정을 한 게 아닐까..)

그 보정이 자동화가 가능한지 아니면 일일이 수작업으로 행해지는지가 궁금하다.
마치 요런 영화 촬영 기법을 떠올리게 한다. 피사체는 시간이 정지한 듯 꼼짝 않고 있는데 카메라가 뱅그르르~ 돌아가면서 다른 위치와 각도에서 피사체를 응시하며 촬영하는 것 말이다. 심지어 사람이 하늘에 붕 떠 있는 채로 그런 장면이 나오기도 하니 더욱 신기한 일이다.

그리고 다음으로 생각할 것은 로드뷰이다.
이것은 앞의 항공 평면 사진과는 반대로, (2) 단일 시점에서의 view를 모든 각도로 제공하는 것이다. 이것은 어쨌든 연속으로 촬영할 수는 없기 때문에 로드뷰의 시점은 수~십수 미터 간격으로 띄엄띄엄 제공된다.

사용자 삽입 이미지

이런 시점 view는 지금이야 지도 사이트에서 쉽게 열람할 수 있는 기능이 됐지만, 옛날에 2000년대 초엔 철도청 홈페이지에서 자바 애플릿 형태로 비슷한 기능을 제공한 게 있었다.
바로 새마을· 무궁화· 통일호 내지 전동차의 객실 내부를 저런 로드뷰처럼 상하좌우 둘러보는 기능이었다.

이 기능은 내부적으로 2차원 평면 형태의 파노라마 사진을 한 장 저장하고, 그 그림의 일부에다 원근법을 적용하여 변형한 것을 표시하는 형태로 구현되어 있다. 내가 아는 건 이게 전부이고 구체적으로 어떤 계산을 하는지, 그리고 이런 용도로 사용하는 사진은 어떤 형태이고 어떻게 촬영하는지에 대해서는 잘 모른다. 그야말로 상하좌우 시야각이 다 열려 있는 특수한 카메라를 써야 할 텐데..

내가 10여 년 전에 이미 3차원 그래픽 시연 프로그램이라는 것도 만들어 봤지만, 비트맵 이미지로부터 3차원 시야를 어떻게 구현하는지는 여전히 감이 안 온다.
2차원 이미지에서 원근감을 넣거나 없애고, 평면과 공간 사이를 오고 가게 하는 기술이 참 대단하게 느껴진다. 그 기술이 인터넷 지도, 더 나아가 증강현실 같은 것도 가능하게 한 셈이다.

Posted by 사무엘

2015/04/08 08:32 2015/04/08 08:32
,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/1081

Trackback URL : http://moogi.new21.org/tc/trackback/1081

Leave a comment

뭐, 무식이 자랑이랄 수는 없겠지만,
본인은 전산학 내지 컴퓨터공학의 여러 분야들 중에서 문외한에 가깝게 제일 모르는 분야는 통신, 네트워크, 웹, 보안 쪽이다.
왜 제일 모르느냐 하면, 저건 컴퓨터 한 대만으로 독학이 가능하지 않고, 뭔가 '감'을 터득할 수 없는 분야이기 때문이다. 그래서 그런 걸 잘하는 사람들이 부럽다..

일례로 완전 최저수준 소켓 API와, 고수준 HTTP API 사이의 중간 과정에 대한 감이 전혀 없다. 후자도 분명 전자를 이용해서 구현됐을 텐데, 내부 구현이 어찌 돼 있는지 난 아는 게 없다.
그리고 네트워크 트래픽이 컴퓨터의 I/O 병목엔 어떤 영향을 끼치는지, 그 패킷이 어떻게 해서 한 운영체제 내부의 특정 응용 프로그램으로 잘 전달이 되는지, DDoS 공격이 서버 컴퓨터에 어떤 물리적인 영향을 끼쳐서 서버를 뻗게 할 수 있는지, (아님 단순히 프로세스/스레드의 무한 스폰으로 인해 소프트웨어적인 자원 고갈만으로 뻗는 건가?)

HTTP 프로토콜에서 파일 업로드는 어떤 절차를 거쳐서 되는지, 방화벽이라는 게 정확히 뭘 하는 물건인지,
왜 구닥다리 윈도 2000/XP sp0을 띄운 채로 랜선을 꽂으면 뭐가 뚫려서 어떻게 되는지..
요즘은 네트워크 패킷은 하부 계층에서 압축이나 암호화를 좀 하는 게 있는지 등등..

이런 것들은 난 하나도 모..른..다. 저런 거 하나도 몰라도 <날개셋> 한글 입력기 개발하는 덴 아무 지장이 없기 때문이다.
그렇다고 해서 내가 컴퓨터 명령어 체계나 운영체제/소프트웨어 자체의 내부 구조나 보안에 대해 전혀 모르느냐 하면 그것도 물론 아니니.. 지식의 분포가 좀 불균형하다면 불균형한 셈이다.

본인은 초딩 중고학년 때 개인용 PC, 중학교 때 모뎀과 PC 통신, 고등학교 때 인터넷과 이메일, 그리고 대학교 때 무선 인터넷과 휴대전화의 순으로 문명의 이기들을 접했다. 랜 선이라는 걸 태어나서 처음으로 구경한 게 고등학교 때부터인데, 그 기간 동안 언젠가 집도 인터넷 접속 방식이 전화 모뎀에서 전용선으로 바뀌었다. 그때가 한창 전국적으로 인터넷 전용선이 깔리던 시절이었으니까.

지금까지 통신 기술은 정말 눈부신 속도로 발전했다.
신문· 방송에서 기자의 이메일을 공개하는 게 대세가 된 게 1990년대 후반부터이다.
지금으로부터 10여 년 전엔 '블로그'라는 단어가 도전 골든벨의 마지막 문제의 답이었다는 게 믿어지시는가? (그것도 학생이 못 맞혔고 그 당시엔 내게도 생소했다)

옛날에는 인터넷 연결을 위해서도 PC 통신을 할 때처럼 먼저 전화를 걸어야 했다. 사용 시간 카운터가 올라가는 자그마한 인터넷 연결 창이 뜬 동안만 인터넷을 이용할 수 있었다.
또한, 모뎀과 마우스를 동시에 사용하려면 두 물건을 서로 COM 포트가 충돌하지 않게 배치를 해야 했다.
Windows 3.x에서는 운영체제 차원의 네트워크 지원이 전무하기 때문에 트럼펫 Winsock인지 뭔지 하는 걸 먼저 설치해야 했다.

이 모든 것들이 지금은 까마득한 옛날 이야기가 됐다.
지금은 뭔가 그렇게 상태를 확인하면서 인터넷을 해야 하는 상황은 스마트폰 태더링으로 무선 인터넷을 쓸 때 정도이고 이것도 제약, 압박감, 부담 같은 건 옛날과는 비교할 수 없이 작아졌다.
메인보드가 어떻게 공간 워프를 했는지, 요즘은 유선 랜과 무선 랜도 전부 내장되어 나온다. 따로 뭘 장착조차 할 필요 없이 바로 접속만 하면 된다.

오늘날 인터넷이라고 불리는 그 통신망은 OSI 레이어 계층 중 제3계층(네트워크 계층)을 차지하는 IP라는 프로토콜을 기반으로 동작한다. IPv4, IPv6 같은 주소 체계도 이 계층에서 규정하는 것이기 때문에 모든 인터넷 통신은 이 체계를 기반으로 구성되어 있다.

그리고 그 아래의 제4계층(전송 계층)에는 인터넷 프로토콜을 따르는 네트워크 패킷을 보내는 방식의 차이를 규정하는 프로토콜이 있는데, 크게 TCP와 UDP가 있다.
TCP는 보낸 패킷이 반드시 순서대로 도착한다는 것은 보장되지만, 보냈던 단위랄까 형태가 그대로 도착하지는 않는다.
aaa, bb, ccccc, ddd, e 이렇게 패킷을 보냈으면 받는 쪽은 aa, ab, bccc, cc, dd, d, e 뭐 이렇게 받을 수도 있고 다른 형태가 될 수도 있다. 조립은 받는 쪽에서 알아서 해야 한다.

UDP는 TCP와는 달리 보낸 패킷이 원래의 형태 그대로 간다는 보장은 되지만.. 일부 패킷이 전송 과정에서 누락될 수가 있다.
즉, 위의 경우 ddd가 누락돼서 aaa, bb, ccccc, e 이렇게 갈지도 모르지만.. 일단 간 놈은 원래 형태 그대로 간다. 패킷의 누락 여부 판단을 받는 쪽에서 알아서 해야 한다.
그래서 TCP는 일종의 스트림 지향적이며, UDP는 개개의 패킷이 모 아니면 도 형태로 가는 메시지 지향적이다.

형태도 보존되고 누락 현상도 없는 만능 프로토콜이 없는 이유야 뭐, 세상에 값도 싸고 성능도 좋은 물건은 존재하지 않기 때문인 것과 같은 맥락일 것이다.
그게 필요하면 UDP 같은 걸 기반으로 패킷 누락을 감지하고 재전송을 요청하는 로직을 응용 프로그램이 별도로 구현해 줘야 한다.

온라인 게임에서는 “기관총 난사 내지 캐릭터 이동 같은 것만 UDP이고 나머지는 다 TCP”라는 말 한 마디로 요약된다.
자주 발생하기 때문에 반응성이 중요하고 적당히 좀 씹혀도 상관 없는 것만 UDP이고.. 나머지 크리티컬한 것들은 다 TCP를 써야 한다는 뜻이다.
그러나 온라인 게임에서 발생하는 트래픽의 상당수, 대략 70% 가까이는 그래도 UDP 방식이라고 한다.

실시간으로 스트리밍되는 대용량 오디오/비디오 데이터도 자명한 이유로 인해 UDP 방식으로 전송된다.
이런 차이를 보면, TCP와 UDP의 관계는 사실상 무손실 압축과 손실 압축의 관계나 마찬가지인 것 같다.

TCP의 경우 응용 프로그램이 아니라 아래의 프로토콜 차원에서 패킷의 누락을 감지하여 누락이 있는 경우 재전송 요청을 한다.
그런데 모바일처럼 네트워크 환경이 원래 워낙 열악해서 패킷 손실이 굉장히 자주 발생하는 곳에서는
TCP 방식에서는 끝도 없이 재전송 요청을 하고 받은 데이터에 결함이 없는지 체크와 빠꾸만 반복하느라 응용 프로그램이 그 동안 멍하니 있어야만 하는 일이 발생한다고 한다.
즉, TCP가 구조적으로 오버헤드가 더 크니, 네트워크가 열악한 곳에서는 그런 동작을 감안해야 한다.

게임에서 그래픽 엔진, 물리 엔진, 동영상/캡처 엔진도 아니고 네트웍 엔진 미들웨어로 먹고 사는 분이 국내에 일단 한 분 계신다. 넷텐션의 대표이사인 배 현직 씨. 이 업계에서는 이미 유명인사이다.

난 네트워크 쪽 프로그래밍을 해 본 건 먼~ 옛날에 소켓 API 대충 뚝딱해서 오목을 만들고..
DirectPlay를 써서 스크래블 정도 보드 게임에다가 네트웍 플레이를 넣어 본 게 전부이다. 그래도 그것만으로도 굉장히 재미있는 경험이었다.
저수준에서 패킷 암호화, 각종 오류 처리 그런 건 모른다. DPlay는 나름 하드웨어 독립을 추구한 통신 API이긴 한데, 요즘은 모뎀이고 시리얼 케이블 그딴 건 다 없어졌으니 그런 추상화 계층이 필요가 없어지면서 자연스레 도태했다. 잘은 모르겠지만 제1계층(물리 계층)은 거의 획일화가 돼 버린 것 같다.

※ 여담. IPX는 어디로 갔는가?

스타크래프트에서 배틀넷 말고 그냥 LAN으로 친구들끼리 팀플을 할 때, 옛날에는 배틀넷 다음으로 위에서 둘째인 IPX를 으레 고르곤 했다. 그러나 어느 패치 때부터인가 맨 아래에 UDP가 추가되었으며 그걸 고르는 걸로 구조가 바뀌었다. IPX는 동작하지 않기 시작했다. 어찌 된 일일까?

IPX라는 프로토콜은 똑같이 이더넷 랜선으로 통신을 하지만, 오늘날의 인터넷과는 다른 방식으로 통신을 한다. 즉, IP와 대등한 제3계층에서 방식이 다른 프로토콜인 것이다. IPX는 옛날에 네트워크 솔루션으로 유명했던 노벨 사에서 개발했고 실제로 매우 널리 쓰이기도 했지만 오늘날은 IP에 밀려서 사라졌다.

Windows 95때까지만 해도 네트워크 구성요소들을 설치하고 나면 기본으로 깔리는 것은 IPX였다. TCP/IP 지원 기능은 운영체제 CD를 넣어서 별도로 설치해야 했다. 무슨 말이냐 하면, 오늘날 당연시되고 있는 이 컴퓨터의 IP 주소를 설정하는 기능이 Windows 95에는 기본으로 없었다는 뜻이다. (심지어 네트워크 기능이 설치된 컴에서도)

사용자 삽입 이미지

그 다음 1990년대 중후반, Windows 98부터는 인터넷의 중요성이 워낙 크게 부각되기 시작했으니 TCP/IP 지원도 같이 포함되었다.
여담이지만 Windows에서는 등록정보/속성을 나타내는 단축키가 R인 편인데, 95에서는 유독 저 대화상자에서만 R은 삭제이고, 등록정보는 P였다. 무척 불편했는데 이 역시 98부터는 다같이 R로 개선됐다.

하긴, 본인도 옛날부터.. Windows가 근거리 네트워크 차원에서 제공하는 컴퓨터 간의 폴더 공유 기능과, 웹브라우저로 띄우는 인터넷은 기술적으로 무슨 관계인가 궁금하긴 했다.
인터넷 열풍 앞에서 IPX는 점점 잉여로 전락했으며, Vista부터는 드디어 IPX 지원이 hlp 도움말만큼이나 짤렸다. 그래서 스타크래프트도 근거리 팀플에 인터넷 프로토콜을 사용하는 UDP 지원이 추가된 것이다.

Posted by 사무엘

2015/02/05 08:37 2015/02/05 08:37
, , , ,
Response
No Trackback , 10 Comments
RSS :
http://moogi.new21.org/tc/rss/response/1058

Trackback URL : http://moogi.new21.org/tc/trackback/1058

Comments List

  1. Lyn 2015/02/05 12:20 # M/D Reply Permalink

    요즘은 그렇지도 않아요.

    해킹문제땜에 UDP로 만들었다가 TCP 로 전환하는경우도 있음

    1. 사무엘 2015/02/05 12:46 # M/D Permalink

      네퉉 성능도 그만큼 뒷받침 되니까 올TCP가 시도되기도 하는가 보군요~!

    2. Lyn 2015/02/05 12:50 # M/D Permalink

      아뇨. 성능보다 중요한게 생긴거죠 ㅎㅎ

  2. 근성인 2015/02/05 21:49 # M/D Reply Permalink

    옛날에 형이 만든 프로그램들중에서 네트워크 대전 지원되는 것들 가지고 이런저런 의견 올렸던게 생각나네
    (날개셋 타자연습 넷 대전 구현하려던 시절에 상대방 대화가 안보이는 문제였던가..)

    1. 사무엘 2015/02/06 10:59 # M/D Permalink

      ㅋㅋㅋㅋ 그 흑역사를.. 네트웍 쪽으로 몰라도 너무 모르던 상태에서 경험했던 시행착오였지~
      특히 IME를 직접 만드는 게 불가능하다고 여겨졌기 때문에 타자방을 아예 자체 제작을 할 생각까지 했던 무모한 시절.. 완전 추억 돋네~~~

    2. Lyn 2015/02/15 03:04 # M/D Permalink

      아하. 초기버전은 IME 의 형태가 아니었나요?

    3. 사무엘 2015/02/15 03:20 # M/D Permalink

      네. 초창기에는 에디터인 날개셋 편집기만 있었습니다. 외부 모듈이 개발된 건 그로부터 4년 정도는 지난 3.0대 이후부터(since 2004~05)이고 그것도 정말 상상을 초월하는 엄청난 시행착오를 겪으면서 안정화가 됐지요.
      http://moogi.new21.org/tc/666 (헉 글 번호가.. ^^ 그런데 이 글에도 Lyn 님 댓글 있습니다)
      이 시간대에 깨 계시네요. 저는 설 연휴에다 휴가를 붙여서 잠시 후 가족 여행을 떠난답니다. 즐거운 연휴 보내세요~

  3. 김강진 2015/02/21 21:56 # M/D Reply Permalink

    안녕하세요? 저는 어쩌다 삼벌식을 쓰고 있는 직장인입니다. 이 좋은 것을 이전에 잠시 알았는데 잊어버리고 있다가 지금에사..완전 천지가 개벽하는 느낌으로 감사하며,,, 사용하고 있습니다. 방금 전부터요ㅎㅎㅎㅎㅎ
    정말 감사드립니다. 밥 한 번 멋지게 사고 싶은데 정말로 진심을 다해서요. 연락할 방법이 있을라나ㅋㅋ

  4. 비밀방문자 2015/02/21 22:04 # M/D Reply Permalink

    관리자만 볼 수 있는 댓글입니다.

    1. 사무엘 2015/02/22 20:50 # M/D Permalink

      안녕하세요? 반갑습니다. 말씀하신 곳으로 회신을 드렸습니다.
      저도 여러가지가 궁금하네요. 감사합니다. ^^

Leave a comment
« Previous : 1 : 2 : 3 : 4 : Next »

블로그 이미지

철도를 명절 때에나 떠오르는 4대 교통수단 중 하나로만 아는 것은, 예수님을 사대성인· 성인군자 중 하나로만 아는 것과 같다.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2018/05   »
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

Site Stats

Total hits:
960102
Today:
215
Yesterday:
526