Domande e risposte sull'allocazione della memoria del sistema operativo # 2
Question: Spiegare i seguenti algoritmi di allocazione.
First Fit
Il più adatto
Peggiore vestibilità
Il sistema di Buddy
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.