Algoritmus LOOK - LOOK algorithm
 | Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)
|
KOUKNI SE je disk plánování algoritmus používaný k určení pořadí, ve kterém jsou zpracovávány požadavky na čtení a zápis nového disku.
Popis
The KOUKNI SE algoritmus je stejný jako SKENOVAT Algoritmus v tom, že také ctí požadavky na oba směry směru diskové hlavy, ale tento algoritmus "se dívá" dopředu, aby zjistil, zda existují nějaké požadavky čekající ve směru pohybu hlavy. Pokud ve směru pohybu hlavy nejsou vyřízeny žádné požadavky, bude průchod hlavy disku obrácen do opačného směru a lze vyhovět požadavkům v opačném směru. V rozvrhu LOOK jde rameno pouze po konečné požadavky v každém směru a poté obrátí směr, aniž by šlo až na konec. Zvažte příklad, Vzhledem k disku s 200 válci (0-199) předpokládejme, že máme 8 nevyřízených požadavků: 98, 183, 37, 122, 14, 124, 65, 67 a že čtecí / zapisovací hlava je aktuálně na válci 53 Aby bylo možné tyto požadavky splnit, bude se rameno nejprve pohybovat v rostoucím pořadí a poté po dosažení konce se bude pohybovat v sestupném pořadí. Pořadí, ve kterém se provede, je tedy 65, 67, 98, 122, 124, 183, 37, 14.[1]
LOOK se chová téměř stejně Nejkratší čas hledání jako první (SSTF), ale vyhýbá se problému hladovění SSTF. Je to proto, že LOOK je předpjatý proti oblasti, kterou nedávno prošel, a silně upřednostňuje stopy seskupené na nejvzdálenějších a nejvnitřnějších okrajích talíře. LOOK je také zaujatý směrem k nově příchozím pracovním místům (v průměru).
Varianty
- C-LOOK (Kruhový VZHLED)
- Jednou z variant LOOK je C-LOOK. Snahou je odstranit odchylku v LOOK pro shluky stop na okrajích talíře. C-LOOK v zásadě skenuje pouze jedním směrem. Buď zametáte zevnitř ven, nebo zvenčí dovnitř. Když dojdete na konec, otočíte hlavu úplně zpět na začátek. To ve skutečnosti využívá výhody skutečnosti, že mnoho disků může pohybovat čtecí / zapisovací hlavou při vysokých rychlostech, pokud se pohybuje po velkém počtu stop (např. Doba hledání od poslední stopy ke stopě 0 je menší, než by se dalo očekávat, a obvykle značně méně než čas, který by trvalo hledání jedné stopy po druhé). Obrovský skok z jednoho koncového požadavku na druhý se nepovažuje za pohyb hlavy, protože válce jsou považovány za kruhový seznam.
- N-LOOK a F-LOOK
- N a F LOOK byly navrženy tak, aby kompenzovaly zaujatost LOOK vůči nedávným úlohám. Oba algoritmy rozdělují frontu požadavků na menší dílčí fronty a zpracovávají dílčí fronty v pořadí (nejstarší první). N-LOOK se nazývá proto, že fronta požadavků je rozdělena na N dílčí fronty. F-LOOK je zjednodušení, kde existují pouze 2 fronty, ale používají se způsobem s dvojitým pufrem. Zatímco F-LOOK zpracovává jednu frontu, všechny nové požadavky přejdou do druhé. K vysvětlení těchto algoritmů použijeme příklad disku s 200 stopami a čtecí / zapisovací hlava začíná na stopě 100. Fronta požadavků v pořadí obsahuje požadavky na stopy: 55, 58, 18, 90, 160, 38 předpokládáme, že fronta požadavků je rozdělena na dvě, přičemž nejstarší obsahuje požadavky na stopy: 55, 58, 18, 90. V tomto případě se N-LOOK a F-LOOK chovají stejně. Všimněte si také, že v této konfiguraci nezáleží na tom, ve kterém směru se hlava pohybovala, všechny požadované stopy jsou menší než 100, takže se bude pohybovat pouze ve směru klesajících stop.
- I přes průměrný počet projetých tras je v nejhorším případě stejný jako LOOK, N a F LOOK jsou v jistém smyslu spravedlivější než obyčejný starý LOOK. Systém podfondů omezuje maximální latenci, kterou může proces očekávat mezi požadavkem a jeho obsluhou (na rozdíl od SSTF, který může procesy hladovět po libovolnou dobu).
- S-LOOK
- Algoritmus Shortest LOOK (S-LOOK) je rozšíření algoritmu LOOK pro zpracování případů, kdy je hlava disku umístěna mezi požadavky na vzdáleném konci. Algoritmus je navržen tak, aby rozhodoval o tom, který směr by měl být obsluhován jako první, místo aby pokračoval v hledání stejným směrem před přijetím nových požadavků. Protože doba hledání je přímo úměrná vzdálenosti hledání, naším cílem je minimalizovat vzdálenost hledání, a tedy zkrátit dobu hledání.
Výkon
LOOK má o něco lepší průměrné časy vyhledávání než SCAN. C-LOOK má mírně nižší rozptyl v době hledání než LOOK, protože nejhorší doba hledání je téměř snížena na polovinu.
Viz také
Mezi další varianty patří:
- SKENOVAT - Výtahový algoritmus
- FSCAN
- N-Step-SCAN