[PintOS] 키워드 정리 ( Process, Thread, CPU Scheduling, Semaphore, Mutex, Race Condition, Deadlock, Context Switching, MLFQ )

프로세스(Process)

- 관리하는 최소 단위의 작업, 주기억장치에 등록된 프로그램 즉 실행중인 프로그램

- CPU에 의해 실행되는 시스템 및 사용자 프로그램

- 하나의 응용 프로그램은 여러 개의 프로세스로 이루어질 수 있음

 

스레드(Thread)

- “하나의 프로세스 내에서 동시에 진행되는” 작업 갈래, 흐름의 단위

ex) 하나의 브라우저에서, 파일을 다운받으면서 음악을 듣고 쇼핑을 하고 게임도 하는 것

- 멀티(다중) 스레드 : 스레드가 여러 개 있는 것

- 스레드는 프로세스의 메모리 영역(Code, Data, Heap, Stack) 중 Stack만 할당받아 복사하며, 나머지 Code, Data, Heap은 다른 스레드들과 “공유” 한다.

- 따라서 Stack은 별도이지만 Heap은 공유하기 때문에 서로 다른 스레드에서 읽고 쓸 수 있다.

 

여기서 말하는 스레드는 프로세스 스레드이다. CPU 스레드와는 별개이다.

CPU 스레드는 실제 존재하는 하드웨어적 스레드이다. 현대 CPU는 일반적으로 코어 수 * 2 개수의 스레드를 갖는다.

 

 

 

교착상태(Deadlock)

- 둘 이상의 프로세스가 하나의 자원을 가지기 위해, 서로 상대방이 자원에 접근하는 것을 방해하여 두 프로세스 모두 기능이 중지되어 있는 상태

 

교착상태의 4가지 조건 , 해당 조건이 동시에 모두 만족되어야 교착상태가 발생한다.

상호배제(Mutual Exclusion)

- 한 프로세스가 자원을 사용하고 있을 때, 다른 프로세스들이 사용하지 못하도록 배제시킴

 

점유와 대기(Hold & Wait)

- 프로세스가 자신에게 할당된 자원을 해제하지 않으면서, 다른 자원을 요구할 때 발생

 

비선점형 방식(Non-preemption)

- 비선점 자원들은, 스스로만이 점유한 자원을 해제할 수 있음

- "다른 프로세스가 사용 중인 자원은 강제로 가져올 수 없음"

 

환형 대기(Circular Wait)

- 각 프로세스가 자원을 할당받은 상태에서, 서로의 자원을 요청하는 경우

 

 

 

레이스 컨디션(Race Condition)

- 둘 이상의 프로세스가 공유자원에 동시에 접근할 때, 접근순서에 따라 비정상적인 결과가 발생하는 현상

- 실행되는 프로세스가 임시파일을 만드는 경우, 다른 곳으로 연결된 동일한 이름의 심볼릭 링크 파일을 생성하여 악의적인 행위를 할 수 있음

- 만약 root소유자의 SetUID 비트가 설정된 프로그램이라면, root권한이 탈취당하는 등 큰 피해가 일어날 수 있음

 

심볼릭 링크를 이용한 레이스 컨디션 공격 시나리오

1 > 임시 파일을 생성하고 거기에 내용을 기록하는 기능이 있는 파일 중, 관리자 소유의 파일이면서 SetUID가 설정된 파일을 찾음.

2 > 공격자는 프로그램이 만들 임시 파일과 같은 이름의 파일을 만들어, 프로그램과 경쟁시킴.

3 > 여기서 공격자는 심볼릭 링크 파일을 만듦.

4 > 심볼릭 링크가 가리키는 주소는 passwd파일 등 중요한 파일이 됨.

5 > 공격자의 파일이 경쟁에서 이길 경우, 관리자 권한으로 passwd파일에 내용을 입력하게 됨.

6 > passwd파일에 내용을 입력한다는 것은 관리자 계정도 추가할 수 있다는 의미임으로, 해킹에 성공했다고 볼 수 있음.

 

레이스 컨디션 대응방안

- 프로그램 실행 시 임시 파일을 생성하지 않도록 함

- 사용하고자 하는 파일에 링크가 걸려 있다면 프로그램 실행 중단

- 동일한 이름의 파일이 있다면, 파일 생성/쓰기를 금지함

- SetUID 비트의 사용을 최소화하고, 반드시 사용해야 한다면 관리를 철저히 함

 

 

 

Context(문맥, 상태)

- 특정 프로세스에 대한 정보들의 총집합

 

Context Switching(문맥 교환)

- 멀티프로세스 환경에서, 현재 실행 중인 프로세스에서 다른 프로세스로 제어를 전환하는 과정

- CPU는 여러 프로세스가 동시에 실행되는 것 처럼 보이지만, 실제로는 아주 빠르게 번갈아가며 실행하는 것이기 때문에 Context Switching은 필수적이다.

- Context Switching은 오버헤드를 발생시키기 때문에, 운영체제는 가능한 한 Context Switching의 빈도를 줄여야 하며 이를 위한 최적화 기법을 사용한다.

 

Context Switching 과정

1. 현재 실행 중인 프로세스의 문맥(레지스터 값, PC 등)을 해당 프로세스의 PCB 또는 컨텍스트 저장 영역에 저장해둔다. ( 컨텍스트 저장 영역은 PCB 내에 있거나 외부에 있지만, 일반적으로 PCB 내에 있음 )

2. 실행될 다음 프로세스의 문맥을 해당하는 레지스터에 로드한다. 이 프로세스는 대기 상태에 있던 프로세스일 수도 있고, 새로운 프로세스일 수도 있다.

3. CPU의 제어를 다음 프로세스로 전환한다. 이전에 실행되던 프로세스는 대기 상태 또는 준비 상태로 전환된다.

 

PCB(Process Control Block)

- 운영체제가 각 프로세스에 대한 정보를 저장하는 자료구조

- 각 프로세스는 고유한 PCB를 가지며, 프로세스가 생성될 때 생성되고 프로세스가 종료될 때 소멸된다.

 

PCB에 포함된 대표적인 정보들

1. 프로세스 상태(Process State)

- 현재 프로세스의 실행 상태를 나타냄.

- 준비(Ready), 실행(Running), 대기(Waiting or Blocked) 등등

2. 프로세스 식별자(PID)

- 각 프로세스는 고유한 식별자를 가지고 있음

3. 프로세스 우선순위(Process Priority)

- 프로세스가 CPU를 할당받을 때 사용되는 우선순위

4. 프로세스 상태 정보(Process State Information)

- 프로세스 실행을 제어하기 위한 추가 정보. 프로세스가 대기중인 이벤트/자원에 대한 정보가 포함될 수 있다.

5. 프로세스 레지스터 상태(Process Register State)

- 프로세스 레지스터 값(PC, rsp, 베이스 레지스터 등)을 저장한다. 프로세스가 다시 실행될 때 상태를 복원하기 위해 사용됨

6. 프로세스 스케줄링 정보(Process Scheduling Information)

- 프로세스 스케줄링에 필요한 정보. CPU를 얼마나 점유했었는지, 다음에 실행되어야 하는 시간 등등

 

 

PCB

 

 

 

CPU Scheduling

- 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업

- CPU 이용률을 높게, 처리량도 높게, 응답시간은 짧게, 준비 큐에 있는 프로세스는 적게 설정하는 것을 목표로 한다.

 

선점 스케줄링

- 다른 프로세스가 점유하고 있는 CPU를 뺏을 수 있다.

- 우선순위가 높은 프로세스가 유리하다.

- 처리 시간이 매우 긴 프로세스의 CPU 독점을 막을 수 있어 효율적인 운영이 가능하다.

- 하지만 잦은 Context Switching으로 인해 오버헤드가 커질 수 있다.

- RR(Round-Robin), SRTF(Shortest-Remaining-Time First), MLQ(MultiLevel Queue), MLFQ(MultiLevel Feedback Queue)

 

비선점 스케줄링

- 다른 프로세스가 점유하고 있는 CPU를 뺏을 수 없다

- 모든 프로세스의 요구를 공정히 처리하며, 응답시간 예측이 가능하다.

- 선점형에 비해 Context Switching 빈도가 적어 오버헤드가 적지만, 프로세스 배치에 따라 효율성 차이가 많이 나게 된다.

- 처리 시간이 짧은 작업이 긴 작업을 기다리는 때가 발생할 수 있음

- FIFO(First In First Out), SJF(Shortest Job First, 선점 비선점 모두가능), HRN(Highest Response ratio Time) 스케줄링

 

비선점형 스케줄링의 종류

FCFS(First Come, First Served)

- 가장 먼저 요청한 프로세스에 CPU를 할당해주는 “선착순 방식”

- Convoy Effect(호위 효과)가 발생할 수 있음.

- Convoy Effect : 소수의 긴 처리시간을 갖는 프로세스로 인해 전체 OS가 느려지는 현상

 

SJF(Shortest Job First)

- 처리 시간이 가장 짧은 프로세스를 먼저 실행하는 방식

- 그러나 프로세스의 처리시간을 예측하는 것이 어렵다.

- 또한, 긴 시간을 필요로 하는 프로세스가 무기한으로 대기하게 되는 기아(Starvation)현상이 일어날 수 있다.

 

선점형 스케줄링

SRTF(Shortest Remaining Time First)

- 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식

- 새로운 프로세스가 도착할 때마다 남은 실행 시간을 비교해 CPU를 넘겨준다

- 평균 응답 시간을 최소화하고, 짧은 프로세스를 빠르게 처리할 수 있다.

- 남은 실행 시간이 긴 프로세스가 무기한으로 대기하게 되는 기아(Starvation)현상이 발생할 수 있다.

 

다단계 큐(MultiLevel Queue, MLQ)

- 우선순위에 따라서 준비 큐가 여러개로 나뉘며, 각각의 큐는 각자의 스케줄링 알고리즘을 가지고 있는 방식

- 일반적으로 우선순위가 높은 큐는 선점형, 우선순위가 낮은 큐는 비선점형 스케줄링이 적용된다.

- 프로세스 우선순위에 따라 적절한 큐로 분류되며, 프로세스의 속성이나 요구사항에 따라 결정된다.

- 다양한 종류의 작업이 혼합되어 있는 경우에 유용하다.

- 각각의 큐가 독립적으로 일한다.

 

다단계 피드백 큐(MultiLevel Feedback Queue, MLFQ)

- MLQ와 비슷하게 준비 큐가 여러 개로 나뉘어져 있고, 각각 큐의 우선순위가 다르다.

- 하지만 모든 큐를 하나의 큐처럼 취급한다. 다만 각 프로세스의 처리량에 따라 프로세스는 동적으로 큐를 옮겨 다니거나 우선순위를 바꾼다.

- 처리량이 적으면 우선순위가 높아지고, 처리량이 많으면 우선순위가 낮아지는 식으로.

 

Round Robin(RR)

- 현대 컴퓨터가 사용하는 우선순위 스케줄링

- 각각의 프로세스에 동일한 할당 시간을 부여해서, 해당 시간 동안만 CPU를 이용하게 함

- 할당 시간이 끝나면 강제중단 후 다음 프로세스를 실행하므로 선점형 방식이다.

- 응답 시간을 빠르게 할 수 있다.

- 모든 프로세스가 공정하게 CPU를 사용하며, 특정 프로세스가 독점하는 현상이 발생하지 않는다.

- 할당 시간이 길면 FCFS(선착순)처럼 작동하고, 할당 시간이 짧으면 process sharing 현상이 일어난다.

 

Process Sharing 현상

- RR 스케줄링에서 할당 시간을 매우 짧게 설정할 때 발생하는 현상

- 할당 시간이 매우 짧으면, 마치 여러 프로세스가 동시에 실행되는 것 처럼 보이게 되는 것

- 일반적으로 할당 시간을 짧게 하여 Process Sharing 현상이 일어나게 하는 건 좋지만, 만약 너무너무 짧으면 잦은 Context Switching에 의한 오버헤드가 증가할 수 있으므로 적절한 할당시간을 선택해야 한다.

 

 

 

Busy waiting(spinlock)

- 프로세스나 스레드가 특정 조건이 만족될 때 까지 계속해서 그 조건을 검사하는 것

- 실제로 유의미한 작업을 수행하지 않으면서도 계속해서 작업을 수행하며, 이 과정에서 CPU 자원을 낭비하고 시스템 성능 저하로 이어진다.

- 주로 멀티스레딩 환경에서 공유 자원에 대한 접근을 제어할 때 일어난다. 한 스레드가 공유자원을 사용중일 때 다른 스레드는 이 자원이 사용가능해질 때 까지 계속해서 상태를 확인하는 등

ex) 클라이언트 측 소켓의 연결 요청이 올 때까지 while문을 무한반복하는 서버 측 소켓

 

Busy waiting - 장점

- 구현이 쉽고 간단하여, 멀티스레딩 프로그램에서 자주 사용된다.

- Context Switching이 발생하지 않기 때문에 오버헤드가 낮다.

-> Cotnext Switching이 발생하지 않는 이유 : 자원을 기다리는 스레드가 중지되지 않고 계속해서 자원을 기다리기 때문

 

Busy waiting - 단점

- CPU 자원을 효율적으로 사용하지 못한다.

- 대기 시간이 길어질 수 있다. 다른 스레드가 자원을 오랫동안 사용하고 있을 경우, 대기하는 스레드는 상당한 시간 동안 아무런 작업도 수행하지 못할 수 있다.

 

Busy waiting의 단점을 극복하기 위해, 대기하는 동안 스레드를 잠시 중지시키고 다른 스레드가 CPU를 사용할 수 있도록 할 수 있다.

Semaphore, Mutex, Event 등의 동기화 메커니즘을 이용한다.

단, 다른 CPU가 스레드를 사용할 때 Context Switching이 발생하기 때문에 이에 따른 오버헤드는 발생할 수 있다.

 

Mutex와 Semaphore

- 동기화 메커니즘

- 다른 스레드가 이미 자원을 사용 중일 경우 대기하는 스레드는 계속해서 조건을 검사하는 것이 아닌 잠시 중지되며, CPU를 반납하고 다른 스레드가 CPU를 사용할 수 있게 한다.

- 프로세스들이 공유메모리를 통해 공유된 자원에 동시에 접근하면 “Critical Section“ 문제가 발생할 수 있다.

- 따라서, 한 번에 하나의 프로세스만 데이터에 접근할 수 있도록 제한하는 ”동기화 방식“이 필요하다.

- 대표적인 동기화 도구는 Mutex, Semaphore가 있다.

 

Critical Section(임계 영역)

- 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터에 접근하는 프로그램 코드 블록

- 즉, 여러 프로세스가 동일 자원을 동시에 참조하여 데이터가 오염될 가능성이 있는 영역을 의미한다.

- 개발자는 성능 향상을 위해 임계영역을 최소화하도록 해야 한다.

 

Mutex

- 공유 불가능해야 하는 자원의 동시 사용을 피하기 위해 사용되는 알고리즘

- 임계구역을 가진 스레드들의 실행시간(Running Time)이 겹치지 않고 단독으로 실행되게 한다.

- 한 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제 기법이다. Binary Semaphore와 유사하다.

- 이진수를 사용하며 0과 1, 즉 잠금(Lock)과 해제(Unlock) 상태가 있다. 잠금 상태일 땐 다른 프로세스가 Mutex를 사용하지 못 한다.

 

Semaphore

- 멀티 프로그래밍 환경에서 공유된 자원에 대한 접근을 제한하는 방법

- 사용중인 스레드/프로세스 수를 ”공통으로 관리하는 하나의 값“을 이용해 상호배제를 달성한다.

- 공유 자원에 접근할 수 있는 최대 프로세스 허용치만큼 동시에 접근할 수 있다.

- 각 프로세스는 세마포어 값을 확인/변경 할 수 있다.

- 접근에 실패했다면, 재시도 전에 일정시간 대기해야 한다.

- Binary Semaphore 또는 Counting Semaphore 방식을 사용할 수 있다. 일반적으로 Counting Semaphore 방식이 사용된다.

 

Binary Semaphore

- Binary Semaphore는 이진수를 사용하며 0과 1, 즉 잠금(Lock)과 해제(Unlock) 상태가 있다. 잠금 상태일 땐 다른 프로세스가 세마포어를 사용하지 못 한다. Mutex와 매우 유사하다.

 

Counting Semaphore

- 자원의 수를 나타내거나 허용되는 동시 접근 수를 나타낼 수 있다. 프로세스가 자원을 사용하고 있으면 값을 감소시키고, 해제할 때마다 값을 증가시킨다.

 

Mutex와 Semaphore의 차이점

1. 동기화 대상의 개수

    - Mutex는 동기화 대상이 only 1개일 때 사용

    - Semaphore는 동기화 대상이 1개 이상일 때 사용

2. Semaphore는 Mutex가 될 수 있지만 Mutex는 Semaphore가 될 수 없다.

3. Mutex는 자원 소유 가능 + 책임을 지지만 Semaphore는 자원 소유 불가

    - Mutex는 0과 1뿐이므로 소유할 수 있다.

4. Mutex는 소유하고 있는 스레드만이 Mutex를 해제할 수 있다. Semaphore는 소유하지 않은 스레드가 해제할 수 있다.

5. Semaphore는 시스템 상의 파일로써 존재한다. Mutex는 프로세스의 범위를 가지며, 프로세스 종료 시 자동으로 사라진다.

 

Mutex와 Binary Semaphore의 차이점

Mutex

- 화장실에 들어가려면 ”열쇠“가 필요하며, 그 열쇠는 1개이다. 열쇠의 소유자만이 화장실 문을 열거나 잠글 수 있고, 다른 사람이 화장실에 들어가려면 소유자가 열쇠를 넘겨야 한다.

 

Binary Semaphore

- 화장실 앞에 표지판이 있다. 표지판은 열림/닫힘 둘 중 하나의 상태이며, 누구나 들어갈 수 있고 들어갈 때 ”닫힘“으로 바꾸고 나올 때 ”열림“으로 바꿔야 한다.