Permalink
| Search for: | |
| Returned: | 18 Documents (sorted by score) |
@MastersThesis{Kurtev00,
author = "Stoyan Kurtev",
title = "Subtyping and Inheritance in Object-Oriented
Programming",
school = "{Technische Universit{\"a}t Wien}",
year = "2000",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/kurtev00.ps.gz",
address = "Vienna, Austria",
month = feb,
}
(2 dupl. with Abstract and URL)
gzipped Postscript
@MastersThesis{Bermann99,
author = "Inge Bermann",
title = "Vergleich von Vererbungsmechanismen anhand von Design
Patterns in C++, Eiffel und Smalltalk",
school = "{Technische Universit{\"a}t Wien}",
year = "1999",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/bermann99.ps.gz",
address = "Vienna, Austria",
month = dec,
note = "in German",
}
@MastersThesis{Peck00,
author = "Patrick Peck",
title = "{Rigorose objektorientierte Analyse mit LOTOS:
Spezifikation eines nebenl{\"a}ufigen,
objektorientierten Datenflu{\ss}systems f{\"u}r die
digitale Signalverarbeitung}",
school = "{Technische Universit{\"a}t Wien}",
year = "2000",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/peck00.ps.gz",
address = "Vienna, Austria",
month = feb,
note = "in German",
}
@MastersThesis{judt06,
author = "Christian Judt",
title = "{Scannergenerator mit benannten regul{\"a}ren
Teilausdr{\"u}cken}",
school = "TU Wien",
year = "2006",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/judt06/Magisterarbeit_Christian_Judt.pdf",
abstract = "Common scanner generators like Lex and Flex share a
disadvantage. The scanners only determine the matched
string and which rule matched it.\par They don't supply
information about the string's internal structure (for
example the digits before and after a floating point
number's dot and the corresponding exponent).
Afterwards, in many cases the string has to be refined
by hand written, scanner like code.\par This master
thesis describes possibilities to implement a scanner
generator without this disadvantage, arising common
problems and corresponding solutions.\par In addition
it describes an extension of the scanner generator Flex
which implements such a system.",
note = "In German",
}
(with Abstract)
PDF
@MastersThesis{ertl90,
author = "M. Anton Ertl",
title = "Coroutining und Constraints in der
Logik-Programmierung",
school = "{Technische Universit{\"a}t Wien}",
type = "Diplomarbeit",
year = "1990",
address = "Austria",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/ertl90.ps.gz",
note = "In German",
abstract = "Logic Programming is distinguished by the declarative
programming style it encourages. Solutions to search
problems are specified easily. Some extensions to
Prolog are necessary to apply these advantages to
real-world problems.\par {\bf Coroutining} provides for
data driven goal execution. Using Coroutining it is
easier to separate logic and control and to use a
declarative programming style.\par {\bf Constraint
Logic Programming} liberates unification from its
restriction to syntactic equality and extends it to
relations on arbitrary computation domains. It also
enables the integration of {\bf consistency techniques}
in logic programming. Combinatorial problems are solved
efficiently using consistency techniques, since they
prune the search tree early and provide information for
the application of heuristics.\par Coroutining and
consistency techniques have been embedded in a Prolog
compiler based on the Warren Abstract Machine. The
application of these extensions to other Prolog
implementations is described.\par The application of
the resulting extended logic programming languages is
demonstrated using examples from artificial
intelligence, operations research, and systems
programming.",
}
(with Abstract)
gzipped Postscript
@MastersThesis{ambrosch93,
author = "Wolfgang Ambrosch",
title = "Vergleich von Registerallokationsalgorithmen",
school = "{Technische Universit{\"a}t Wien}",
type = "Diplomarbeit",
year = "1993",
address = "Austria",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/ambrosch93.ps.gz",
note = "In German",
abstract = "Register allocation is one of the most important
optimizations in modern compilers. Most of the
algorithms used today are based on the work of Gregory
Chaitin who was the first to implement a graph coloring
register allocator in 1981. This thesis concentrates on
register allocation via graph coloring.\par After
explaining the fundamental ideas we present a basic
framework for register allocation. We analyze existing
algorithms and show how their parts can be integrated
in and combined with the help of our framework.
Important but often neglected details as the
retargeting of register allocators, the handling of
different classes of registers, or the effects of
different subprogram linkage conventions are covered in
a separate chapter.\par Experimental results on the
effectiveness of the described methods for a large
suite of test programs are given. Compile-time
characteristics, register usage and the behavior in the
case of spilling were some of the issues we in
vestigated. An exact description of the papers our work
was based on completes the thesis.",
}
(with Abstract)
gzipped Postscript
@MastersThesis{baumann10,
author = "Christian Baumann",
title = "Efficiently Implementing Postscript in C\#",
school = "TU Wien",
year = "2010",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/baumann10.pdf",
abstract = "PostScript is a very powerful language for describing
graphics for displaying and printing. What most people
don't know, is that PostScript is also a mighty
stack-based programming language. The .NET Framework is
a huge collection of class libraries, programming
languages and standards built by Microsoft. The aim of
this work is it to develop a PostScript interpreter
with the .NET Framework whose main focus lies on the
execution speed of PostScript programs. In a first step
we will find out the bottlenecks of the execution of
PostScript programs. For this purpose we will analyse
some {"}real-world{"} programs. Another important point
for the execution are so-called procedures. These are
represented by arrays in PostScript. They can be
changed even when they are being executed by the
interpreter and allow infinite tail-call recursion.
Name resolution in PostScript is also of importance,
because of its impact on the overall execution time. We
will see that is is possible to write an interpreter
for PostScript in a high-level programming language
like C# which can keep up with current (commercial)
interpreters.",
}
(with Abstract)
PDF
@MastersThesis{pirker95,
author = "Christian Pirker",
title = "{{\"U}bersetzung von Forth in Maschinensprache}",
school = "{Technische Universit{\"a}t Wien}",
type = "Diplomarbeit",
year = "1995",
address = "Austria",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/pirker95.ps.gz",
note = "In German",
abstract = "Forth is an extensible and interactive language. It
provides two programmer-visible stacks (data and
returnstack). The supplied instructions (words)
manipulate data on the stacks. The efficiency of the
stack access and control flow determine mainly the
performance of Forth implementations.\par This thesis
builds a compiler that generates native code for {\em
MIPS RISC processors}. The compiler translates Forth
programs into native code using state of the art
compiler technology. The code is directly executable on
the processor.\par The compiler generates a {\bf data
flow graph} for each basic block of the program. Then
simple {\bf instruction selection}, {\bf instruction
scheduling} and {\bf register allocation} algorithms
produce the native code. The algorithms try to reduce
the stack operations and eliminate unneccesary stack
pointer updates.\par The native code compiler is
written in Forth and can compile itself. The compiler
is integrated into the interpreter. Therefore it also
handles interpreter words.\par Forth programs compiled
by this compiler run about 13 to 196 \% faster compared
to interpreted programs. Currently compiling takes 220
\% longer than compiling into interpreting code.",
}
(3 dupl. with Abstract and URL)
gzipped Postscript
@MastersThesis{czezatke98,
author = "Christian Czezatke",
title = "dtfs---A Log-Structured Filesystem for Linux",
school = "{Technische Universit{\"a}t Wien}",
type = "Diplomarbeit",
year = "1998",
address = "Austria",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/czezatke98.ps.gz",
abstract = "This thesis discusses the design and implementation of
dtfs, a log-structured filesystem for Linux. dtfs
features a generic core providing logging facilities
that are filesystem-independent and a ``filesystem
personality'' that borrows heavily from the Linux ext2
filesystem. Furthermore, the dtfs design supports the
placement of multiple filesystems (even of different
filesystem personalities) on top of one dtfs filesystem
device and the creation of snapshots and different
versions for these filesystems.\par I have also made a
first implementation of dtfs using the Linux 2.0.33
kernel and investigated the performance effects caused
by a log-structured filesystem. The results show that
this implementation of dtfs is already approximately on
par with the 2.0.33 ext2 filesystem performance-wise.
This also illustrates that traditional approaches have
been closing the performance gap during the last years,
especially when dealing with write and metadata update
operations. However, other qualtitative improvements
offered by the dtfs design, such as fast crash recovery
or the ability to create consistent backups without
restricting user access to the filesystem, cannot be
added to traditional approaches easily.",
}
(3 dupl. with Abstract and URL)
gzipped Postscript
@MastersThesis{eller05,
author = "Helmut Eller",
title = "Optimizing Interpreters with Superinstructions",
school = "TU Wien",
year = "2005",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/eller05.ps.gz",
abstract = "Superinstructions can be used to make virtual machine
(VM) interpreters faster. A superinstruction is a
combination of simpler VM instructions which can be
executed faster than the corresponding sequence of
simpler VM instructions, because the interpretative
overhead, like instruction dispatch and argument
fetching, is reduced. This work discusses the following
three topics related to superinstructions. First, I
present some heuristics to choose superinstructions. I
evaluated the heuristics for Forth and Java programs.
If the number of allowed superinstructions was very
large, $> 1000$, then the heuristic which chooses all
possible subsequences up to length 4 achieved the best
results. If the number of allowed superinstructions was
more limited, then a heuristic which favors short
sequences and sequences which occur in many different
programs and many different basic blocks performed
better than the others. Second, I compare a simple
greedy algorithm and an optimal algorithm to cover a
program with superinstructions. I found that the greedy
algorithm achieves almost optimal results. Finally, I
compare superinstructions with non-sequential patterns.
In my experiments, superinstructions performed slightly
better than non-sequential patterns.",
}
(with Abstract)
gzipped Postscript
@MastersThesis{levrinc08,
author = "Rastislav Levrinc",
title = "LLFS: A Copy-On-Write File System For Linux",
school = "TU Wien",
year = "2008",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/levrinc08.pdf",
abstract = "This thesis discusses the design and implementation of
LLFS, a Linux file system. LLFS combines clustering
with copy-on-write. With copy-on-write no allocated
blocks are overwritten between commits, and thanks to
the clustering the speed of LLFS remains comparable
with clustered file systems such as Ext2. Copy-on-write
opens new possibilities for features like snapshots,
writable snapshots (clones) and fast crash recovery to
the consistent state of the file system, while the
clustering helps to keep fragmentation low and speed
high.\par Clustered reads and writes are achieved with
Ext2-like groups and free-blocks bitmaps for allocating
and freeing of blocks. Journaling file systems like
Ext3 need to keep a journal and write blocks twice; By
using copy-on-write, LLFS avoids these overheads. By
using free-blocks bitmaps, it does not need a cleaner
like log-structured le systems. Yet LLFS offers the
combined functionality of journaling and log-structured
le systems.\par I have implemented LLFS starting from
the Ext2 file system and tested the performance. The
benchmarks have shown that LLFS achieves similar
performance and in some cases better than Linux
journaling file systems.",
}
(with Abstract)
PDF
@MastersThesis{blechmann11,
author = "Tim Blechmann",
title = "Supernova --- A Multiprocessor Aware Real-Time Audio
Synthesis Engine For SuperCollider",
school = "TU Wien",
year = "2011",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/blechmann11.pdf",
abstract = "These days, most computer systems are built with
multi-core processors. However, most computer music
systems use a single-threaded synthesis engine. While
the single-core performance for current CPUs is
sufficient for many computer music applications, some
demanding applications benefit from using multiple
processors simultaneously.\par Real-time audio
synthesis imposes specific constraints regarding
real-time safety, since the synthesis engine needs to
be tuned for worst-case latencies below one
millisecond. As a result, no blocking synchronization
can be used and the signal processing graph needs to be
split into reasonably sized parts, that provide enough
parallelism without introducing a significant
scheduling overhead.\par During the work on this master
thesis, I developed Supernova as a multiprocessor aware
synthesis engine for SuperCollider. SuperCollider is a
computer music system based on a dynamic scripting
language with a real-time garbage collector, that is
used to control a separate audio synthesis server.
Supernova replaces the original audio synthesis engine.
It is not possible to automatically parallelize the
synthesis graph of SuperCollider without fundamentally
changing the semantics of the SuperCollider class
library. Therefore a the programming model for the
synthesis graph was extended, exposing parallelism
explicitly to the user. To achieve this, I propose two
simple concepts, `parallel groups' and `satellite
nodes'.\par To my knowledge, Supernova is the first
parallel audio synthesis engine that is designed for
real-time operations under low-latency constraints
without adding any additional latency to the audio
signal.",
}
(with Abstract)
PDF
@MastersThesis{maierhofer97,
author = "Martin Maierhofer",
title = "Erzeugung optimierten Codes f{\"}r Stackmaschinen",
school = "{Technische Universit{\"a}t Wien}",
type = "Diplomarbeit",
year = "1997",
address = "Austria",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/maierhofer97.ps.gz",
abstract = "The success of the Java programming language and the
underlying stack architecture (the JavaVM) recently
have caused renewed interest in stack architectures.
New and special techniques are required to provide
support for the efficient execution of Algol-like high
level languages on stack machines. An optimizing
compiler should be able to eliminate dispensable
accesses to main memory when loading and storing local
variables by temporarily keeping a copy of their value
on the stack. This technique, however, is only
meaningful for machines that can handle
stackmanipulations faster than accesses to main memory.
\par This thesis presents two solutions for the problem
and compares the results that can be achieved for two
stack architectures (one of them is the JavaVM). Both
techniques work on a ``local'' level, meaning that each
basic block is considered separately. Phil Koopman's
``stack scheduling'' performs well in cooperation with
a simple instruction scheduling strategy (a depth first
postorder traversal of the dependency graph is used).
The second technique (``{\scshape Dag} scheduling'')
reorders the instructions (i.e. it schedules the
instructions) in order to minimize accesses to local
variables and leads to optimal code. \par The
efficiency of Koopman's algorithm can be assessed with
respect to the results achieved by {\scshape Dag}
scheduling: stack scheduling leads to results that come
quite near the optimum. Accesses to variables can be
reduced from around 40\% (in code produced by the Java
compiler \texttt{javac}) to some 30\% (after
optimization) of the total instructions in JavaVM code.
Instructions for stackmanipulation, however, increase
from about 5\% to up to 15\% of the total.",
note = "In German",
}
(with Abstract)
gzipped Postscript
@MastersThesis{reisner00,
author = "Philipp Reisner",
title = "{DRBD -- Festplattenspiegelung {\"u}bers Netzwerk
f{\"u}r die Realisierung hochverf{\"u}gbarer Server
unter Linux}",
school = "{Technische Universit{\"a}t Wien}",
type = "Diplomarbeit",
year = "2000",
address = "Austria",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/reisner00.ps.gz",
sourceurl = "http://www.complang.tuwien.ac.at/reisner/drbd/",
abstract = "This work shows that it is possible to implement
high-availability clusters without expensive shared
devices. A description of the design and the
implementation of a device driver for Linux is
provided, which allows harddisk mirroring via the
network. In order to be able to offer good performance
and support for journaling filesystems an algorithm was
developed which gives the disk scheduler maximum
freedom during the write process to reorder blocks
without compromising the order imposed by the
filesystem.\par The device reaches between 50~\% and
98~\% of the maximum theoretical performance. Apart
from that, this work gives an overview of how DRBD is
integrated into the other clustering components under
Linux.",
kurzfassung = "Diese Arbeit zeigt, da{\ss}
Hochverf{\"u}gbarkeits-Cluster auch ohne teure Shared
Devices implementiert werden k{\"o}nnen. Es werden das
Design und die Implementierung eines Ger{\"a}tetreibers
(=DRBD) f{\"u}r Linux gezeigt, der das Spiegeln von
Festplatten {\"u}ber das Netzwerk erlaubt. Um sowohl
gute Leistung als auch Unterst{\"u}tzung f{\"u}r
Journaling-Filesysteme bieten zu k{\"o}nnen, wurde ein
Algorithmus entwickelt, der dem Disk-Scheduler beim
Schreiben die grtm{\"o}gliche Freiheit einr{\"a}umt,
Bl{\"o}cke umzuordnen, dabei aber die Reihenfolge, die
das Filesystem vorgibt, nicht verletzt.\par Das
Ger{\"a}t erreicht zwischen 50~\% und 98~\% der
theoretisch m{\"o}glichen Leistung. Weiters gebe ich
einen {\"U}berblick dar{\"u}ber, wie sich DRBD in die
anderen Clustering-Komponenten unter Linux
eingliedert.",
note = "in German",
}
(with Abstract)
gzipped Postscript
@MastersThesis{strauss-haslinglehner05,
author = "Stefan Strau{\ss}-Haslinglehner",
title = "Schnelles Starten grosser Programme",
school = "TU Wien",
year = "2005",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/strauss-haslinglehner05.ps.gz",
abstract = "This thesis shows a way to reduce application startup
time. This is done by preloading the data needed during
application startup in an order optimized for block
device I/O performance. The thesis describes the design
and implementation of a Linux kernel module, consisting
of a recording unit, a database and a preloading unit.
The recording unit is responsible for recording access
patterns on block-devices at application startup. The
recorded access patterns are optimized and stored
persistently in the database. The preloading unit is
responsible for preloading the corresponding access
patterns on future application startups.\par The effect
of preloading was analyzed using several applications
on two test systems. Measurements showed a speedup by a
factor of 1.5 to 1.8.",
kurzfassung = "Diese Arbeit zeigt eine M{\"o}glichkeit zur Reduktion
der Zeit f{\"u}r den Kaltstart von Anwendungen durch
Preloading der f{\"u}r den Start ben{\"o}tigten
Blockger{\"a}tedaten. Dabei wird die Zugriffsfolge des
Demand Pagings so umgeordnet, dass die Blockger{\"a}te
I/O Performance beim Preloading optimiert wird.\par
Gezeigt wird das Design und die Implementierung eines
Linux Kernelmoduls, bestehend aus einer Recording
Einheit, einer Datenbank und einer Preloading Einheit.
Das Recording zeichnet die Zugriffsfolge eines
Anwendungsstarts auf die Blockger{\"a}te des Systems
auf. Die so gewonnenen Daten werden persistent in einer
Datenbank gespeichert. Zu Beginn zuk{\"u}nftiger Starts
der Anwendung f{\"u}hrt das Preloading die optimierte
Zugriffsfolgen konzentriert aus.\par Die Auswirkung des
Preloadings wurde auf zwei unterschiedlichen
Testplattformen mit verschiedenen Anwendungen
untersucht. Messungen zeigten dabei eine Reduktion der
Startzeit um den Faktor 1.5 bis 1.8.",
}
(with Abstract)
gzipped Postscript
@MastersThesis{khyo11,
author = "G{\"u}nther Anton Khyo",
title = "Language Support for Linux Device Driver Programming",
school = "TU Wien",
year = "2011",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/khyo11.pdf",
poster = "http://www.complang.tuwien.ac.at/Diplomarbeiten/khyo11-poster.pdf",
abstract = "The success of any commodity operating system is
determined by the quality of device driver support.
Over the last decades, the computer hardware industry
has been advancing at a rapid pace, putting high
pressure on device driver developers. About 52\% of the
Linux kernel code is comprised by device drivers,
accounting for close to 7.4 million lines of code.
While managing such a huge code base is a challenge on
its own, Linux device driver developers have to
overcome additional obstacles. The complex,
multithreaded programming model of the kernel creates a
high potential for bugs and many of them result in
kernel crashes. Device drivers constitute the largest
and most unreliable component of the kernel.\par This
thesis analyses the root causes of the device driver
reliability problem, and demonstrates how the current
driver programming model can be improved to assist
programmers in creating better driver code. To examine
and test feasible improvements, a prototype language
(called CiD) based on a subset of C was designed with
the special requirements on Linux device driver
development in mind. CiD features syntactical additions
for three essential device driver code aspects:
concurrency, synchronization and hardware
communication. The compiler is programmed with basic
rules of the concurrency model of the kernel and is
able to detect simple but common mistakes that lead to
deadlocks. Additional consistency checks support the
programmer in generating correct hardware I/O code.\par
Two device drivers have been converted into CiD code to
test the language extensions and the implementation of
the compiler. The results for concurrency and
synchronization are satisfying: race conditions in the
data-flow are reported with a false positive rate of
6\% to 21\%. The compiler also generates correct
concurrency and synchronization code, thus mitigating
the potential for deadlocks. The results show that
hardware I/O generator leaves much room for
improvement, since it generates 1.5 times more I/O
operations than the original driver. Related approaches
show that further optimizations can reduce the gap.\par
In conclusion, we find that device driver programming
can be made more robust with only minor alterations to
the existing programming model and little compiler
complexity.",
}
(with Abstract)
PDF
@MastersThesis{sabin11,
author = "Patrick Sabin",
title = "Implementing a Reversible Debugger for Python",
school = "TU Wien",
year = "2011",
type = "Diplomarbeit",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/sabin11.pdf",
codeurl = "http://code.google.com/p/epdb/",
abstract = "The programmer usually initiates a debugging process
because of a failure and his goal is to find the
defect. The defect is always executed before the
failure occurs, so it is natural to start at the
failure and move backwards in a program to find the
defect. However this procedure is usually not supported
by actual debuggers. \par There are two different
methods of implementing a reversible debugger, i.e., a
debugger which can run the program forwards and
backwards. The first one is the logging-based approach,
which records the state of the program after every
instruction and allows inspection after the program has
finished running. The second one is the replay-based
approach, where the debugger runs the debuggee
interactively. For this purpose it makes periodic
snapshots. The debugger runs the debuggee backwards by
restoring a previous snapshot and then running the
program forward until it reaches the desired position.
\par In this thesis, I show that it is possible to
implement a reversible debugger by continuous
snapshotting of the program state. There are indeed
some challenges with using such a feature. For example,
there are non-deterministic instructions, which execute
differently each instance the interpreter executes
them, e.g., a function, which returns the system time.
Another example of this is when instructions change
some external state like a file on the hard drive,
which the debugger does not save when it makes a
snapshot. Another problem is that some instructions do
something different each time the debugger executes
them. \par Therefore I present some methods of treating
these problems. Accompanying this thesis, I have
developed a proof-of-concept implementation of a
reversible debugger called epdb for the Python
programming language, which solves most of the problems
of reversible debugging. \par In order to support
reversible debugging of programs which have
non-deterministic instructions in it, I introduce the
new concept of timelines. With timelines, the user can
decide which execution path he wants to take. I also
introduce stateful resource management to support the
management of the external state. This allows the user
to investigate the environment corresponding to the
actual position inside the program, when he executes
the program backwards.",
}
(with Abstract)
PDF
@MastersThesis{syrowatka00,
author = "Peter Syrowatka",
title = "Verallgemeinerung von mmap() am Beispiel des Memory
Mappings von Pipes in Linux",
school = "{Technische Universit{\"a}t Wien}",
type = "Diplomarbeit",
year = "2000",
address = "Austria",
URL = "http://www.complang.tuwien.ac.at/Diplomarbeiten/syrowatka00.ps.gz",
sourceurl = "http://www.complang.tuwien.ac.at/syro/thesis.html",
abstract = "Memory mapping (API function \texttt{mmap()}) is a
alternative way of accessing files. Compared to the IO
functions \texttt{read()} and \texttt{write()} it
avoids unnecessary copy operations. The method is not
widely used, though, because its standard
implementations cannot be applied to stream objects
like pipes, sockets or (pseudo-)terminal devices. This
consistent applicability of the standard IO functions
to all kinds of objects makes them more attractive.\par
To eliminate this disadvantage I present the model of
an extended \texttt{mmap()} call, that allows for
mapping arbitrary stream objects into a program's
address space. A program using this extended call can
be written adhering to only one paradigm of interacting
with external objects, the one of \texttt{mmap()}, and
still avoid unnecessary copying.\par The properties of
the memory object that is created by mapping a stream
object, are modeled after the behavior of a mapped
file, though they still keep some properties of the
original object, e.g.\ the size of a pipe or a socket
is by definition not known. Although \texttt{mmap()}
cannot change this, the large virtual address spaces of
current architectures make the model very useful.\par
Using the example of memory mapped pipes I specify the
model of extended \texttt{mmap()} in detail, benchmark
it and demonstrate a sample implementation for
Linux.\par Extended memory mapping, especially the
shift from page granularity to byte granularity,
requires some refinements in virtual memory
management.\par I have adapted some simple commands
(\texttt{cat}, \texttt{wc} and \texttt{grep}) and
compared their performance to the unmodified versions
implemented on basis of standard IO. As expected, the
versions using \texttt{mmap()} of ordinary files
performed better. The difference being mostly in system
time used. For the standard IO implementations the
measurements required more than twice as much time for
\texttt{mmap()}.\par A second experiment measured the
run-times of programs communicating via a pipe. Access
methods were either \texttt{read()/write()} or
\texttt{mmap()}. Here we see that the result was not as
expected. The slight increase of by factor of 1.1 for
\texttt{mmap()} can be attributed to the sample
implementation not being optimized.",
kurzfassung = "Memory Mapping (API-Funktion {\tt mmap()}) bietet eine
M{\"o}glichkeit auf Dateien zuzugreifen. Dabei
entfallen Kopieroperationen, die bei Verwendung der
normalen I/O-Funktionen {\tt read()} {\tt write()}
intern durchgef{\"u}hrt werden. Diese Methode wird von
den Anwendungsprogrammierern aber nicht sehr oft
verwendet, da sie nicht auf Stream-Objekte wie Pipes,
Sockets oder Terminals angewendet werden kann. Die
Standard-I/O Methoden stellen hier einen Weg zur
konsistenten Handhabung der unterschiedlichen Objekte
zur Verf{\"u}gung. \par Um diesen Nachteil zu
eliminieren, stelle ich ein Modell f{\"u}r einen
erweiterten {\tt mmap()}-\-Aufruf vor. Mit dieser
Erweiterung ist es m{\"o}glich, auch Stream-Objekte in
den Adressraum einzublenden. Dadurch kann auch bei
Verwendung der alternativen, mmap()-bedingten
Programmiermethode eine konsistente Struktur der
Programme realisiert und durch die Vermeidung der
Kopieroperationen eine Effizienzsteigerung erreicht
werden.\par Die Eigenschaften des Speicherobjektes,
welches durch das Einblenden eines Stream-Objektes
entsteht, orientieren sich am Verhalten einer
eingeblendeten Datei, beh{\"a}lt aber einige
Eigenheiten des Ursprungsobjektes. So ist zum Beispiel
die Gr{"}o{\ss}e einer Pipe oder eines Sockets per
Definition unbestimmt. Diese Eigenschaft bleibt auf
jeden Fall auch beim Einblenden erhalten. Abhilfe
bietet die Nutzung der gro{\ss}en virtuellen
Adressr{\"a}ume, die auf aktuellen Architekturen zur
Verf{\"u}gung stehen.\par Am Beispiel des Memory
Mappings f{\"u}r Pipes spezifiziere ich das Modell des
erweiterten {\tt mmap()} im Detail und unterziehe es
einer Pr{\"u}fung und demonstriere es anhand einer
beispielhaften Implementierung f{\"u}r Linux.\par Das
erweiterte Memory Mapping stellt einige Anforderungen
an das Virtual Memory Management, vor allem den
{"}Ubergang der Verwaltung von {\em
Page-Granularit{\"a}t} auf {\em
Byte-Granularit{\"a}t}.\par Als Demonstrations- und
Benchmark-Programme habe ich einfache Anwendungen ({\tt
cat, wc} und {\tt grep}) entsprechend angepasst und
zwei Messreihen durchgef{\"u}hrt. Es erfolgte ein
Vergleich zwischen den Applikationen auf Standard-I/O-
und {\tt mmap()}-Basis. Dabei schneiden die Programme
mit Memory Mapping erwartungsgem{"}a{\ss} besser ab
(Basissysteme: FreeBSD, SCO, Sun Solaris und Linux).
Der Gewinn betrifft vor allem die Systemzeit. Die
erhaltenen Messwerte f{\"u}r die Standard-I/O-Methode
sind mindestens doppelt so hoch wie bei Verwendung von
{\tt mmap()}.\par In der zweiten Messreihe wurden die
Laufzeiten von Programmen, die {"}uber eine Pipe
untereinander Daten austauschen, ermittelt. Der Zugriff
erfolgt mit {\tt read()/write()} oder mit {\tt mmap()}.
Das Ergebnis dieser Messungen entspricht leider nicht
ganz den Erwartungen. Aufgrund der nicht optimierten,
beispielhaften Implementierung kommt es zu einer
leichten Erh{\"o}hung der Laufzeit (Gesamt-Zeit steigt
ca. um Faktor 1,1 im {\tt mmap()}-Fall).",
note = "in German",
}
(with Abstract)
gzipped Postscript
Some entries might have been ommited on the list above if author/title combination has already occurred. If in doubt check the duplicate list linked on the right of some citations.
| 18 matches: | Papers and talks produced by the Institut für Computersprachen, TU Wien |
This page has been served in 0.03 secs.