Search

Kaasaegsed arvutiarhitektuurid võimaldavad üheaegselt läbi viia mitmeid arvutusi. Programmide kirjutamine niisuguste süsteemide jaoks on äärmiselt raske, kuna paralleelselt käivitatavate lõimede vaheline koosmõju on ettearvamatu. Üks eriti raskesti tabatav viga mitmelõimelises süsteemis on andmejooks, s.o. olukord, kus mitu lõime üritavad samaaegselt ühele ja samale jagatud mäluasukohale ligi pääseda. See võib kaasa tuua andmete riknemise ja sellega süsteemi kokku jooksmise või muu ebakorrektse käitumise. Staatiline programmianalüüs on formaalne meetod, millega saab välja arvutada programmi kõigi võimalike käitumiste ülemhulga, lahendades teatava andmevoogu kirjeldava võrrandisüsteemi. Käesoleva doktoritöö põhiteesiks on väide, et staatilise programmianalüüsiga on võimalik kindlaks teha andmejooksude puudumine reaalsetes keerukates süsteemides, eriti operatsioonisüsteemide tuumamoodulites. Selliste süsteemide jaoks on analüüside arendamine raskendatud, sest nii andmestruktuurid kui ka neid kaitsvad lukud luuakse alles programmi täitmise ajal. Probleemi ületamiseks on töö raames arendatud kolm uudset meetodit: aadressavaldiste võrduste analüüs, dünaamilise mälu regioon-analüüs ja süsteemkoodile sobiv mälukuju analüüs. Mainitud meetodid on realiseeritud mitmelõimeliste C programmide analüsaatorite raamistikus Goblint ja nende praktilisust on demonstreeritud mitmete vabavaraliste rakenduste ja operatsioonisüsteemi Linux tuumamoodulite analüüsiga., Modern computer architectures are capable of carrying out many computations at the same time. Writing and testing programs for such systems is notoriously difficult because the interaction between concurrently executing threads is unpredictable. A particularly elusive flaw in shared-memory concurrent systems is the data race, a situation where multiple threads may simultaneously attempt to update the same memory location. This may result in data corruption and ultimately system malfunction. Static program analysis is an automated formal method, which computes all possible run-time behaviours of a program by solving a system of data flow equations. This dissertation contends that static analysis can be used to verify the absence of data races in real-world systems, especially operating system modules like Linux device drivers. The challenge in developing static analyses for such code is that both data structures and locks protecting the data are created at run-time. To face this problem, three novel techniques were developed: an abstract domain for equalities between address expressions, a region-based heap abstraction, and a shape domain suitable for low-level programs. We have implemented these techniques in the Goblint analyzer and used it to experimentally validate the contention that verification of race-freedom in real-world systems is possible by means of static analysis.

Programmide käitusaegset uuendamist on põhjalikult uuritud ning selle kasutamine programmeerimiskeelte implementatsioonides kogub hoogu. Senised pakutud lahendused programmide käitusaegse uuendamise osas on rakendatavad ainult konkreetsetele keeltele ja ei ole taaskasutatavad. Käesolevas lõputöös on uuritud seda, kuidas Truffle-nimeline programmeerimiskeelte loomise raamistik suudaks aidata keelte loojatel lisada käitusaegse uuendamise tuge. Autor on loonud taaskasutatava dünaamilise uuendamise lahenduse, mida erinevad Truffle raamistikus loodud keeled saavad kasutada selleks, et vähese vaevaga toetada käitusaegseid uuendusi. Antud lahendusega on võimalik uuendatavaks teha Pythoni, Ruby ja JavasScripti Truffle implementatsioone. Väljatöötatud lahendusel on peaaegu olematu mõju keele tippvõimsusele, kui on sisse lülitatud Truffle täppisajastusega (JIT) kompilaator. See lahendus teeb käitusaegse uuendamise toe lisamise uutele ja tulevastele keeltele märkimisväärselt lihtsamaks., Reloading running programs is a well-researched and increasingly popular feature of programming language implementations. There are plenty of proposed solutions for various existing programming languages, but typically the solutions target a specific language and are not reusable. In this thesis, we explored how the Truffle language implementation framework could aid language creators in adding reloading capabilities to their languages. We created a reusable reloading core that different Truffle-based languages can hook into to support dynamic updates with minimum amount of effort on their part. We demonstrate how the Truffle implementations of Python, Ruby and JavaScript can be made reloadable with the developed solution. With Truffle’s just-in-time compiler enabled, our solution incurs close to zero overhead on steady-state performance. This approach significantly reduces the effort required to add dynamic update support for existing and future languages.

Funktsioonikutsete ajalugu, mida kasutajale trükitakse pinujäljena, on suureks abiks programmis toimuva vea täpse asukoha leidmiseks lähtekoodis. Sügavamate probleemide puhul on aga vaja programmi täitmist pikemalt jälgida ja oluliste sündmuste toimumisel nende funktsioonikutsete ajalugu salvestada. Kuna terve ajalugu on väga pikk, siis on mõistlik seda kodeerida. Selles magistritöös uuritakse ühte konkreetset kodeerimise algoritmi Lucce, tuues välja nii selle eeliseid teiste algoritmidega võrreldes kui ka probleeme jõudlusega. Eesmärgiks on selle algoritmi jõudlust tõsta ja sellel näitel tutvustada üldiseid ning Java agentidega seotud jõudluse tõstmise võtteid., The idea behind calling context encoding algorithms is to efficiently build a call graph of an application in order to be able to give developers a call stack trace of any event at any point of the program execution. Having the information that calling context provides ena-bles developers to better interpret results of monitoring and profiling tools. In this paper, we discuss in greater detail the benefits of calling context encoding and the problems with current algorithms that are trying to construct calling context. We take an algorithm im-plemented as Java instrumentation agent - Lucce - and explain its promising possibilities, benefits over other similar algorithms, as well as its main performance problem. This thesis contributes to this field firstly by presenting an analysis of different methods of perfor-mance optimization and their applications to a Java agent, and secondly by applying these methods to the performance optimization of the Lucce algorithm and its Java implementa-tion.

Nim on programmeerimiskeel, mis on inspireeritud selliste keelte poolt nagu C, Python ja Lisp. Tegu on eelkõige madala taseme süsteemide programmeerimiskeelega, kuid selle paindlik süntaks ja automaatse mäluhalduse tugi võimaldavad ka näiteks veebirakenduste kirjutamist. IntelliJ IDEA on firma JetBrains poolt loodud arenduskeskkond (IDE), mis võimaldab arendada rakendusi erinevates keeltes (nt. Java, PHP, Python, C++, Ruby jt). Käesoleva töö eesmärgiks on luua IntelliJ arenduskeskkonnale laiendus, mis võimaldaks Nim keeles rakenduste kirjutamist. Põhiline eesmärk on realiseerida sümbolite järgi navigeerimine ja automaatne sümbolite sisestamine., Nim is a programming language that takes inspiration from such languages as C, Python and Lisp. It is mainly a low-level systems programming language, albeit its flexible syntax and built-in support for garbage collection have facilitated its use in web application development among other areas. IntelliJ IDEA is a popular integrated development environment (IDE) created by JetBrains and used to develop in languages such as Java, PHP, Python, C++, Ruby and others. The aim of this thesis is to create a plugin for IntelliJ IDEA that would allow writing applications in Nim. The main focus is on providing symbol navigation and code completion.

Seadmedraiverite ehk ohjurite paralleelne olemus muudab\n\rnendest vigade leidmise inimese jaoks väga keeruliseks. Staatiline analüsaator\n\rGoblint üritab automaatselt verifitseerida, et ohjuris puuduvad andmejooksud.\n\rSealjuures on suureks väljakutseks analüüsi täpsus. Käesolev töö arendab edasi\n\rGoblinti regioonianalüüsi, mis võimaldab arvesse võtta valdkonnale eriomaseid\n\rhappens-before tagatisi. Väljapakutud täienduse implementeerimise ning\n\rmuudatuste mõju analüüsimise aluseks on võetud Linuxi ohjurite alamhulk. Me\n\rnäitame, et mainitud edasiarendus suurendab Goblinti täpsust character tüüpi\n\rohjurite analüüsimisel., The concurrent nature of device drivers makes them notoriously\n\rdifficult to manually debug. Goblint, a static analysis framework tries to\n\rautomatically verify the inexistence of data races. The key challenge in doing\n\rthat is the precision of the analysis. This paper proposes an enhancement to the region analysis of Goblint to incorporate domain-specific happens-before\n\rguarantees. The proposed addition is implemented and evaluated on the Goblint benchmark suite. We show that the given enhancement increases the precision of Goblint when analysing character drivers.

Käesoleva magistritöö eesmärgiks oli kavandada ja implementeerida Eclipse’i põhine töövahend, mis võimaldaks kontrollida PHP-skriptides leiduvate SQL-päringute süntaktilist ning semantilist korrektsust. Aluseks sai võetud juba eksisteeriv töövahend Alvor, mis on mõeldud Java koodis leiduvate SQL lausete kontrollimiseks. Töö tulemusena valmis laiendus AlvorPHP, mis kogub kokku päringulaused neid sisaldava PHP funktsiooni või skripti skoobis ning tagastab edasiseks käitlemiseks. PHP dünaamilise eripära tõttu ei olnud võimalik realiseerida toetust kõigile temas esinevatele keelelistele konstruktsioonidele. Mõned neist jäid realiseerimata ka ajapuuduse tõttu, mis jätab võimaluse laienduse edaspidiseks täiendamiseks. Sellele vaatamata on toetatud enam levinud ning kasutatavad vahendid. Antud laienduse kasutajate sihtgrupp peaks olema ennekõike algajad programmeerijad, kes saaksid seda kasutada õppimist toetava abivahendina., During code development it is crucial to get fast feedback about the correctness of our code. Various hints are given by compiler through warnings and error messages that are displayed in the IDE, e.g. Eclipse. Unfortunately, this covers only the general host-language, in which we write the code. Often we need to use another language to communicate with a specific application domain: e.g. SQL for sending queries to a database engine. By default these SQL strings are not checked statically, although it would be highly beneficial. Alvor is a tool that statically checks SQL queries in Java programs. This thesis presents an extension for Alvor to add PHP support. The key challenge when adapting Alvor to PHP was the dynamic nature of PHP. The solution is therefore limited to operate only within the scope of a PHP function or a PHP script. We evaluated the tool on open-source software and the results showed that it would be most beneficial to use it as a tool to support beginners in learning programming.

C-keelsetes programmides lõimede loomise/lõpetamise struktuuri staatiline analüüs., Static analysis of thread creation/join structure in C-programs.

Iseorganiseeruvad kujutised (self-organizing maps, SOMs) on tehislikud neurovõrgud, mida kasutadakse kõrg-dimensionaalsete andmete kujutamiseks madaladimensionaalsesse neuronite massiivi. Saadud kujutist võib kasutada andmete pakkimiseks ja andmete visualiseerimiseks, mistõttu on SOM algoritm kasutuses paljudes statistika- ja monitoorimisrakendustes. Keskendudes andmete visualiseerimisele, on magistritöö eesmärk välja pakkuda juhtnöörid, mille alusel saaks SOM algoritmi tuua kasutusele väiksematesse ja täielikku automatiseeritust eeldavatesse tarkvara-rakendustesse. Töös antakse ülevaade SOM ja hilisemast PLSOM algoritmist, pakutakse välja ühine sõnavara ja klassifikatsioon erinevat tüüpi visualiseerimismeetoditele. Selle põhjal tuuakse välja soovituslik raamistik tarkvarapaketile, mis oleks võimeline haldama kõiki andmetest visuaalse pildi saamiseks vajalikke samme. Raamistiku eesmärk on olla lihtsalt laiendatav, tehes lihtsaks ja arusaadavaks uute andmete importimise/töötlemise ja uute visualiseerimismeetodite lisamise. Magistritööga tuleb kaasa tarkvarapakett, mis järgib töös väljatoodud juhtnööre. Tarkvarapakett on kasutatav nii musta kastina, võttes vastu juhtnööre XML kujul kui ka valge kastina, ehk siis integreeritav otse mõnda teise rakendusse.