[sp] Concurrent Programming(1)

1. 문제점

(1) Races : 결과는 임의의 scheduling decision에 의존

**scheduling은 여러 프로세스가 time sharing하면서 발생

 

ex) 화장실

fork하여 생성된 자식 프로세스인 A,B,C,D가 화장실을 가기 위해 race를 한다고 가정

이때 이 프로세스들은 화장실 일을 제외하고 나머지 일을 병렬적으로 수행할 수 있음

이때 화장실은 shared resource (shared data structure)임

race를 통해 화장실을 갈 사람을 선정한다고 할 때 문제가 발생

 

1. livelock : 키를 잡기 위해 계속 시도하므로 비효율적으로 cpu를 사용

2. starvation : 프로세스 D와 같이 한 번도 화장실을 가지 못함

3. fairness : 경쟁을 하다 보니 모든 사람이 똑같은 횟수로 화장실을 갈 수 없음

 

 

(2) Deadlock : 부적합한 리소스 할당으로 2개 이상의 프로세스가 preceedig하지 못하고 서로 기다림

 : 어쩌다 한 번씩 예기치 못하게 발생

ex) traffic gridlock

 

 

sol) Traffic sign : 순서 정하기

 

(3) Livelock / Starvation / Frairness : 외보의 사건들이나 시스템의 scheduling decision은 sub-task의 progress를 막음

 

 

2. Iterative Servers : 한 번에 하나의 요청만 수행

 

서버가 single process이므로 돌면서 이 과정을 혼자 수행하므로 concurrent하지 않으므로 시간이 많이 듦

서버가 client1이 보낸 connect request를 accept하면 connected fd가 생성되면서 부모 프로세스가 자식 프로세스를 fork

자식 프로세스는 부모 프로세스의 메모리를 복제하면서 자동으로 connected fd를 가지게 되고 client1과 서버 사이의 connection 생성

클라이언트1에선 boy를 write, read, return

이때 서버는 read하면서 데이터가 왔는지 확인하고 TCP IP 스택 안의 버프에 boy 쌓임

이후 boy를 받으면 write, read, close

 

 

이 과정에서 client2의 connect request를 받으면 이 요청을 queuing

client2에선 girl을 write하고 read를 호출하는데 이때 girl은 buffering만 하고 서버는 이를 읽을 수 없음

 

이 후 client1과 서버의 connect가 끝날 때까지 wait한 후 client1이 끝나면 connect되면서 위의 과정 반복

 

이 때 t1과 t2를 비교해보면 t2가 더 긺

클라이언트가 많아질 수록 각 클라이언트의 처리 시간은 더 길어짐

 

 

=> Client2는 어디서 blocking?

client2는 iterative 서버와 연결을 시도함

 

connect 호출을 리턴

-> connect 요청이 들어갔지만 accept하지 않음

-> 서버 사이드의 TCP 매니저는 이 요청을 queuing

 

rio_writen 호출을 리턴

-> 서버 사이드 TCP 매니저는 input 데이터를 버퍼링

 

rio_readlineb의 호출을 blocking

-> 서버는 아직 읽을 내용을 write하지 않음

 

 

 

3. Fundamental Flaw of Iterative Servers

 

client1은 유저가 데이터 입력하기를 기다리는 것을 block

서버는 클라이언트1의 데이터를 기다리는 것을 block

클라이언트2는 서버로부터 read하는 것을 기다리는 것을 block

 

sol) concurrent 서버를 사용

: concurrent 서버는 동시에 여러 클라이언트를 처리하기 위해 다수의 concurrent한 flow를 사용

 

 

4. Approaches for Writing Concurrent Servers : 서버는 다양한 클라이언트를 concurrent하게 처리

(1) Process-based

- connection을 맺을 때마다 부모 프로세스가 accept하고 자식 프로세스를 fork

- 서버의 자식 프로세스와 클라이언트 프로세스가  connection하면서 logical flow를 수행하여 서비스를 수행

- 커널은 자동으로 다양한 logical flow를 interleave

- 각 flow는 각자 private address space를 가짐

즉 각 프로세스마다 하나의 logical flow를 가짐

 

-> 각 클라이언트에 대해 별도의 프로세스를 형성

 

 

client1에서 서버로 connect request를 보내서 서버가 accept하게 되면

서버는 fork를 하여 자식 프로셋를 생성해줌으로써 client1과 서버의 자식 프로세스가 connect

client1의 connect request를 accept하는 동안 client2가 요청을 보내면 TCP manager에 queuing

 

int main(int argc, char **argv) {
    int listenfd, connfd;
    socklen_t clientlen;
    struct sockaddr_storage clientaddr;
    
    Signal(SIGCHLD, sigchld_handler); // 모든 좀비 자식 프로세스를 reaping
    listenfd = Open_listenfd(argv[1]);
    
    while (1) {
        clientlen = sizeof(struct sockaddr_storage);
        connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
        if (Fork() == 0) {
            Close(listenfd); /* Child closes its listening socket */
            echo(connfd); /* Child services client */
            Close(connfd); /* Child closes connection with client */
            exit(0); /* Child exits */
    	}
    Close(connfd); /* Parent closes connected socket (important!) */
    }
}

void sigchld_handler(int sig)
{ 
    while (waitpid(-1, 0, WNOHANG) > 0)
    ;
    return;
}

서버에서 클라이언트가 보낸 connect request를 accept하면서 connfd가 생성이 되면

fork를 하여 자식 프로세스를 생성하고 이 자식 프로세스에선 더이상 listenfd가 필요없으므로 close

echo함수를 이용하여 connfd를 통해 클라이언트와 자식 프로세스가 채널을 형성하여 데이터를 주고 받음

이 작업이 끝나면 자식 프로세스에선 더이상 connfd가 필요없으므로 close를 해주고 exit

 

**중요!! 부모 프로세스에서도 connfd가 있는데 더이상 필요하지 않으므로 close 해줘야함

 

- concurrent 서버에서 accept하는 과정

 

이때 서버는 listenfd를 이용하여 connection request가 올 때까지 accept 안에서 기다림

 

클라이언트는 clientfd를 이용하여 서버의 listenfd에게 connect request를 보냄

 

서버는 요청을 accept하면서 connfd를 리턴해주고 fork를 띄워 서버 자식 프로세스를 생성한다.

이 자식 프로세스의 connfd와 클라이언트의 client가 채널을 형성하여 connect

이때 부모 서버는 connfd가 필요하지 않으므로 close, 자식 서버는 listenfd가 필요하지 않으므로 close

 

-Process-based Server Execution model

 

 

listening 서버 프로세스는 connect 요청을 받으면 fork를 띄워 자식 프로세스를 생성하고

이 자식 프로세스들은 독립적으로 클라이언트 처리

따라서 자식 서버 프로세스 사이의 shared state가 없음

부모와 자식 프로세스는 모두 listenfd와 connfd를 복제하므로 

반드시! 부모는 connfd를 close

자식은 listenfd를 close

 

- 서버 프로세스 리스닝은 반드시 좀비 자식 프로세스를 reaping해야함

안그러면 메모리 누수 발생

 

- 만약 부모 프로세스에서 connfd를 close하지 않을 경우

 : 커널은 각 소켓과 open file에 대한 reference count를 가짐

 : fork 후, refcnt (connfd) = 2 (그러면서 계속 증가) 

 : connection은 refcnt (connfd)가 0이 될 때까지 끊기지 않음

 

- 장 : 여러 connection을 concurrent하게 처리할 수 있음

 : clean sharing model (descriptor x, file table x, global variables x)

 

- 단 : 프로세스 제어권에 대한 추가적인 overhead 발생

 : 서버에서 fork하여 자식 프로세스가 생성되면 이 자식 프로세스는 독립적으로 각자 address space를 가짐 -> nontrivial한 data sharing

-> IPC(interprocess communication) 메카니즘 필요 : FIFO (named pipes), System V로 메모리와 semaphore 공유 

 

 

 

(2) Event-based

- 프로그래머는 여러 logical flow를 논리적으로 수동으로 interleave

- fork하지 않음

- 프로세스 1개, logical flow 1개

-> 모든 flow는 같은 address space를 공유

-> I/O multiplexing : 단일 프로세스에서 유저가 standard input에 입력한 interactive 명령어에 응답하는 에코 서버를 작성한다고 가정

event 1 : 네트워크 클라이언트가 에코 서버로 connect request를 보내면 서버는 connfd를 리턴

event 2 : 유저는 명령어를 입력

 

어떤 이벤트를 먼저 wait?

 

=> Event-based Servers

1. 서버는 active connection들의 집합을 유지한다 -> connfd의 배열

2. descriptor (connfd / listenfd)가 pending input을 가지는지 확인 (select, epoll 함수 사용, pending input의 도착은 event)

 : listenfd -> connect request를 accept하여 connfd 생성

 : connfd -> 클라이언트와 connect하여 채널을 생성하고 클라이언트가 보낸 msg를 읽어서 echo

3. listenfd가 pending input을 가지면 connection을 accept, 새로운 connfd를 배열에 추가

4. pending input이 있는 모든 connfd를 처리

5. 2~4 반복

 

 

- I/O Multiplexed Event Processing

 

pending input을 확인하여 active descriptor의 프로세스를 각각 처리

 

- I/O Multiplexing : select / epoll을 사용하여 커널에게 프로세스를 suspend하도록 요청 -> 하나 이상의 I/O 이벤트가 발생하면 응용프로그램에 대한 제어권을 리턴

 

ex) {0,4}의 descriptor가 읽을 준비가 되면 리턴 

{1,2,7}의 descriptor가 쓸 준비가 되면 리턴

#include <sys/select.h>

int select(int n, fd_set *fdset, NULL, NULL, NULL);
//n은 비트의 개수, fdset은 bit vector(bit array)
//bit array에서 pending bit가 있으면 action 취함
					Returns: nonzero count of ready descriptors, -1 on error
FD_ZERO(fd_set *fdset); // fdset의 모든 비트를 클리어
FD_CLR(int fd, fd_set *fdset); // 특정 fd의 비트를 클리어
FD_SET(int fd, fd_set *fdset); // 특정 fd의 비트를 turn on
FD_ISSET(int fd, fd_set *fdset); // 특정 fd의 비트가 set되어있는지? , pending bit 확인

울고싶다 하

 

 

read_set : bit vector

ready_set : read_set을 유지하기 위해 원본을 복사하여 사용

 

FD_ZERO(&read_set); // read_set을 모두 0으로 초기화

FD_SET(STDIN_FILENO, &read_set); // read_set 비트 배열의 0번째 원소를 1로 set

FD_SET(listenfd, &read_set); // read_set 비트 배열의 3번째 원소를 1로 set

->listenfd, stdin에 해당하는 배열 원소에 pending input이 있으므로 해당하는 이벤트가 발생하면 action을 취함

 

ready_set에 read_set을 복사해줌으로써 원본을 유지

-------------------------------------->ready_set : 1001

Select(listenfd + 1, &ready_set, NULL, NULL, NULL); // ready_set의 총 4개의 원소를 점검하여 set되어 있는 비트들만 감시

만약  ready_set 비트 배열의 0번 원소가 1로 pending input을 가지면 stdin으로부터 명령어를 read

만약  ready_set 비트 배열의 3번 원소가 1로 pending input을 가지면, accept함수가 listenfd를 통해 클라이언트의 connect request를 수락하여 connfd를 리턴하고 EOF를 받을 때까지 클라이언트 에코를 수행

 

*문제점: 만약 클라이언트가 EOF를 보내지 않으면 서버는 보낼 때까지 계속 기다리게 됨

따라서 multiplexing이 불가능

 

*Blocking problems

: 클라이언트와 서버가 연결되면, 클라이언트가 연결을 끝낼 때까지 input line을 계속 echoing

-> 만약 유저가 standard input에 명령어를 입력하면, 서버가 클라이언트와의 연결을 끝낼 때까지 응답을 얻을 수 없음

-> 따라서 프로그래머들이 server loop를 통해 매번 하나의 text line을 echoing하면서 finer granualarity로 multiplex해야함 ( 더 미세한 단위로 multiplexing) : 하나의 텍스트 라인을 다 읽자마자 echoing을 빠져나옴

 

- I/O multiplexing and event-driven programs

 : I/O multiplexing은 concurrent event 구동 프로그램에 대한 기본으로 사용 가능하므로

flow는 확실한 이벤트의 결과로 흐름

 : concurrent하지 않고 1개의 프로세스가 여러 개의 이벤트를 빠르게 처리

 

- Modeling logical flows as state machines

 : State machine은 state, input events, transition (state에 대한 input events와 state를 맵핑) 의 집합

 

- 상태 머신은 concurrent event 구동 에코 서버에서 logical flow에 대한 것

 

input event에서 디스크립터가 읽을 준비가 되면 -> transition은 디스크립터로부터 텍스트 라인을 읽음 -> State는 읽을 준비를 하기 위해 디스크립터를 기다림

 

 

nready : select로 부터 ready set에 들어있는 비트 벡터의 1의 개수를 리턴

clientfd[FD_SETSIZE] : active 디스크립터의 집합

clientrio[FD_SETSIZE] : 클라이언트가 보내는 메세지를 버퍼링하기 위한 버퍼

 

pool을 static하게 선언하여 init_pool(listenfd, &pool)로 pool 초기화

* init_pool

pool의 모든 clientfd를 -1로 초기화

비트 배열(read_set)의 가장 큰 디스크립터 안에 listenfd를 넣어줌

비트 배열을 모두 0으로 클리어

비트 배열의 listenfd 원소에 비트를 1로 세팅

 

 

원본 비트 배열인 read_set을 유지하기 위해 ready_set에 원본을 복사

Select 함수를 통해 비트 벡터에서 1로 표현되는 비트의 개수를 리턴하여 nready에 넣어줌

 

만약 비트 벡터 안의 listenfd의 비트가 1로 세팅이 되어있으면, 즉 listenfd에 pending input이 있으면

listenfd를 통해 클라이언트로부터 온 connect request를 accept하고 connfd를 리턴

pool에 connfd를 추가한다. 

 

add_client -> 세팅된 fd의 작업을 처리하므로 nready 감소

pool안의 비어있는 clientfd를 찾아서 connfd를 넣어줌

Rio_readinitb함수를 이용하여 pool의 clientrio를 connfd로 초기화

비트 배열에 connfd를 세팅

 

 

check_clients(&pool);

각 connect된 디스크립터로부터 텍스트 라인을 에코

 

비트 벡터에 connfd의 비트가 세팅이 되어있으면 모두 처리함

?????? 모르겠다 책읽어

 

- Event-based Servers의 장/단점

: 장 - 하나의 논리적 flow와 addr space

 - 디버거를 한 번에 가능

 - 프로세스나 thread control에 대한 overhead 없음

 

: 단 - fine-graind concurrency하기 어려움 -> 핸들링하는 프로세스 중간에 interleaving할 수 없음

ex) echo 서버에서 fd에 pending input이 있어서 msg에 응답을 할 때 이 작업이 끝날 때까지 다른 fd의 pending input을 처리할 수 없음

 - multi-core를 할 수 없음 : single thread of control

-> 하나의 프로세스가 여러 개의 이벤트를 처리하기 때문에, 여러 cpu가 있어도 처리를 담당하는 cpu를 제외하고 나머지는 놀게 됨

 

(3) Thread-based

- 프로세스 하나에 여러 execution flow를 가짐

- 커널은 자동으로 다양한 logical flow를 interleave

- 각 flow는 같은 address space를 공유

- 1,2 복합