En aquest tutorial, aprendrem un concepte important en els algorismes de planificació de processos de la CPU. El nom del concepte important és First Come First Serve. Aquest és l'algorisme bàsic que cada estudiant ha d'aprendre per entendre tots els conceptes bàsics dels algorismes de planificació de processos de la CPU.
First Come First Serve obre el camí per a la comprensió d'altres algorismes. Aquest algorisme pot tenir molts inconvenients. Però aquests inconvenients van crear algorismes molt nous i eficients. Per tant, és la nostra responsabilitat conèixer els algorismes de programació de processos de la CPU del primer arribat, primer servit.
Abreviatures importants
- CPU - - - > Unitat central de processament
- FCFS - - - > Primer arribat, primer servit
- AT - - - > Hora d'arribada
- BT - - - > Temps de ràfega
- WT - - - > Temps d'espera
- TAT - - - > Temps de volta
- CT - - - > Temps de finalització
- FIFO - - - > Primer en entrar Primer en sortir
Ordre d'arribada
L'algoritme de planificació de la CPU del primer que arriba, conegut com a FCFS, és el primer algorisme de l'algoritme de planificació del procés de la CPU. A l'algoritme First Come First Serve, el que fem és permetre que el procés s'executi de manera lineal.
Això vol dir que qualsevol procés que entri al procés entra primer a la cua preparada que s'executa primer. Això demostra que l'algoritme del primer en arribar, primer servir segueix el principi del primer en entrar, primer en sortir (FIFO).
L'algoritme First Come First Serve es pot executar de manera preemptiva i no preemptiva. Abans, entrant en exemples, entenem què és l'enfocament preemptiu i no preemptiu en la programació de processos de la CPU.
Enfocament preemptiu
En aquesta instància de la programació preemptiva de processos, el sistema operatiu assigna els recursos a un procés durant un període de temps predeterminat. El procés passa de l'estat en execució a l'estat llest o de l'estat d'espera a l'estat preparat durant l'assignació de recursos. Aquest canvi es produeix perquè la CPU pot assignar prioritat a altres processos i substituir el procés actiu actualment pel procés de prioritat més alta.
Enfocament no preemptiu
En aquest cas de la programació de processos no preemptiva, el recurs no es pot retirar d'un procés abans que el procés s'hagi acabat d'executar. Quan un procés en execució acaba i passa a l'estat d'espera, els recursos es canvien.
Efecte comboi en primer arribat, primer servit (FCFS)
L'efecte comboi és un fenomen que es produeix a l'algoritme de programació anomenat First Come First Serve (FCFS). L'algoritme de planificació del primer arribat, primer servit es produeix de manera no preventiva.
La manera no preventiva significa que si s'inicia l'execució d'un procés o treball, el sistema operatiu ha de completar el seu procés o treball. Fins que el procés o treball sigui zero, el procés o la feina nou o següent no s'inicia l'execució. La definició de programació no preventiva en termes de sistema operatiu significa que la Unitat Central de Processament (CPU) estarà completament dedicada fins al final del procés o treball iniciat primer i el nou procés o treball només s'executa després d'acabar el procés anterior o feina.
Hi pot haver alguns casos, que poden fer que la Unitat Central de Processament (CPU) dediqui massa temps. Això es deu al fet que a l'enfocament no preventiu de l'algoritme de planificació del primer arribat, primer servit, els processos o els treballs s'escullen per ordre en sèrie. A causa d'això, els treballs o processos més curts darrere dels processos o treballs més grans triguen massa temps a completar la seva execució. A causa d'això, el temps d'espera, el temps de volta i el temps de finalització és molt elevat.
Per tant, aquí, com que el primer procés és gran o el temps de finalització és massa elevat, es produeix aquest efecte de comboi a l'algoritme First Come First Serve.
Suposem que el treball més llarg triga un temps infinit a completar-se. Aleshores, els processos restants han d'esperar el mateix temps infinit. A causa d'aquest efecte comboi creat pel treball més llarg, la fam dels processos d'espera augmenta molt ràpidament. Aquest és el major desavantatge de la programació de processos de la CPU FCFS.
Característiques de la programació de processos de la CPU FCFS
Les característiques de la programació de processos de la CPU FCFS són:
- La implementació és senzilla.
- No causa cap causalitat durant l'ús
- Adopta una estratègia no preventiva i preventiva.
- Executa cada procediment en l'ordre en què es reben.
- L'hora d'arribada s'utilitza com a criteri de selecció dels tràmits.
Avantatges de la programació de processos de la CPU FCFS
Els avantatges de la programació de processos de la CPU FCFS són:
- Per tal d'assignar processos, utilitza la cua First In First Out.
- El procés de programació de la CPU FCFS és senzill i fàcil d'implementar.
- En la programació preventiva de la situació de FCFS, no hi ha cap possibilitat que el procés mori de gana.
- Com que no es té en compte la prioritat del procés, és un algorisme equitatiu.
Desavantatges de la programació de processos de la CPU FCFS
Els desavantatges de la programació de processos de la CPU FCFS són:
- L'algoritme de programació de la CPU FCFS té un llarg temps d'espera
- La programació de la CPU FCFS afavoreix les operacions d'entrada o sortida de la CPU
- A FCFS hi ha la possibilitat que es produeixi l'efecte comboi
- Com que FCFS és tan senzill, sovint no és gaire efectiu. Els períodes d'espera ampliats van de la mà d'això. Totes les altres comandes es deixen inactius si la CPU està ocupada processant una comanda que requereix molt de temps.
Problemes en l'algoritme de planificació de la CPU del primer arribat, primer servei
Exemple
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
Enfocament no preemptiu
Ara, resolem aquest problema amb l'ajuda de l'algoritme de programació anomenat First Come First Serve en un enfocament no preventiu.
El diagrama de Gantt per a l'exemple 1 anterior és:
Hora de volta = Temps de finalització - Hora d'arribada
Temps d'espera = Temps de volta - Temps de ràfega
Solució a la pregunta anterior Exemple 1
| S. No | ID del procés | Temps d'arribada | Temps d'explosió | Temps de finalització | Temps de resposta | Temps d'espera | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | B | 1 | 3 | 12 | 11 | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | 11 |
| 4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | I | 2 | 3 | 21 | 19 | 16 |
| 6 | P 6 | F | 3 | 2 | 23 | 20 | 18 |
El temps mitjà d'acabament és:
CT mitjà = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
CT mitjà = 97/6
CT mitjà = 16,16667
El temps d'espera mitjà és:
WT mitjà = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Pes mitjà = 66/6
Pes mitjà = 11
El temps mitjà de volta és:
TAT mitjà = ( 9 + 11 + 13 + 17 + 19 + 20 ) / 6
TAT mitjà = 89/6
TAT mitjà = 14,83334
text d'ajustament css
Així és com es resol l'FCFS en l'enfocament no preemptiu.
Ara, entenem com es poden resoldre amb l'enfocament preemptiu
Enfocament preemptiu
Ara, resolem aquest problema amb l'ajuda de l'algoritme de programació anomenat First Come First Serve en un enfocament preemptiu.
A Pre Emptive Approach busquem el millor procés disponible
El diagrama de Gantt per a l'exemple 1 anterior és:
| S. No | ID del procés | Temps d'arribada | Temps d'explosió | Temps de finalització | Temps de resposta | Temps d'espera | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 23 | 23 | 14 |
| 2 | P 2 | B | 1 | 3 | 8 | 7 | 4 |
| 3 | P 3 | C | 1 | 2 | 3 | 2 | 0 |
| 4 | P 4 | D | 1 | 4 | 15 | 14 | 10 |
| 5 | P 5 | I | 2 | 3 | 11 | 9 | 7 |
| 6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
| següent → ← anterior Per desfer-se del problema de malgastar els senyals de despertador, Dijkstra va proposar un enfocament que implica emmagatzemar totes les trucades de despertador. Dijkstra afirma que, en lloc de donar les trucades d'atenció directament al consumidor, el productor pot emmagatzemar la trucada d'atenció en una variable. Qualsevol dels consumidors pot llegir-lo sempre que ho necessiti. El semàfor són les variables que emmagatzemen totes les trucades d'atenció que s'estan transferint del productor al consumidor. És una variable sobre la qual la lectura, la modificació i l'actualització es produeixen automàticament en mode nucli. El semàfor no es pot implementar en el mode d'usuari perquè sempre es pot produir una condició de carrera quan dos o més processos intenten accedir a la variable simultàniament. Sempre necessita suport del sistema operatiu per ser implementat. Segons la demanda de la situació, Semàfor es pot dividir en dues categories.
En parlarem de cadascun amb detall. |