개발하는데 다 이유가 있겠지

PintOS 궁금증

세마포어의 wait_list와 조건(Condition)의 wait_list의 차이	- Semaphore는 critical section에 들어가기 위해 대기하는 스레드들이 있는 리스트입니다. Semaphore를 사용하는 스레드는 먼저 세마포어를 획득하기 위해 대기 리스트에 등록되고, 세마포어를 획득한 후에는 다른 스레드가 이용할 수 있도록 세마포어를 해제합니다. -조건(Condition)은 특정 조건이 충족되지 않아 대기하는 스레드들이 있는 리스트입니다. 조건(Condition)를 사용하는 스레드는 조건이 충족되지 않으면 대기 리스트에 등록되고, 조건이 충족되면 대기를 해제하여 작업을 수행하게 됩니다. **세마포어의 wait_list는 critical section에 들어가기 위해 대기하는 스레드들의 리스트이고, 조건 변수의 wait_list는 특정 조건을 충족하지 못한 스레드들의 리스트입니다. (참고) 모니터 - lock에 대한 동시적으로 접근을 방지 -> 다시 정리...
idle thread(유휴 스레드)	ready_list에 대기중인 쓰레드들이 없을경우 실행되는 쓰레드
blocked thread(잠들어있는 쓰레드)	sleep_list에서 지정된 local_tick에 wake_up을 대기하고 있는 쓰레드
ready_thread(실행 준비된 쓰레드)	wake_up해서 ready_list에서 CPU만 할당받으면 실행되는 쓰레드
running_thread(실행중인 쓰레드)	현재 CPU를 할당받아서 실행중인 쓰레드

---

Priority Scheduling

주요 목표	- Pintos는 기본적으로 FIFO(선입선출) 스케줄링을 사용합니다. - Pintos 스케줄러를 우선순위(priority) 스케줄링으로 수정하십시오.     - 준비 목록(ready list)을 스레드 우선순위에 따라 정렬합니다.     - 동기화 원시(primitives)인 세마포어(semaphore)와 조건 변수(condition variable)의 대기 목록(wait list)을 우선순위에 따라 정렬합니다.     - 선점(preemption)을 구현하십시오.     - 선점 시점: 타이머 인터럽트가 호출될 때마다가 아니라 스레드가 준비 목록에 추가될 때입니다
변경할 파일	- threads/thread.* - threads/synch.*
고려 사항	준비 리스트에서 스레드를 선택할 때, 가장 높은 우선순위를 가진 스레드를 선택합니다. 선점 - 새로운 스레드를 준비 리스트에 삽입할 때, 현재 실행 중인 스레드와 우선순위를 비교합니다. - 새로 삽입된 스레드의 우선순위가 현재 실행 중인 스레드보다 높으면, 새로 삽입된 스레드를 스케줄링합니다. 락: 세마포어, 조건 변수 - 락(또는 조건 변수)을 기다리는 스레드 집합에서 스레드를 선택할 때, 가장 높은 우선순위를 가진 스레드를 선택합니다.

---

CPU Scheduling 알고리즘

프로세스 스케줄링 목적	- CPU가 끊임없이 일할 수 있도록 스케줄을 짜주는 것 - 한정된 자원으로 높은 성능을 이끌어내기 위해서 CPU가 놀지 않도록 적절한 타이밍에 계속 일을 줌
FCFS (First Come First Served)	- 선입선출 알고리즘은 비선점 스케줄링 기법 - 먼저 도착한 순서에 따라 처리함(반응형보다는 배치형(일괄처리) 시스템에 적합) - 비선점 스케줄링을 사용해 오버헤드가 낮음 - 긴 수행시간을 가진 프로세스가 자원을 점유하는 경우, 다른 프로세스들이 대기시간을 가짐(Convey Effect)
	공식 -대기시간: 프로세스가 생성되어 작업을 마치고 종료될 때까지 큐에서 기다리는 시간  (공식: 왕복 시간 - 수행 시간) -소요시간: 프로세스가 생성되어 작업을 마치고 종료될 때까지의 걸리는 시간   (공식: 종료 시간 - 도착한 시간) -정규화(Nomalized): 일의 효율성 측정, 총 소요된 시간   (공식: 수행시간 / 대기시간)
SJF (Shortest Job First)	- 최소작업 우선 알고리즘은 각 작업의 프로세서 실행 시간을 이용해 실행 시간이 가장 짧은 작업에 할당하는 방법 - 항상 실행 시간이 짧은 작업을 신속하게 실행하므로 평균 대기 시간이 가장 짧음 - 기본적으로 실행 시간이 가장 짧은 작업이 실행되므로 불공정한 작업 - 실행 시간을 예측하기 어려워 실용적이 못함 - 비선점 SJF 스케줄링     반환 시간 = 실행 순서에 따른 실행 시간 + 대기 시간     대기 시간 = 반환 시간 - 실행 시간 - 선점 SJF 스케줄링     반환 시간 = 종료까지 걸린시간 + 시작 시간(중복 시간)     대기 시간 = 반환 시간 - 시작 시간(중복 시간) || - 실행시간
SRTF (Shortest Remaining Time First)	- 프로세스를 비교해 최소 잔여시간이 적은 프로세스를 먼저 실행하는 알고리즘 - 공정성, 응답시간 측면에서 문제가 있음
Round Robin	- Ready Queue에 있는 모든 프로세스들에게 공정하게 실행시간을 배분해주는 알고리즘 - SRTF에서 실행시간이 많이 남은 프로세스가 CPU를 계속 할당받지 못하는 공평성 문제를 해결(응답시간 대폭 개선) - 새로 Ready 상태가 되거나 실행시간을 마친 프로세스는 Ready Queue의 맨 뒤로 감 - 반환시간 관점으로 최악의 알고리즘 - 잦은 Context Switch는 성능 저하를 발생시킴
Multilevel Queue Scheduling	- Ready Queue를 여러 개로 분할하고 각각의 Queue에 우선순위를 정하고, 각각의 프로세스는 해당 프로세스의 우선 순위에 따라 각각의 Queue에 배치되고, Queue간 경쟁을 통해 하나의 Queue가 CPU를 점유 - Foreground Queue(Round Robin 방식) : CPU burst가 짧은 Queue로서 우선순위가 높음 - Background Queue(FCFS 방식) : batch 등 긴 시간을 필요로 하는 작업
Multi-level Feedback Queue Scheduler (MLFQS)	- 여러 레벨의 큐 : MLFQS는 다양한 우선순위 레벨을 가진 여러 개의 큐를 사용. 각 큐는 특정 우선순위를 가진 프로세스들을 담고 있으며, 우선순위가 높은 큐의 프로세스가 먼저 CPU를 할당 받음 - 동적 우선순위 조정 : 프로세스가 시스템에서 실행되면서, 그 특성(예: CPU 사용량, 대기 시간)에 따라 우선순위가 동적으로 조정. 이를 통해, CPU를 많이 사용하는 프로세스의 우선순위를 낮추고 I/O 작업 등으로 대기하는 프로세스 우선순위를 높여 공정성 유지 - 우선순위 상속 : 프로세스가 다른 프로세스를 기다릴 때(예: 락을 기다림), 대기 중인 프로세스의 우선순위를 기다리고 있는 프로세스에게 "상속"하여, 우선순위가 높은 프로세스가 낮은 프로세스 때문에 오랫동안 대기하는 것을 방지
	장점 - 공정성: 모든 프로세스가 공평하게 CPU 시간을 할당 받을 수 있도록 함 - 응답성: I/O 작업이 많은 프로세스나 사용자 상호작용이 필요한 프로세스에 빠른 응답 제공 - 자원 활용 최적화: 프로세스의 실행 특성에 따라 우선순위를 조정함으로써, CPU와 같은 시스템 자원 활용도 높임
	4BSD 스케줄러 - 4BSD(Berkeley Software Distribution) 스케줄러는 UNIX 시스템에서 사용되는 스케줄링 알고리즘 - 스케줄러의 주요 목표는 시스템의 반응성과 효율성을 최적화하는 것 - 4BSD 스케줄러는 CPU 사용 패턴(예: CPU 집중적인 작업 vs I/O 집중적인 작업)에 따라 프로세스의 우선순위를 동적으로 조정 - 인터랙티브 프로세스 우선순위 향상 : 사용자와의 상호작용이 필요한 프로세스(예: 텍스트 편집기, 그래픽 인터페이스)는 빠른 반응 시간이 중요. 4BSD 스케줄러는 이러한 프로세스가 자주 CPU를 양보하는 경향을 감지하고, 그들의 우선순위를 높여 반응성 개선 - 백그라운드 작업 우선순위 감소 : CPU 사용량이 매우 높은 프로세스(예: 컴파일러, 대규모 계산 프로그램)는 시스템의 전반적인 반응성에 영향을 줄 수 있음. 이러한 프로세스의 우선순위는 시간이 지남에 따라 점차 감소하여, 인터랙티브 프로세스에게 CPU 사용 기회를 더 많이 제공
	nice - UNIX 및 UNIX 계열 운영 체제에서 프로세스의 우선순위를 조정하는 데 사용되는 값 - nice 값은 사용자가 프로세스의 기본 우선순위를 조정할 수 있게 해주며, 이 값은 프로세스의 우선순위에 직접적인 영향을 미침 - nice 값의 범위 : 일반적으로 nice 값은 -20에서 19 사이. 낮은 값(예: -20)은 높은 우선순위를 의미하고, 높은 값(예: 19)은 낮은 우선순위를 의미. 기본 값은 0 - nice 값의 사용 : 사용자는 nice 명령어를 사용하여 실행 중이거나 새로 시작하는 프로세스의 nice 값을 설정할 수 있음. nice 값을 높이면(양수 방향으로), 프로세스는 더 낮은 우선순위를 갖게 되어 CPU 접근이 더 적게 됨. 반대로, nice 값을 낮추면(음수 방향으로), 프로세스의 우선순위가 높아져 CPU를 더 많이 사용할 수 있게 됨 - nice 값은 시스템의 부하가 높을 때 특정 프로세스의 우선순위를 조정하거나, 백그라운드 작업을 실행할 때 유용하게 사용 - 예를 들어, 시스템의 자원을 많이 사용하는 대규모 계산 작업을 백그라운드에서 실행할 때, nice 값을 높여 다른 사용자 또는 인터랙티브 작업에 더 많은 CPU 시간을 할당할 수 있음
비선점 스케줄링	- 프로세스가 자원을 할당받으면 스스로 자원을 반납하거나, 작업이 끝날때까지 프로세스 전환이 일어나지 않음 - 우선순위 높은 스케줄링이 와도 작업 순서가 바뀌지 않고, 수행시간이 긴 프로세스가 있으면 모든 작업 처리 시간에 영향을 줌

---

쓰레드의 상태 정의

Thread Blocked (블록 상태)	설명: 쓰레드가 실행을 중지하고 특정 조건이 충족될 때까지 기다리고 있는 상태입니다. 원인: I/O 작업 완료 대기, 자원 접근을 위한 락(lock) 대기 등. 특징: 블록된 쓰레드는 CPU를 사용하지 않으며, 조건이 충족되면 다시 ready 상태로 전환됩니다.
Thread Running (실행 상태)	설명: 쓰레드가 현재 CPU에서 실행 중인 상태입니다. 특징: 한 번에 하나의 CPU 코어에서는 하나의 쓰레드만 실행될 수 있습니다. 실행 중인 쓰레드는 CPU 시간을 소모하며, 실제로 프로그램의 명령어를 수행합니다.
Thread Ready (준비 상태)	설명: 쓰레드가 실행을 위해 준비된 상태입니다. 실행할 준비가 되었지만, 현재 CPU가 다른 쓰레드를 실행하고 있기 때문에 대기 중입니다. 특징: 다중 스레딩 환경에서는 여러 쓰레드가 ready 상태에서 대기할 수 있으며, 스케줄러가 CPU 시간을 할당할 때까지 기다립니다.
Thread Dying (종료 상태)	설명: 쓰레드가 종료 중인 상태입니다. 일반적으로 종료 절차를 밟고 있는 중입니다. 특징: 종료 중인 쓰레드는 더 이상 새로운 작업을 받지 않으며, 리소스를 해제하고, 종료 절차를 완료하면 완전히 소멸됩니다.

느낀점

 

우선순위를 변경해주는 1번 문제(priority_change)를 팀원들과 9시간 동안 코드를 두들기면서 느낀 것은 개념도 개념대로 중요한 것 같은데, 코치님께서 말씀해주신대로 코드에 뛰어드는게 답인 것 같다..

내일은 우선순위 기부에 관한 내용에 들어가야 하는데 개념이 명확하게 잡히지 않아서 걱정이 되지만, 어떻게든 코드에 뛰어들겠지 하고 할 생각이다.

1.5주간 첫번째 주제인 쓰레드 동기화 관련 문제를 해결해봤는데, MLFQS 문제는 한 개도 해결하지 못했다.

조금 현타가 많이 왔는데, 다음 주제에서는 공부 방식과 접근법을 다르게 바꿔봐야 할 것 같다.

이번 주가 PintOS에서 가장 쉬운 주라는게 믿기질 않아요..