교수님: 일을 반드시 여러 사람과 함께 해야 효율이 높아지나요? 과제를 두 명이서 같이 한다고 생산성이 반드시 두 배가 되던가요? 뭐 프리라이더도 있고, 서로 안 맞아서 싸워서 혼자 하느니만도 못하게 될 수도 있고.. 뭐 커뮤니케이션 안 맞고, 로드 밸런스 안 맞고? issue가 많죠?
You know there's some kind of cost you need to pay in order to run things in pararell. So that's basically what this module is about. So we're going the last module is about concurrent programming!

이재욱 교수님의 5월 30일 목요일자 명강의, 정리 레츠고❤️

Concurrent Programming

Concept

• programs with more than a single flow of control
• "doing several thigs at the same time"

본 강의에서 다룰 concurrency는 OS level의 concurrency와는 다르다. 여러 개의 task를 수행하는 것에 있어 동시성이 아니라, 하나의 작업 내에서 어떻게 concurrent 하게 작업을 수행할 것인지에 관한 논의.

most useful for data pararellism and task pararellism.
(+ 추가. GPU에서 CUDA 같은 것도 data para~의 대표적인 예시임)

Data Parallelism

예시를 통해 이해하는 것이 빠름.

[예시] C[i] = A[i] + B[i] 벡터 연산

한 번에 다 수행하기만을 기다리면 너무 오래걸리니깐 4개로 나눠서 수행하도록 하기. 방식은 여러 가지가 있을 수 있는데 효율성도 고려해서 나누는 게 좋다. (cache miss/hit 측면에서도 생각해보면 좋음)

Task Parallelism

distribute different tasks to multiple execution threads.
하나의 프로그램 안에서 task 별로 thread 다르게 하기.

대표적인 예시: 웹 서버

Interesting Problems..

• workload distribution: static, dynamic, how much at once?
• workload breakdown: consecutive or interleaved...?
• how many parallel tasks?
• data dependencies..

interleaved 개념에 대해 부연설명: 어떤 프로그램의 일부를 다른 프로그램에 끼워 넣는 일. 결과적으로 2개의 프로그램이 동시에 수행되게 함.

보통 사용하는 16 코어 CPU 에서,
Q. What would be the optimal parallelism?

degree of parallelism and throughput?

• Scenario I. dop=16 지점까지는 throughput 점진적 증가, 이후 saturated.
• Scenario II. dop=8~9 지점까지는 throughput 점진적 증가, 이후 saturated.
• Scenario III. dop=16 을 넘어서도 꾸준히 증가, 이후 saturated.

설명

• Scenario I. 일반적인 경우 코어가 16개면 노는 코어가 없게 16으로 설정하긴 함.
• Scenario II. 일의 양이 적을수도 있고^^, memory 나 network bandwidth가 bottle neck 인 경우(!)
• Scenario III. memory or i/o bound가 saturated 되지 않은 경우 가능.

Classical Problems

Concurrent programming is hard..😂

1. Race
2. Deadlocks
3. Livelock / Starvation / Fairness

Race

자식 프로세스나 부모 프로세스 중 누가 먼저 실행될지는 아무도 모른다.

아래 코드를 순차적인 코드로 바꾸려면 barrier()를 삽입해서 실행 순서를 정해줄 수 있다. 아래 코드에서 주석을 해제하면 무조건 parent가 먼저 실행되게 됨.

int main(int argc, char *argv[])
{
	pid_t pid = fork();
    
	if (pid > 0) {
    	printf("Hello from parent!\n"); 
        // barrier();
    }
	else if (pid == 0) {
    	// barrier();
    	printf("Hello from child!\n");
    }
	else printf(“Cannot fork.\n");
    
	retun EXIT_SUCCESS;

Deadlock

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
exclusive lock을 걸었을 때 서로가 서로를 기다리는 현상이 발생해서 아무것도 실행되지 못하는 상황을 가리킨다. 물고 물리는 관계~

p1.c: lock(A)-> lock(B)
p2.c: lock(B)-> lock(A)
p2은 p1의 A가 해제될 때까지 기다리고,
p1은 p2의 B가 해제될 때까지 기다리고, 결국 아무것도 시작하지 못한다

Starvation

When people always jump in front of you in line(!)

livelock 이라고도 불리는 이유 (deadlock과 비교해서): 내가 차를 몰고 가고 있는데, 옆 차선의 차량이 끼어들기를 하려고 함. 근데 서로 양보해서 그 자리를 아무도 차지 하지 않는 거임. 그래서 갈까..?하고 속도를 더 내면 둘이 또 부딫힐까봐 또 못 가는 거임. 그래서 갈 수 있는데 못 가는 상황이니깐. livelock임.. ㅠㅠ
deadlock은 애초에 못 가서 못 가는 거니깐. (프로세스가 끝날때까지 계속 기다리고 있으니깐)

Iterative Server

• Iterative servers process one request at a time

• Iterative Echo Server Example:
  
  여러 클라이언트의 요청을 동시에 처리하기 어려움, concurrency가 필요하다!

• Concurrent servers use multiple concurrent flows to serve multiple clients at the same time ^^

Concurrency Models

1. Process

• Kernel automatically interleaves multiple logical flows
• Each flow has its own private address space
• private memory by default

2. Threads

• Kernel automatically interleaves multiple logical flows
• Each flow shares the same address space
• shared memory by default

3. I/O multiplexing with select()

• not cover for this class

Concurrent Processes

Iterative Echo Server

/// @brief main server routine accepting new connections.
/// Calls run_instance() for every client and blocks until the client exits.
/// @param listen_fd listening socket
void run_server(int listen_fd)
{
    while (1) {
        int client_fd;
        struct sockaddr client;
        socklen_t clientlen = sizeof(client);

        client_fd = accept(listen_fd, &client, &clientlen);
        if (client_fd > 0) {
            printf(" connection from "); 
            dump_sockaddr(&client); 
            printf("\n");

            run_instance(client_fd);
            close(client_fd);
        } else {
            // print error message and abort on any error
            perror("accept");
            break;
        }
    }
}

Process-Based Concurrent Echo Server

/// @brief main server routine accepting new connections. Forks a new
/// instance for every client and calls run_instance() on it.
/// @param listen_fd listening socket
void run_server(int listen_fd)
{
    // register signal handler
    if (signal(SIGCHLD, reaper) == SIG_ERR) { … }
    
    while (1) {
        int client_fd;
        struct sockaddr client;
        socklen_t clientlen = sizeof(client);

        client_fd = accept(listen_fd, &client, &clientlen);
        if (client_fd > 0) {
            printf(" connection from "); 
            dump_sockaddr(&client); 
            printf("\n");

            if (fork() == 0) {
                // close listening socket in client & set sock_fd to cfd for close at exit
                close(listen_fd);
                sock_fd = client_fd;
                run_instance(client_fd);
                exit(EXIT_SUCCESS);
            }
            close(client_fd);
        } else { 
            // handle error
        }
    }
}

/// @brief signal handler for SIGCHLD, reaps all exited children
/// @param signal signal ID (==SIGCHLD)
void reaper(int signal)
{
    while (waitpid(-1, 0, WNOHANG) > 0) ;
}

code difference?

그래서 뭐가 어떻게 달라진건데? 가장 주요한 차이점은 자식 프로세스에서 클라이언트의 요청을 처리하도록 바꾸었다는 것이 코드에서 달라진 부분임.

또한 자식 프로세스가 종료될 때 시그널(SIGCHLD)을 처리할 핸들러를 등록하였다는 것도 달라진 점.

공통 부분 설명
서버는 계속해서 클라이언트의 연결을 대기하면서, 리스닝 소켓 listen_fd에서 클라이언트의 연결을 수락하고, 새로운 연결이 들어오면 client_fd를 반환.

client_fd = accept(listen_fd, &client, &clientlen);

달라진 부분 설명
자식 프로세스 생성 (fork())
자식 프로세스에서는 리스닝 소켓을 닫고(close(listen_fd)), run_instance(client_fd)를 호출하여 클라이언트의 요청을 처리
부모 프로세스는 클라이언트 소켓을 닫고(close(client_fd)), 다음 클라이언트 연결을 대기

// child process
if (fork() == 0) { 
    close(listen_fd);
    sock_fd = client_fd;
    run_instance(client_fd);
    exit(EXIT_SUCCESS);
}
// parent process
close(client_fd);

Process Execution Model

• each client handled by independent process
• no shared state

• parent process must close client_fd

• child process must close listen_fd

  부모 프로세스가 client_fd를 닫는 이유:
  리소스 해제 및 파일 디스크립터 누수 방지
  자식 프로세스가 클라이언트 소켓을 닫았을 때 실제로 소켓이 완전히 닫히도록 보장
  자식 프로세스가 listen_fd를 닫는 이유:
  불필요한 리소스 점유 방지
  리스닝 소켓이 여러 프로세스에서 관리되는 것을 방지하고, 부모 프로세스가 올바르게 새로운 클라이언트 연결을 처리할 수 있도록 보장
  요약
  이와 같은 리소스 관리와 프로세스 간 간섭 방지는 서버가 안정적으로 동작하도록 하는 중요한 요소입니다.

• listening server process must close its copy of client_fd

• forked-off echo server process should close its copy of listen_fd

• listening server process must reap zombie children to avoid fatal memory leak

Pros and Cons of Process-Based Design.

• 장점: 아무래도 프로세스의 특징 상 독립적인 메모리 공간을 가진다는 거랑, 쓰레드와 비교해서는 단순하다는 점이 장점이지.
• 단점: 프로세스 생성 및 해제 오버헤드가 크다는 거? ㅠㅠ

Module Summary