[TIL] - 2023.05.29

📌  공부한 내용

선점형(Preemption)

• 선점형은 하나의 프로세스가 다른 프로세스 대신에 프로세서를 차지할 수 있다는 뜻이다.
• 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어 할 수 있다.

선점형 방식의 스케쥴링에는

• Round Robin : 시간 단위가 설정되어 각 시간동안 프로세스를 실행하고 시간이 지나면 다음 프로세스로 전환되게 한다. 전체적인 응답 속도가 빨라질수도 있으나, 시간 단위마다 프로세스를 전환할 때 문맥 전환에 따른 오버헤드가 발생할 수 있기 때문에 적당한 시간 단위 설정을 해야한다.

비선점형(Non-Preemption)

• 비선점형은 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없다.
• 순서대로 처리되는 공정성이 있고, 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있다.
• 일괄 처리 시스템에 적합하다.
• CPU사용 시간이 긴 하나의 프로세스가 CPU 사용시간이 짧은 여러 프로세스를 오랫동안 대기 시킬 수 있으므로, 처리율이 떨어질 수 있다.

비선점형 방식의 스케쥴링에는

• FIFO : 대기 큐에 먼저 들어온 작업순으로 CPU를 할당
• SJF : 소요시간이 짧은 작업순으로 할당
• HRN : 우선순위와 대기 시간에 따라 작업을 할당

 

세마포어

• 공유자원에 접근할 수 있는 최대 허용치만큼 동시에 사용자 접근을 할 수 있게 하는 기법
• 공유자원에 진입할 수 있는 사용자가 꽉 찬 경우 사용자는 대기상태

• sema_init(struct semaphore *, unsigned value)
  - 세마포어의 value 값 초기화
• sema_down(struct semaphore *)
  - 세마포어의 value가 0일 경우 현재 스레드를 THREAD_BLOCK 상태로 변경 후 schedul() 호출
• sema_up(struct semaphore *sema)
  - 대기 리스트에 스레드가 존재하면 리스트 맨 처음에 위치한 스레드를 THREAD_READY 상태로 변경 후 schedule()호출

 

락(lock)

• 한 프로세스가 임계 영역에 해당하는 코드를 실행하고 있을 때 다른 프로세스가 *임계영역으로 진입하지 못하도록 하는것

*임계영역 : 한 번에 하나의 프로세스만 이용하도록 다른 프로세서의 접근을 제한하는 영역

 

• lock_init(struct lock *lock)
  - lock 구조 초기화
• lock_acquire(struct lock *lock)
  - lock 요청
• lock_release(struct lock *lock)
  - lock을 release

 

조건 변수(condition variable)

• Condition Variable은 특정 조건을 만족하기를 기다리는 변수라는 의미이다. 따라서 이를 이용하여 주로 thread간의 신호 전달을 위해 사용한다. 하나의 thread가 waiting 중이면 조건을 만족한 thread에서 변수를 바꾸고 signaling을 통해 깨우는 방식이다.

• cond_init(struct condition *cond)
  - condition data 초기화
• cond_wait(struct condition *cond, struct lock *lock)
  - 조건 변수가 보내는 신호 기다림
• cond_signal(struct condition *cond, struct lock *lock UNUSED)
  - 조건 변수 안에서 가장 큰 우선순위를 가진 스레드에게 신호를 보냄
• cond-broadcast(struct condition *cond, struct lock *lock)
  - 조건변수 안에서 신호를 기다리는 모든 스레드에게 신호를 보냄

 

Implementation of Priority Scheduling-Synchronization

• 변형할 함수
• 우선순위로 waiters_list에 스레드를 넣기위해 수정할 함수들
  • sema_down(struct semaphore *sema)
  • cond_wait(struct condition *cond, struct lock *lock)
• waiters_list를 우선순위 순으로 정렬
  • waiters_list 에서 thread의 우선순위를 바꾸는 것에 고려되기도 한다.
    • sema_up(struct semaphore *sema)
    • cond_signal(struct condition *cond, struct lock *lock UNUSED)

 

우선순위 역전

• 우선 순위가 높은 스레드가 낮은 우선순위를 가진 스레드를 기다리는 현상

 

위의 예제를 보면 현재 Thread L이 실행되고 있는 중간에 Thread H가 key를 요청하는 경우

이미 L이 실행중이기 때문에 H는 Blocked 상태에 들어가게 되고 그 후에 Thread M이 실행되면서

우선 순위가 높은 H는 실행되지 못하고 우선순위가 낮은 M먼저 실행되는 경우를 inversion이라고 한다.

 

 

 

Priority Donation

• 위의 문제를 해결하기 위해 Donation을 사용한다.
• lock holder에게 우선권을 상속한다.

 

 

 

Nested Donation

 

Multiple Donation

 

Implementation of Priority Donation

• init_thread(struct thread *t, const char *name, int priority)
  - priority donation 초기화
• lock_acquire(struct lock *lock)
  - lock이 이용 불가능하면, lock의 주소 저장
  - 현재 우선순위를 저장하고, 기부받은 스레드를 리스트에 저장
  - 우선순위 기부

 

 

 

✅ 알고리즘

14425	S3	문저열	문자열 집합	solved	…
1543	S4	문자열	문서검색	solved	…
9996	S3	문자열	한국이그리울땐..	solved	…

 

 

---

 

💭  느낀 점 & 배운 점

 

Priority의 개념에 대한 내용은 어느 정도 이해를 했는데, priority donation을 쓰면서 구현을 하는게 쉽지 않아 보인다.

오늘 정리한 내용들과 내일 바꿔야할 코드를 비교해 보고 겪으면서 느끼는 것이 가장 빠를 것으로 보인다.

 

---

 

🔥  내일 공부할 내용

 

priority 수정

 

 

---

 

🗒️  포스팅

 

 

 

 

「 나는 단지 읽고 쓴다고 해서, 심지어 밤새도록 그렇게 됐다고 해서 자네들을 열심히 했다고 평가할 수는 없네. 무엇을 위해 하는지 알지 못하는 이상 성실하다고 말하지 않겠네. (...) 자신의 지배적인 도덕 원칙을 위해 그것을 할 때에야 비로소 자연이 우리에게 준 본성과 끊임없이 조화를 이루고 있다고 말하겠네. 」

-에픽테토스, 대화록, 4.4.41: 43

 

안타깝게도 어수선하다 싶을 정도로 눈코 뜰 새 없이 분주하게 움직이면서 그에 합당한 보상을 받는 경우는 실제로 많지 않다. 게다가 스스로 만족하는 경우도 드물다.

'하고있는 일'로 자신을 평가하지 말고, '왜 하는가?' 그리고 '무엇을 성취하려 하는가?'로 평가하라. 여기에 좋은 답을 할 수 없다면 그 일을 그만두어도 좋다.

시간을 쓰는 만큼 효율이 많이 없는 것은 본인과 동일 한 것 같다. 무엇을 성취하고 싶은가 왜 하는가 내가 바라는 것은 무엇인가?

「 철학은 밖으로 드러나는 것에 관심이 없다. 단지 필요한 것에 주의를 기울이고, 마음에 담아둘 것에만 관심을 둔다.  」

-무소니우스 루푸스, 강의록, 16.75.15-16

 

승려는 승복을 입는다. 가톨릭 사제는 로만 칼라가 달린 신부복을 입는다. 은행원은 값비싼 양복과 서류가방을 들고 다닌다. 하지만 스토아 철학자들은 법복이 없었으며 이들을 규정할 수 있는 일관된 양식도 없었다. 보이는 외양으로 이들을 규정하거나 구별할 수 없었다. 그렇다면 이들을 알아보는 유일한 방법은 무엇이었을까? 오직 품성뿐이다.

말을 하지 않아도 보여주지 않아도 알아볼 수 있도록 철학자가 아니어도 철학자로 착각할 수 있도록 스스로를 가꾸자.

 

 

---