Week 7 Multiprocessor Scheudling, Energy-aware/Real-time Scheduling

Week 7 Multiprocessor Scheudling, Energy-aware/Real-time Scheduling

Work conserving: meaning that if one flow is out of packets, the next data flow will take its place.

 

여러 core들이 scheduler의 structure를 share하면 cache coherence를 맞추기 위해 너무 많은 비용이 든다. 심지어 DRAM에서 읽고 쓰는 것 보다 느릴 때도 있다.

 

Amdahl’s Law: runtime >= sequential portion + parallel portion / # CPUs

 

Affinity scheduling: MFQ가 각각의 core마다 존재하고 책임지는 thread들이 core마다 정해져있다. 어느 한 core의 queue의 길이가 평균 queue의 길이보더 충분히 길 때에만 다른 core로 thread를 migrate한다. (linux의 경우 15%)

 

Oblivious scheduling: Co-scheduling과 반대로 thread들이 속한 process를 고려하지 않고 scheduling하는 것. 이 때에는 아래와 같은 문제들이 발생한다.

  • Bulk synchronous delay: 여러 core들이 work를 나누어서 가져가고 각자의 일이 끝난 뒤 sync한다고 할 때 가장 느린 core의 속도에 의해 전체 job의 성능이 결정되는 것
  • Producer-consumer delay: pipeline을 구성하였을 때
  • Critical path delay:
  • Preemption of lock holder: Lock acquirer thread would be delayed

 

Co-scheduling: 같은 program에서 생성된 thread들을 모두 같은 core에서 돌리는 것 (반대로 되어야 하는 것 아닌가????) 같은 process의 thread들을 같은 시간대에 여러 core들에서 돌리는 것. Oblivious scheduling의 문제를 해결하기 위함.

 

Space sharing: 서로 다른 process끼리 time을 잘 나누어서 parallel하게 core를 이용하는 것이 아니라 각자 몇 개 씩의 CPU를 나누어 가져가서 다른 process들의 간섭을 최소화하고 context switching을 줄이는 것.

  • Scheduler activations: kernel이 app에게 app이 사용가능한 core의 갯수를 알려준다. 예를 들어 다른 앱 중 하나가 IO에 block된다면 그것을 app에게 달려주어 thread를 하나 더 만든다던가 할 수 있게 해준다. 어떻게 보면 scheduling의 일부를 app에게 맡기는 것.

 

Energy saving scheduling: 적게 사용하는 core는 speed를 줄이고, 안 쓰는 core는 끄고, …

 

Real-time scheduling:

  • Over-provisioning: real-time task에게 아예 system의 computing power중 일부를 떼어 주는 것.
  • Earliest deadline first:
    이게 deadline을 guarantee해주지는 않음. 예를 들어 deadline이 많이 남았고, computing에 필요한 시간을 얼마 되지 않지만 IO에 많은 시간이 필요한 task를 생각해보자. 이것이 deadline이 얼마 남지 않은 task와 경쟁했을 때 priority가 밀리면 deadline을 지키지 못할 수 있다.
    task를 언제까지 끝내야 하는지, 즉 finishing deadline이 아니라 task를 언제 시작해야 끝낼 수 있는지, 곧 starting deadline을 기준으로 scheduling하면 위와 같은 문제는 피해갈 수 있다.
  • Priority donation: Priority inversion, 즉 a lock holder with low priority가 생길 수 있다.

 

Leave a Reply