Domande e risposte sull'allocazione della memoria del sistema operativo # 2

Question: Spiegare i seguenti algoritmi di allocazione.

  1. First Fit

  2. Il più adatto

  3. Peggiore vestibilità

  4. Il sistema di Buddy

  5. Prossimo adattamento

Answer:

First Fit

Nel primo approccio fit è quello di allocare la prima partizione libera o buco abbastanza grande da poter ospitare il processo. Termina dopo aver trovato la prima partizione libera adatta.

Vantaggio

Algoritmo più veloce perché cerca il meno possibile.

Svantaggio

Le restanti aree di memoria inutilizzate lasciate dopo l'allocazione diventano sprecate se sono troppo piccole. Pertanto, la richiesta di un requisito di memoria maggiore non può essere soddisfatta.

Il più adatto

La soluzione migliore riguarda l'allocazione della partizione libera più piccola che soddisfa i requisiti del processo di richiesta. Questo algoritmo cerca prima l'intero elenco di partizioni libere e considera il foro più piccolo adeguato. Quindi cerca di trovare un foro vicino alla dimensione effettiva del processo necessaria.

Vantaggio

L'utilizzo della memoria è molto meglio del primo adattamento in quanto cerca prima la partizione libera più piccola disponibile.

Svantaggio

È più lento e può persino tendere a riempire la memoria con piccoli buchi inutili.

Peggiore vestibilità

L'approccio peggiore consiste nell'individuare la porzione libera disponibile più grande in modo che la porzione rimasta sia abbastanza grande da essere utile. È il contrario di best fit.

Vantaggio

Riduce il tasso di produzione di piccole lacune.

Svantaggio

Se un processo che richiede una memoria più grande arriva in una fase successiva, non può essere adattato poiché il buco più grande è già diviso e occupato.

Buddy's System

Nel sistema buddy, le dimensioni dei blocchi liberi sono in forma di potenza integrale di 2. Ad esempio 2, 4, 8, 16 ecc. Fino alla dimensione della memoria. Quando viene richiesto un blocco libero di dimensione 2k, viene allocato un blocco libero dall'elenco dei blocchi liberi di dimensione 2k. Se non è disponibile alcun blocco libero di dimensione 2k, il blocco di dimensione maggiore successiva, 2k + 1 viene diviso in due metà chiamate amici per soddisfare la richiesta.

Esempio

Lascia che la dimensione della memoria totale sia 512 KB e che un processo P1 richieda lo scambio di 70 KB. Poiché gli elenchi dei fori sono solo per potenze di 2, 128 KB saranno abbastanza grandi. Inizialmente non ci sono 128 KB, né ci sono blocchi da 256 KB. Pertanto il blocco da 512 KB viene diviso in due amici di 256 KB ciascuno, uno viene ulteriormente suddiviso in due blocchi da 128 KB e uno di essi viene assegnato al processo. Next P2 richiede 35 KB. Arrotondando 35 KB fino a una potenza di 2, è richiesto un blocco da 64 KB.

Quindi, quando il blocco da 128 KB viene diviso in due amici da 64 KB. Anche in questo caso un processo P3 (130KB) verrà regolato in tutto 256KB. Dopo aver soddisfatto la richiesta in questo modo quando tale blocco è libero, i due blocchi / compagni possono essere ricombinati per formare il blocco originale due volte più grande quando è anche la seconda metà compagno libero.

Vantaggio

Il sistema Buddy è più veloce. Quando un blocco di dimensione 2k viene liberato, viene cercato un buco di dimensione di memoria 2k per verificare se è possibile una fusione, mentre in altri algoritmi si deve cercare tutta la lista dei fori.

Svantaggio

Spesso è diventato inefficiente in termini di utilizzo della memoria. Poiché tutte le richieste devono essere arrotondate per eccesso a una potenza di 2, un processo da 35 KB viene allocato a 64 KB, sprecando così 29 KB in più causando la frammentazione interna. Potrebbero esserci buchi tra gli amici che causano la frammentazione esterna.

Prossimo adattamento

Next fit è una versione modificata del first fit. Inizia come primo tentativo per trovare una partizione libera. Alla successiva chiamata, inizia la ricerca dal punto in cui era stata interrotta, non dall'inizio.