Беладијева аномалија

Из Википедије, слободне енциклопедије
Захтеви за страницама 3 2 1 0 3 2 4 3 2 1 0 4
Најновија страница 3 2 1 0 3 2 4 4 4 1 0 0
    3 2 1 0 3 2 2 2 4 1 1
Најстарија страница     3 2 1 0 3 3 3 2 4 4
Захтеви за страницама 3 2 1 0 3 2 4 3 2 1 0 4
Најновија страница 3 2 1 0 0 0 4 3 2 1 0 4
    3 2 1 1 1 0 4 3 2 1 0
      3 2 2 2 1 0 4 3 2 1
Најстарија страница       3 3 3 2 1 0 4 3 2
Пример Беладијеве аномалије. Користећи три странична оквира, дешава се 9 страничних грешака. Повећање на четири странична оквира резултује са 10 страничних грешака. Страничне грешке су означне црвено.

На пољу складиштења података у рачунарским системима, Беладијева аномалија (позната и као FIFO аномалија) доказује да је могуће да постоји више страничних грешака када се повећа број страничних оквира при употреби FIFO метода за замену страница. Ласло Белади је ово показао 1969. године.

Код стандардног управљања рачунарском меморијом, подаци се смештају у блокове одређене величине и сваки такав блок назива се страница. Централни процесор може да учита само ограничени број страница у неком тренутку и потребан му је оквир за сваку страницу коју може да учита. Странична грешка се дешава када страница није пронађена и тада ју је потребно довући са диска у меморију.

Када се деси странична грешка и сви оквири су у употреби, један од њих се мора избацити како би се направило место за нову страницу. Један прост алгоритам је FIFO, по коме ће бити избачена она страница која је била у оквирима најдуже. Док није била доказана Беладијева аномалија, овај алгоритам се сматрао за прихватљивим.

Литература[уреди]