=== Concurrent Programming ===

0. Concurrent Programming is Hard!

• The human mind tends to be sequential
• The notion of time is often misleading
• Thinking about all possible sequences of events in a computer system is at least error prone and frequently impossible

우리는 sequential하게 프로그래밍 하기 때문에 쉽지 않다. 시간이라는 개념이 다르게 돌아갈 수 있다.

이벤트가 컴퓨터안에서 언제 발생할지 예상할 수 없어서 비동기방식으로 처리해야 한다. 그러지 않으면 버그가 많이 생긴다.

---

• Classical problem classes of concurrent programs:
  • Races: outcome depends on arbitrary scheduling decisions elsewhere in the system
    • Example: who gets the last seat on the airplane?
      OS가 프로세스 여러개 띄어놓고 time sharing하기 때문에 scheduling한다. 하지만 이건 우리가 제어할 수 없다. 그래서 scheduling이 어떤순서로 일어나는지에 따라 결과값이 다를 수 있다.
  • Deadlock: improper resource allocation prevents forward progress
    • Example: traffic gridlock
      resource할당을 잘 못 할당해서 두 개 이상의 프로세스가 proceed를 못하고 기다리고 있는 문제이다.
  • Livelock / Starvation / Fairness: external events and/or system scheduling decisions can prevent sub-task progress
    • Example: people always jump in front of you in line
      Livelock은 lock을 계속 획득해서 critical section에 들어가기 위해 lock을 계속 요청하는 경우
      Starvation은 내가 critical section에 들어가고 싶은데 다른 프로세스가 이미 들어가 있어서 스케쥴링도 잘못되어서 내가 그 안에 들어갈 수 있는 기회를 계속 놓치어 굶어 주는 경우
      Fairness는 스케쥴링이 되는 순서에 따라서 내가 필요한 만큼의 clock cycle을 받지 못하는 경우
      (필요한 부분만 공부예정)
• Many aspects of concurrent programming are beyond the scope of our course..
  • but, not all happy
  • We’ll cover some of these aspects in the next few lectures.

Iterative Servers

• Iterative servers process one request at a time
  

현재 서버를 띄우고 listen중일때 client가 connect request를 보내고 accept하고 read하려고 기다리고 있는다고 하자. 그 찰나에 clinet2가 connect request를 보낸다. request는 Server에서 tcp manager에서 buffering된다. 하지만 얘에 대한 accept를 하지 않는다.

client1은 write하면 이걸받지만 client2의 write는 tcp manager의 buffer에 쌓이게 된다.

client1의 메세지를 받아서 서버는 그것에 대해 write를 하고 client는 그것을 읽어 화면에 띄운다. 그러다가 close 메세지가 오면 이 프로세스는 종료된다.

client2의 것을 close이후에 accept한다. 그러면 이전에 받은 메세지는 queueing되어 있을테니 그것을 read해서 client2로 write한다.

결국 client2는 오랜 write되어 ret read될떄까지 계속 기다려야 하는 concurrent하지 않은 상황이 만들어진다.

Where Does Second Client Block?

• Second client attempts to connect to iterative server
• Call to connect returns
  • Even though connection not yet accepted
  • Server side TCP manager queues request
  • Feature known as “TCP listen backlog”
    client는 connect를 하고 바로 return을 한다. 하지만 서버쪽의 TCP manager가 queue를 하고 있기 때문에 return을 할 수 있다.
• Call to rio_writen returns
  • Server side TCP manager buffers input data
    클라이언트는 write함수를 호출할 수 있다. server는 TCP manager에서 buffer된 메세지를 queueing한다.
• Call to rio_readlinebblocks
  • Server hasn’t written anything for it to read yet.
    그리고 여기에서 blocking된다.
    

Fundamental Flaw of Iterative Servers

• Solution: use concurrent servers instead
  • Concurrent servers use multiple concurrent flows to serve multiple clients at the same time

결국에는 server가 connect를 하고 client1과 통신하지만 client2는 request를 보내서 queueing은 되었으나 connect는 establish되지 않은 상황이다.

client1이 close되기 전까지는 client2는 계속 기다려야 한다.

동시에 여러개의 client의 서비스를 할 수 있도록 concurrent flow를 여러개 만든다.

=== Approaches for Writing Concurrent Servers ===

1. Approaches for Writing Concurrent Servers

Allow server to handle multiple clients concurrently

1. Process-based

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

---

2. Event-based

• Programmer manually interleaves multiple logical flows
• All flows share the same address space
• Uses technique called I/O multiplexing.

---

3. Thread-based

• Kernel automatically interleaves multiple logical flows
• Each flow shares the same address space
• Hybrid of of process-based and event-based.

concurrent flow를 여러개 만드는 방법이 존재한다. 총 3가지 방법이 존재한다.

1. Process 기반은 connection맺을때마다 parent가 accept하고 child를 띄어준다. 그래서 커널이 여러개의 logical flow를 맺어 커널이 얘들 사이의 time sharing을 해서 어찌되었든 concurrent하게 서비스 할 수 있게 한다.
   

2. Event 기반은 포크를 띄우지 않고 서버 프로세스는 하나만 있다. 각 client가 accpet을 해서 fd를 따로따로 가지고 있다. 그리고 fd마다 어떤 메세지가 오면 조건문에 따라서 각 fd에 해당하는 내용을 처리해주는 방식이다. logical flow가 있지만 manual하게 처리해야 한다. 이걸 보고 I/O multiplexing이라고 부른다.

3. thread-based는 kernel이 자동적으로 interleave한다. 각 flow는 동일한 address space를 공유한다. 이게 process-based와 차이점이다.

Approach #1: Process-based Servers

• Spawn separate process for each client
  

클라이언트가 connect 요청 accept하고 fork를 띄운다. 그 사이에 connect가 또 오고 queueing한다. child process는 client1과 소통한다.
서버는 그 사이 client2에 대한 fork를 띄어서 소통한다.

2. Process-Based Concurrent Echo Server

connfd로 온 요청을 받고 Fork()를 띄운다음에 client와 소통한다.

parent입장에서는 connfd를 닫아준다.

---

• Reap all zombie children
  

reaping을 위해 signal handler를 등록한다. signal handler로 child process를 reaping한다.

Concurrent Server: accept Illustrated

3번째 과정에서 child process를 fork해서 connfd를 만든다.

Process-based Server Execution Model

• Each client handled by independent child process
• No shared state between them
• Both parent & child have copies of listenfd and connfd
  • Parent must close connfd
  • Child should close listenfd

이 모델자체가 프로세스 기반으로 connection이 만들어지면 각각의 child process가 만들어져서 처리된다. 각 child는 독립된 공간을 가지고 있어서 shared data structure이 없다.

Issues with Process-based Servers

• Listening server process must reap zombie children
  • to avoid fatal memory leak
• Parent process must close its copy of connfd
  • Kernel keeps reference count for each socket/open file
  • After fork, refcnt(connfd) = 2
  • Connection will not be closed until refcnt(connfd) = 0

connfd는 반드시 종료해주어야 한다. 이 refcnt가 감소하지 않고 누적되기 때문에 메모리 누스가 날 수 있다.

Pros and Cons of Process-based Servers

• • Handle multiple connections concurrently
• • Clean sharing model
  • descriptors (no)
  • file tables (yes)
  • global variables (no)
• • Simple and straightforward

• – Additional overhead for process control

• – Nontrivial to share data between processes

  • Requires IPC (interprocess communication) mechanisms
    • FIFO’s (named pipes), System V shared memory and semaphores

단점은 fork를 띄우면 자원을 굉장히 많이 소모한다.
그리고 프로세스간의 data sharing이 안된다.