[pintos] 1주차 - 키워드 정리 (2) : Process/Thread, DeadLock, 프로세스 상태/CPU Scheduling

https://whatissoimportantyou.tistory.com/58

VSCode에서 PintOS 네이티브 디버깅하기: 완벽 가이드

오늘 키워드 다 정리하고 내일 코드 볼 때 이거 해봐야지

 

Process와 Thread

코어타임에 팀원분이 프로세스와 스레드의 차이에 있어서 가장 중요한 부분을 짚어주셨다.

OS 책을 읽을 때 이해되지 않은 채로 넘어갔던 문장인데 알고 보니 스케줄링을 구현할 때 굉장히 중요한 개념이었다.

정리하고 넘어가보자.

🤔 프로세스와 달리 스레드의 문맥 교환에서는 주소공간을 그대로 사용한다?

문맥 교환이란 cpu가 어떤 실행흐름(프로세스나 스레드)에서 다른 실행흐름으로 전환하는 과정이다.

이 때 다음과 같은 정보를 저장하고 복원한다.

- 레지스터 값 (pc, sp(스택포인터))

- 페이지 테이블 (주소 공간 정보)

- 커널 스택

프로세스 끼리는 주소 공간이 다르기 때문에, 스위치할 때 페이지 테이블이 교체되어야 한다.

반면 스레드는 같은 프로세스 안의 실행 흐름이므로, 같은 주소 공간 안에서 스택 포인터만 바뀌고 페이지 테이블 교체가 없다.

스레드 간의 문맥 교환이 더 빠르기 때문에 병렬 작업 시 비용이 더 적다.

대신 스레드 간에 같은 주소 공간(데이터, 힙)에 있는 공유 자원을 사용할 때 race condition이 발생할 수 있다.

따라서 semaphore, mutext를 적용해야 하는 비용이 생긴다.

-> pintos에서 스케줄러와 같은 문맥 교환 함수를 구현할 때 스레드 간 문맥 교환이면 스택 포인터만 바꾸면 된다.

 

* 페이지 테이블은 프로세스 마다 가지고 있으니 어차피 문맥 교환할 때 교체되어야 하는 거 아닌가? 

-> cpu는 여러 프로세스가 사용하는 가상 주소 공간을 하나의 MMU(memory management unit)를 통해 처리해야 한다. 

     프로세스는 스레드와 달리 문맥 교환할 때 cpu의 컨텍스트 스위칭 뿐만 아니라 MMU가 사용하는 페이지 테이블도 함께 교체되어야 함

 

Deadlock

데드락은 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상이다.

p1이 r1을 사용 중이고 p2가 r2를 사용 중이다. 그리고 p1은 r2를 기다리고 p2는 r1을 기다리고 있다.

출처: KOCW 운영체제 강의

같은 예시를 semaphore를 통해 설명하면 위와 같다.

p0, p1이 semaphore 변수가 각각 1인 S, Q라는 자원을 하나씩 차지했다고 하자.

다음 작업을 위해 p0은 Q, p1은 S가 필요하다면 서로 점유한 자원을 요구하고 있으므로 데드락 상태에 빠진다.

 

🤔 Deadlock과 Starvation의 차이?

데드락은 프로세스나 절대 일어나지 않는 이벤트나 자원을 위해 무한히 대기하는 것이다.

즉 프로세스가 block 상태- 특정 이벤트나 자원을 기다리는 상태- 에서 무한히 대기한다.

기아 상태는 프로세스가 cpu의 할당을 무한히 대기하는 것이다.

즉 프로세스가 ready 상태에서 무한히 대기한다. 기아 상태는 cpu 스케줄링과 밀접하게 관련 있다.

레디 큐에 들어 있는 ready 상태의 프로세스들은 스케줄링 방식에 따라 우선순위가 정해지는데, 이 때 우선순위가 계속해서 뒤로 밀리게 되면 해당 프로세스는 기아 상태이다. 

 

 

deadlock에 대해서 잘 정리된 블로그

https://velog.io/@ken1204/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-8-1%EA%B0%95-Deadlock%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C

 

CPU Scheduling

먼저 프로세스의 상태에 대해 정리해보면 다음과 같다.

• 생성(create/new) 
  • 새로운 프로세스가 생성된 상태
  • 이 상태에서 프로세스는 아직 큐에 들어가지 않았으며, 필요한 초기화 작업이 진행 중임
• 준비(ready)
  • 프로세스가 cpu를 사용하고 있지는 않지만 언제든지 사용할 수 있는 상태
  • 이들 중 하나가 스케줄러에 의해 선택되어 실행됨
• 실행(running)
  • 프로세스가 cpu를 차지하여 명령어를 실행 중인 상태
• 대기(waiting)
  • 프로세스가 어떤 조건이 충족되기를 기다리고 있는 상태
  • 보통 I/O작업이 완료되기를 기다리는 경우 이 상태로 전환된다.
• 종료(terminated)
  • 프로세스가 모든 작업을 완료하고 종료된 상태
  • 운영체제는 이 상태에서 프로세스의 자원을 해제하고 프로세스를 시스템에서 제거함

* cpu burst time : cpu 할당 후 입출력을 요구할 때까지의 시간

 

상태 전이와 관련된 이벤트

 

https://kyoulho.tistory.com/252

 

1. 선점형 스케줄링

• 하나의 프로세스가 cpu를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 cpu를 점유하는 스케줄링 방식
• 비교적 응답이 빠르다
• 처리 시간을 예측하기 힘들다
• 우선순위가 높은 프로세스들이 계속 들어오는 경우 오버헤드 발생
• Real-time, Deadline 응답환경 등 우선순위가 높은 프로세스를 빠르게 처리해야 할 경우 유용

(1) Round Robin

cpu 점유 시간을 균등하게 분배

프로세스가 할당된 시간 내에 작업을 완료하지 못하면 ready queue의 가장 뒤로 보내지고 cpu는 대기 중인 다음 프로세스를 실행

 

(2) SRTF(Shortest Remaining Time First)

작업 시간이 가장 짧은 프로세스 먼저 수행

ready queue에 남은 처리 시간이 더 짧다고 판단되는 프로세스가 들어오면 그 프로세스가 cpu를 먼저 선점

 

 

2. 비선점형 스케줄링

• 하나의 프로세스가 cpu를 할당 받으면 작업 종료 후 cpu를 반환할 때까지 다른 프로세스가 cpu를 점유할 수 없는 스케줄링 방식
• 모든 프로세스의 요구를 공정하게 처리
• 작업 시간이 짧은 프로세스가 길게 대기해야 할 수 있음

(1) FCFS(First Come First Served)

프로세스가 대기 큐에 도착한 순서에 따라 cpu 할당

queue와 동일한 FIFO 알고리즘

 

 

(2) SJF(Shortest Job First)

그 당시 작업 시간이 가장 짧은 프로세스가 실행 종료할 때까지 cpu 점유

cpu 요구 시간이 긴 프로세스와 짧은 프로세스 간의 불평등이 심해 starvation 발생 가능성

 

Multilevel Queue Scheduling

처음 들어온 프로세스는 항상 우선순위가 높은 큐로 먼저 들어감

프로세스가 타임 퀀텀(8) 내에 실행된다면 빨리 빠져나가고

타임 퀀텀(8)보다 길다면 다음 우선순위 큐로 밀려 다시 더 긴 타임 퀀텀을 부여받음

빨리 끝나는 프로세스는 높은 우선순위를 받을 수 있고, 더 쓰고싶은데 할당 받은 시간이 끝난 프로세스는 다음 우선순위 큐로 가서 기다려야 하는 방식

Round Robin만으로는 실행 시간이 짧은 프로세스에게 우선순위를 줄 수 없기 때문에 쓰이는 방식

이 방식은 cpu 사용 시간을 측정하지 않아도 된다는 장점이 있음. 먼저 들어온 프로세스는 무조건 우선 순위이고 점점 할당 시간을 길게 주면서 우선순위에서 밀려나는 방식이기 때문

 

 

ref:

https://velog.io/@yslys/%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98FCFS-RR-SJF-SRT-Priority-MLQ-MFQ