Алгоритъм „първи дошъл първи обслужен“ (fcfs)
Най-простият алгоритъм, с който трябваше да свикнем, е алгоритъмътFirst Come First Served (FCFS)- първи дошъл, първи обслужен. Всички заявки са организирани в FIFO опашка и се обслужват на принципа първи дошъл, първи обслужен. Алгоритъмът е лесен за изпълнение, но може да доведе до доста дълго общо време за обслужване на заявката. Помислете за пример. Да предположим, че имаме следната опашка от заявки на диск от 100 цилиндъра (от 0 до 99): 23, 67, 55, 14, 31, 7, 84, 10 и главите първоначално са на 63-ия цилиндър. Тогава позицията на главите ще се промени, както следва:
63236755143178410
и общите глави ще движат 329 цилиндъра. Неефективността на алгоритъма е добре илюстрирана от последните две движения от цилиндър 7 през целия диск до цилиндър 84 и след това отново през целия диск до цилиндър 10. Една проста промяна в реда на последните две движения (71084) би намалила значително общото време за обслужване на заявката. Така че нека преминем към друг алгоритъм.
Алгоритъм за кратко време за първо търсене (sstf).
Както видяхме, съвсем разумно е да се приоритизират заявки, за които данните се намират в близост до текущата позиция на главите и едва след това на далечни. АлгоритъмътПърво за кратко време за търсене (SSTF)- първо за кратко време за търсене - идва от тази позиция. За следваща услуга ще изберем заявка, за която данните са най-близки до текущата позиция на магнитните глави. Естествено, при наличието на равноотдалечени заявки, решението за избор между тях може да се вземе въз основа на различни съображения, например чрез алгоритъмаFCFS. За предишния пример алгоритъмът ще даде следната последователност от позиции на главата:
63675531231410784
и всичкоглавите ще се преместят на 141 цилиндъра. Обърнете внимание, че нашият алгоритъм е подобен на алгоритъма за планиране на процеса SJF, ако изберем разстоянието между текущата позиция на главата и позицията, необходима за удовлетворяване на заявката, като аналог на оценката на времето на следващия процес на взрив на процесора. И точно като SJF алгоритъма, той може да доведе до дълго забавяне на изпълнението на всяка заявка. Трябва да се помни, че заявките в опашката могат да се появят по всяко време. Ако имаме всички заявки, с изключение на една, постоянно групирани в области с голям брой цилиндри, тогава тази заявка може да бъде в опашката за неопределено време.
Точният SJF алгоритъм беше оптимален за даден набор от процеси с дадени времена на избухване на процесора. Очевидно алгоритъмътSSTFне е оптимален. Ако изместим обслужването на заявката на 67-ия цилиндър между заявките на 7-ия и 84-ия цилиндър, ще намалим общото време за обслужване. Това наблюдение ни води до идеята за цяло семейство от други алгоритми - сканиращи алгоритми.
Алгоритми за сканиране (сканиране, c-scan, look, c-look)
В най-простия алгоритъм за сканиране,SCAN, главите постоянно се движат от единия край на диска до другия, обслужвайки всички заявки, които срещат по пътя си. При достигане на другия ръб посоката на движение се променя и всичко се повтаря отново. Нека в предишния пример, в началния момент от време, главите се движат в посока на намаляване на броя на цилиндрите. След това ще получим реда на заявките за обслужване, надникнал в края на предишния раздел. Последователността на движение на главата е следната:
635531231410706784
и общите глави ще движат 147 цилиндъра.
Ако знаем, че сме служили на последното преминаванезаявка в посоката на движение на главите, тогава не можем да стигнем до ръба на диска, но веднага променяме посоката на движение на обратното:
63553123141076784
и общите глави ще движат 133 цилиндъра. Получената модификация на алгоритъмаSCANсе наричаLOOK.
63553123141070998467
По аналогия с алгоритъмаLOOKза алгоритъмаSCAN, можем да предложим алгоритъмаC-LOOKза алгоритъмаC-SCAN:
63553123141078467
Има и други разновидности на алгоритми за сканиране и много различни алгоритми, но ние ще приключим тук, защото беше казано: "И пак казвам: никой няма да прегърне необятността."