Multilevel feedback queue
La planificació mitjançant cues multinivell és un algorisme de planificació de processos en un sistema operatiu. El seu objectiu és diferenciar entre diferents tipus de treballs, per això divideixen la cua de processos preparats en diverses cues, una per cada tipus de treball, i no permeten el moviment dels processos entre les diferents cues.[1]
Els algoritmes de cues multinivell realimentades es basen en els algoritmes de cues multinivell, però permeten el moviment dels treballs d'unes cues a altres.[1]
Les sigles MLQ i MLFQ són els acrònims anglesos de multi level queues (cues multinivell) i multi level feedback queues (cues multinivell realimentades).
Planificació MLQ: cues multinivell. modifica
Aquest algorisme de planificació classifica els processos en diferents grups, de manera que podem assignar a diferents cues amb diferent planificació per gestionar-los de la manera que realment necessiten.[2][3][4]
Els processos s'assignen permanentment a una cua del sistema, generalment en funció d'alguna propietat del procés, per exemple la mida de memòria, la prioritat del procés o el tipus de procés.[4]
Per exemple, tenim el grup de processos foreground (interactius) i background (batch), que necessiten diferents temps de resposta.[2] Cadascun d'ells serà gestionat en una cua diferent amb un algoritme de planificació diferent, per exemple la cua de processos foreground amb Round Robin, i la de processos background amb FCFS.[2][4]
A més ha d'existir un criteri de planificació entre les cues. Pot ser de prioritat fixa amb requisa o sense requisa, o de prioritat variable amb requisa o sense requisa.
En els algorismes FCFS, SJF i aquells que utilitzen prioritats, un procés pot romandre en el processador fins que realitzi una entrada / sortida o fins que acabi. Si no acaba o no fa cap entrada / sortida, el procés podria arribar a monopolitzar la CPU.
Per evitar aquest monopoli, el mecanisme de requisa permet que un procés pugui ser expulsat del processador.[1]
El criteri de planificació sol implementar com a prioritat fixa amb expropiació[2][4] que consisteix que no és possible iniciar un procés si hi ha algun altre en una cua més prioritària. I si un procés s'està executant i arriba un altre procés més prioritari que ell, abandonarà el processador i l'hi cedirà al procés amb major prioritat.
Les característiques d'aquesta política de planificació són:[2]
- És apropiativa, és a dir si arriba un procés amb més prioritat que el que s'està executant podrà expulsar i apropiar-se del processador.
- Cada cua tindrà una prioritat interna, d'acord amb el seu algorisme de planificació. I quan un procés entri a la cua, automàticament es calcularà la prioritat interna. Això no afectarà el funcionament global de les cues múltiples.
- El procés que s'executarà serà el de major prioritat. I si n'hi ha diversos, es triarà el major segons les normes de les polítiques de gestió corresponents.
Si apliquem la planificació apropiativa de prioritat fixa l'exemple anterior, la cua de processos foreground serà més prioritària que la de processos background.[2] Mentre hi hagi processos a la cua de foreground, els de la cua de background no es podran executar.
Una altra possibilitat seria fer l'expulsió amb intervals periòdics o quantum, repartint el temps entre les cues.[4][5]
En resum, aquest algorisme es pot definir pels següents paràmetres:
- El nombre de cues.
- L'algorisme de planificació de cada cua.
- L'algorisme de planificació entre les diferents cues.
- El mètode usat per determinar en quina cua s'introduirà un procés quan calgui donar-li servei.
Planificació MLFQ: cues multinivell amb realimentació modifica
L'algorisme de cues multinivell presenta baixa càrrega de planificació però és poc flexible.[4]
Mitjançant la planificació amb cues multinivell realimentades, un procés es pot moure d'una cua a una altra depenent del seu comportament en temps d'execució.[6][4]
En les cues multinivell realimentades se separen els processos en grups però depenent de les característiques del seu ràfega de CPU. Els processos amb ràfegues curtes aniran a una cua més prioritària de processos preparats que els processos amb ràfegues llargues.[4]
El funcionament d'aquest algorisme consisteix a executar els processos de la cua de prioritat més alta, a continuació es passen a executar els processos de la cua i així successivament. Amb aquesta distribució, els processos amb ràfegues curtes s'executaran de forma ràpida sense necessitat d'arribar molt lluny en la jerarquia de cues de llestos. Mentre que els processos amb ràfegues llargues aniran degradant gradualment.[5][6]
Per gestionar els processos de la manera més justa, és necessari conèixer la seva longitud, si estan limitats per entrada/sortida o pel processador, la memòria que necessitaran, etc.[2]
La forma òptima d'atendre'ls és:
- Establir una preferència per als treballs més curts i penalitzar els que s'han estat executant durant més temps.[5]
- Afavorir els treballs limitats per entrada/sortida, per mantenir els recursos ocupats i deixar el processador lliure el major temps possible.[2]
En general, a un procés se li concedeix un temps T de permanència en una cua, quan el supera, passarà a la cua immediatament inferior amb menor prioritat, és a dir, es disminuirà la seva prioritat en una unitat. L'elecció del valor que se li donarà en el moment T varia molt d'un sistema a un altre, depèn del nombre de processos existents, del tipus de processos i del nombre de cues.
Es poden utilitzar mecanismes d'envelliment per evitar el bloqueig indefinit d'un procés, aquests mecanismes consisteixen a incrementar la prioritat dels processos que estiguin massa temps esperant en una cua de prioritat baixa, per passar-los a una cua de prioritat més alta i que es puguin executar abans.[4]
En resum, aquest algorisme es pot definir pels següents paràmetres:[4][2][1]
- El nombre de cues.
- L'algorisme de planificació de cada cua.
- L'algorisme de planificació entre les diferents cues.
- El mètode usat per determinar quan passar un procés a una cua de prioritat més alta.
- El mètode usat per determinar quan passar un procés a una cua de prioritat més baixa.
- El mètode usat per determinar en quina cua s'introduirà un procés quan calgui donar-li servei.
Referències modifica
- ↑ 1,0 1,1 1,2 1,3 Sánchez, Sebastià A. Sistemes Operatius. Servei de Publicacions de UAH, 2005.
- ↑ 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8 Pérez-Campanero, Joan A. Conceptes De Sistemes Operatius. Universitat Pontifícia de Comillas, 2002.
- ↑ Aranda, Joaquin. Sistemes Operatius, Teoria i problemes. Sanz i Torres, 2002.
- ↑ 4,00 4,01 4,02 4,03 4,04 4,05 4,06 4,07 4,08 4,09 Silberschatz, Abraham. Fonaments de Sistemes Operatius. 7 ª. McGraw Hill, 2006.
- ↑ 5,0 5,1 5,2 Stallings, William. Sistemes Operatius, Aspectes interns i principis de disseny. 5a. Prentice Hall, 2005.
- ↑ 6,0 6,1 Milenkovic, Milan. Sistemes Operatius, conceptes i disseny. 2. McGraw-Hill, 1989.
Bibliografia complementària modifica
Tanenbaum, Andrew. Sistemes Operatius, Disseny i Implementació. 2 ª. Prentice Hall, 1998.