[ 운영체제 ] 12. Scheduling ( Multiple - Process / Real - Time CPU )

Thread Scheduling

 

요새는 OS에 의해 실행되는 Kernel - Level Threads 가 메인이다.

User - Level Threads 는 Library로 관리한다.

 

요약:  Kernel Thread = OS가 관리 / User Thread = Library가 관리

 

CPU를 작동시키려면, User Thread는 연관된 Kernel Thread랑 연결되어야 함. ( LWP ) 

 

 

User Thread와 Kernel Thread를 이어주는 역할을 하는 건 Light-weight Process이다.

 

그렇게 이어진 Kernel Thread를 통해 Hardware에 접근한다.

 

 

 

 

Multi- Processor Scheduling

● 상황에 맞게 해야한다.
   ▶ 2개

- 모든 Thread가 공통(하나의) Ready queue에 있을 때          ▶ 동기화 문제 

- 각각의 core( processor ) 에 각각의 thread들이 할당될 때   ▶ 메모리를 많이 먹음 = 멀티프로세서 스케쥴링

 

● Multicore Processor ( = 하나의 Processor 안에 여러 Core가 있다. )

: 빠르고, 전력 소비가 낮다.

 

Scheduling 할 때 변수가 하나 있음.

Thread가 Compute 하려고 하는데, 관련 data들이 정보가 없을 때 메모리에서 가져오고 쓸 수 있을 때까지 기다려야 한다.

 

아래와 같은 형태임

 

 

이걸 그럼 어떻게 해야 효율적으로 쓸 수 있을까?

 

해답 ▶ 한 프로세서에 여러 Thread를 만든다.

 

 

 

교대 근무 하는 느낌이라고 생각하면 될 것 같다.

 

하나의 Thread가 memory stall일 때, 다른 하나로 전환한다.

 

 

 

그래도 그 안에서 Thread들도 스케쥴링을 해야한다.

 

 

이것도 알아는 두기

 

 

여기서부터 내일 아침에 하기

https://will-behappy.tistory.com/22

 

Multiprocessor Schduling 을 할 때 

고려할 사항이 2가지가 있다.

 

● Load Balancing

= 예를 들어 1번 core에는 100개의 task가 있는데

   0번 core에는 4개밖에 없다? 이게 불균등한 거임 , 균등하게 분배해야함

   

 - Push migration

: 바쁜 Core가 가진 Task  → 덜 바쁜 Core 

 - Pull migration

: 덜 바쁜 Core가 바쁜 Core의 Task를 받아오는 거

 

 

이 상황에서

 

 

 

● Processor Affinity

: 유연성 - Process가 하나의 Processor에서 실행되었으면, 거기서 끝장을 봐야함 (끝장을 보는 게 편함)

> 중간에 어떤 Interrupt가 생기거나 Ready queue로 갔다오거나 어떻게 되어도

   다시 원래 실행되던 Processor로 돌아가서 실행되는 게 좋다.

 

목적 : Migration overhead를 줄이기 위해서

 (정보들도 다 그 프로세서,캐시에 남아있으니까)

 

  - Soft affinity

: 원래 실행되던 Processor에서 실행하려고 OS가 노력은 하지만, 

 같은 Processor에서 실행된다는 보장은 할 수 없다.

 

 

  - Hard affinity

: 어느 프로세스 출신인지 설명해서 무조건 거기로 다시 돌아가서 실행된다.

 

 

Real-Time CPU Scheduling

: https://coding-gongbu.tistory.com/27

https://howudong.tistory.com/308

 

 

● 방법

 

- Real-time Operating Systems (RTOS)

- Minimizing Latency

- Dispatch Latency

- Priority-based

- Rate-Monotonic Scheduling

- Earliest-Deadline-First Scheduling

 

 

 

Real-time Operating Systems (RTOS)

: 실시간 OS에는 2가지 종류가 있다.

 

1. Soft real-time System  " 시간 되면 해줄게 "

: 중요한 프로세스가 언제 실행되는 걸로 Scheduling 되는지 보장되지 않는다.

 

단, 중요한 프로세스일수록 상대적으로 먼저 Scheduling되기는 한다.

 

 

2. Hard real-time System   " 내일까지 무조건 다 해서 제출 가능 " (늦으면 부분점수 X)

: Task 가 Deadline 이전에는 된다고 보장해줌.

  + Deadline 넘겨서 겨우 끝낸 Service = No Service

 

 

---

---

Minimizing Latency

 

실시간 시스템의 가장 큰 특징은 Event- Driven System이라는 거다.

Event가 생겼을 때, 시스템은 항상 그에 맞게 반응하고 움직여야 한다.

 

● Event Latency

: 이벤트가 발생한 후, 그와 관련된 Service ( Task ) 가 수행되기 시작할 때까지 걸리는 시간을 말한다.

 

이 시간에 따라 실시간 시스템 성능에 영향을 준다.

https://howudong.tistory.com/308

 

1. Interrupt Latency

: [ CPU에 Interrupt발생 ▶ Interrupt Service Routine (ISR) 시작 ]

사이에 걸리는 시간

 

 

 

 

2. Dispatch Latency

: [ 하나의 프로세스 멈추고 ▶ 다음 프로세스 시작 ]

사이에 걸리는 시간

 

- 선점형 커널을 사용하는 것이 Dispatch Latency 를 줄이는데 효과적이다.

  ▶ 프로세스가 커널모드에서 수행되는 동안 선점되는 걸 허용

 

위 사진에서 Conflicts 단에는 2가지 요소가 있다. 

( Conflict = 그냥 다 뺏어오는 부분 ( 프로세스 사용 순서 , 자원 )) 

 

1. Kernel에서 동작하고있는 프로세스가 있으면 자리 뺏음

 

2. 높은 우선순위의 프로세스가 필요한 자원 A를 쓰고있는 
    낮은 우선순위의 프로세스가 그 자원을 Release한다.

 

---

---

RTOS 특징 )

Priority-based

RTOS 에서 가장 중요한 특징은

Real-Time Process에 즉각적인 응답이다.

 

이 때문에

● 스케쥴러는 우선순위 기반 선점형 알고리즘 을 지원하며

● OS는 중요도에 따라 우선순위를 부여하고 ,

   CPU를 사용하고 있더라도 우선순위가 더 높은 프로세스에 의해 선점될 수 있음

 

● 위와 같은 선점형 우선순위 스케줄러는   Soft - realtime 기능을 보장한다. 

 

   ▶ 웬만하면 Hard - realtime인 게 좋음

   ▶ 그럼 Deaeline 내에 수행되는 게 보장되어야 한다.

   결론 : 추가적인 Scheduling 이 필요하다.

 

 

● 주어진 작업을 하는 데 걸리는 시간             = t

● 주어진 작업을 마무리 해야하는 기한          = d

● 주어진 작업을 하기 위해 할당 받은 시간    = p

 

https://coding-gongbu.tistory.com/28

 

 

우선순위는 DeadLine 으로 정해지기 때문에 Process는 Deadline을 Scheduler에게 알려야 한다.

 

● RTOS 특징 )

Admission - Control Algorithm이 필요하다.

 

새로 들어오려고 하는 Process에 대해서 , 들어왔을 때 DeadLine을 지킬 수 있는지 고려하여

Admit / Reject 하는 알고리즘  

 
- Admits the process

: Process가 새로 들어와도 마감기한 지킬 수 있을 때  ▶ Admit

 

 

- Rejects the request

: 얘가 들어왔을 때 마감기한 내에 완료하는 걸 보장하지 못할 때  ▶ Reject

 

 

 

 

---

---

Rate-Monotonic Scheduling

● 특징 

Optimal 한 Schduling

 

- 이 알고리즘으로 스케줄링 불가 = 정적 우선순위를 사용하는 어떤 알고리즘도 스케줄링 X

 

● 우선순위 : 1 / Period 

 = Period가 짧은 놈을 우선순위로

 = CPU를 더 자주 사용해야하는 애들에게 우선순위

 

 그렇게 나온 놈의 Period로 돌아감.

 

 

● 한계 

▶ CPU 활용의 한계가 있다. 따라서 항상 CPU 자원 사용을 최대화 할 수 있는 건 아니다.

 

https://coding-gongbu.tistory.com/28

 

 

 

P1 은 5시까지 일을 끝내서 일어나야하고, 

P2 는 8시까지 일을 끝내서 일어나야 함.   

 

책상은 한 명만 쓸 수 있다 하자.

 

일단 1/Period 으로 P1이 우선순위를 가져간다. = P1 의 Period로 감  ( 5시에 불 꺼짐 + P1이 불을 킬 수 있음  )
+ 먼저 끝내야 하는 사람 = P1 = P1 먼저 시작

 

 

1. P1 시작 > 2.5시에 끝내고 나옴   

// 현재 시간 2.5 = P1 Deadline pass

   - P1이 5시까지 쓰려고 했는데 다 끝내서 P2가 옴.

 

2. P2 가 앉아서 하다가 2.5시간치 했을 때 불이 꺼짐 ( P2 한 시간치 남음 )
      // 현재 시간 5 

   - P1이 와서 불켜줘야함

 

3. P1이 불키러 온 김에 2.5시간 공부 조지고 감

      // 현재 시간 7.5

    - 남은 2.5시간으로 할 거 끝내려고 P2가 바로 옴

    - 1시간만에 끝냄 = // 현재 시간 8.5 = DeadLine 넘음

    - 1.5시간 비어있음

 

 

 

---

---

Earliest-Deadline-First Scheduling

● 우선순위

- 마감기한(Dead line) 이 얼마 안 남은 프로세스가 Higher prioirity.

 

-  CPU는 하나 , 프로세스는 2개(이상)

    = 충전기 하나 , 필요한 사람 2명(이상) 이라고 생각하셈

 

먼저 꺼지는 놈 먼저 충전

 

특징)

1. 프로세스가 CPU를 쓸 수 있는 상태가 될 때 , 자신의 마감시간을 OS에 알려야 한다.

2. 우선순위가 매번 비교할 때마다 다르다.

3. 프로레스들이 주기적으로 실행될 필요도 없다.

 

CPU 를 쓸 수 있을 때 = { 다른 프로세스 작업이 끝났을 때 + 시작할 때 + 각각 Period }

 

[ 시작 / T = 0 ]

- 우선순위 : p1 마감기한 = 50 / p2 마감기한 = 80

   ▶  p1 먼저 실행

 

 

[ p1 끝 / T = 25 ]

- 우선순위 : p1 마감기한 = 100( 한 번 했으니까 )  / p2 마감기한 = 80

   ▶  p2 먼저 실행 

   ▶ time =50일 때, p1이 다시 가져올까 하는데

     p2 마감기한 = 80 , p1 마감기한 = 100

     =그냥 p2가 계속 씀

 

 

[ p2 끝 / T = 60 ]

- 방금 P2가 실행할 때 P1이 가져오려고 했는데 양보해줬으니 P1이 씀 ( 그냥 사용 연장 개념 )

   ▶  p1 실행

   ▶  p2 period 인데, 마감기한 100 vs 160이라서 p1계속 씀

 

 

[ p1 끝  / T = 85 ]

 방금 P1할 때 P2가 가져오려고 했는데 양보해줬으니 P2줌 

   ▶  P2 실행

   ▶  T = 100 에서 p1 period 인데, 마감기한 150 vs 160이라서 p1한테 넘겨줌

 

 

[ p1 끝  / T = 125]

- 우선순위 : p1 마감기한 = 200( 한 번 또 했으니까 )  / p2 마감기한 = 160

   ▶  P2 실행 ...이런 식으로 감

 

 

주로 [ 시작했을 때 ] + [ 다른 프로세스가 끝났을 때 ] + [ 매 Period ] 마다 확인하면 되는 것 같다.

 

이론상으로는 Optimal하다.

1. 각 프로세스의 마감시간에 끝내기 성공

2. CPU 이용률 Maximization 성공

 

 

● 한계

▶ Context switching + Interrupt Handling 때문에 Utilization 100%는 불가능

 

 

---

---

Proportional Share Scheduling

작동 방식)

1. Schduler가 Application들에게 시간을 T만큼 할당

2. 각 Application이 N개의 Task를 받음

3. 그럼 그 Application은 N/T를 할당받을 수 있음.

 

 

작동 방식)

admission-control policy 가 꼭 필요함

 : 나눠줄 수 있는 양을 요구하는 Application에게 나눠줄 수 있음

   아니면 거절

 

 

(출처)

한동대학교 고윤민교수님 - 운영체제

 

 

(참고)

https://coding-gongbu.tistory.com/29

 

https://howudong.tistory.com/308