Jednostavno upravljanje memorijom temeljeno na integraciji dodjeljivanja i zbrinjavanja memorije

doctoral thesis

• Title (english): Single layer memory management based on integration of memory allocation and garbage collection
• Author: Dorian Ivančić
• Mentor: Danko Basch (mentor)
• Committee member: Danko Basch (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Control and Computer Engineering); Zagreb
• Defense date and country: 2015, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Electrical Engineering; Automation and Robotics
• Universal decimal classification (UDC): 621.3 - Electrical engineering

Abstract

Algoritmi za upravljanje memorijom uvelike utječu na brzinu rada programa i njegove memorijske zahtjeve pa su zbog toga predmet istraživanja već dugi niz godina. Iako postoji mnoštvo algoritama, oblikovanjem novih želi se postići efikasnije korištenje računalne memorije i poboljšati performanse rada sustava. Tradicionalno se algoritam za zbrinjavanje ugrađuje povrh algoritma za dodjelu. U ovom radu opisana je metoda kombiniranja mehanizama za dodjelu i mehanizama za zbrinjavanje memorije s ciljem oblikovanja jednoslojnog algoritma za upravljanje memorijom koji utjelovljuje najbolje karakteristike početnih algoritama, a istodobno primjenjuje nove paradigme. Model je zasnovan na iskustvu postojećih algoritama, a posebno na algoritmu za dodjelu s odijeljenim listama memorijskih blokova te klasičnom algoritmu označi-oslobodi za zbrinjavanje nedohvatljivih objekata. Jednoslojni algoritam ima manju složenost postupka zbrinjavanja u odnosu na algoritam označi-oslobodi i postiže veću efikasnost. Oblikovani algoritam evaluiran je simulacijama obzirom na performanse. On ima slične memorijske zahtjeve kao i klasični algoritam označi-oslobodi, no provodi 19% manje vremena u zbrinjavanju, a uz njega je sustav 28% brži. Temeljem analize rezultata rada ispitnih programa razvijeno je nekoliko modela i na osnovu njih oblikovano nekoliko inačica heurističkog mehanizma prilagodbe jednoslojnog algoritma značajkama memorijskih objekata, no u konačnoj evaluaciji se koristi ona inačica koji ostvaruje najprihvatljiviji omjer dobitka na brzini u odnosu na dodatno memorijsko zauzeće. Memorijski zahtjevi heurističkog jednoslojnog algoritma slični su zahtjevima standardnog jednoslojnog i klasičnog algoritma označi-oslobodi, međutim heuristički jednoslojni algoritam provodi 47% manje vremena u zbrinjavanju u odnosu na algoritam označi-oslobodi, dok je uz njega sustav u cjelini 30% brži. Rezultati ovog istraživanja pokazuju da se relativno jednostavnim, ali dobro osmišljenim mehanizmima i tehnikama mogu značajno poboljšati performanse memorijskih algoritama i time ukazuju na nekoliko mogućih smjerova daljnjih istraživanja.

Abstract (english)

Memory management algorithms greatly affect the execution speed and memory requirements of programs which are executed. Although there are a number of existing algorithms, new ones are devised with the goal of achieving more efficient memory use and improved system performance. Traditionally a garbage collector is built in as a layer above a memory allocator. This research describes a method which combines memory allocation and garbage collection mechanisms to achieve a single layer method of memory management which embodies best characteristics of initial algorithms whilst simultaneously applying new paradigms. Resulting model is based on the well-established algorithms, in particular on memory allocation algorithm which uses segregated lists of free memory blocks and classical mark-and-sweep garbage collector. Analysis shows that the single layer algorithm has lower collection complexity and higher efficiency in comparison to the mark-and-sweep. Performances of a devised model are evaluated using simulation. Its memory requirements are similar to those of the classical mark-and-sweep but its garbage collection time and total time are improved by 19% and 28% respectively. Based on the analysis of the results, several models of heuristic mechanism which adapts to the behavior of memory objects are developed. However, in the final evaluation only the last model is considered as it shows the best memory-vs-speed trade-off. Memory consumption of the heuristic single layer algorithm is similar to those of the single layer algorithm and the classical mark-and-sweep. However, heuristic algorithm improves garbage collection time by 47% and total time by 30% in comparison to classical mark-and-sweep. This research shows that relatively simple, but well-devised mechanisms and techniques may greatly improve performances of memory algorithms thus suggesting several possible directions for further research.

• Keywords: zbrinjavanje memorije; dodjela memorije; jednoslojno upravljanje memorijom; heuristički algoritmi
• Keywords (english): garbage collection; memory allocation; single layer memory management; heuristic algorithms
• Language: croatian
• URN:NBN: urn:nbn:hr:168:244015
• Study programme: Title: Electrical Engineering and Computing; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti elektrotehnike i računarstva (Doktor znanosti elektrotehnike i računarstva)
• Type of resource: Text
• Extent: str. 155 ; 30 cm
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-04-16 13:54:38