[내장형]황세선 2011년7월12일 수업내용

Linked List

저번시간에 배운 링크드 리스트 중에서 Double Linked List 를 살펴 보겠다. 먼저 일반 적인 Double Linked List 의 구조는 아래와 같다.

Double Linked List 란 양방향으로 연결되어진 Linked List 를 말한다. 이것은 다른말로 이중 연결리스트, 양방향 연결리스트 라고도 한다.

Linked List 의 사용예
우리가 즐겨쓰는 메모장이 한 예라고 할 수 있다. 아래 그림을 통해 설명한다.

메모장에 다음과 같은 글이적혀있다면 글자 하나하나가 링크의 대상이 되어 아래와 같이 연결되어 져 있는 셈이 된다.

이런 메모장에서 글자가 하나씩 추가 될때 마다 링크가 연결되는데 먼저 맨앞에 a 라는 문자가 들어왔을때는 아래와 같이 연결이 된다.

맨앞 t 에 묶여 있던 NULL(접지모양) 을 a 문자에 연결하고 a 문자는 다시 t 를 연결 시킨다. 그리고 연결된 a 문자의 한 링크는 NULL(접지모양)에 묶이게 된다.

다음은 뒤에 붙을 경우다.

뒤에 붙는 과정 역시 앞에 붙는것과 비슷하다.

다음은 중간에 삽입될 경우이다. 이 경우는 조금 복잡해지는데 일단 아래 그림을 보자.

t 와 e 사이에 a 가 들어오는 경우다. 이 경우는 t 의 링크와 e 의 링크 모두를 수정해야되기 때문에 복잡하다. 복잡하기는 하지만 단순하게 생각해 보자. 먼저 단방향만 생각해서 연결한다음 그 단방향의 역방향을 연결해 주면 쉽게 연결이 완성된다.
위와 완전히 같지는 않지만 메모장은 저런 식으로 문자를 관리하고 있다. 이런 연결 리스트의 특징때문에 우리는 중간에 문자를 삽입하거나 지우거나 해도 문장이 유지 된다. 마지막 으로 아래는 메모장에서 여러 줄을 입력했을때의 구조다.

중간에 t 문자를 봤을때 그 주변 으로 4방향의 양방향 연결 구조를 가진다. 이렇게 메모장은 연결 리스트로 되어 있으며 그 구조는 참 복잡하다는 것을 알수 있다.

배열과 비교한 연결리스트의 장점
연결리스트는 배열과 비교했을때 그 장점이 들어 난다. 연결리스트는 데이터를 효율적으로 저장하기 위해 쓰인다. 그리고 그 데이터는 클수도 있고 작을수도 있다. 만약 데이터가 크다고 생각해보자. 그리고 이 데이터를 배열에 저장한다고 하자. 배열에 이 큰 데이터를 순차적으로 넣을때는 문제가 없다. 하지만 중간에 삽입 한다 던가 맨앞에 붙인다 던지 하면 문제가 생긴다. 중간에 붙일 경우를 예로 들면 붙인 자리 뒤쪽의 모든 데이터는 중간 데이터가 차지한 공간 만큼 뒤로 밀려 져야 된다. 또한 일반 적인 배열은 그 크기가 딱 정해져 있다. 그러니까 우리는 배열을 선언할때 아래와 같이 배열의 크기를 딱 정해 버린다.

int array[1024];

위 선언을 예로 들면 만약 4바이트 데이터가 1024 개를 넘어가게 되면 더이상 저장을 할수 없다. 이런 문제를 해결하기 위해서 동적할당이 있다. 그러나 이런 문제점을 해결했다 해도 중간에 삽입할때 뒤로 데이터가 밀어져야 하는 문제는 여전히 해결하지 못한다.
이제 연결리스트의 장점이 드어난다. 연결리스트는 위의 두 문제를 해결한다. 제일 처음 Double Linked List 에서 봤던것 처럼 앞, 뒤 , 중간 에 대한 삽입도 쉽게 할 수 있다. 또한 노드를 동적으로 할당하기 때문에 heap 영역이 수용할수 있을 만큼 가변 적으로 데이터를 저장할 수 있다.
정리 하자면 연결리스트는 데이터의 삽입이 쉽고 동적으로 할당된 노드로 인해 저장할 데이터의 수가 크거나 작을 지라도 유연하게 대처할 수 있다.

메모리 구조 리뷰
배운 내용이지만 약간의 내용을 더 추가하여 메모리 구조를 리뷰해 보겠다. 먼저 그림을 하나 그려놓았다.

그림이 상당히 복잡해 보이는데 먼저 맨 왼쪽 위의 그림을 보자. 이것은 프로그램이 메모리에 적재 되었을때의 모습이다. 우리가 잘 알고 있는 5개의 영역이 그려져 있다. 5개 의 영역중 맨위 3개의 영역은 컴파일시에 생성이 된다. 이것을 다른 말로 Compile Time 에 생성된다고 한다. 그리고 3영역 외의 나머지 2 영역은 실행시 생성되는 부분이고 이를 Run Time시 생성된다고 한다.
아래 2 영역을 잠깐 살펴 보면 먼저 스택 영역은 잘 알고 있다. 이것은 지역 변수를 저장하기 위해 쓰이는 공간이다. 그리고 바로 위에 heap 영역이 있는데 이곳이 바로 동적할당을 위해 쓰이는 공간이다. 우리는 malloc 함수 등을 이용하여 메모리 할당을 요구하면 이 영역에 메모리를 할당 받는 것이다.

그림의 왼쪽 맨아래를 보면 exe 파일의 대략적인 모습을 그려놓은 것인데 앞 부분에 header 가 있으며 뒷 부분에는 컴파일시 생성되는 3개의 영역이 있다. header 는 뒤의 데이터에 대한 정보를 저장하고 있으며 이정보는 윈도우즈의 경우 PE 구조, 리눅스의 경우 ELF 구조를 분석해보면 알수 있게 된다. 3개의 영역을 code, data, bss 순으로 나열해 놓았지만 이는 정말로 저런 순으로 저장되어 있는것이 아니다. 3개 영역이 저장된 모습은 이 보다 훨씬 복잡하게 되어 있다.

이제 맨 오른쪽의 그림을 보자. 이 그림이 설명하고 있는 것은 스택이 자라나는 방향과 힙이 자라나는 방향에 대한 설명이다. 자라난다고 하였는데 이는 메모리 안에 데이터가 쌓여가는 방향을 뜻한다고 할 수 있다. 일반 적으로 heap 영역은 위에서 아래로 자라난다. 그리고 스택은 아래에서 위로 자라난다. 생각해보면 자라나는 방향이 특이한데 이것은 다 이유가 있다. 그림을 보면 두 그림을 비교해 놓았는데 왼쪽이 지금 설명하고 있는 그것이고 오른쪽 것은 문제가 있는 구조다. 둘의 차이는 스택이 자라나는 방향과 스택의 시작 위치가 차이가 난다. 그림에서도 설명하고 있듯이 오른쪽의 경우는 스택은 공간을 얼마 쓰지도 않으면서 아래 공간을 차지하고 있고 힙은 부족하지만 스택이 쓰지 않는 공간을 활용할수가 없다.  반면 왼쪽 같은 구조에서는 스택이 공간을 얼마 쓰지 않는다면 힙은 그 공간을 활용할수 있게 되고 반대로 힙이 공간을 적게 사용하고 있을 경우 스택이 그 공간을 활용할수 있게 된다. 결과 적으로 왼쪽 구조가 공간 활용도가 높기 때문에 쓰이고 있는것이다.
참고로 이러한 스택과 힙 영역의 크기는 얼마로 해야 적당할지 알수 없는데 이는 경험에 비롯하여 그 크기가 정해진다.

exe 파일의 실행
우리가 실행하는 exe 파일은 어떠한 다른 프로그램이 우리의 exe 파일을 메모리에 적재 시켜 주기 때문에 실행이 가능하다. 우리의 exe 파일을 메모리에 적재 시켜 주는 것을 Loader 라고한다. 이 로더는 내부 적으로 open 과 같은 함수로 파일을 열어 파일처리한 결과를 메모리 상으로 넣어 주게 된다. Loader 부분은 아직 PE 구조와 Loader에 대해 잘 알지 못하기 때문에 자세한 설명 생략한다.

API
API 란 Application Programming Interface 약자다. 이 API 는 함수의 묶음을 뜻하고 우리가 알고 있는 printf 함수 및 scanf 함수도 표준 C 에서 제공하는 API 함수다. 이거 외에 Network 의 socket 함수, 동적 할당의 malloc, calloc 함수 등도 다 API 라고 할 수 있다.

동적할당 함수
리눅스 터미널창에서 man 으로 malloc 을 쳐보면 아래와 같이 나온다. 이것은 동적할당과 관련있는 함수들로 함수의 기능에 대해서 조금 설명하겠다.
먼저 잘 알고 있는 malloc 함수다. 이 함수는 heap 영역에 size 만큼의 바이트를 할당하고 그 할당된 주소를 반환 하는 함수다. 이 함수의 특징은 할당된 메모리의 초기 값이 쓰레기 값이라는 점이다.
calloc는 malloc 과 거의 같으며 차이점은 메모리의 초기 값이 0 이라는 점이다. free 는 동적 할당된 메모리를 해제 하
는 함수이며 realloc 함수는 동적 재할당 하는 함수다.
참고로 테스트 삼아 malloc 함수를 동적할당을 하고 메모리를 확인해본 결과 0 으로 초기화 되어 있었다. 쓰레기 값일줄 알았는데 예상 밖이다. 이 점에 대해서는 좀더 알아 봐야할것 같다.

납땜
흘려 들어도 될 내용이다. 납땜에 대해서 조금 정리한다. 아래 그림을 보자.

위 그림은 실납과 납땜 부위를 확대 해 놓은 동판 및 부품 다리다. 실납 이라고 했는데 실처럼 생긴 납이라 그렇게 불려지는게 아닌가 싶다. 이 실납에는 중간에 송진이 들어가 있다. 이 송진은 납땜을 하면 납땜 부위에 막을 형성해 부식을 방지 한다. 그리고 오른쪽 그림의 동판은 납이 잘 붙는 성질로 되어 있어 납땜을 쉽게 해준다.


아래 그림은 납땜 하는 법과 불량에 관해서 그려 놓은 그림이다.

납땜이 잘 되려면 동판과 다리에 온도가 골고루 전해 져야 납땜이 잘된다. 만약 그렇지 않을 경우 납이 다리 및 동판에 잘 붙어 있지 않아 시간이 지나면서 떨어져 나가 접촉 불량이 생길수 있다. 또한 납땜중 기포가 들어가게 되면 나중에 외부 열에 의한 팽창으로 역시 납이 떨어져 나가 접촉 불량이 생길수 있다.

아래는 납땜 모습을 보여준다.

납땜은 왼쪽 과 같이 너무 부족하게 해서도 안되며 과하게 해서도 안된다. 개인 적으론 그래도 부족한것 보단 과한게 그나마  좋지 않나 싶다. 이유는 일단 튼튼해 보여서다.

아래 그림은 납강 에 대한 그림이다.

요즘은 가판 아래에 납물을 흘려 납땜을 한다고 한다.

교제 10-1 소스
아래 소스는 구조체의 동적 할당을 보여주는 간단한 예다. 우리가 주목해야 할 부분은 소스의 중간 쯤인 빨간 색 및 파란색, 초록색 코드 부분이다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
  char name[20];
  int score;
} STUDENT;

int main()
{
  STUDENT st[3];
  STUDENT  *sp;
  int i;

  sp = malloc(sizeof(STUDENT));
  if(NULL == sp)
  {
    printf("allocation error\n");
    exit(-1000);
  }

  printf("main %08X\n", main);
  printf("st %08X\n", st);
  printf("sp %08X\n", sp);

  i = 0;
  while(3 > i)
  {
    printf("Please enter student name & score : ");
    scanf("%s %d", sp->name, &sp->score);
    //strcpy(st[i].name, sp->name);
    //st[i].score = sp->score;

    //bcopy(sp, &st[i], sizeof(STUDENT))
    memcpy(&st[i], sp, sizeof(STUDENT));
    ++i;
  }
  free(sp);

  for(i = 0 ; 3 > i ; ++i)
  {
    printf("student name : %s,\tscore : %d\n", st[i].name, st[i].score);
  }
  
  return 0;
}

위 프로그램은 3번 학생 이름과 성적을 입력 받는데 입력 데이터는 동적으로 할당한 구조체서 받아오며 저장은 st 라는 구조체 변수에 옮겨 저장하고 있다.
결론 부터 말하자면 위의 빨간 두줄의 명령은 아래의 파란줄 명령, 초록색줄 명령 과 같은 역활을 한다. 즉 아래와 같은 그림이 된다.

빨간 명령과 파란 명령 그리고 초록 명령이 같은 일을 수행하고 있다. 빨간 명령은 두번에 걸쳐 실행 되지만 아래 두 명령은 단 한번의 명령으로 수행이 된다. 빨간 명령이 두개인 이유는 사용자 입력이 저장된 영역의 정보를 name 과 score 로 나누어 들고 오고 있기 때문이다. 하지만 아래 두 명령은 name 과 score 의 구분없이 정확히 구조체의 크기 만큼 byte 를 복사해 오고 있다.

빨간색 명령의 strcpy 함수는  많이 보온터라 잘 알고 있을것이고 아래 두 명령은 리눅스의 man 명령으로 확인해보면 아래와 같다.

두 함수는 거의 비슷한 일을 하는 함수다. 근원지 주소로 부터 목적지 주소로 n 비트 많큼 복사하는 함수로 두 함수의 차이점은 인자의위치 및 반환 형이 다르다.  memcpy 함수는 반환 형으로 void* 를 반환하며 이는 dest 의 목적지 주소를 나타낸다.

추가 적으로 위 소스에서 보면 printf 함수로 main, st, sp 의 값을 출력해 보고 있는데 이는 전부 주소 값의 출력이다. 일단 출력 결과는 아래와 같다.

main 의 주소 출력 결과는 분명 코드 영역의 주소다. 그리고 구조체 배열변수인 st는 분명 스택 영역의 주소다. 그리면 sp 의 값은 어떤 영역의 주소일까? 이것이 바로 힙 영역의 주소다. 우리는 구조체 를 동적으로 할당하기 위해 malloc 을 호출 하였다. 그 반환 값을 sp 에 넣었었고, 이것으로 볼때 이 값은 heap 영역의 일부라는 것을 알수 있다. 주소 값을 보더라도 main(code) -> sp(heap) -> st(stack) 순으로 커진다는 것을 알수 있다.

캐릭터 LCD
아래는 오늘까지 진행한 ARM, LCD 결선도 다.
GND 선과 VCC 선은 절대 적으로 정확히 연결되어야 된다.

UDP 상에서의 connect 함수
connect 함수는 TCP 상에서 서버와 통신을 하기 위한 연결 요청 함수로 사용해 왔다. 그러나 이 함수는 TCP 뿐 아니라 UDP 상에서도 사용할수 있는데 그 의미가 달라진다. 아래 그림을 보자.

위 그림은 TCP 를 사용할때와 UDP 를 사용할때의 시스템 내부 모습이다. 우리가 패킷을 전송하기 위해서는 소켓이 있으면 된다. 하지만 소켓만 있다고 전송되지 않는다. 바로 커널과 연결이 되어 야지만 전송 되는 것이다. 일단 TCP 의 경우는 connect 함수를 통하여 항상 커널과 연결이 되어 있다.
이제 UDP 를 보면 TCP는 커널과 항상 연결되어 있는 반면 UDP 는 그렇지 않다. 패킷을 전송할때만 커널과 소켓이 연결된다. 그리고 패킷을 전송하면 다시 연결을 끊어 버리게 된다.  결국 패킷을 100번 보낸다면 커널과 소켓의 접속을 100 번 연결하고 끊게 된다. 윤성우 저의 TCP/IP 소켓 프로그래밍 책을 보면 소켓과 커널의 연결이 데이터 송/수신 시간에 있어 1/3 이나 소모 한다고 한다. 소켓과 커널의 연결은 생각보다 오래 걸리는 작업이다.

이제 UDP 상에서의 connect 함수의 효과 에 대해서 알아보겠다. 데이터를 먼저 송신하는 쪽을 클라이언트로 봤는때 connect 함수를 호출하면 이는 커널과 소켓을 연결한다. connect 함수 인자로 서버의 IP 와 PORT 번호를 넣어주는데 이것 때문에 우리는 TCP 에서나 쓸수 있던 write, read 함수를 쓸수 있게 된다. 그렇게 되면 sendto 나 recvfrom 에서 적어주던 목적지의 IP 및 PORT 번호를 매번 패킷을 보낼때마다 적어주는 수고를 덜수 있다. 또한 책 91 페이지의 내용에 따르면 소켓에서 일어날수 있는 이전 행위에 대한 에러를 확인 할 수 있다고 한다. 에러에 대한 예를 들면 존재 하지 않는 IP 나 포트 번호에 대한 에러가 있다. 원래 UDP 는 신뢰 할수 없는 전송을 가지지만 connect 함수를 이용하게되면 어느 정도의 신뢰성은 보장할수도 있겠다는 생각이 든다.

이제 이 connect 함수를 이용한 클라이언트를 구현해 보겠다. 소스는 아래와 같다.

소스를 보면 18 번째 줄에서 21 번째 줄까지가 패킷을 전송할 서버의 IP 및 PORT 번호 설정하는 부분이다. 이 설정 값을 connect 함수에 넣어 주면 이제 커널과 소켓이 연결되고 read, write 함수를 사용할수 있게 된다. 원래 위 소스 코드를 실행하게 되면 서버가 잘 응답을 했는지 알길이 없다. 그 대안으로 read 함수 뒤에 printf 로 read 의 반환 값을 찍게 하여 -1 이 나올경우 서버가 꺼져있거나 무엇인가가 잘못됐다는 것을 알수 있다. 이 방법 외에 message 변수를 하나더 만들어 read 로 읽을때 이 새로운 message 변수로 읽어와 출력해 보면 된다.
아래는 성공시 결과와 실패시 결과화면이다.

 성공시 화면

 실패시 화면

잘보면 성공시 6 이나오고 실패시 -1 이 나온다. hello 는 5자 인데 6이 나오는 이유는 fgets 함수에서 엔터문자까지 받아 들이고 엔터 문자를 포함하여 송/수신 하였기 때문이다. 즉 hello + '\n' 가 포함 되어 있는 셈이다.

소켓 옵션
소켓은 생성시 기본 옵션 값을 가지는데 우리는 여태까지 이 기본 옵션을 아무 불편함 없이 써왔다. 하지만 프로그램이 고급화 되고 상황에 맞는 소켓이 필요하게 되면 소켓 옵션을 적절히 사용하여야 한다.  소켓 옵션 설정에서 주로 사용하는 함수는 아래와 같다.

get 함수는 소켓의 현재 설정 값을 읽어 오는 함수이며 set 함수는 소켓의 옵션을 설정하는 함수다. 인자를 간단히 설명하자면 첫번째 인자는 소켓이며, 두번째 인자는 소켓 옵션 레벨을 뜻한다. 세번째 인자는 옵션의 종류 이고 4번째 인자는 옵션 값을 저장하는 버퍼에 대한 포인터다. 마지막으로 다섯번째는 옵션의 종류에 따라 알맞게 지정되어야 하는 버퍼의 크기를 나타낸다. 참고로 옵션 표는 교재 146 페이지에 나와 있다.