기아

기아는 어떤 실행 흐름이 필요한 것을 끝내 못 받아 혼자 멈춰 서는 고장입니다. 글을 읽는 요청이 쏟아지는 동안 글을 고치려는 요청 하나가 몇 분째 못 들어갑니다. 나머지 흐름은 멀쩡히 일을 끝내고 있어서 지표만 보면 아무 일도 없어 보입니다. 밀린 쪽은 오류 하나 없이 기다리기만 합니다.

쉽고 빠른 이해

차례가 영영 안 오는 고장입니다. 글을 읽는 요청이 끊이지 않는 게시판에서 글을 고치려는 요청 하나가 몇 분째 못 들어가는 것이 그런 경우입니다.

차례를 정하는 규칙이 얼마나 기다렸는지를 안 보기 때문에 생깁니다. 규칙이 매번 지금 조건만 보고 고르면, 조건이 늘 불리한 흐름은 매번 집니다.

이렇게 터집니다:

1. 한 번에 쓸 수 있는 수가 정해진 것을 여럿이 나눠 씁니다
2. 다음 차례를 고르는 규칙이 기다린 시간을 안 봅니다
3. 그 규칙에서 유리한 요청이 끊이지 않고 들어옵니다

막으려면 처리량을 내줘야 합니다. 기다린 순서를 지키면 지금 당장 제일 싸게 끝낼 수 있는 요청을 뒤로 미루게 됩니다.

상세

이 절은 굶는 쪽을 먼저 가릅니다. 이어서 터지는 조건 셋과 그 조건을 그대로 만든 재현 둘, 닮은 고장과의 차이, 알아채는 지표, 막을 때 내주는 값을 봅니다.

굶는 흐름과 자원

문 하나뿐인 진료실 앞에 사람들이 모여 있다고 해 봅시다. 접수대가 부를 사람을 고를 때마다 제일 급해 보이는 사람을 고르면, 덜 급한 사람은 급한 사람이 오는 동안 계속 뒤로 밀립니다. 급한 사람이 쉬지 않고 오면 그 사람의 차례는 끝내 안 옵니다.

실행 흐름은 명령을 차례차례 밟아 나가는 단위 하나를 말합니다. 한 프로그램 안에서 따로 도는 흐름이 스레드입니다. 저마다 메모리를 따로 쥔 흐름은 프로세스입니다. 한 스레드 안에서 번갈아 도는 코루틴도 같은 노릇을 합니다.

기아는 줄에 들어선 실행 흐름이 필요한 자원을 남들에게 계속 밀려 못 받는 고장입니다. 요청은 받아들여졌습니다. 못 받을 까닭도 없습니다. 차례만 안 옵니다.

한 번에 한 흐름만 들여보내는 장치가 락입니다. 글을 읽는 요청이 계속 새로 오는 게시판에서 글을 고치려는 요청 하나가 몇 분째 락을 못 잡습니다.

여기서 자원은 한 번에 쓸 수 있는 수가 정해진 것을 말합니다. 한 흐름만 들어갈 수 있는 락, 나눠 쓰는 계산 시간, 개수가 정해진 커넥션 풀의 연결이 전부 자원입니다.

수가 정해져 있으니 누가 먼저 쓸지를 누군가 골라야 합니다. 그 고르는 쪽이 스케줄러입니다. 스케줄러가 누구를 먼저 넣을지 정하는 방식을 이 편에서는 차례 규칙이라 부릅니다.

아래 그림은 밀리는 모양입니다. 대기 줄에 셋이 서 있고 스케줄러는 기다린 시간을 안 봅니다.

flowchart TD
    subgraph Q["대기 줄"]
        W["먼저 선 요청"]
        N1["뒤에 온 요청"]
        N2["더 뒤에 온 요청"]
    end
    W -.->|번번이 안 골린다| S["스케줄러 · 기다린 시간을 안 본다"]
    N1 -->|먼저 골린다| S
    N2 -->|먼저 골린다| S
    S --> R["자원 · 한 번에 쓸 수 있는 수가 정해짐"]

먼저 선 요청만 점선입니다. 뒤에 온 요청들은 그 앞을 지나 자원까지 갑니다. 그래서 줄 길이는 그대로인데 맨 앞 요청의 나이만 늘어납니다.

이름은 굶주림에서 왔습니다. 영어로는 starvation 이라고 적습니다. 밥을 나눠 주기는 합니다. 내 몫만 매번 남에게 가는 그림입니다.

터지는 조건

셋이 모두 맞을 때만 터집니다. 하나라도 빠지면 아무리 흐름이 많고 다툼이 잦아도 특정 흐름만 영영 밀리는 일은 안 생깁니다.

가운데 조건이 이 고장의 뿌리입니다. 규칙이 매번 지금 상태만 보고 고르면 기다린 시간은 아무 힘이 없습니다. 조건이 늘 불리한 흐름은 매번 집니다. 진 횟수가 쌓여도 다음 판이 유리해지지 않습니다.

셋이 다 맞아야 기아입니다. 막는 방법도 이 셋을 거꾸로 밟습니다.

조건은 이 정도로 좁혀야 재현이 됩니다. 「다툼이 심할 때 터집니다」는 조건이 아닙니다. 「읽기 요청이 겹치도록 끊임없이 들어오는 동안 쓰기 요청 하나를 넣으면 그 쓰기가 끝까지 못 들어간다」가 조건입니다.

읽기-쓰기 락의 최소 재현

제일 작은 재현은 읽기-쓰기 락입니다. 이 락은 읽기만 하는 흐름끼리는 같이 들여보냅니다. 고치는 흐름은 혼자만 들여보냅니다. 읽기끼리 겹쳐 들어가도 값이 안 갈리니 그만큼 처리량을 버는 장치입니다.

읽기를 먼저 들여보내는 규칙에서 무슨 일이 나는지 봅시다. 읽기 잠금은 겹쳐서 바로 잡힙니다. 쓰기 잠금은 읽는 흐름이 0 일 때만 잡힙니다.

읽는 흐름 수는 3 · 2 · 4 · 1 로 오르내립니다. 새 읽기가 계속 들어오는 한 0 은 안 찍습니다. 쓰기는 0 이 되는 순간을 기다립니다. 그 순간이 안 옵니다.

아래는 그동안의 진행 순서입니다.

sequenceDiagram
    participant R as 읽기 흐름들
    participant L as 락
    participant W as 쓰기 흐름
    R->>L: 읽기 잠금 요청
    L-->>R: 바로 내준다
    W->>L: 쓰기 잠금 요청
    Note over L,W: 읽는 흐름이 0 이 돼야 내준다
    R->>L: 새 읽기 잠금 요청
    L-->>R: 또 내준다
    Note over W: 읽기가 멎을 때까지 선다

쓰기는 한 번도 거절당하지 않았습니다. 거절이면 오류가 남아 누군가 알아챕니다. 여기서는 요청이 받아들여진 채로 대기 줄에 얹혀 있을 뿐이라 로그에 아무것도 안 남습니다.

우선순위와 선점

차례를 우선순위로 고르는 곳에서도 같은 일이 납니다. 급한 일을 먼저 처리하려고 흐름마다 등급을 매기면, 등급이 낮은 흐름은 높은 흐름이 없을 때만 차례를 받습니다. 높은 흐름이 쉬지 않고 들어오면 낮은 흐름의 차례는 안 옵니다.

선점이 있는 곳에서는 더 세게 밀립니다. 선점은 돌고 있던 흐름에게서 차례를 도로 빼앗아 급한 흐름에게 주는 동작입니다. 낮은 등급의 흐름은 겨우 받은 차례마저 중간에 빼앗깁니다.

이름이 비슷한 우선순위 역전과는 다른 고장입니다. 우선순위 역전은 낮은 등급의 흐름이 락을 쥔 채 밀려서 그 락을 기다리는 높은 등급의 흐름까지 같이 멈추는 것입니다. 기아는 밀린 흐름 자신이 못 나아가는 것입니다. 우선순위 역전은 그 밀림이 위로 번지는 것입니다.

되돌려 다시 시키는 구조

다시 시도하는 구조도 같은 조건을 만듭니다. 낙관적 잠금은 값을 고쳐 쓰기 직전에 남이 먼저 고쳤는지 봅니다. 고쳤으면 되돌려 다시 시킵니다.

여기에는 대기 줄이 없습니다. 그래도 다툼이 잦으면 유난히 오래 걸리는 요청 하나가 다시 할 때마다 또 집니다. 되돌린 요청이 한꺼번에 다시 몰리는 것을 재시도 폭풍이라고 합니다.

stateDiagram-v2
    읽음: 값을 읽음
    검사: 고쳐 쓰기 직전 검사
    되돌림: 되돌림
    마침: 고쳐 쓰기 성공
    [*] --> 읽음
    읽음 --> 검사
    검사 --> 되돌림: 남이 먼저 고쳤다
    되돌림 --> 읽음: 다시 시킨다
    검사 --> 마침: 아무도 안 고쳤다

굶는 흐름은 이 고리를 계속 돕니다. 오른쪽 화살표 하나가 못 나오는 것이 기아입니다.

데드락·라이브락과의 차이

이름이 나란히 불리는 고장 셋은 「무엇이 안 나아가나」에서 갈립니다.

데드락은 둘 이상이 서로 쥔 것을 기다리며 통째로 섭니다. 기아는 다른 흐름들이 잘 끝나고 있다는 것이 오히려 조건입니다. 그래서 전체 처리량이나 오류율로는 안 보입니다. 밀린 흐름 하나를 따로 봐야 보입니다.

라이브락은 서로 양보하다가 아무도 못 끝냅니다. 상태는 계속 바뀌지만 일은 안 끝납니다. 그 점이 기아와 닮았습니다. 갈리는 곳은 범위입니다. 라이브락은 얽힌 쪽이 다 같이 못 끝내고, 기아는 남들이 끝내는 동안 한쪽만 못 끝냅니다.

굶는 흐름을 드러내는 지표

평균으로는 안 보입니다. 굶는 흐름은 대개 한 줌이라 평균 대기 시간에 거의 영향을 못 줍니다. 요청이 만 건이면 그중 한 건이 아무리 오래 걸려도 평균은 멀쩡합니다.

그래서 분포의 끝을 봅니다. 상위 몇 퍼센트가 얼마나 기다렸는지를 재는 꼬리 지연과 대기 시간의 최댓값이 먼저 움직입니다. 최댓값이 계속 커지기만 하고 안 내려오면 누군가 줄에서 안 빠져나가고 있다는 뜻입니다.

제일 곧은 지표는 대기 줄에서 제일 오래 기다린 요청의 나이입니다. 줄의 길이는 짧아도 이 나이가 계속 늘면 그 줄은 순서대로 빠지고 있지 않은 것입니다. 앞 그림에서 점선으로 남은 요청이 이 나이를 혼자 키웁니다.

타임아웃을 걸어 두었다면 오래 기다린 요청이 취소로 나타납니다. 그때는 대기가 실패로 바뀔 뿐 굶은 것은 그대로입니다.

차례 규칙을 바꾸는 세 방법

고치는 곳은 자원이 아니라 차례를 고르는 규칙입니다. 기다린 시간이 힘을 갖게 만들면 「안 보는 규칙」 조건이 깨집니다. 이름 붙은 방법이 셋 있고, 어느 것도 새 자원을 만들지 않습니다.

도착 순서를 기억하는 줄을 세우는 것이 첫째입니다. 먼저 온 요청이 먼저 들어가면 내 앞에 선 요청 수가 정해지므로 기다림에 끝이 생깁니다. 이 성질이 공정성입니다. 이 성질을 지키는 락은 공정 락입니다.

기다린 만큼 등급을 올려 주는 것이 둘째입니다. 이 방법을 나이 먹이기라고 부릅니다. 밀린 흐름은 기다릴수록 급해지므로 언젠가는 제일 급한 흐름이 됩니다.

몫을 미리 갈라 주는 것이 셋째입니다. 흐름마다 받을 몫을 정해 두고 돌아가며 나눠 주면 한쪽이 전부 가져가는 일이 없습니다. 라운드 로빈처럼 차례로 한 번씩 주는 방법이 제일 단순한 꼴입니다.

셋 다 값을 치릅니다. 순서를 지키면 지금 당장 제일 싸게 끝낼 수 있는 요청을 뒤로 미루게 됩니다. 그만큼 처리량이 줄어듭니다. 읽기-쓰기 락에서 쓰기를 기다리는 동안 새 읽기를 막으면 겹쳐 읽어 벌던 이득이 사라집니다.

안 굶는 경우

오래 기다린다고 다 기아가 아닙니다. 조건 셋 중 하나만 빠져도 기다림에는 끝이 있습니다.

몰린 요청이 빠지면 풀리는 것은 밀림이지 기아가 아닙니다. 아침에 쌓인 줄이 낮에 풀린다면 경쟁이 끊긴 셈입니다. 「끊기지 않는 경쟁」이 빠진 것입니다. 이때 봐야 할 것은 차례 규칙이 아니라 줄이 쌓이는 병목입니다.

자원이 바닥난 것과도 다릅니다. 연결을 하나도 못 여는 것은 남이 다 쓰고 있어서가 아니라 열 수 있는 수가 0 이 된 것입니다. 이쪽은 모두가 같이 못 받으므로, 한쪽만 밀리는 기아와는 손댈 곳이 다릅니다.

도착 순서를 지키는 줄에서도 안 굶습니다. 내 앞에 선 요청 수는 들어설 때 정해집니다. 그 수는 늘지 않습니다. 뒤에 누가 아무리 많이 와도 내 차례는 그만큼 뒤로 안 밀립니다. 이 성질이 앞 소절에서 말한 공정성입니다.

관련 항목

기아가 자라는 실행 구조

동시성 · 스레드 · 프로세스 · 코루틴 · 스케줄링 · 스케줄러 · 선점 · 문맥 교환 · 임계 구역 · 공유 자원

기아가 나는 잠금 장치

락 · 뮤텍스 · 세마포어 · 스핀락 · 읽기-쓰기 락 · 낙관적 잠금 · 비관적 잠금 · 분산 락 · 락 경합

기아와 나란히 나는 동시성 고장

데드락 · 라이브락 · 우선순위 역전 · 경쟁 상태 · 락 호위 · 썬더링 허드 · 재시도 폭풍 · ABA 문제

기아를 막는 차례 규칙

공정성 · 라운드 로빈 · 나이 먹이기 · 공정 락 · 티켓 락 · 가중 공정 큐잉 · 할당량 · 속도 제한 · 우선순위 상속

기아를 드러내는 지표

꼬리 지연 · 지연 · 처리량 · 대기 시간 · 큐 길이 · 포화 · 병목

기아가 잦은 자원 공유 도구

스레드 풀 · 커넥션 풀 · 작업 큐 · 부하 분산 · cgroup · 멀티테넌시 · 시끄러운 이웃 · 타임아웃