Multiprocessor, Multicore and Real-Time Scheduling

Ова претставува еден краток курс на темата „Multiprocessor, Multicore and Real-Time Scheduling“, во склоп на предметот Учење на далечина.

Курсот се состои од неколку секции, во кои се дадени подетални информации поврзани со самата тема. На крајот, поставени се прашања за проверка на вашето знаење, според материјалот кој што е презентиран.

Со среќа!

Multiprocessor and multicore scheduling

Intro

Кога компјутерскиот систем содржи повеќе од еден процесор, во дизајнот на распоредувачките функции се појавуваат неколку нови проблеми.

Повеќепроцесорските системи може да се класифицираат на следниов начин:

  • Loosely coupled or distributed multiprocessor or cluster
    • се состои од колекција на релативно автономни системи, каде што секој процесор има своја главна меморија и И/О канали
  • Functionally specialized processors
    • пример за процесор со специјална функција се И/О процесорите. Ваквите процесори се контролирани од страна на главниот (master) процесор кој ги обезбедува соодветнити сервиси
  • Tightly coupled multiprocessor
    • се содржи од множество на процесори кои делат заедничка главна меморија и се под интегрирана контрола на оперативниот систем

Granularity   1/2

Категории на паралелизам во зависност од степенот на грануларност:

  • Fine-Grained Parallelism
  • Medium-Grained Parallelism
  • Coarse and Very Coarse-Grained Parallelism
  • Independent Parallelism

Granularity   2/2

  • Fine-Grained Parallelism
    • овој тип на паралелизам претставува многу покомплексна употреба на паралелизмот отколку онаа кај користење на нитките. Претставува специјализирана и фрагментирана област, на која може да се пристапи на повеќе начини
  • Medium-Grained Parallelism
    • една апликација може да биде ефективно имплементирана како колекција од нитки во еден процес. Во овој случај, програмерите мора експлицитно да го потенцираат потенцијалниот паралелизам на апликацијата. Поради тоа што различните нитки на апликацијата вршат меѓусебна интеракција доста често, донесувањето одлуки во врска со некоја нитка може да влијае на перформансите на целата апликација
  • Coarse and Very Coarse-Grained Parallelism
    • со овие паралелизми, постои синхронизација помеѓу процесите, на многу погорно ниво. Множество од конкурентни процеси се извршуваат на мултипрограмиран унипроцесори може да биде подржано на мултипроцесор со многу мала, или пак никаква промена на корисничкиот софтвер
  • Independent Parallelism
    • со овој паралелизам, не постои експлицитна синхронизација помеѓу процесите. Секој од нив, претставува посебна, независна активност или апликација. Секој корисник извршува конкретна апликација. Просечното време на одговор е релативно пократко.

Thread Scheduling   1/3

Една апликација може да биде имплементирана како множество од нитки кои соработуваат и се извршуваат конкурентно во истиот адресен простор.

Кај апликациите кои бараат значителна интеракција помеѓу нитките, малите разлики во менаџирање и распределување на нитките, може да имаат големо влијание врз перформансите. Разликуваме четири посебни пристапи на овој проблем:

  • Load Sharing
  • Gang Scheduling
  • Dedicated Processor Assignment
  • Dynamic Scheduling

Thread Scheduling   2/3

  • Load Sharing: процесите не се доделуваат на некој конкретен процесор. Разликуваме три верзии:
    • First-come-first-serve (FCFS):   кога ќе пристигне некоја задача, секоја нова нитка се додава последователно на крај од редицата. Кога процесорот ќе биде слободен, ја зима следната нитка, која се извршува се додека не предизвика блокада или пак биде комплетирана
    • Smallest number of threads first:   редицата е организирана како приоритетна редица, каде што највисок приоритет за извршување им се дава на нитките од задачите со најмал број на нераспределени нитки. Оние со ист приоритет, се извршуваат според времето кога пристигнале, односно се извршуваат оние кои пристигнале први
    • Preemptive smallest number of threads first:   највисок приоритет се дава на задачите со најмал број на нераспределени нитки. Доколку пристигне задача со помал број на нитки од онаа која се извршува во моментот, ќе ги превземе нитките од таа задача


  • Dedicated Processor Assignment:   пристап кој е обратен од Load Sharing и обезбедува имплицитно доделување дефинирано според нитките кои се доделени на процесорите. Кога една апликација ќе биде стартувана, секоја од нејзините нитки се доделува на некој процесор кој е посветен исклучиво на таа нитка, се додека апликацијата не биде комплетирана

Thread Scheduling   3/3

  • Gang Scheduling:   множество од поврзани нитки кое е планирано да работи на множество од процеси во исто време. Доколку имаме група од процеси кои се поврзани или координирани на некој начин, блокирачката синхронизација може да биде редуцирана, а перформансите зголемени. Еден од највпечатливите начини на кој Gang Scheduling ги подобрува перформансите на некоја апликација, е со тоа што го минимизира бројот на префрлување од еден на друг процес.


  • Dynamic Scheduling:   бројот на нитки во еден процес може да биде променет во самиот тек на извршување. Оперативниот систем е одговорен за поделбата на процесорот и неговите ресурси помеѓу разните задачи. Секоја задача ги користи доделените ресурси во својата партиција за да изврши некое подмножество од задачи преку мапирање на задачите со нитките.

Multicore Thread Scheduling

Најкористените оперативни системи, како Windows и Linux, воглавно процесите ги третираат во повеќејадрени системи на ист принцип како повеќепроцесорските системи. Се трудат да ги балансираат процесорите и нивните ресурси, за процесите да бидат дистрибуирани и да се извршуваат рамномерно кај сите процесори. Со зголемување на бројот на јадра по чип, се зголемува и потребата да се минимизира пристапот до off-chip меморијата, во споредба со потребата за максимизирање на процесорската искористеност.

Постојат два различни аспекти за делење на кеш меморијата:

  • Кооперативна поделба на ресурсите:   повеќе нитки пристапуваат до исто множество на мемориски локации од главната меморија
  • Утврдување на ресурсите:   во овој случај нитките треба да се изборат за локациите на кеш меморијата. Целта е да се алоцираат нитките до јадрата на начин со кој се максимизира ефективноста на заедничката кеш меморија, а со тоа да се минимизира потребата од пристап до off-chip меморијата

Real-Time Scheduling

Background

Пресметувањето во реално време, станува се позначајно како дисциплина кај компјутерските науки. Една од најважните нешта кај ваквите системи, кои вршат пресметки во реално време, е самиот оперативен систем. Работата на системот не зависи само од логичките резултати при пресметките, туку и од времето во кое што тие биле продуцирани.

Генерално, кај системите кои вршат пресметки во реално време (Real-Time Systems - RTS), дел од задачите се извршуваат во „real-time“ и имаат одреден степен на итност, или приоритет при извршувањето. 

Тие може да се поделат на:

  • Hard real-time tasks
    • овие задачи мораат да го запазат својот зададен рок за извршување, во спротивно може да предизвикаат фатална грешка на системот, или некаква штета
  • Soft real-time tasks
    • за овие задачи исто така е поставен рок за нивно извршување, кој е пожелно да се исполни, но не задолжителен. Доколку се надмине рокот, истата треба да се изврши и комплетира

Characteristics of Real-Time Operating Systems 1/3

Real-Time оперативните системи се карактеризираат со нивните барања во пет различни области:

  • Детерминација
  • Респонзивност
  • Корисничка контрола
  • Релијабилност
  • Fail-Soft операција

Characteristics of Real-Time Operating Systems   2/3

  • Детерминација:   еден систем е детерминистички кога ги извршува операциите во фиксно, однапред дефинирано време и временски интервали. Кај ваквите оперативни системи, процесорските барања за сервиси, се диктираат од страна на некој надворешен настан и тајминг. Степенот до кој оперативниот систем може детерминистички да ги задоволи таквите барања зависи најпрвин од брзината со која може да одговори на прекините, а потоа и од тоа дали системот има доволно капацитет за да се справи со сите барања во дадено време.


  • Респонзивност:   со оваа карактеристика, се обрнува внимание на тоа колку време после приемот на барањето, му е потребно на оперативниот систем за да го обработи прекинот. Оваа карактеристика заедно со детерминизмот, го сочинуваат потребното време за реагирање на надворешни настани. Времето за одговор е од круцијално значење за real-time системите, бидејќи тие мора да ги исполнат временските рокови кои им се поставени од страна на индивидуалци, други уреди и податочните текови.

Characteristics of Real-Time Operating Systems   3/3

  • Корисничка контрола:   кај real-time оперативните системи, корисничката контрола е многу поразгранета. Од големо значење е на корисникот да му се овозможи fine-grained контрола над приоритетот на операциите. Корисникот треба да биде способен да направи разлика помеѓу hard и soft операции и да ги специфицира релативните приоритети во секоја класа. Системите исто така треба да му овозможат на корисникот да избере кои карактеристики ќе се користат кај процесите, кои алгоритми да се користат, кој е нивниот приоритет и слично


  • Релијабилност:   оваа карактеристика обично е многу поважна за real-time системите отколку за non-real-time системите. Доколку настане некаква фатална процесорска грешка кај real-time системите, последиците може да бидат катастрофални, почнувајќи од финансиски загуби, па се до огромни хардверски штети. Воглавно, тоа е поради тоа што контролира и реагира на настани во реално време.

Real-Time Scheduling

Real-Time Scheduling е една од најактивните области кои се истражуваат во компјутерските науки. Во оваа област разликуваме четири класи на алгоритми:

  • Static table-driven approaches:   овие алгоритми извршуваат статична анализа на распоредот по кој ќе бидат извршувани операциите. Како резултат на оваа анализа, е распоред кој одлучува за време на извршувањето, кога една операција ќе започне. Оваа класа на алгоритми се користат за операции кои се периодични
  • Static priority-driven preemptive approaches:   се прави статична анализа, но не се прави никаков распоред. Поточно, анализата се користи за да им се зададе приоритет на операциите, за да може да се искористи традиционалниот распоред
  • Dynamic planning-based approaches:   изводливоста се одлучува за време на извршувањето, наместо пред самиот старт на извршување
  • Dynamic best effort approaches:   не се прави никаква анализа изводливоста. Системот пробува да ги исполни сите рокови кои му се зададени, а истовремено ги абортира сите почнати процеси, чии рокови се веќе надминати

Deadline Scheduling

Real-Time оперативните системи, најчесто се дизајнирани со цел да ги започнат real-time задачите што е можно побрзо, што значи дека мора многу брзо да се справуваат со прекините и издавањето, стартувањето на задачите. Со цел сето ова да се одвива подобро и поефикасно, се користат некои дополнителни информации за секоја задача, како што се:

  • Ready time:   време во кое задачата е подготвена за извршување
  • Starting deadline:   време до кое задачата мора да започне
  • Completion deadline:   време до кое задачата мора да биде завршена. Real-Time системите обично имаат или starting или completion deadline, но не и двете
  • Processing time:   време кое е потребно за да се изврши задачата до самиот крај, односно да се комплетира
  • Resource requirements:   множество од ресурси кои и се потребни на задачата за време на нејзиното извршување
  • Priority:   ја мери релативната важност на задачата
  • Subtask structure:   една задача може да биде поделена во задолжителна подзадача и опционална подзадача. Само задолжителните подзадачи поседуваат рок кој мора да се испочитува

Priority Inversion

Приоритетна инверзија е феномен кој може да се случи во било која шема за доделување која е базирана според приоритетот, но е важна во контекст на real-time scheduling. Најчесто се случува, кога поради одредени услови, операциите со висок приоритет се поттиснати и мора да чекаат да се изврши некоја операција со низок приоритет. 

Пример за таков случај е кога некоја задача со низок приоритет ќе заклучи некој ресурс, а задача со висок приоритет ќе проба да го заклучи истиот тој ресурс и да го искористи за себе. Тогаш задачата со повисок приоритет ќе биде блокирана се додека потребниот ресурс не е достапен.


Постои и така наречена unbound приоритетна инверзија, каде времетраењето на инверзијата не зависи само од времето потребно за справување со заедничкиот ресурс, туку и од непревдливите акции на другите задачи.

Се среќаваме и со приоритетно наследување, каде задача со низок приоритет го наследува приоритетот од било која задача со повисок приоритет, кој чека на заедничкиот ресурс. Промената на приоритетот настанува веднаш штом задачата со повисок приоритет ќе се блокира поради ресурсот, а завршува кога ресурсот ќе биде ослободен.

Кај приоритетниот „таван“ (priority ceiling), секој ресурс е асоциран со одреден приоритет. Приоритетот доделен на ресурсите е едно ниво повисоко од највисокиот приоритет на неговиот корисник. На секоја задача што ќе пристапи до тој ресурс, ќе и биде доделен тој приоритет. Откако ќе заврши со користење на ресурсот, приоритетот се враќа во нормала.

Test your knowledge!

1. Како може да се класифицираат повеќепроцесорските системи?

  • Tightly coupled multiprocessor
  • Softly coupled multiprocessor
  • Functionally specialized processors
  • Loosely coupled or distributed multiprocessor, or cluster

2. Колку категории на паралелизам разликуваме, во зависност од степенот на грануларност?

  • 1
  • 3
  • 5
  • 7

3. Колку техники разликуваме кај thread scheduling?

  • 1
  • 2
  • 3
  • 4

4. Кој од следниве поими НЕ претставува една од  техниките на thread scheduling?

  • Load Sharing
  • Relative Scheduling
  • Gang Scheduling
  • Dynamic Scheduling

5. Кај Dynamic Scheduling бројот на нитки во процесот може да се промени во текот на извршување.

  • Да
  • Не

6. Кои од следниве поими преставуваат верзии на Load Sharing?

  • Last-in-first-out
  • First-come-first-serve
  • Smallest number of threads first
  • Biggest number of threads first

7. Кај first-come-first-serve, секоја нова нитка:

  • се додава на почетокот од редицата
  • се додава во средина на редицата
  • се додава на крајот од редицата
  • се додава на некоја рандом позиција

8. Кај real-time задачите ги разликуваме следните типови:

  • raw
  • soft
  • medium
  • hard

9. Што од следново е точно?

  • hard real-time задачите имаат рок кој задолжително мора да се запази
  • hard real-time задачите имаат рок кој е пожелно да се запази, но не е задолжителен
  • soft real-time задачите имаат рок кој задолжително мора да се запази
  • soft real-time задачите имаат рок кој е пожелно да се запази, но не е задолжителен

10. Кои од следниве карактеристики се препознатливи за real-time оперативните системи?

  • детерминизам
  • респонзивност
  • робустност
  • квалитативност

11. Колку класи на алгоритми разликуваме кај Real-Time Scheduling?

  • 2
  • 3
  • 4
  • 5

12. Кои дополнителни информации за задачите може да бидат корисни во Real-Time Scheduling?

  • ready time
  • starting deadline
  • priority
  • size

13. Во случај на приоритетна инверзија, доколку задачата со помал приоритет завземала (заклучила) некој ресурс, тогаш задача со поголем приоритет која има потреба од истиот ресурс:

  • веднаш го превзема ресурсот
  • чека задачата со помал приоритет да го ослободи ресурсот
  • ќе биде ставена во блокирана состојба
  • ќе побара друг ресурс

14. Со каков вид на инверзија се среќаваме?

  • селективна инверзија
  • unbound приоритетна инверзија
  • приоритетна инверзија
  • примарна инверзија

15. Покрај приоритетната инверзија, се среќаваме и со:

  • приоритетно наследување
  • приоритетна делба
  • приоритетен „таван“
  • приоритетна маса