C언어 - 연결리스트

▣ 연결리스트 - step2

어제 실습했던 step1은 파일을 읽어서 단순히 연결리스트만 만든 것이다.

step2는 step1의 중첩되는 부분을 for문이나 while문으로 변경하여 작성한다.

step2 소스보기(icount)

   1:  #include <stdio.h>

   2:  #include <stdlib.h>

   3:  #include <sys/stat.h>

   4:  #include <sys/types.h>

   5:  #include <fcntl.h>

   6:  #include "node.h"

   7:   

   8:  int main()

   9:  {

  10:      int ifd;

  11:      int iret;

  12:      NODE *stp_node;

  13:      NODE *stp_header = 0;

  14:      ifd = open("a.dat",    O_RDONLY);

  15:      if(0 > ifd)

  16:      {

  17:          printf("File open error()\n");

  18:          return -99;

  19:      }

  20:      /*------------------------중첩 되는 부분--*/

  21:      for(icount = 0; icount < 5; ++icount)

  22:      {

  23:          stp_node = malloc(sizeof(NODE));

  24:          if(stp_node == 0)

  25:          {

  26:              printf("동적 할당 실패\n");

  27:              return -88;

  28:          }

  29:          iret = read(ifd, stp_node, sizeof(NODE));

  30:          stp_node -> next = 0;

  31:          if(icount == 0)

  32:          {

  33:              stp_header = stp_node;

  34:          }

  35:          else

  36:          {

  37:              stp_node -> next = stp_header;

  38:              stp_header = stp_node;

  39:          }

  40:      }

  41:      /*---------------------------------------*/

  42:      while(0 != stp_header)

  43:      {

  44:          printf("%d -> ", stp_header -> iNum);

  45:          stp_header = stp_header -> next;

  46:      }

  47:      printf("NULL\n");

  48:      close(ifd);

  49:      return 0;

  50:  }

반복문 for문을 사용하여 중첩되는 부분을 줄여준다. 조건문 if로 icount가 0일 때

stp_header = stp_node; 명령 수행한다.

step1과 비교할 때 결과는 바뀐 것은 없다. 다만 긴 소스코드의 중첩된 부분을 반복문을 통해 줄여준 것이다.

하지만 문제점은 있다. icount라는 변수를 사용하여 동적 할당의 의미를 없게 만든 것이다. 연결리스트가

50개가 되면 icount < 50이라고 바꾼다. 이렇게 되면 고정된 수만큼의 동적 할당 받게 되고 그러면 동적 할당

의 의미가 없어지기 때문이다. icount를 사용하고 싶다면 동적 할당이 아닌 고정된 수만큼을 저장하는 배열을

쓰는 것이 편하다.

 

다음과 같이 바꿔준다.

step2 소스보기(while)

   1:  #include <stdio.h>

   2:  #include <stdlib.h>

   3:  #include <sys/stat.h>

   4:  #include <sys/types.h>

   5:  #include <fcntl.h>

   6:  #include "node.h"

   7:   

   8:  int main()

   9:  {

  10:      int ifd;

  11:      int iret;

  12:      NODE *stp_node;

  13:      NODE *stp_header = 0;

  14:      ifd = open("a.dat",    O_RDONLY);

  15:      if(0 > ifd)

  16:      {

  17:          printf("File open error()\n");

  18:          return -99;

  19:      }

  20:      /*------------------------중첩 되는 부분--*/

  21:      while(1)

  22:      {

  23:          stp_node = malloc(sizeof(NODE));

  24:          if(stp_node == 0)

  25:          {

  26:              printf("동적 할당 실패\n");

  27:              return -88;

  28:          }

  29:          iret = read(ifd, stp_node, sizeof(NODE));

  30:          stp_node -> next = 0;

  31:          if(0 == iret)

  32:          {

  33:              free(stp_node);

  34:              break;

  35:          }

  36:                  

  37:          if(0 == stp_header)

  38:          {

  39:              stp_header = stp_node;

  40:          }

  41:          else

  42:          {

  43:              stp_node -> next = stp_header;

  44:              stp_header = stp_node;

  45:          }

  46:      }

  47:      /*---------------------------------------*/

  48:      while(0 != stp_header)

  49:      {

  50:          printf("%d -> ", stp_header -> iNum);

  51:          stp_header = stp_header -> next;

  52:      }

  53:      printf("NULL\n");

  54:      close(ifd);

  55:      return 0;

  56:  }

반복문 while을 사용하여 무한반복 시키고 stp_header를 0으로 초기화 시켜준다.

if문에서 보면 stp_header가 0일 때 stp_header = stp_node; 명령 수행하도록 한다.

명령을 수행 후에 stp_header는 0이 아닌 stp_node가 가리키는 주소를 가리키게 된다.

그 이후에 else안의 명령이 계속 수행되어 iret의 값이 0일 때 while문을 빠져 나온다.

만약에 stp_header의 초기값을 0으로 초기화 하지 않으면 어떻게 될까?

stp_header의 초기값이 0으로 정해져 있지 않으면 if문을 수행하지 않고 바로 stp_node를

따라간 주소의 next가 stp_header의 쓰레기 값을 가리키게 된다.

그래서 결과를 출력하게 되면..

보기 좋게 세그멘테이션 오류가 발생한다.

▣ 연결리스트 – step3

step2가 step1의 업그레이드 된 버전이라면 step3은 사람을 생각하게 만드는

연결리스트이다. 삽입할 위치 정하여 정렬하는 소스이다.

step3 소스보기

   1:  #include <stdio.h>

   2:  #include <stdlib.h>

   3:  #include <sys/stat.h>

   4:  #include <sys/types.h>

   5:  #include <fcntl.h>

   6:  #include "node.h"

   7:   

   8:  NODE* insert (NODE*, NODE*);

   9:  int main()

  10:  {

  11:      int ifd;

  12:      int iret;

  13:      NODE *stp_node;

  14:      NODE *stp_header = 0;

  15:      ifd = open("a.dat",    O_RDONLY);

  16:      if(0 > ifd)

  17:      {

  18:          printf("File open error()\n");

  19:          return -99;

  20:      }

  21:      /*------------------------중첩 되는 부분--*/

  22:      while(1)

  23:      {

  24:          stp_node = malloc(sizeof(NODE));

  25:          if(stp_node == 0)

  26:          {

  27:              printf("동적 할당 실패\n");

  28:              return -88;

  29:          }

  30:          iret = read(ifd, stp_node, sizeof(NODE));

  31:          stp_node -> next = 0;

  32:          if(0 == iret)

  33:          {

  34:              free(stp_node);

  35:              break;

  36:          }

  37:          stp_header = insert(stp_header, stp_node);

  38:      }

  39:      /*---------------------------------------*/

  40:      while(0 != stp_header)

  41:      {

  42:          printf("%d -> ", stp_header -> iNum);

  43:          stp_header = stp_header -> next;

  44:      }

  45:      printf("NULL\n");

  46:      close(ifd);

  47:   

  48:      return 0;

  49:  }

  50:  /*연결리스트의 제일 처음을 리턴한다*/

  51:  NODE* insert (NODE* stp_header, NODE* stp_node)

  52:  {

  53:      NODE* current;            //삽입할 위치를 찾아줄 포인터

  54:      NODE* prev;                //current의 이전 위치를 찾아줄 포인터

  55:      if(0 == stp_node)        //삽입할 값이 없다면

  56:      {

  57:          return stp_header;    //연결리스트에 삽입하지 않고 바로 반환

  58:      }

  59:      if(0 == stp_header)        //처음인지 확인

  60:      {

  61:          stp_header = stp_node;

  62:          stp_header -> next = 0;

  63:          return stp_header;    //처음위치를 가리키는 stp_header를 반환

  64:      }

  65:      current = stp_header;     /*초기화. current가 움직이면서 

  66:                                삽입할 위치를 찾음*/

  67:      prev = current;

  68:      

  69:      while(1)    //반복문으로 삽입할 위치를 찾는다.

  70:      {

  71:          if(0 == current)    //리스트를 끝까지 검색하게 되면

  72:          {

  73:              break;

  74:          }

  75:                  

  76:          if(stp_node -> iNum < current -> iNum)//삽입할 위치를 찾을때

  77:          {

  78:              break;            //prev와 current사이에서 break;

  79:          }

  80:          prev = current;

  81:          current = current -> next;

  82:      }

  83:      if(stp_header == current)            //처음 삽입

  84:      {

  85:          if(0 != current)

  86:          {

  87:              stp_node -> next = stp_header;

  88:              stp_header = stp_node;

  89:          }

  90:          else

  91:          {

  92:              stp_header -> next = stp_node;

  93:          }

  94:      }

  95:      else                            //중간 삽입과 뒤에 삽입

  96:      {

  97:          stp_node -> next = current;

  98:          prev -> next = stp_node;

  99:      }

 100:      return stp_header;

 101:  }

 

기본적으로 하나의 리스트에서 또 다른 리스트가 추가 될 때 앞에 삽입된다.

step3는 앞에 삽입외에 중간 삽입, 끝에 삽입을 위해 삽입할 위치를 찾아 삽입하고자

하는 위치에 넣고 원하는 위치에 삽입하므로써 정렬이 되어 출력하도록 하는 것이 목적이다.

step2의 소스에서 앞에 삽입에 해당하는 소스를 복사하여

insert함수를 선언하고 붙혀 넣은 후 else안의 명령들을 삭제한다.

 

a.dat파일은 아래와 같이 저장되어 있다고 가정한다.

1, 3, 5는 리스트가 만들어져 있고 2를 삽입하기 위해 1과 3사이에 중간 삽입하기 위한 과정을

일부를 설명하고자 한다. 삽입하고자 할 때는 정렬이 전제 되어야 한다. 사람도 1,3,5라는 번호를 보여 주지

않고 2를 어디에 삽입해야 할지 모른다. 함수입장에서 리스트의 내용을 알 수 없게 되면 정렬이 불가능해 진다.

삽입할 위치를 찾기 위해서 stp_header 포인터를 움직이게 되면 뒷 쪽으로 움직인 포인터가

다시 앞쪽으로 움직일 수 없는 단뱡향 연결리스트의 단점 때문에 앞에 생성된 리스트의

위치를 알 수 없게 된다.

그래서 stp_header 대신 삽입할 위치를 찾아줄 구조체 포인터 current 선언해준다.

포인터 current는 stp_header가 가리키고 있는 주소를 가리키게 된다.

하지만 current가 찾게 되는 곳은 삽입해야 할 위치의 그 다음 위치를 가리키게 된다. 이전 위치를

알 수 없게 된다. 그렇게 되면 앞의 삽입과 다르지 않다. 그래서 이전을 뜻하는 구조체 포인터 prev를

선언해준다.

포인터 prev는 current가 가리키고 있는 주소를 가리키게 된다.

while문으로 진입하여 if문이 참인지 거짓인지를 판단한다.

current가 0이 아니므로 다음 if문의 참 거짓을 판단한다. 참일 경우는 삽입해야 할 위치를 찾았을 때

거짓인 경우는 삽입해야 할 위치를 찾지 못했을 때이다. 참과 거짓은 유일한 키값인 iNum을 비교하여

판단하게 된다.

주민등록번호는 데이터베이스에서 키값이다. 유일하게 자신을 나타낼 수 있는 고유 값인 것이다.

while문을 다시 수행하게 되면 두번째 if문에 조건에 만족하게 된다. prev와 current사이에서 break가

발생한다. if문에서 다시 참과 거짓을 판단한다.

위의 if문이 참이 되기 위해서는 다음과 같은 상황이어야 한다.

리스트가 하나만 존재할 때이다. if문을 수행하게 되면 아래와 같이 앞에 삽입되고

else를 수행하게 되면 뒤쪽 삽입이 된다.

하지만 지금은 1과 3사이에 중간 삽입을 해야 한다.

중간 삽입이 이루어 진 것을 알 수 있다.

▣ 네트워크

좀비 프로세스

좀비 프로세스는 프로세스 종료 후 메모리상에서 사라지지 않은 프로세스를 말한다.

fork()함수 호출 이후 자식 프로세스가 종료되면서 반환된 값 0을 부모 프로세스가 받지

못하면 자식 프로세스는 좀비 프로세스가 된다.

자식 프로세스가 좀비 프로세스가 되지 않기 위해서 부모프로세스가 커널에게 자식 프로세스가 종료될

때의 반환값을 요청한다. 함수를 요청하는 함수로 wait()함수를 사용한다.

status : 포인터 status가 가리키는 변수에 자식 프로세스 종료시 리턴하거나 exit 함수 호출시 전달한

           인자 값이 저장됨.

fork_wait.c 소스보기

   1:  /* fork_wait.c */

   2:   

   3:  #include <sys/types.h>

   4:  #include <unistd.h>

   5:  #include <sys/wait.h>

   6:   

   7:  int global_var = 0;            //전역 변수 선언

   8:   

   9:  int main()

  10:  {

  11:      pid_t fork_ret;

  12:      pid_t child;

  13:      int local_var = 0;        //지역 변수 선언

  14:      int state;

  15:      

  16:      fork_ret = fork();        //하나의 프로세서가 fork에 의해 두 개로 나눠짐.

  17:      if(fork_ret < 0)

  18:      {

  19:          printf("fork() error");

  20:          exit(1);

  21:      }

  22:      else if(fork_ret == 0)    //자식 프로세스인 경우

  23:      {

  24:          global_var++;

  25:          local_var++;

  26:          printf("CHILD - my PID : %d parent's PID : %d \n", getpid(), getppid());

  27:      }

  28:      else                    //부모 프로세스인 경우

  29:      {

  30:          global_var += 5;

  31:          local_var += 5;

  32:          printf("PARENT - my PID : %d child's PID : %d \n", getpid(), fork_ret);

  33:          

  34:          child = wait(&state);    //자식 프로세스의 종료대기

  35:          printf("\t Child PID = %d \n", child);

  36:          printf("\t retur value = %d \n", WEXITSTATUS(state));

  37:   

  38:          sleep(10);

  39:      }

  40:      printf("\t global_var : %d \n", global_var);

  41:      printf("\t local_var : %d \n", local_var);

  42:   

  43:      return 0;

  44:  }

커널이 반환값을 전달 해주면 자식 프로세스는 소멸된다. 하지만 wait()함수는 호출 시점에서 자식 프로

세스의 종료가 없을 경우에 자식 프로세스가 종료될 때까지 Blocking상태에 빠진다.

이러한 Blocking상태를 해결하기 위해서 Waitpid()함수를 쓴다.

pid : 종료 확인을 원하는 자식 프로세스 ID. 임의의 자식 프로세스인 경우 -1 대입.

status : wait 함수의 status와 같은 역할

options : sys/wait.h에 정의된 ‘WNOHANG’ 상수를 인자로 전달하게 되면 이미 종료한 자식 프로세스가

            없는 경우 blocking 상태로 가지 않고 바로 리턴함. 이때 waitpid 함수의 리턴 값은 0이 된다.

하지만 waitpid()함수는 자식 프로세스가 언제 종료될지 몰라 함수를 여러 번 호출해야 한다.

fork_waitpid.c 소스보기

   1:  /* fork_waitpid.c */

   2:   

   3:  #include <sys/types.h>

   4:  #include <unistd.h>

   5:  #include <sys/wait.h>

   6:   

   7:  int global_var = 0;

   8:   

   9:  int main()

  10:  {

  11:      pid_t fork_ret;

  12:      pid_t child;

  13:      int local_var = 0;        

  14:      int state;

  15:      

  16:      fork_ret = fork();        

  17:      if(fork_ret < 0)

  18:      {

  19:          printf("fork() error");

  20:          exit(1);

  21:      }

  22:      else if(fork_ret == 0)    //자식 프로세스인 경우

  23:      {

  24:          global_var++;

  25:          local_var++;

  26:          printf("CHILD - my PID : %d parent's PID : %d \n", getpid(), getppid());

  27:          sleep(10);            //종료를 10초 지연

  28:      }

  29:      else                    //부모 프로세스인 경우

  30:      {

  31:          global_var += 5;

  32:          local_var += 5;

  33:          printf("PARENT - my PID : %d child's PID : %d \n", getpid(), fork_ret);

  34:          

  35:          do

  36:          {

  37:              sleep(3);

  38:              puts("3초 대기");

  39:   

  40:              child = waitpid(-1, &state, WNOHANG);

  41:          }

  42:          while(child == 0);    //종료된 자식 프로세스가 있으면 빠져나옴

  43:      

  44:          printf("\t 종료된 자식 프로세스 ID = %d \n", child);

  45:          printf("\t 종료된 자식 프로세스의 리턴값 = %d \n", WEXITSTATUS(state));

  46:   

  47:          sleep(10);

  48:      }

  49:      printf("\t global_var : %d \n", global_var);

  50:      printf("\t local_var : %d \n", local_var);

  51:   

  52:      return 0;

  53:  }

그래서 sigaction함수를 사용하여 SIGCHLD가 발생시 부모 프로세스가 자식 프로세스의 리턴 값을 읽도록

한다. waitpid 함수의 호출 시점은??

- 자식 프로세스가 종료되는 순간 부모 프로세스가 waitpid 함수를 호출하도록 해야 함

- 자식 프로세스가 종료된 시점에 발생하는 시그널 SIGCHLD를 이용

fork_signal.c 소스보기

   1:  /* fork_signal.c */

   2:   

   3:  #include <sys/types.h>

   4:  #include <unistd.h>

   5:  #include <sys/wait.h>

   6:   

   7:  void z_handler();            //시그널 처리함수

   8:  int global_var = 0;

   9:   

  10:  int main()

  11:  {

  12:      pid_t fork_ret;

  13:      pid_t child;

  14:      int local_var = 0;        

  15:      int state;

  16:   

  17:      struct sigaction    act;

  18:      act.sa_handler = z_handler;

  19:      sigemptyset(&act.sa_mask);

  20:      act.sa_flags = 0;

  21:   

  22:      state = sigaction(SIGCHLD, &act, 0);    //자식 프로세스 종료시

  23:      if(state != 0)

  24:      {

  25:          puts("sigaction() error. ");

  26:          exit(1);

  27:      }

  28:      

  29:      fork_ret = fork();        

  30:      if(fork_ret < 0)

  31:      {

  32:          printf("fork() error");

  33:          exit(1);

  34:      }

  35:      else if(fork_ret == 0)    //자식 프로세스인 경우

  36:      {

  37:          global_var++;

  38:          local_var++;

  39:          printf("CHILD - my PID : %d parent's PID : %d \n", getpid(), getppid());

  40:      }

  41:      else                    //부모 프로세스인 경우

  42:      {

  43:          global_var += 5;

  44:          local_var += 5;

  45:          printf("PARENT - my PID : %d child's PID : %d \n", getpid(), fork_ret);

  46:          

  47:          sleep(5);

  48:      }

  49:      printf("\t global_var : %d \n", global_var);

  50:      printf("\t local_var : %d \n", local_var);

  51:   

  52:      return 0;

  53:  }

  54:   

  55:  void z_handler()

  56:  {

  57:      pid_t    child;

  58:      int        state;

  59:   

  60:      child = waitpid(-1, &state, WNOHANG);

  61:      printf("\t 소멸된 자식 프로세스 ID = %d \n", child);

  62:      printf("\t 소멸된 자식 프로세스의 리턴값 = %d \n", WEXITSTATUS(state));

  63:  }