[CS] 운영체제

<프로세스와 스레드의 차이>

프로세스

정의

- 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램. 프로그램의 인스턴스
- 스케쥴링의 대상이 되는 작업(task)이라는 용어와 거의 같은 의미
- 프로그램은 하드디스크 등에 저장되어 있는 실행코드를 뜻하고, 프로세스는 프로그램을 구동하여 메모리 상에서 실행되는 작업 단위

특징

- 프로세스는 각각 독립된 메모리 영역(code, data, stack , heap)을 할당받음
- 프로세스 당 최소 1개의 스레드를 지님
- 각 프로세스는 각기 다른 주소 공간에서 실행되고, 한 프로세스는 다른 프로세스의 존재를 모름
- 프로세스끼리 통신하려면 IPC(Inter process communication)을 사용해야 함(ex. 파이프, 파일, 소켓)

스레드

정의

- 프로세스 내에서 실행되는 흐름의 단위
- 한 프로그램은 일반적으로 하나의 스레드를 가지지만, 둘 이상의 스레드를 동시에 실행할 수 있음(멀티스레딩)
- 스레드는 프로세스 내에서 stack만 따로 할당받고(독립적인 함수 실행 등), code, data, heap 영역은 공유

종류

사용자 레벨 스레드

커널 레벨 스레드

멀티스레드를 사용하는 이유

이점

- 멀티프로세스는 프로세스들이 독립적으로 동작하므로 Context switching에 대한 오버헤드가 크다
- 멀티스레드가 Context switching이 없는 것이 아니라, 한 프로세스 내에서 여러 단위 실행흐름을 가지고 stack을 제외한 자원을 공유하기 때문에 프로세스 전환보다 스레드 전환이 빠름

주의점

- 어떤 스레드가 먼저 실행될지 알 수 없다
- 디버깅이 까다롭다
- 경쟁 조건(race condition)을 고려해야 한다

<Context Switching>

멀티프로세스(or 스레드) 환경에서 context switching은 어쩔 수 없다. 한 번에 한 가지 프로그램만 돌리는 일은 이제 거의 없으니까. CPU내에 존재하는 레지스터들은 현재 실행 중인 프로세스의 관련 데이터들로 채워진다. 프로세스 A가 실행되다가 프로세스 B가 실행되기 위해서, 프로세스B의 데이터를 레지스터에 넣어야 하고 프로세스 A의 데이터는 날려버리는 게 아니라 나중에 이어서 작업하기 위해 메모리에 저장돼야 한다.

실행 중인 프로세스가 레지스터에 저장되고 우선 순위가 밀린 프로세스는 추후에 작업을 이어나가기 위해 레지스터에 있던 정보를 메모리에 저장한다. 이 과정이 context switching이다. 프로세스의 변경 과정인 context switching은 시스템에 적지 않은 부하를 준다. 프로세스 안에 있는 스레드는 함수 호출 등을 위해 스레드별로 스택만 별도로 생성되고 code, data, heap이 공유되기 때문에 context switching으로 인한 오버헤드가 적다.

<가상 메모리>

각 프로그램에 실제 메모리가 아닌 가상 메모리를 할당하는 방식이다. 가상적으로 주어진 주소를 가상 주소 또는 논리 주소라고 하며, 실제 메모리 상에서 유효한 주소를 물리 주소라고 한다. 가상 주소 공간은 메모리 관리 장치(MMU)를 통해 물리 주소로 변환된다. 가상 메모리는 크게 세그멘테이션과 페이징 두 가지가 있다. 실행 중인 프로그램(프로세스)마다 가상 메모리가 만들어진다. 주 메모리(RAM)로 부족한 부분은 보조 메모리(SDD, HDD)를 이용한다.

<페이징, 세그멘테이션, 메모리 풀>

가상 메모리를 이용해 메모리 단편화를 해결하기 위한 기법. 메모리 단편화는 메모리 공간이 작은 조각으로 나뉘어져 사용할 수 있는 총 메모리는 충분하지만 사용할 수 없는 상태. 실행하고자 하는 프로그램 용량이 5gb인데 메모리가 4gb라면 어떻게 해야 하지? 가상 메모리는 각 프로세스당 메인 메모리와 동일한 크기로 하나씩 할당된다. 그 공간은 보조기억장치(HDD, SSD)를 사용한다. 프로세스의 일부만 메모리에 로드하고 나머지는 보조기억장치에 로드한다. 가상 메모리는 CPU의 메모리 관리 장치(MMU)에 의해 물리 주소로 변환되어 사용된다.

내부 단편화(internal fragmentation)

프로세스가 필요한 양보다 더 큰 메모리를 할당해 메모리가 낭비되는 상황. 1mb만 필요한 프로그램인데 4mb가 할당된다면 3mb 만큼 내부 단편화가 발생한 것.

외부 단편화(external fragmentation)

메모리가 할당되고 해제되는 작업이 반복될 때 중간 중간에 생기는 메모리 조각. 프로세스 사이에 존재하는 메모리 조각들이 1mb, 2mb, 4mb, 8mb이라고 할 때 합이 15mb이지만 15mb 크기의 프로그램을 올릴 수 없다.

페이징

외부 단편화를 해결할 수 있다. 가상 메모리를 같은 크기의 블록으로 나눈다. 일정한 크기를 가진 가상 메모리 블록을 페이지라고 한다. 실제 메모리를 페이지와 같은 크기로 나눈 것을 프레임이라고 한다. 이 둘은 프로세스마다 별도로 존재하는 페이지 테이블을 통해 매핑된다. 두 프로세스가 동일하게 0x1000 주소에 접근하는 명령을 실행할 경우 각 페이지 테이블을 통해서, 접근하는 물리 메모리의 실제 주소는 0x3000, 0x4000인 것이다. 외부단편화로 생긴 불연속적인 메모리를 연속된 것처럼 사용할 수 있다.

내부단편화는 해결할 수 없다. 페이지의 크기는 컴퓨터의 구조에 따라 512byte에서 16mb 사이이며 2의 제곱으로 증가한다. 페이지의 크기가 1024byte이고 프로세스가 10500byte일 때 11개의 페이지를 할당하고 마지막 페이지에 남은 764byte는 내부 단편화 영역이 된다. 페이지 크기가 작을수록 내부 단편화 영역이 줄어들지만 페이지 수가 늘어나므로 유지 비용이 늘어난다.

페이지 폴트

프로그램이 접근한 메모리 페이지가 MMU에 의해 프로세스 가상 주소로 맵핑되지 않았을 때 발생하는 예외다. 조금 더 쉽게 표현하자면 실제 메모리에 할당되지 못한 페이지를 참조할 때 생기는 트랩(trap)이다. 페이지는 프로세스에 접근할 수 있지만 페이지 테이블에 맵핑이 추가되도록 요청한다. 실제 페이지가 디스크 같은 저장 장치에서 로드될 수 있도록 요청할 수도 있다.

페이지 폴트를 처리하는 예외 처리 소프트웨어가 운영체제의 일부인 반면, 프로세서의 MMU는 페이지 폴트를 감지한다. 페이지 폴트를 다룰 때, 운영체제는 요구된 페이지가 물리 메모리의 위치에서 접근할 수 있도록 하거나, 불법적인 메모리 접근일 경우에는 프로그램을 종료한다.

폴트라는 단어가 암시하는 것과 다르게, 유효한 페이지 폴트(valid page falut)는 에러가 아니다. 가상 메모리를 활용하는 윈도우, 맥, 리눅스 등의 운영체제에서 프로그램의 메모리 사용량을 증가시키기 위한 필수 사항이라고도 할 수 있다.

마이너

페이지 폴트가 발생했을 때 페이지가 메모리에서 로드됐지만, 메모리에 로드된 것으로 MMU에 표시되지 않으면 마이너 혹은 소프트 페이지 폴트라고 한다. 운영체제의 페이지 폴트 핸들러는 MMU의 페이지가 메모리의 페이지를 가리키게만 하면 된다. 페이지를 메모리로 읽을 필요가 없다. 프로그램이 공유하고 있는 메모리가 이미 다른 프로그램이 요청한 페이지일 경우에 발생한다.

메이저

운영체제가 요청에 따라서 프로그램의 메모리 사용량을 늘이기 위해 사용하는 매커니즘이다. 운영체제는 프로그램이 디스크 사용을 시도하고 페이지 폴트가 발생할 때까지, 디스크에서 프로그램 일부를 로딩하는 것을 늦춘다. 폴트가 발생했을 때 페이지가 메모리에서 로드되지 않았다면 메이저 혹은 하드 페이지 폴트라고 한다. 운영체제의 페이지 폴트 핸들러는 자유 위치를 찾아야 한다: 메모리의 자유 페이지 혹은 논프리 페이지.

후자는 다른 프로세스에서 사용될 수 있다. 이 경우에 운영체제는 해당 페이지의 데이터를 기록하고 (마지막 수정 이후 기록되지 않았다면), 해당 페이지를 프로세스의 메모리에 로드되지 않은 것으로 표시해야 한다. 일단 공간이 확보되면 운영체제는 새로운 페이지의 데이터를 메모리로 읽고 MMU의 해당 위치에 항목을 추가하고 페이지가 로드된 것을 표시할 수 있다. 메이저 폴트는 마이너 폴트보다 비용이 많이 들고 중단된 프로그램 실행에 저장 공간 접근 레이턴시를 추가한다.

세그멘테이션

내부 단편화를 해결할 수 있다. 페이징에서는 가상 메모리를 같은 크기로 분할했지만 세그멘테이션은 서로 크기가 다른 논리 단위인 세그먼트로 분할해 실제 주소와 맵핑된다. 세그먼트를 메모리에 할당하는 건 페이지를 할당하는 것과 동일하다. 세그멘테이션을 위한 테이블은 세그먼트 테이블이라고 한다.

프로세스가 필요한 만큼 할당하므로 내부 단편화는 일어나지 않는다. 물리주소 a는 base[s]+d로 결정된다. 논리 주소(2,100)는 물리 주소 4400번지를 의미한다. 논리 주소(1, 500)은 limit 400을 초과하므로 프로세스가 강제로 종료된다. 메모리가 할당, 해지되는 과정에서 생기는 외부 단편화는 해결할 수 없다.

출처:https://spacefordeveloper.tistory.com/174

결론(페이징, 세그멘테이션)

세그멘테이션은 세그먼트의 크기가 달라 외부 단편화로 인한 메모리 낭비가 크다. 페이징 기법이 많이 사용된다. 내부 단편화로 인한 메모리 낭비는 외부 단편화로 인한 메모리 낭비보다 적다. 두 장점의 합친 방법으로 세그먼트를 페이징 기법으로 나누는 방법도 있다. Paged segmentation. 세그먼트와 페이지과 동시에 존재하기 때문에 주소 변환이 두 번 이뤄지는 것이 단점이다.

메모리 풀

필요한 메모리 공간을 미리 할당받아 놓고 필요할 때만 사용하고 반납하는 방법. 동적으로 메모리 할당과 해제를 반복하지 않으므로 외부 단편화를 해결할 수 있다. 필요한 만큼만 메모리를 할당하기 때문에 내부 단편화 또한 발생하지 않는다. 메모리 풀을 만들어놓고 사용하지 않는 것은 낭비이므로 이에 대한 고민이 필요하다. 메모리의 할당과 해제가 잦은 경우에 효과적이다.

< 교착 상태(Dead lock) >

멀티 프로그래밍 환경에서 여러 스레드(or 프로세스)가 한정된 자원을 사용하기 위해 경쟁할 수밖에 없다. 공유 자원을 사용하기 위해 스레드들이 끝없는 대기 상태에 놓여 있는 것을 말한다. 1번 스레드가 1번 자원을 사용하기 위해 lock1을 획득한 상태에서 2번 자원을 사용하려고 lock2의 unlock을 기다리는 하는 상황에서, 2번 스레드가 1번 스레드보다 2번 자원에 먼저 접근해 lock2를 획득한 상태에서, 1번 자원을 사용하기 위해 lock1의 unlock을 기다리는 상황이 교착 상태다.

필요충분 조건

다음의 네 가지 조건이 모두 충족되어야 교착상태가 발생한다. 교착상태가 발생하려면 다음의 네 가지 조건이 모두 충족되어야 한다. P->Q이면서 Q->P이기 때문에 필요충분 조건이다.

상호배제(Mutual exclusion) - 한 번에 하나의 스레드만 공유자원을 사용할 수 있다.
점유와 대기(Hold and wait) - 최소한 하나의 자원을 점유하고 있으면서 다른 스레드가 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 스레드가 있어야 한다.
비선점(Non-preemption) - 다른 스레드에 할당된 자원은 사용이 끝날 때까지 강제로 가져올 수 없다.
환형 대기(Circular wait) - 여러 스레드가 점유와 요청의 관계가 순환된다.

교착 상태의 해결

회피(Avoidance)

은행원 알고리즘을 통해 시스템이 안전 상태를 유지할 수 있도록 하는 방법. 안전 상태는 교착 상태가 발생할 수 없는 상태를 의미한다. 이 알고리즘에선 불안전 상태를 초래할 위험이 있는 사용자의 요구는 만족될 수 있을 때까지 거절한다.

은행원 알고리즘
정상적으로 작동하기 위한 전제
- 시스템의 프로세스 수가 고정되어 있어야 한다.
- 자원의 수가 고정되어 있어야 한다.
- 각 프로세스가 요구할 자원의 최대 개수를 알아야 한다.
- 각 프로세스는 할당받은 자원을 유한한 시간 안에 반드시 반납해야 한다.
프로세스의 자원 요청이 있을 때마다 요청에 따른 할당이 안전 상태를 유지할 수 있는지 확인한다. 안전 상태의 판단은 모든 프로세스가 정상적으로 종료될 수 있는 길이 적어도 하나 이상 있는 것으로 한다.

OS가 은행원 알고리즘을 적용하기 위한 전제를 현실적으로 어렵고 안전 상태를 유지하기 위한 오버헤드가 커서, 현재는 쓰고 있는 방식이 아니다.

탐지와 회복(Detection and recovery)

교착 상태 프로세스들을 모두 중지하는 방법, 또는 교착 상태가 해결될 때까지 한 프로세스씩 중지한다. 최소 비용으로 프로세스를 중지하는 방법을 찾아야 한다. 교착 상태(deadloc)를 발견하면 이전 상태로 회복하는 기법이다. 데드락에 걸린 프로세스(or 스레드) 중에서 하나를 강제로 중지해 자원을 내려놓게 한다. 데드락이 발생을 검사하는 것, 회복하는 것 모두 큰 오버헤드를 가진다.

예방(Prevention)

데드락이 발생하는 원인이 다양한 만큼 탐지하고 해결하는 방법이 전부 오버헤드가 크다. 그래서 지금의 운영체제는 데드락이 발생했을 때 아무 조치도 취하지 않는다. 운영체제가 프로그램이 다운됐을 때 강제로 프로세스를 죽이거나, 컴퓨터를 재부팅해 문제를 해결하는 것에서 알 수 있다. 때문에 개발자가 데드락을 예방하는 것이 중요하다.

C++11부터 스레드가 자원 사용을 위해 넋 놓고 대기하지 않아도 되는 함수들이 생겼다. mutex::try_lock()은 lock을 얻지 못하면 false를 반환한다. timed_mutex::try_lock_for(duration)은 lock을 획득하기 위해 duration만큼 혹은 lock을 얻을 때까지 대기한다. timed_mutex::try_lock_until(time_limt)은 time_limit 지점까지 혹은 lock을 얻을 때까지 대기한다.

교착 상태의 원인이 되는 조건 중 하나를 부정해 교착 상태 발생을 방지하는 방법. 교착 상태는 확실하게 예방할 수 있지만 특정 스레드가 무한대기할 수 있다.(기아 상태 starvation)

상호배제 부정
배타적으로 사용되어야 하는 자원을 공유하면 문제가 발생할 수 있다.

점유와 대기 부정
프로세스가 실행될 때 필요한 모든 자원을 할당한다. 특정 자원을 요청해야 하는 프로세스가 있을 경우에 무한대기에 빠질 수 있다.

비선점 부정
모든 자원에 대해 선점이 가능하게 되면, 스레드가 연속적인 실행 흐름을 갖지 못해 잦은 컨텍스트 스위칭으로 오버헤드가 발생할 확률이 높아진다.

환형대기 부정
자원에 선형으로 우선 순위를 부여하는 방법이 있다. 우선 순위가 계속 낮은 스레드의 경우 무한 대기를 할 가능성이 생긴다.