Wednesday, April 30, 2008

Manipulating Memory

메모리를 다루는 여러 함수들을 살짝 다루고 넘어가자.

특정 값으로 초기화 는 memset을 사용한다. BSD에서는 bzero를 사용하기도 한다. malloc 한 후 memset 하는 짓... 하지 말고 그냥 calloc() 을 사용하는 것이 함수 호출도 줄이고, 코드도 짧아지고, 성능도 향상된다.

#include <string.h>
void * memset(void *s, int c, size_t n);

메모리 비교하기 는 memcmp를 쓰면된다. 마찬가지로 BSD에서는 bcmp를 지원한다. 주의할 것은 구조체의 경우 패딩값으로 쓰레기 값들이 들어갈 수 있어서 구조체의 비교를 memcmp로 하면 안된다(같아도 다른 값이 나올 수 있기 때문이다). 구조체는 해당 값들을 일일이, 직접 비교해줘야 한다.

#include <string.h>
int memcmp (const void *s1, const void *s2, size_t n);

메모리 복사(이동) 은 memmove 와 좀더 친근한 memcpy가 있다. 둘간에 차이가 있는데, memmove는 src, dst 공간의 overlap을 허용한다는 것과, memcpy는 overlap되는 경우 동작이 unknown이라는 거다. overlap된 메모리의 데이터를 변환할거라면 구지 이런 함수들 쓰지 말고 포인터로 직접 해줘야 겠다.

#include <string.h>
void * memmove(void * dst, void * src, size_t n);
void * memcpy(void * dst, void * src, size_t n);

그외에도 특정 문자가 나타날 때까지만 복사하는 memccpy(*dst, *src, size) 가 있고, 특정 바이트를 찾는 memchr 가 있다(memrchr은 GNU에서 제공하는 것인데, 뒤에서부터 꺼꾸로 찾는다).

#include <string.h>
void * memchr(const void *s, int c, size_t n);
#define _GNU_SOURCE
void * memrchr(/* same as above*/);

그리고 haystack에서 needle을 찾는 함수 (일종의 strstr...?) memmem도 있다.

#define _GNU_SOURCE
#include <string.h>
void * memmem(const void *haystack,
size_t hatstacklen,
const void *needle,
size_t needlelen);

조금 희한한 함수로, 무조건 '42'와 XOR 해서 넘겨주는 memfrob이 있는데, 두번 XOR하면 원래 것이 나오므로, 임시로 데이터를 희끄므리 ... 하게 하고 싶을 때 쓴다(아마도 encryption이 중시되지 않을 때 만든 것인듯).

#define _GNU_SOURCE
#include <string.h>
void * memfrob(void *s, size_t n);
memfrob(memfrob(text, len), len); // same!

Memory Allocation Mechanism

메모리를 할당하는 여러가지 방법들이 있는데, 각각의 장단점을 생각해보자.
  • malloc 일반적인데, 초기화 안된다.
  • calloc 0으로 초기화 되나 malloc보단 조금 복잡하다
  • realloc resize
  • brk, sbrk 아주,.. low level 하다.
  • Anonymous Memory Mappings 큰 공간 할당시 유용하고, 쉽고, 공유가능하다. 작은 공간 사용시에는 낭비가 있다(페이지 단위로 할당하니까... 맞나 ㅡ.ㅡ;).
  • posix_memalign align이 중요할때만 사용...
  • alloca 스택에서 할당. 편리. 해제할 필요없음. 큰 공간할당에는 부적절. 안되는 시스템도 있고..
  • VLA scope 내에서 할당 가능. 배열인 경우만 유용.

VLA Variable Length Array

C99에서 도입한 것으로 VLA - 가변 길이 배열이 있다. 알다시피 일반적인 배열은 compile time에 해당 영역이 고정된다. 그러나 함수안에서 가변으로 배열을 선언하면 VLA로 잡히는데, (확실치는 않지만) 스택에 잡힌다. 아래와 같이 VLA를 사용할 수 있다.

for (i = 0; i < n; ++i) {
char foo[i+1];
/* ... */
}

거의 둘이 흡사하나, alloca와 VLA가 다른 점이 있다. alloca로 스택에 잡은 메모리는 함수가 리턴하는 시점에 해제되지만, VLA의 경우는 위 코드와 같이 for loop을 벋어나는 순간, 즉 scope를 벗어나는 순간 해제 된다(위의 경우에 alloca를 사용한다면 loop을 도는 수만큼 공간을 사용했을 것이다).

alloca() : Allocating memory from the stack

스택은 프로그램의 자동변수들이 들어있는 공간이다. heap말고 이 스택에서 메모리를 할당받으려면 alloca()를 사용하면 된다. 스택에서 메모리를 할당받을 때의 장점은 별도의 메모리 해제가 필요없다는 것이다. 함수가 종료되면 메모리는 자동으로 해제된다. 왜? 스택에 있으니까. alloca()는 에러를 반환하지 않는다. 스택 메모리 할당의 실패는 stack overflow로 처리되기 때문이다. 아래와 같이 함수내에서 간단한 스트링 처리를 위해 사용하는 것이 일반적이다.

#include <alloca.h>

int func(const char* tail) {
const char *str = "temporal string";
char * fullstr;

fullstr = alloca(strlen(tail)+strlen(str)+1);
strcpy(fullstr, str);
strcat(fullstr, tail);

/* do something */

return 0;
}

주의할 사항은 이렇게 alloca로 할당된 메모리 영역을 함수 호출시에 인자로 사용해서는 안된다는 것이다. (다른 함수 호출시 alloca로 할당 받은 스택 영역은 push 되니까!) 그리고 alloca()는 그다지 portable하지 않으므로 사용에 주의할 필요가 있다. 그러나 메모리 해제가 필요 없다는 점, 할당시 malloc에 비해 오버헤드가 적다는 점에서 자주 사용할 수 있는 유용한 함수이다.

스트링을 스택 메모리에 복사해서 사용하는 경우도 있는데, 이를 위해서 Linux에서 제공하는 함수로 아래와 같은 것들이 있다(POSIX에서는 제공하지 않는다)

#define _GNU_SOURCE
#include <string.h>
char * strdupa(const char *s);
char * strndupa(const char *s, size_t n);

예상되다시피 스트링을 스택 메모리에 복사한 후 포인터를 넘겨준다.

Monday, April 28, 2008

Memory, advanced memory allocation

메모리 할당과 관련된 커널의 제한 값은 mallopt()를 통해 변경할 수 있다.

#include <malloc.h>
int mallopt(int param, int value);

자세한 옵션값은 ... 넘어가자 ㅡ.ㅡ;

glibc에서 할당된 메모리는 실제보다 클수도 있다. 그래서 실제로 할당된 메모리 사이즈를 malloc_usable_size(void *ptr)를 통해 확인할 수 있다. 또 malloc_trim(size_t padding)함수를 사용하면 padding공간으로 있던 영역을 해제하여 여분의 메모리를 (아주 조금 이겠지만) 확보하는데 일반적으로 이런 과정은 자동으로 이루어진다.

메모리를 디버깅할 때는 MALLOC_CHECK_ 환경 변수를 사용할 수 있다. 아래 처럼 이 값을 1로 주면 동작시에 메모리와 관련된 메세지들을 stderr로 뿌여준다. 2로 설정되어 있는 경우에는 바로 abort()를 호출하고 종료한다.


$ MALLOC_CHECK_=1 ./test

그외에도 사용하고 있는 memory alocation system에 대한 정보를 mallinfo()를 통해서 볼 수 있다(이 함수가 리턴하는 구조체는 return by value이다. 포인터가 아니다). 그리고 malloc_stats()를 호출하면 메모리 관련된 정보를 stderr로 뿌려주기도 한다.

Memory, Anonymous Memory Mappings

glibc에서 메모리를 할당할 때는 data segment나 memory mapping을 사용한다. 초기에는 2의 배수로 메모리를 쪼개 놓고 malloc호출시 요청한 size와 비슷한 free 공간을 할당해주는 식으로 동작했는데, 이 경우 실제 할당되는 메모리가 요청되 메모리보다 커서 낭비인 internal fragmentation 이 발생하고, 여러개의 작은 free memory로 쪼개져 있는 경우 공간은 있는데, 할당은 못하는 external fragmentation이 발생하는 문제가 있었다. - 이렇게 할당하던 방식을 buddy memory allocation scheme라고 불렀다(glibc는 이 알고리즘 말고도 arena algorithm이라는 더 발전된 알고리즘도 사용한다).

glibc에서 메모리를 할당할 때 사용하는 heap이 free를 한다고 바로 줄어들지는 않고 할당된 메모리보다 heap이 너무 커진 경우에만 shrink 한다. 그리고 glibc는 큰 메모리 할당의 경우에는 heap을 사용하지 않는다. 일반적으로 요청된 메모리의 크기가 128 KB 이상인 경우 glibc는 anonymous memory mapping을 사용한다(mmap 과 비슷한 식으로 메모리를 커널로 부터 할당받는다). anonymous memory mapping은 아래와 같은 장단점이 있다.

  • fragmentation이 없다.

  • 할당 후 크기조절이 가능하다.

  • heap을 거칠 필요가 없다.



  • 커널의 페이지 사이즈 크기 배수로 할당 받는다(공간 낭비가 있을 수 있다).

  • 새로운 공간을 할당받는 overhead가 heap에거 가져오는 건 보다는 크다


anonymous memory mapping은 직접할 수도 있는데, 아래처럼 mmap을 사용하면 된다.

void *p;

p = mmap(NULL,
512*1024, // size
PROT_READ|PROT|WRITE, // 권한
MAP_ANONYMOUS|MAP_PRIVATE, // anonymous !
-1, // fd 인데, -1안줘도 되긴 함
0); // offset (ignored)

if (p == MAP_FAILED) perror("mmap");


이렇게 할당된 메모리에서 특정 코드를 수행하려 할 수도 있겠으나, 심각한 보안 취약점이 될 수 있으므로, 하지 않는다. 할당된 메모리들은 모두 0으로 초기화 되어 있다(커널에서 이렇게 할당된 메모리들은 copy on write 로 zero filled 하기 때문에 효율적으로 0으로 초기화 된 메모리를 사용할 수 있다.)

다른 unix 시스템들의 경우에는 MAP_ANONYMOUS 같은 flag이 없다. 대신에 mmap시 /dev/zero를 사용한다(이전의 linux에서도 이 방식을 사용하였다). 하지만 이 경우 추가적인 system call을 수반하기 때문에 anonymous memory가 더 빠른 방식이다.

Friday, April 25, 2008

links

book

Pthreads Programming

url

https://computing.llnl.gov/tutorials/pthreads/

Memory, Data Segment, Break Point

지금이야 heap과 stack 영역이 별도로 구분되어 있지만, 옛날에는 한 Data Segment 안에 들어있었다(학교 때 이렇게 배웠는데, 벌써 옛날이 되었네..). 그래서 스택은 제일 윗쪽 주소로 부터 내려오고, 힙은 아래서 부터 올라갔다. 두 영역이 만나는 지점을 Break 혹은 Break point 라고 하는데, 따로 구분되어 있는 지금에도 이 이름은 계속 사용된다. POSIX나 C에서 공식적으로 제공하는 것은 아니지만 brk() 함수를 통해 break point 값을 조정할 수 있고, sbrk()를 통해 현재 break point 값에서 증감할 수 있다(sbrk(0)으로 호출하면 현재 break point의 값을 알 수 있다.).

Thursday, April 24, 2008

Vector Juggling Rotation

임의의 벡터를 쉬프트 시킬 때 최소한의 메모리를 사용하여 구현할 수 있는데, 이 때 각 백터 원소의 크기 x 2 의 공간만 있으면 되고 연산은 벡터의 길이에 비례하도록 할 수 있다 ( O(n) ). 저글링 연산인데, 예를들어 8개의 원소를 가지는 벡터를 왼쪽으로 2만큼 쉬프트 시키면 아래와 순서와 같다.


1 2 3 4 5 6 7 8 - 임시공간 - 연산횟수

x 2 3 4 5 6 1 8 - 7 - 1 // 1을 왼쪽으로 2만큼 이동 시키고 전에 있던 7을 보관

x 2 3 4 7 6 1 8 - 5 - 2 // 7을 왼쪽으로 2만큼 이동한 공간에 놓고 5를 보관

x 2 5 4 7 6 1 8 - 3 - 3 // ...

3 2 5 4 7 6 1 8 - x - 4

3 x 5 4 7 6 1 2 - 8 - 5

3 x 5 4 7 8 1 2 - 6 - 6

3 x 5 6 7 8 1 2 - 4 - 7

3 4 5 6 7 8 1 2 - x - 8

막상 코드로 짤려니 아주 햇갈렸다 ㅡ.ㅡ;...

#include <stdio.h>
struct vector
{
char *data;
int size;
};
void * vec_init (int size)
{
struct vector *pvec;
pvec = (struct vector *) malloc (sizeof (struct vector));
pvec->data = malloc (sizeof (char) * (size + 1));
*(pvec->data + size) = '\0';
pvec->size = size;
return pvec;
}

void vec_free (struct vector *pvec)
{
free (pvec->data);
free (pvec);
}

// juggling rotation
void vec_rotate (struct vector *pvec, int shift_by)
{
char tmp;
int i, j, k, f, t;
int cnt = 0;;
for (i = 0; i < pvec->size - 1; i++)
{
j = i;
k = (pvec->size + j - shift_by) % pvec->size;
f = *(pvec->data + j);
do
{
k = (pvec->size + j - shift_by) % pvec->size;
t = *(pvec->data + k);
*(pvec->data + k) = f;
cnt++;
f = t;
j = k;
}
while (j != i);
if (cnt >= pvec->size)
break;
}
return;
}

int main ()
{
int i;
struct vector *pvec = vec_init (20);

for (i = 0; i < pvec->size; i++)
*(pvec->data + i) = 'a' + i;

printf ("%s\n", pvec->data);
vec_rotate (pvec, 12);
printf ("%s\n", pvec->data);
vec_free (pvec);

return 0;
}

실행시키니 정상동작한다. 다행 ^^;

Wednesday, April 23, 2008

Memory, Alignment

어떤 변수가 자신의 size의 정수배가 되는 위치에 align된 경우 naturally aligned라고 한다(예로, 32bit 정수가 4bytes 정수배의 메모리에 위치한 경우 - 이 경우 주소의 마지막 두자리가 '00'이 된다). 따라서 2^n 크기의 변수가 naturally aligned 되려면 주소의 마지막 n 비트들이 0이 된다.

시스템에 따라서 alignment가 잘못되는 경우 비정상적으로 동작하거나 심각한 성능 저하를 초래할 수 있다. posix에서 alignment를 맞춰주는 함수를 제공하는데 아래와 같다.

#include <stdlib.h>

int posix_memalign (void **memptr, size_t alignment, size_t size);

위 함수는 alignment의 정수배에 해당하는 주소에 size 만큼의 메모리를 할당한 후 그 주소를 **memptr에 담아 돌려준다.

Friday, April 18, 2008

Memory, free

free()를 사용한다. 알다시피, Linux에서 이미 할당된 메모리공간의 일부만을 free할 수는 없다(애초에 나눠서 할당하는 수밖에는). SunOS같은 경우는 cfree()같은 것을 제공하지만, linux에서는 이게 free와 같이 동작하므로(기대치 않은 동작을 발생시키는 경우가 있으니) 사용하지 않는 게 낫다.

메모리 free할 때 조심해야하는 게 memory leak 이다. 이를 위해 제공되는 툴이 electric fence와 잘 알고 있는 valgrind 이다. (전자는 이름 그대로 '전기 울타리' 라서 구글링하기 상당히 불편하다 ㅡ.ㅡ;)

Memory, reallocation

그렇다. realloc()으로 할당된 메모리 공간을 조절한다.

void *realloc(void *ptr, size_t size);

리턴되는 포인터는 원래의 것과 다를 수 있다(더 큰 메모리 공간을 연속적으로 얻기 위해 원래 위치에서 다른 위치로 옮길 수 있기 때문이다. 이 때 복사 cost가 있다). size 가 0인 경우 free와 같으나 이렇게 변태적으로 사용할 사람은 없을 거 같다.

realloc()을 통해 사이즈를 더 줄일 수도 있는데, 이때 원래 ptr도 사용가능하다 (심리적으로는 이렇게 안 쓰기 마련이다.) 만약 realloc이 실패하면 원해 ptr는 유효하게 된다.

Memory, Allocation

메모리는 잘 알다시피 malloc(size_t size)로 할당하여 사용할 수 있다. C에서는 해당 포인터에 바로 대입할 수 있지만, C++에서는 void 포인터를 자동으로 캐스팅 해주지 않으므로 아래처럼 명시적으로 케스팅 해줘야 한다.

char * name;

name = (char *)malloc(512);

일부 프로그래머는 포인터를 리턴하는 함수 일부를 호출할 때 void로 변환하여(리턴값을 확인하지 않고) 쓰는데, 상당히 좋지 않은 습관이다.

malloc()은 NULL을 리턴할수 있기 때문에 에러체크를 꼭해줘야한다. 그래서 일반적으로 아래 처럼 wrapper를 둬서 사용한다.

void * xmalloc(size_t size)
{
void *p;
p = malloc(size);
if (!p) perror("xmalloc"), exit (EXIT_FAILURE);
return p;
}

배열을 할당할 때는 calloc()을 사용할 수 있는데, 이 함수는 값들을 0으로 초기화 해준다.

#include <stdlib.h>
void *calloc(size_t nr, size_t size);

nr x size 만큼의 공간을 할당해서 0으로 초기화 한 후 포인터를 돌려준다(이미 0으로 초기화된 메모리를 돌려주기 때문에 효율적이다). 이 함수를 사용해서 아래 처럼 0으로 초기화하는 malloc의 wrapper를 따로 두기도 한다.

void *xmalloc0(size_t size)
{
void *p;
p = calloc(1, size); // 1 x size
if (!p) perror("xmalloc0"), exit(EXIT_FAILURE);
return p;
}

Memory, Paging and etc.

알다시피 Linux의 메모리는 페이지로 나누어져 있다(대략 4kb인데 64비트에서는 8kb이다). 실제 물리적 메모리나 하드디스크에 mapping 되어 있는 경우가 valid page이고 그외에는 fault를 일으키는 invalid page이다. 상주되지 않은 디스크를 읽으려 하는 경우 page fault가 발생하고 커널에서 해당 페이지를 하드에서 읽어 메모리로 올리는 paging in을 해준다. 반대로 메모리가 없으면 앞으로 가장 덜 사용될 것 같은 메모리의 부분을 디스크로 옮겨는 paging out을 한다.

때때로 한 물리적인 공간을 여러 (virtual memory address)메모리 주소가 가지고 있는 경우가 있는데, 이때 두가지로 동작이 가능하다. 하나는 share - 말그대로 공유하게 되어 한 프로세스가 write한 내용이 다른 프로세스에 의해 보이는 경우이고, 다른 경우는 그렇게 write 동작이 일어날 때 해당 프로세스에게 독자적인 영역을 할당해주는 COW(Copy-on-write) 동작을 하는 경우이다.

메모리는 여러 블럭을 묶어 memory region, segment, mapping 라고 부를 수 있는데, 각각은 아래와 같이 구분된다.

  • text segment 는 프로그램 영역이고,

  • stack

  • data segment(heap) : 동적 메모리 영역

  • bss segment : 초기화 안된 전역 변수공간 (이 변수들에 대해 object file에서 초기값이 없으므로 값을 저장하지 않는다. 그래서 바이너리 사이즈를 줄일 수 있다. 또 실행시에 메모리에 올라갈 때에도 copy-on-write로 동작하여 0으로 초기화 하는 작업을 효율적으로 진행한다)


이러한 영역들은 /proc/self/maps나 pmap을 통해 프로세스별로 어떻게 메모리가 할당되어 있는지 확인할 수 있다.

Monday, April 14, 2008

Resource Limits

시스템의 리소스 제한값을 보거나 설정하는 것은 아래 함수를 통해 할 수 있다.

#include <sys/time.h>
#include <sys/resource.h>

struct {
rlim_t rlim_cur; // soft
rlim_t rlim_max; // hard
};

int getrlimit(int resource, struct rlimit *rlim);
int setrlimit(int resource, const struct rlimit *rlim);

리소스 제한 값에는 soft limit과 hard limit 두가지가 있는데, soft limit는 hard limit 한도내에서 자유롭게 변경할 수 있다. 각 값들은 0인 경우 disable이고, RLIM_INFINITY(-1) 인 경우 무한대이다. limit 값들의 flag 이름들은 아래와 같다.

  • RLIMIT_AS : address space 제한

  • RLIMIT_CORE : 코어파일 크기

  • RLIMIT_CPU : 최대 CPU 사용시간

  • RLIMIT_DATA : data segment 크기 제한

  • RLIMIT_FSIZE : File size

  • RLIMIT_LOCKS : 최대 File Lock 개수

  • RLIMIT_MEMLOCK : CPY_SYS_IPC 설정없이 mlock(), shmctl()등으로 가질수 있는 메모리 크기

  • RLIMIT_MSGQUEUE : massage queue 크기

  • RLIMIT_NICE

  • RLIMIT_NOFILE : fd갯수 제한

  • RLIMIT_NPROC : user가 돌릴 수 있는 process 수 제한

  • RLIMIT_RSS : maximun number of pages

  • RLIMIT_RTPRIO

  • RLIMIT_SIGPENDING : 최대로 queue될 수 있는 signal갯수

  • RLIMIT_STACK : 프로세스 스택 크기 제한


이러한 값들을 가지고 설정하거나, 값을 확인하는 코드 예는 아래와 같다.

struct rlimit rlim;
int ret;

// get RLIMIT_CORE value
ret = getrlimit(RLIMIT_CORE, &rlim);
if (ret == -1) perror("getrlimit"), return 1;

printf ("RLIMIT_CORE sft(%ld), hrd(%ld)\n", rlim.rlim_cur, rlim.rlim_max);

// set RLIMIT_CORE value
rlim.rlim_cur = 32 * 1024 * 1024;
rlim.rlim_max = RLIM_INFINITY;
ret = setrlimit(RLIMIT_CORE, &rlim);
if (ret == -1) perror("setrlimit"), return 1;

Real-time Systems

특정 외부요인이 발현된 시점에서 응답이 있기까지의 시간에 대해 deadline이 제한된 상황에서 동작하는 시스템을 realtime system이라 할 수 있다. 책에서는 soft/hard realtime system으로 나누는데, deadline을 넘겨도 system failure가 발생하지 않는 경우는 soft realtime system 으로 보면 된다.

Latency & Jitter 두 단어에 대하 잠깐 짚고 넘어 가면, Latency는 외부요인이 발생한 시점에서부터 response가 일어나기 전까지의 시간이고, jitter는 연속적인 이벤트들 사이의 시간 편차이다.

Linux에서도 realtime 을 지원하는데, scheduling class 라고 불리는 스케쥴링 정책을 통해서 이루어진다. 세가지 정책이 있는데 flag으로는 SCHED_FIFO, SCHED_RR, SCHED_OTHER로 구분된다.

FIFO Class는 더 높은 우선순위를 가진 프로세스가 들어오기 전까지 FIFO순으로 처리하는 방식이고,

Round-robin 은 같은 우선순위를 가진 프로세스들 간에 RR방식으로 timeslice를 가지고 실행되는 스케쥴링 방식이다.

SCHED_OTHER는 일반적인 스케쥴링 정책이다. 이외에 SCHED_BATCH도 있는데, 다른말로 idle scheduling policy라고도 불린다. 이 정책은 runnable한 프로세스가 없을 때 실행되는 방식으로 realtime 과는 반대 개념으로 동작한다. 스케쥴링을 설정하거나 확인할 때는 sched_getscheduler(), sched_setscheduler()를 사용한다. RR 에서 timeslice 값을 확인하고 싶은 경우에는 sched_rr_get_interval()함수를 사용하면 된다.

Real-time Process를 구현할 때 주의할 사항들이 있는데, 요약하면 아래와 같다고 한다.

  • 무한 루프를 돌 경우 시스템이 응답하지 않게 될 수도 있다.

  • 한 프로세스로 인해 다른 프로세스가 starve하지 않도록 주의해야한다.

  • 자신보다 낮은 우선순위의 프로세스를 busy-wait하는 경우를 주의해야한다(deadlock될수 있음)

  • 개발 시에는 터미널 프로세스를 최상위에 두면 좋다.

  • chrt라는 util-linux 패키지를 쓰면 도움이 된다


Realtime 시스템에서는 생각할 게 많다. 미사일 요격 시스템을 만들어서 잘 동작하다가, 갑자기 중요한 코드를 수행하는데 예를들어 ABM(Anti-Ballistic Missile)를 발사하려는 시점에서 갑자기 해당 코드가 하드디스크에 swap되어 있다고 가정하자. 하드에서 읽어와 메모리에 다시 올리는 순간, 이미 미사일이 나아들어 기지를 덮칠 수도 있다 ㅡ.ㅡ;... realtime 에서 동작하는 프로세스라면 해당 메모리는 swap out되지 않도록 lock해 놓을 필요가 있다.

CPU Affinity를 통해서 realtime process를 설정하는 방법도 있다. multiprocessor를 가진 시스템에서 realtime process를 통작시킨다고 해보자. 이 경우에 모든 일반 프로세스를 한 프로세서에서 동작시키고 중요한 rt 프로세스를 다른 프로세서에서 동작시키면 dealine 안에 job을 마치도록 안전하게 설정 시켜 놓을 수 있다. 간단하게 init 프로세스의 CPU affinity를 한쪽으로 고정시키면 이로부터 fork되는 프로세스들도 같은 affinity를 가지므로 한쪽에서만 돈다. 그리고 원하는 RT 프로세스를 다른 CPU에서 돌도록 하면 된다. 샘플코드를 보자.

// #### init process
cpu_set_t set;
int ret;

CPU_ZERO(&set);
ret = sched_getaffinity(0, sizeof(cpu_set_t), &set);
//check error
CPU_CLR(1, &set); // cpu1에서 못돌게함
ret = sched_setaffinity(0, sizeof(cpu_oset_t), &set);
// check error

// #### real-time process
cpu_set_t set;
int ret;

CPU_ZERO(&set)l
CPU_SET(1, &set);
ret = sched_setaffinity(0, sizeof(cpu_oset_t), &set);
// check error

Tuesday, April 8, 2008

Processor Affinity

SMP 같이 여러 프로세서를 사용하는 경우, 프로세서를 바꿀 때 마다 cache 효과가 사라지는 단점이 있다. (오늘날의 SMP에서는 프로세서간에 Cache 접근이 가능하도록 인텔에서 설계하나, 커널 단에서 이를 고려하고 있는지는 모르겠다.) 그래서 스케쥴러는 되도록 이면 특정 프로세스를 특정 프로세서에서 동작시켜려고 하는 경향이 있는데 이를 'soft affinity' 라고 한다. 이 경향은 프로세서가 아주 imbalance해질 때 풀어지는데, 코드 상에서 특정 프로세서에서만 실행되도록 한다면 이는 'hard affinity' 가 된다. 몇개의 매크로와 sched_setaffinity(), sched_getaffinity()를 사용하여 hard affinity를 줄 수 있는데, 귀찮다... 소스하나만 보고 가자.

cpu_set_t set;
int ret, i;

CPU_ZERO (&set);
CPU_SET (0, &set); // CPU0을 선택
CPU_CLR (1, &set); // CPU1을 배제
// 첫째 인자는 pid
ret = sched_setaffinity(0, sizeof(cpu_set_t), &set);

// 이제 출력해 보면,
// (CPU_SETSIZE는 한 프로세서가 최대로
// 가질 수 있는 프로세서 수이다.)
for (i=0; i<CPU_SETSIZE; i++)
{
int cpu;
cpu = CPI_ISSET(i, &set);
printf ("cpu=%i is %s\n", i,
cpu ? "set" : "unset");
}

Process Priorities

프로세스의 우선 순위는 nice 라고 불리는 값으로 우선 순위가 결정된다. 다른 프로세스 들에게 "be-nice" 하자는 의미에서 우선순위 값이 nice로 정해졌덴다. -20에서 19까지 가질 수 있고, 낮을 수록 우선 순위가 높다. nice 값 자체가 프로세스의 timeslice를 알려주는 역할도 한다. 디폴트 nice 값은 0이다. 이 값을 올려주는 것이 다른 프로세스들에게는 "nice" 해보는 방법이다. nice는 아래와 같이 간단히 사용할 수 있다.

#include <unistd.h>

int nice(int inc);

inc 값만큼 nice 값을 올릴 수 있다. 내릴 수는 없다. 내리는 것 - 우선순위를 높이는 것은 (CAP_SYS_NICE capability가 있는)root만 할 수 있다. 리턴값으로 변환후의 우선 순위 값을 반환하기 때문에 간단히 현재 자신의 우선 순위를 볼 때는 nice(0)으로 확인 가능하다.

이 외에 프로세스, 프로세스 그룹, user 별로 우선순위를 지정할 수 있는 getpriority, setpriority함수들이 있는데, 간단히 살피면 아래와 같다.

#include <sys/time.h>
#include <sys/resource.h>
/* which - PRIO_PROCESS, PRIO_PGRP, PRIO_USER
* who - pid, pgid, user id..
*/
int getpriority (int which, int who);
int setpriority (int which, int who, int prio);

위에서 인자에 0을 주면 현재 프로세스/프로세스 그룹/사용자에 대해 동작한다. 비슷한 식으로 I/O 스케쥴러에 대해서도 우선순위를 조절하는 ioprio_get(...), ioprio_set(..)가 있으나 glibc에서 제공하지 않는다. 대신 ionice 라는 util-linux package를 통해 조절할 수 있다.

Monday, April 7, 2008

Advanced Process Management - process scheduling

프로세스 스케쥴링에서 멀티테스킹을 지원하는 경우 아래의 두가지 방법이 있다.
  • preemtive multitasking(선점형)
  • cooperatice multitasking

cooperative 멀티테스킹에서는 프로세서가 스스로 yield (다른 프로세스로 스위치 하도록) 하지 않는 이상 계속적으로 프로세서 자원을 사용할 수 있다. preemptive에서는 커널이 '선점형' 이기 때문에 특정 프로세스가 일정 timeslice이상을 사용하지 못하도록 제어할 수 있다.

linux의 scheduling algorithm은 O(1)이다. 즉 프로세스의 수가 늘어나도 스케쥴링을 위해 소요되는 시간은 일정하다.

Timeslice 는 너무길거나 짧을 경우 둘다 문제가 된다. 너무 짧을 경우 context switch 하는 비용이 많아지고, 캐시의 temporal locality가 떨어진다. 너무 길게 되면 User Interactivity가 떨어지게 된다.

Processor bound & I/O bound. 프로세스가 할당된 timeslice를 거의 다 사용하는 경우 processor bound 이고, 대부분 파일, 키보드 입력, 마우스 등의 I/O작업인 경우 I/O bound 이다. 전자의 경우 캐시 hit를 늘이기 위해 되도록 많은 timeslice를 사용하여 작업을 마치기 원하고, 후자의 경우에는 짧게 짧게 작업이 이루어지는데 스케쥴러가 빨리 다시 작업을 시작해주도록 해주기를 원한다. Linux Scheduler는 프로세서의 각각 특징에 따라 다른 방식으로 프로세스들을 다루려고 노력한다(주로 IO bound에 대해서는 우선 순위를 높여주고, processor bound에는 penalty를 준다).

Idle Process는 실제 프로세스가 아니다. Idle process는 커널이 자신의 scheduler algorithm을 재조정하는 시간이다. idle time은 이러한 idle process를 돌리는데 소용된 시간이다.

Thread에 대해서 잠깐 생각해보면, Linux에서는 Thread를 같은 주소 공간을 공유하는 프로세스로 간주한다(Thread라고 별다르게 생각하지 않는다). 대부분의 개발자들은 thread 프로그래밍을 위해 IEEE에서 제정한 thread API인 API pthreads를 사용한다.

Yielding processor 란 '나 끝났어, 딴 프로세스 돌려' 라고 알려주는 것이다. 말그대로 프로세서를 양보하는 것인데, 아래 함수를 통해 할 수 있다(별로 일반적이지는 않다).



#include <sched.h>

int sched_yield(void);

이 system call을 사용해서 일종의 non-block한 코드를 구현할 수도 있겠지만, 그리 좋은 방법은 아니다(그냥 non-block 을 지원하는 함수를 쓰는 편이 낫다). 이전에 thread를 구현할 때 user space에서의 thread locking을 구현하기 위해 잠시 사용하기도 했으나, 근래에는 futex로 user space locking이 지원되고 있다.

프로세서가 서로 yield를 해서 ping pong pathological case가 발생할 수 있다. 하지만, 2.6이후 버전에서 yield 알고리즘을 개선하여 이런 문제를 해결하였다.

Friday, April 4, 2008

Daemons

Daemon은 background에서 동작하고, terminal에 연결되지 않은 상태로 동작하는 프로세스를 의미한다. 통상 'd'로 끝나는 이름을 가지고, 아래와 같은 순서로 생성할 수 있다.
  1. fork()
  2. 부모 프로세스는 exit()
  3. setsid()로 새로운 세션을 가진다. (예전 세션이나 pgid로 종료 signal을 받을 수 있기 때문)
  4. chdir()로 작업 디렉토리를 '/'로 바꾼다. (엉뚱한 데를 물고 있다 unmount할 때 문제를 만드는 수가 있다.)
  5. 부모로 부터 받은 fd를 모두 닫는다.
  6. 0,1,2 (in,out,err) I/O를 /dev/null에 연결한다.

이를 기반으로 daemon을 만들 수 있으나, 귀찮다. 그래서 daemon() 함수를 제공하고 있다.



#include <unistd.h>

int daemon(int nochdir, int noclose);

nochdir가 0이 아니면 dir path를 안바꾸고, noclose가 0이 아니면 fd를 안 닫는다.

Sessions and Process groups

간단히 얘기하면 한 시스템에 여러개의 세션이 존재할 수 있고, 세션은 job control의 단위인 여러개의 프로세스 그룹으로 나눠질 수 있는데, 세션과 프로세스 그룹에는 각각 리더가 존재해서 이를 세션 리더, 프로세스 그룹 리더라고 한다. 프로세스 그룹은 foreground/background 로 나누어 진다. 사용자가 터미널을 종료하면 SIGQUIT이, 네트웍이 끊어지면 SIGHUP가, Ctrl-C를 누르면 SIGINT가 foreground process group에 전달된다. 사용자가 세션을 시작하면 그 사용자의 pid가 pgid, sid로 되어 세션 및 프로세스 그룹이 생성된다. 새로운 새션을 시작하기 위해서는 setsid()를 사용하는데, 이를 호출하는 프로세스는 다른 프로세스 그룹의 리더여서는 안된다. 이를 위해 일반적으로 fork()한 후 부모는 종료하고, 자식 르로세스에서 setsid()를 수행해서 새로운 세션을 만든다.

pid_t pid;

pid = fork();

if (pid == -1) perror("fork");
else if (pid !=0) exit(EXIT_SUCCESS);

if (setsid() == -1)
{
perror("setsid");
return -1;
}

현재 세션 id는 비슷하게 getsid()를 통해서 볼 수 있다.(인자에 pid를 주면 다른 프로세스의 sid도 볼 수 있다.) sid에 대한 함수들 같이 pgid도 같은 식으로 set, get할 수 있는데 setpgid(), getpgid()를 통해 볼 수 있다. 리눅스에서는 한 때 이러한 함수들을 setpgrp(), getpgrp()로 제공했었다.

Thursday, April 3, 2008

Process User IDs

user ID에는 네가지가 존재한다. real, effective, saved, filesystem 이다. real은 부모 프로세스의 user ID 이고, effective ID는 현재 프로세스의 user ID이다. fork하면 effective ID가 상속되고, exec해도 setuid 같은 경우를 제외하고는 안바뀐다. setuid 같은 경우란 특정 프로그램을 실행하는 경우 그 프로그램 바이너리의 user ID로 effective ID가 바뀌어 사용되는 경우이다. 예를 들어 /usr/bin/passwd는 root 권한으로 동작한다. 그래서 user가 passwd를 실행하면 그 실행 프로세스는 user ID에서 root ID 권한으로 바뀌어 동작한다는 얘기다. saved ID는 exec으로 권한이 바뀐 경우 그 전의 ID를 적어놓는 것이고, 프로세스가 fork하면 saved ID권한을 자식에게 상속한다.

Wednesday, April 2, 2008

Waiting child process termination & zombie process

부모프로세스는 자식 프로세스 종료에 대해 정보를 얻고 싶다. (왜 죽었나, 에러가 있었나 등등..) 그래서 자식이 종료될 때 좀비로 만들어 부모 프로세스가 자식의 상태를 체크할 수 있도록 해준다. 소위 waiting on zombie process라고한다. 종료된 자식 프로세스를 기다려 상태를 얻어오는 함수가 wait()인데 아래같이 생겼다.

#include <sys/types.h>
#include <sys/wait.h>
pit_t wait(int *status);

이 함수를 실행하면 자식이 죽을 때까지 블럭 된다. 종료될 때 받은 status값을 아래 매크로?함수?를 통해 상태를 파악할 수 있다.

  • int WIFEXITED(status) : 정상 종료인지

  • int WEXITSTATUS(status) : 종료시 상태값 (0, 에러...)

  • int WIFSIGNALED(status) : 시그널 받았는 지

  • int WTERMSIG(status) : 그 때의 시그널 값

  • int WIFSTOPPED(status) : ... 주로 디버깅 때 사용

  • int WSTOPSIG(status) : 프로세스를 멈춘 시그널

  • int WIFCONTINUED(status) : ... 주로 디버깅 때 사용

  • int WCOREDUMP(status) : 코어 생겼는지.


모든 프로세스에 대하여 생사여부(?)를 기다리는 wait외에도 특정 pid에 대해 wait 할 수 있는데, 이게 waitpid()이다.

#include <sys/types.h>
#include <sys/wait.h>

pid_t waitpid(pid_t pid, int *status, int options);

pid에 체크할 프로세스 번호 외에 음수 즉 -500같은 값을 넣으면 프로세스 그룹 아이디가 500인 것들에 대해 기다리고, -1은 모든 자식에 대해(wait()과 같다) 기다린다. 0인 경우는 자신과 같은 프로세스 그룹에 대해 기다린다. options에는 WNOHANG을 줘서 nonblock으로 실행할 수 있다.

이외에도 더좀 더 다향한 방법으로 사용할 수 있는 함수로 waitid()가 있다.

Process : Termination - Ways to exit

프로세스의 종료는 간단하다.

#include <stdlib.h>
void exit (int status);

status에 0 혹은 EXIT_SUCCESS를 주면 성공이고, EXIT_FAILURE나 그외 값을 주면 에러로 종료된 것이다. exit()은 atexit()을 통해 등록된 함수들을 (스택에서 pop하듯이) 등록된 역순으로 실행시켜준 후 종료한다. exit()은 프로세스 종료를 위해 여러가지 일들을 하고 내부적으로 다시 _exit()을 실행한다. return 0;으로 main 함수를 끝내도 system call은 호출된다. 컴파일러가 종료시점에 _exit()을 호출하도록 코드를 삽입한다. (vfork()를 사용한 경우 _exit()을 써야한다. exit()는 안되...) 프로세스는 종료할 때 아래 일들을 한다.

  • atexit()에 등록된 함수들을 실행한다.

  • 열려있던 I/O를 닫는다.

  • tmpfile()로 마는 파일들을 삭제한다.


atexit()은 아래와 같이 생겼다.

#include <stdlib.h>
int atexit(void (*function)(void));

등록할 수 있는 함수 갯수는 대략 32개 정도 인데, 정확한 값은 sysconf(_SC_ATEXIT_MAX)를 통해 알 수 있다. 간단한 예를 만들어 볼까...

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

void t1(void) {
printf("exit sub-function 1\n");
}
void t2(void) {
printf("exit sub-function 2\n");
}
int main() {
if (atexit(t1)) fprintf (stderr, "atexit() failed\n");
if (atexit(t2)) fprintf (stderr, "atexit() failed\n");

return 0; // or exit(0);
}

역시 등록한 역순으로 실행된다.

> gcc atexit.c
> ./a.out
exit sub-function 2
exit sub-function 1

exec을 사용하면 atexit()으로 등록한 함수들은 없어지고, 시그널을 받아 종료된 경우에는 이 함수들은 실행되지 않는다.

그외의 방법으로 프로세스가 종료되는 경우에는 SIGTERM, SIGKILL 등의 시그널을 받거나, 메모리 부족, segmentation fault 등으로 커널이 죽이는 경우이다.

Tuesday, April 1, 2008

Basics on Process

리눅스 프로세스에 대한 기초를 복습해보자. 음,. 프로세스는 pid로 구별된다. idle process는 0, init process는 1이다. init의 command-line parameter를 통해서 프로세스를 실행시킬 수 있다. 커널은 init의 위치를 아래 네가지 순서대로 찾아 다닌다.
  1. /sbin/init
  2. /etc/init
  3. /bin/init
  4. /bin/sh (init을 못찾으면 Bourne shell 이라도 실행시킨다)

프로세스는 옛날 Unix 시스템과의 호환을 위해 32768개 이상 띄울 수 없게 되어 있으나, /proc/sys/kernel/pid_max 값을 조절하여 더 키울 수 있다.

프로세스는 ppid가 부모 프로세스이고, user group 접근 권한도 가지고 있다. 이 접근 권한과 헷갈리면 안되는 것이 process group인데, 프로세스 그룹은 예를 들어 'ps aux | grep aaa' 같이 파이프로 묶여 실행되는 프로세스 들이라고 생각하면 된다. process group을 알면 전체 파이프 라인된 프로세스들에게 시그널을 보낼 수 있어 좋다. job 명령이 이 process group과 관련이 있다.

프로세스는 pid_t 로 표기 되는데, getpid(), getppid() 등으로 자신과 부모의 프로세스를 알 수 있다. (통상 이를 출력할 때 unsigned int로 간주한다.)

프로세스 실행 방법은 두가지가 있는데, exec과 fork이다.

exec은 excel(path, arg, ...) 처럼 실행 바이너리 경로와 인자를 주어 실행한다. 아래는 vi를 싱행하는 예다.



int ret;

ret = excel ("/bin/vi", "vi", NULL);
if (ret == -1) perror("excel");

일반적으로 excel은 리턴되지 않는다(당연하다). exec이 실행되면 pending signal이 없어지고, 메모리 lock도 없어지고 thread관련된 값들도 default로 바뀌고, 프로세스 관련 값들도 변하고, mmap 되어 있던 부분도 drop된다. pid, ppid, priority, 권한 등은 유지된다. 그리고 열려있는 파일들도 exec 후 상속된다. 하지만 일반적으로 exec 하기 전에는 열려있는 파일들은 닫는다. exec은 인자나 실행 파일을 어떻게 알려주느냐에 따라 execve를 wrapping한 execle, execv, execvp, execve, execlp 등으로도 제공되고 있다.

fork()는 알다시피 자식 프로세스를 만든다. 리턴값이 0이면 자식이고, 아니면 부모이다. signal은 clear되고, file lock 등은 자식에게 상속되지 않는다. 많은 경우 fork는 exec과 같이 사용된다. "fork plus exec".

Copy-on-write 개념을 알아둘 필요가 있는다. 이는 매번 자식 프로세스가 생성될 때마다 부모 프로세스를 복사하기 부담 스러우니, 자식 프로세스와 부모 프로세스가 달라지는 시점이 되서야 비로소 프로세스를 copy하자는 개념이다. fork plus exec의 경우에는 사실 프로세스 복사가 무의미 하므로 이러한 copy-on-write를 통해 부담을 줄일 수 있다. 대부분의 COW 매커니즘은 프로세서의 MMU를 통해 하드웨어 적으로 지원되고 있다.


아예 fork 할 때 부모 프로세스를 복사하지 않고, 자식 프로세스가 종료하거나 exec할 때까지 기다리는 vfork()도 있는데, 리눅스에서는 (정식 버전에서는) vfork를 구현한 적이 없다. 자식이 exec 하다 실패한 경우 부모 프로세스가 멈출 수 있는 잠재적인 버그를 가지고 있다. 비추다.