스터디 일자 : 2022.05.21

도서 및 진행범위 : 리눅스 커널 내부구조- Chapter 3 태스크 관리

 

[다음주차 진행 준비내용]

- 다음 주차 진행 범위 : 리눅스 커널 내부구조 - Chapter 4 메모리 관리

 

 

 

[스터디 진행 내용]

 

읽어보면 좋을 자료들

Understanding the Linux 2.6.8.1 Scheduler
O(1) 스케줄러에 대한 설명이 자세하게 적혀있습니다.

CPU balancing, schedule() 함수,  NUMA에서의 migration, O(1) 스케줄러 등도 잘 설명되어있습니다.

Inside the Linux 2.6 Completely Fair Scheduler
CFS를 간략하게 설명합니다.
 

프로세스와 스레드

사진과 같이 프로세스는 독립적인, 가상의 프로세스 주소 공간을 사용한다. 그럼 코드에서 스레드를 생성했을 때와 프로세스를 생성했을 때는 어떤 차이가 있을까?

아래 두 사진을 봤을 때 프로세스를 새로 생성할 때는, 한 프로세스가 전역변수의 값을 바꿔도 다른 프로세스에서는 값이 그대로이다.
 

 

반대로 다음 그림에서는 한 스레드에서 바꾼 전역변수의 값이 다른 스레드에서도 바뀐 부분이 반영됨을 보여준다.

 

위 두 예시를 보았을 때, 한 프로세스 내의 스레드들은 주소 공간의 일부를 공유함을 알 수 있다. (스택영역은 공유하지 않는다. -> 공유하지만 일반적으로 공유해서 사용하지 않는다.)
 

 

 

fork vs vfork

참고자료: https://taeguk2.blogspot.com/2015/10/fork-vfork.html

 

 

fork()와 자주 쓰이는 함수는 exec*()이다.

예로 쉘에서 ls를 수행하면, 쉘은 우선 fork()로 프로세스의 주소 공간 및 메모리를 복사한 이후 exec*()로 /bin/ls를 실행한다.

exec*() 이후에는 fork()에서 복사했던 주소 공간과 메모리는 반환된다.
이는 큰 오버헤드가 아닐 수 없는데, 프로세스 하나는 최소 수kb~수mb의 메모리를 사용한다.

그런데 fork()를 수행하자마자 exec*()를 수행하면 fork()에서 주소 공간과 메모리를 복사할 필요가 없었던 것이다.

그래서 예전에는 새로운 프로세스를 생성하지만 주소 공간을 복사하지 않는 vfork()라는 시스템 호출을 사용했다.

요즘에는 fork()를 호출한다고 무조건 메모리를 복사하지 않고, 주소 공간만 복사한 다음 페이지 테이블에서 메모리를 read only로 바꾼 이후 쓰기를 할 때 복사한다. (Copy-On-Write라고 한다.)
(Copy-On-Write를 실제로 구현해보는 과제를 해보고 싶으신 분들은 아래 mit 운영체제 강좌의 CoW 과제를 해보셔도 좋은 경험이 될 것 같습니다. CoW 과제 이외에도 운영체제에 익숙하지 않으신 분들은 해당 링크에 있는 Labs를 직접 해보시면 많은 도움이 되실 것이라 생각합니다. - 6.S081 / Fall 2021)

 

리눅스의 태스크 모델
 

 

앞서 프로세스는 “실행중인 프로그램”, 스레드는 “수행의 단위”라고 했다.

리눅스에서 프로세스와 스레드를 어떻게 구현하고, 이를 구분하는지 알아보자.

 

리눅스에서는 프로세스가 생성될 때마다 task_struct가 생성되고, 스레드가 생성될 때도 task_struct가 생성된다.

(제 생각에는 프로세스가 생성될 때, 이에 해당하는 스레드(task_struct)가 하나씩 생긴다고 보는게 맞는 것 같습니다.)

또한 위 사진을 보면 알 수 있듯이 fork(), vfork(), pthread_create() 무엇을 호출하든 결국에는 do_fork()로 새로운 '태스크'(task_struct)를 생성하기 때문에 리눅스는 프로세스와 스레드를 크게 구분하지 않음을 알 수 있다. (다만 태스크 간에 얼마나 자원을 공유하냐에 따라서 사용자 입장에서스레드 또는 프로세스로 구분할 수 있다.)

 

 

 

[책 그림 3.8- color 버전] 출처-  https://akkadia.org/drepper/nptl-design.pdf

 

 

리눅스의 태스크 모델 (N:1, 1:1)

커널상에는 스레드가 하나인데, 사용자 수준 라이브러리에서 스레드를 구현하는 경우 (N:1 모델)도 존재하지만 (사진 참고) 

 

리눅스는 사용자 프로세스가 생성하는 스레드도 커널이 그 존재를 알고, 스레드 단위로 스케줄링을 한다. (1:1 모델)

 

 

 

pid(process id), tgid(thread group id)

리눅스는 스레드와 프로세스를 크게 구분하지 않기 때문에 task_struct마다 각각의 pid를 부여한다.

그러나 POSIX 표준상 한 프로세스 내의 스레드들은 같은 pid를 가져야하기 때문에 getpid()는 task_struct의 pid가 아닌 tgid를 반환한다.

 

 

태스크 문맥

스케줄러가 여러 태스크들을 번갈아가면서 실행하려면 태스크가 어떤 코드를 실행하고 있었는지, 레지스터의 값이 무엇이었고 어떤 페이지 테이블을 사용하는지, 어떤 파일을 열었는지 등의 다양한 정보가 필요한데 이를 책에서는 태스크 문맥이라고 한다.

 

태스크의 상태 및 상태 전이

태스크는 항상 실행중이지 않고 IO를 대기하는 등 다양한 상태에 놓일 수 있다.상태간의 전환을 상태 전이라고 한다.

• TASK_RUNNING: 태스크가 CPU 상에서 실행중이거나 실행을 대기중
• TASK_UNINTERRUPTIBLE: 태스크가 어떤 이벤트를 기다리는 중 (시그널에 반응 안함)
• TASK_INTERRUPTIBLE: 태스크가 어떤 이벤트를 기다리는 중 (시그널에 반응함)
• TASK_KILLABLE: 태스크가 어떤 이벤트를 기다리는 중 (주요한 시그널에만 반응함)
• TASK_DEAD: 태스크가 종료되었으나 부모에게서 회수되지 않은 상태

*TASK_INTERRUPTIBLE, TASK_KILLABLE이 시그널을 받은 경우에는 기다리던 이벤트가 발생하지 않았더라도 중간에 깨어날 수 있다.

 

 

 

사용자 프로세스의 커널 컨텍스트

TASK_RUNNING 상태인 태스크는 다시 사용자 모드인 경우와 커널 모드(시스템 호출)인 경우로 나눌 수 있다.

사용자 모드에서 커널 모드로 전환하는 것도 문맥 전환이 필요하기 때문에, 리눅스에서는 태스크마다 커널 스택을 할당하며, 그중 일부를 사용자 모드에서 사용하던 레지스터들의 값과 thread_info를 저장하는데 사용한다.

 

 

 

런 큐와 스케줄링

스케줄러의 일은 시스템 상의 태스크들을 (어느 정도) 공정하고, 시간당 처리량이 높으면서도 한 태스크가 너무 오랫동안 CPU를 쓰지 못하는 일이 없도록 스케줄링 latency도 고려해서 실행하는 것이다. (그리고 스케줄링 자체의 오버헤드도 너무 크지 않아야한다.) 
스케줄러는 태스크들을 스케줄링하기 위해서 런 큐라는 자료 구조를 관리한다.

이런 큐는 CPU마다 존재한다. 참고로, 태스크들을 관리하는데 무조건 큐를 사용하지는 않고 현재 리눅스에서는 스케줄링 클래스에 따라서 태스크의 priority별 runqueue (Real-Time) 또는 red-black tree (Deadline or CFS)로 태스크들을 관리한다.

 

 

 

 

 

 

 

스케줄러의 성능: latency와 throughput

스케줄러는 태스크가 작업을 처리할 수 있도록 일정 시간을 부여하는데, 이를 time slice라고 한다.

스케줄러는 각 태스크를 순회하며 태스크가 자신의 time slice를 소모하면 다음 태스크로 넘어가면서 여러 태스크들이 CPU를 사용할 수 있도록 한다.
이 때 “태스크에게 얼마나 긴 time slice를 할당할 것인가”는 쉽지 않은 문제인데, 문맥 전환을 자주할 경우 응답 시간(latency)이 좋아지며, 문맥 전환을 적게할 경우 문맥 전환의 오버헤드가 줄어들기 때문에 시간당 작업 처리량(latency)가 올라간다.
좋은 스케줄러란 무엇일까? 이 질문은 무엇을 스케줄러를 평가하는 척도로 삼냐에 따라서 달라질 것이다.

환경에 따라서 ‘좋은 스케줄러’가 달라질 수 있음을 (조금 고전적일 수 있다.) 설명해보자.
 

데스크탑 환경
데스크탑 환경에서는 사용자의 입력에 빠르게 반응해야 사용자가 컴퓨터가 느리지 않다고 생각할 것이다.

예를 들어서 워드 프로세서에서 키보드를 눌렀는데 10ms동안 반응이 없다면 사용자가 느끼는 성능 체감이 크다.

반면에 사용자가 백그라운드에서 컴파일을 하는 것과 같은 작업은 조금 느리게 처리되어도 키보드의 반응 속도보다는 덜 체감된다. 따라서 데스크탑에서는 시간당 작업의 처리량(throughput) 보다는 응답 시간(latency)에 민감하다.

서버 환경
반면 서버 환경에서는 데스크탑 보다는 응답 속도에 대해 덜 민감하다. (아무래도 웹 서버에서 응답이 오는 시간은 키보드에서 누른 값이 처리되는 것보다는 느려도 덜 체감된다.)

서버 환경에서는 많은 사용자들의 요청을 처리하기 때문에, 각각의 사용자에게 빨리 응답을 보내는 것 보다는 같은 시간동안 많은 사용자의 요청을 처리하는 것이 효율적이다.

따라서 태스크의 time slice를 적당히 길되 너무 오랫동안 응답을 처리하지 못하는 경우는 없도록 throughput과 latency사이의 밸런스를 조절해야 한다.

HPC (High-Performance Computing) 환경
우리가 일상 생활에서 보기 어려운 고성능 컴퓨팅 환경에서는 과학적인 계산을 하는 등 사용자가 빠른 응답을 기다리는 상황이 아니기 때문에 문맥 전환을 최소화 (거의 없다시피 할 정도로)해야한다. 

캐시 친화성 cache affinity
만약 컴퓨터 내에 단 하나의 런큐만 존재한다고 상상해보자. 그럼 CPU는 하나의 태스크를 실행하고, 다음 태스크를 런 큐에서 꺼내고, 다시 실행하고를 반복할 것이다.

하지만 스케줄러가 이러한 방식으로 작동할 경우 태스크는 여러 CPU를 왔다갔다 하게 되는데, 이럴 경우 CPU의 캐시를 잘 활용하지 못하게 된다.

그래서 되도록 태스크는 여러 CPU 사이를 옮겨가지 않고 하나의 CPU에서 실행되도록 하는 것이 좋다. (다만 태스크를 로드밸런싱할 때는 옮겨야한다.)

fork()를 할 때는 이러한 점을 고려해서 리눅스는 부모 프로세스가 fork()를 했을 때, 자식 프로세스가 같은 CPU에서 실행되도록 한다.

load balancing: scheduler domain & scheduler group
많은 태스크를 실행하는 환경에서는 여러 CPU에게 태스크를 분산해야 작업의 처리량이 올라간다.

그런데 어떤 CPU(i)에서 태스크가 매우 많아서 부하를 분산할 때 임의의 CPU(j)로 옮겨도 상관이 없을까?
아쉽게도 그렇지 않다. 현대의 CPU는 매우 복잡한 기술들로 이루어져 있는데, CPU와 CPU의 관계를 복잡하게 만드는 기술이 몇가지 있다. (CPU 캐시, SMT, NUMA 등)
예를 들어 SMT(Simultaneous Multi-Threading, or Hyper Threading in Intel)를 사용하는 프로세서의 경우 하나의 물리적인 코어가 여러 개의 논리적인 코어를 시뮬레이션하기 때문에 내부적으로 캐시를 공유한다.
 

위 사진에서는 CPU 0-1과 CPU 2-3이 실제로는 각각 하나의 물리적인 코어이다.

이러한 경우에는 CPU 0에서 태스크를 다른 곳으로 분산할 때는 CPU 2-3보다 CPU 1로 옮기는 것이 더 효율적이다.

스케줄러는 이러한 CPU의 특성을 struct sched_domain과 struct sched_group으로 관리한다.
그리고 책에서는 Hyper-Threading에 더불어 캐시의 계층구조 (L1/L2/L3)와 NUMA 구조도 이러한 CPU간의 관계에 영향을 준다고 설명한다.

(struct sched_domain도 계층구조를 형성할 수 있음)
 

 

scheduler classes & policies

최근의 리눅스에서는 다양한 스케줄링 정책을 구현한다.

일반 태스크는 CFS로 공정한 스케줄링을, latency에 민감한 실시간 태스크는 DEADLINE or Real-Time으로 우선순위가 높거나 데드라인이 가장 급한 태스크를 실행한다.

이렇듯 어떤 태스크냐에 따라서 스케줄링 정책도 달라진다. 하나 이상의 스케줄링 정책을 묶어서 리눅스에서는 스케줄링 클래스라고 부른다.

리눅스에는 STOP, DEADLINE, REALTIME, CFS, IDLE 스케줄링 클래스가 존재한다.

 

리눅스는 스케줄링 클래스간에도 우선순위가 존재한다.

위의 PPT가 이러한 스케줄링 클래스간의 우선순위를 보여준다.

 

리눅스는 schedule()로 다음에 실행할 태스크를 찾을 때, 스케줄링 클래스를 순서대로 돌면서 실행할 태스크를 찾는다.

이렇게 스케줄링 정책들을 스케줄링 클래스로 묶음으로서 (당연하게도) DEADLINE, REALTIME 태스크들이 일반 태스크보다 먼저 실행될 수 있다. 이제 각 스케줄링 클래스별로 어떠한 정책이 있는지 알아보자.
 

 

STOP
가장 우선순위가 높은 스케줄링 클래스이며, 태스크의 이동, CPU hotplugging, ftrace 등에 사용된다.

이 클래스에는 별다른 정책이 없다.

Deadline
Deadline은 말 그대로 ‘마감 시간’이 가장 빠른 태스크부터 실행하는 클래스이며 SCHED_DEADLINE 정책만을 사용한다. 이 때 태스크들은 마감 시간을 키로 하는 red-black tree로 관리된다. 데드라인 정책에서는 우선순위의 의미가 없다. (무조건 데드라인 빠른 순)
-실시간 태스크 스케쥴링의 비트맵 상수시간 소요에 대한 코멘트
태스크가 n개가 있다고 가정하자
연결리스트 : n개를 모두 탐색해야한다(30,000개가 되면, 30,000개를 다 찾아야함).
비트맵: 0부터 루프를 돌아도 최악의 경우에도 99까지만 루프를 돈다

Real-Time
Real-Time 스케줄링 클래스에 해당하는 태스크들은 priority별로 큐와 bitmap을 통해서 항상 우선순위가 높은 태스크가 먼저 실행됨을 보장한다.

SCHED_FIFO
FIFO 정책을 사용하는 태스크는 태스크가 CPU를 직접 반납하기 전까지는 선점되지 않는다. 단, 우선순위가 더 높은 FIFO 태스크가 존재하는 경우에는 선점된다.

SCHED_RR
RR은 FIFO와는 다르게 CPU를 무한정 사용하지 않고 정해진 타임 슬라이스씩만 돌아가면서 실행한다. RR 정책을 사용하는 태스크는 우선순위가 더 높은 RR 태스크나 FIFO 태스크에 의해 선점될 수 있다.

Fair
공정 스케줄러 or CFS는 실시간 태스크가 아닌 일반 태스크를 위해서 사용되며, vruntime으로 정렬된 red-black tree에서 가장 vruntime이 작은 태스크를 찾아서 실행한다. 이때, time slice의 크기와 vruntime의 증가 폭은 우선순위에 따라서 달라질 수 있다. (단, 어떤 태스크를 실행할지는 우선순위에 관계 없이 vruntime이 가장 작은 태스크를 실행한다.

SCHED_NORMAL
위에서 설명한, CFS에서 기본적으로 사용하는 정책이 SCHED_NORMAL이다.

SCHED_BATCH
BATCH는 SCHED_NORMAL보다 덜 interactive한 태스크들을 위한 정책으로, 문맥 전환을 최소화하는 정책이다.

(위에서 살펴본 HPC 환경의 예시에 적합한 정책)

SCHED_IDLE
CFS에서의 가장 낮은 우선순위 19보다도 우선순위가 더 낮은 태스크로 CPU가 할 일이 없을 때만 실행된다 ㅡ 다만 이 문장은 항상 참은 아닌데, SCHED_IDLE 정책을 사용하는 태스크에서 세마포어를 획득한 후 sleep한 경우 데드락이 발생할 수 있기 때문에 우선순위가 일시적으로 높아질 수 있다 (?) priority inversion (?)
 

IDLE

 

 

 

 

[진행 내용 및 질의 응답 내용]

Q. 스레드를 만들면 pthread_join()으로 자원을 해제하는데, clone()을 호출했을 땐 어떻게 자원이 반환되나요?
A.

좀비 프로세스와 고아 프로세스
어떤 태스크가 종료하면 (스레드 또는 프로세스) 태스크가 사용하던 자원은 운영체제에 의해 반환됩니다.

(물론 스레드가 종료된 경우에는 텍스트 영역 등의 경우 아직 사용자가 있기 때문에 반환하지 않겠죠.)

하지만 부모가 이 태스크가 어떻게 종료되었는지 등에 대한 정보를 운영체제가 태스크의 식별자를 별도로 관리하는데, 종료되었지만 아직 부모에 의해서 식별자가 회수되지 않은 경우를 좀비 프로세스(스레드)라고 합니다.

스레드를 생성했을 때는 pthread_join()로 이러한 식별자를 회수해주지만 clone()으로 프로세스나 스레드를 만든 경우에는 wait*() 시스템 호출로 이러한 식별자를 해제해주어야 합니다.
-> 라고 생각했는데, pthread_create() 같은 경우에는 태스크의 식별자 뿐만 아니라 새로 만드는 스레드의 스택을 힙에서 할당하기 때문에 스택도 사용한 후 pthread_join()에서 반환해준다고 하네요.

 

 

Q. 스레드간의 자원공유는 어떤 식으로 되나요?
A.

특정 프로세스에서 파생된 스레드들이 공유하는 건 프로세스의 “스택” 부분을 제외하고는 동일함. 전역변수만 가지고도 같은 데이터를 가지고 공유 가능.

스택도 주소를 알면 접근 가능함, but 쓰레드 통신을 할 때는 서로간의 쓰레드간에 접근 안하는게 좋습니다.(스택 값이 수시로 바뀌기 때문에)
프로세스같은 경우는 서로 ipc나 시그널, 소켓을 통해서 전달(?) -> 네 맞습니다.
– 가령 예를 들어서, 프로세스 1은 데이터를 저장하고, 프로세스2는 해당 데이터를 연산하는 기능을 가지고있다면, ipc 를 통해서 프로세스1에서의 데이터를 프로세스2에 전달하는 징검다리개념으로 보시면됩니다.

 

 

Q. vfork를 요즘에는 잘 안 쓰는 이유
A.

함수가 너무 제한적, 스택조차도 복사하지 않음
exit이나 execl 실행될 때까지 계속 wait함
fork() 함수가 COW를 지원

Q. N:1과 1:1 모델의 차이점
N:1 모델은 커널의 입장에서 한 프로세스에 속해있는 N개의 쓰레드를 하나의 프로세스로 본다.
1:1 모델은 프로세스랑 쓰레드 하나하나를 각각의 고유한 태스크로 본다.

스레드/프로세스와 관계 없이 유일한 식별자 = pid
우리가 프로세스 id라고 부르는 것 = tgid
프로세스 내 스레드끼리는 pid가 다 다르지만 tgid는 같습니다

 

Q. p63의 pthread_self가 return하는 값?
A.

생성된 thread 자기자신의 pthread_id return
유저 영역에서 쓰는 고유 스레드 아이디

 

Q. pthread_join이란?
A.

기본적으로 스레드를 생성하면 부모가 먼저 실행될지 자식이 먼저 실행될지가 보장되어있지 않은데 순서를 보장할 필요가 있을 때 쓰는 것으로 알고 있습니다

Q. pthread_create () 함수는 스레드 생성시, 해당 스레드의 스택을 힙에 할당한다는데 정말인가요? 
A.

네 정말이더라구요. 아래 링크 예제 확인해보세요
https://mrsoulware.github.io/multithreading/pthread-memory/

 

 

Q. 왜 TASK_WAKING이 없으면 데드락이 날까요
A.

스레드 간에 락 걸리는 순서가 다르면 데드락이 발생하잖아요
근데 스레드 동기화 거는 순서를 사용자가 잘못한 경우
커널이 마냥 기다릴수없는데
그것을 강제로 깨워주는거 같아요
강제 종료 같은 극단적인 상황인 것 같아요
TASK_WAKING이 커널에 추가된 커밋

 

 

Q. 어떻게 비트맵을 찾는 게 상수시간이 걸리나요?
A.

비트맵의 크기가 상수라서
큐를 나눌 수 있었던 이유는 비트맵이 있기에 

 

 

Q. 중복 인터럽트일 경우
A.

같은 인터럽트는 중첩이 안되나
다른 인터럽트는 동시에 실행이 가능한것으로 알고 있음

 

Q. 커널 빌드할 때 관련 용어 질문
A.

qemu: vmware나 virtual box같이 가상으로 커널을 돌릴 수 있음
yocto: wifi같은 필요 없는 기능 쉽게 지우고 쓸 수 있음 
bitfake: 수정하거나 할 때 많이 씀