Project 1: Threads

Time-sharing system

1. Context Switching

운영체제가 현재 실행 중인 프로세스의 상태를 저장하고 다음으로 실행할 프로세스의 상태를 복원하는 과정

• Task의 대부분 정보는 Register에 저장되고 PCB(Process Control Block)로 관리
  (Pintos 에서는 PCB 대신 running thread 의 stack 에 저장)

2. RR (Round Robin) 스케줄링

프로세스를 ready queue에 도착한 순서대로 스케줄링하는 방식으로,
CPU를 점유할 수 있는 최대 시간(time quantum)을 정해 놓고 해당 시간이 지나면 다음 프로세스를 스케줄링 하는 것이 특징

• 선점형 스케줄링 방식(preemptive)
• 시간 할당량 안에 완료되지 못한 프로세스는 ready queue 맨 뒤에 배치

3. Priority 스케줄링 (Priority Donation)

준비 큐에 프로세스가 도착하면, 도착한 프로세스의 우선순위와 현재 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서를 할당하는 방식

우선순위 스케줄링에서 중요한 사항은 “우선순위 역전(priority inversion)” 이다.

Pintos 과제 설명서 중...

우선순위가 높은 쓰레드 H, 중간 M 그리고 낮은 L가 있다고 생각해보세요.
만약 L이 락을 갖고있어서 H가 L을 기다려야하고 M이 ready list에 있다면, H는 절대로 CPU를 사용하지 못할 것입니다.
왜냐면 낮은 우선순위의 스레드가 CPU시간을 얻지 못할 것이기 때문입니다.
이 문제에 대한 부분적으로 해결하는 방법은 L이 락을 갖는 동안 H가 L에게 우선순위를 기부(donate)한 다음,
L이 잠금을 해제하면 (따라서 H가 획득) 이 기부를 회수하는 것입니다.

• Pintos 에서는 우선순위 기부할 때, multiple donation 상황과 nested donation 상황을 고려해야 한다고 나와있다.

4. Multi-Level Feedback Queue Scheduler (MLFQS)

다단계 큐와 우선순위 조절을 통해 프로세스 스케줄링을 관리하는 스케줄링 알고리즘

1) 여러 개의 큐를 사용하여 프로세스 그룹화

• 각 큐는 서로 다른 우선순위 레벨을 나타내며, 일반적으로 높은/낮은 우선순위의 큐가 있다.
• 높은 우선순위 큐에서 실행되는 프로세스는 선점형 스케줄링을 사용
  낮은 우선순위 큐에서 실행되는 프로세스는 비선점형 스케줄링을 사용

2) 프로세스의 실행 상태에 따라 우선순위를 동적으로 조절

• 실행 중인 프로세스가 CPU 시간을 많이 사용하면 우선순위를 낮추고, 대기 중인 프로세스는 우선순위를 높일 수 있습니다.
  => CPU를 사용한 프로세스는 원래 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.

3) 각 큐마다 시간 할당량 또는 시간 슬라이스 설정

• 시간 할당량은 해당 큐에서 실행되는 프로세스에게 할당된 CPU 시간을 나타냄
• 낮은 우선순위 큐에서는 긴 시간 할당량을 설정하여 비선점형 스케줄링을 시뮬레이트 한다.
  높은 우선순위 큐에서는 짧은 시간 할당량을 설정하여 선점형 스케줄링을 시뮬레이트 한다.

+) 다단계 큐 스케줄링은 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없어 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는데 이러한 문제를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링이다.

---

Synchronization (동기화)

다중 프로세스 또는 다중 스레드 환경에서 공유 자원에 대한 접근 및 조작을 조절하고 조화시키는 프로세스 또는 메커니즘

동기화 목표

: 여러 프로세스 또는 스레드가 공유 자원에 동시에 접근하는 것을 제어하여 데이터 일관성과 정확성을 보존하고 경쟁 조건을 방지

• 경쟁 조건 방지
  : 여러 프로세스/스레드가 동시에 공유 자원을 수정하려고 할 때, 발생할 수 있는 경쟁 조건을 방지하고 데이터의 일관성을 유지

• 데이터 일관성 : 공유 데이터에 대한 일관성을 보장 목적
  + 동시에 여러 스레드 또는 프로세스가 데이터를 수정하는 경우 데이터 일관성이 깨질 때를 방지

• 임계 영역 보호 : 동시에 하나의 스레드만 접근할 수 있는 임계 영역을 정의하고 보호
  + 공유 자원에 대한 안전한 접근을 보장

• 프로세스 간 통신: 다중 프로세스 간에 데이터를 안전하게 교환하고 통신
  ex) Multi-thread 에서 semaphore 기법 사용

동기화 기법

1. 뮤텍스 (Mutex) : 공유 자원에 대한 접근을 동기화하는 데 사용

   • 하나의 스레드 또는 프로세스만 뮤텍스를 소유할 수 있으며, 뮤텍스를 소유한 스레드만이 공유 자원에 접근할 수 있다.

2. 세마포어 (Semaphore) : 특정한 자원에 대한 접근을 제어하는 데 사용

   • 정수 카운터를 가지며, 특정 조건을 충족할 때까지 다른 스레드가 접근을 기다리도록 함

3. 모니터 (Monitor) : 공유 자원을 보호하는 데 사용되는 추상 데이터 유형

   • 모니터 내부에서 공유 자원에 접근하는 메서드는 한 번에 하나의 스레드만 실행됨

4. 조건 변수 (Condition Variable) : 스레드가 특정 조건을 만족할 때까지 대기하도록 하는 데 사용

5. 스핀락 (Spinlock): 다른 스레드가 잠금을 해제할 때까지 반복적으로 잠금을 시도하는 락

• busy wait 방식을 사용하며 Pintos 과제에서 수정해야 하는 부분!