1. List four distinct types of content that reside in a virtual address space of a typical process.

a) Executable code. 
	contains the machine code instructions to be executed by the processor. 
	It is often write protected and shared among processes that use the same main program or the same shared libraries.
b) Static data. 
	contains the statically allocated variables to be used by the process.
c) Heap. 
	contains the dynamically allocated variables to be used by the process.
d) Stack. 
	contains the stack to be used by the process for storing items such as return addresses, procedure arguments, temporarily saved registers or locally allocated variables.

Kod a static data su nemenne a ich poloha je determinovana compilerom. Stack a heap su dynamicke a rastu oproti sebe (stack dole a heap smerom hore).

------------------------------------------------------------------------------------------------------------
2. Explain the advantages of segmentation over flat virtual memory address space.

    No page faults -- whole segment is present at once -- only access violations need to be trapped
    No internal fragmentation -- segment size is customized to each process
    Easier to implement virtual OS 
    per segment protection
    snadnejsi sdileni dat (sdilim funkci/ ne naky stranky)

virtual space
Ochrana pameti.

------------------------------------------------------------------------------------------------------------
3. Explain why random placement of allocated blocks in the virtual address space
of a process can contribute to improved security.

Prevencia proti exploitom - napr buffer overflow. S kazdym spustenim programu ho rozhadze po pamati randomne, teda sa neda predpokladat ze bude napr. buffer overflow fungovat.

------------------------------------------------------------------------------------------------------------
4. Explain what the processor stack is used for with typical compiled procedural
programming languages.

The process stack is typically used for return addresses, procedure arguments, temporarily saved registers and locally allocated variables. The processor typically contains a register that points to the top of the stack. This register is called the stack pointer and is implicitly used by machine code instructions that call a procedure, return from a procedure, store a data item on the stack and fetch a data item from the stack.

------------------------------------------------------------------------------------------------------------
5. For a contemporary processor, explain how the same machine instructions can
access local variables and arguments of a procedure regardless of their absolute
address in the virtual address space. Explain why this is important.

The use of stack for procedure arguments and locally allocated variables relies on the fact that the arguments and the variables reside in a constant position relative to the top of the stack. The processor typically allows addressing data relative to the top of the stack, making it possible to use the same machine code instructions to access the procedure arguments and the locally allocated variables regardless on their absolute addresses in the virtual address space, as long as their addresses relative to the top of the stack do not change.
Importance: shared libraries.

------------------------------------------------------------------------------------------------------------
6. Explain how stack overflow can be detected using paging. Discuss possible
handling of the stack overflow including its limitations.

Allocating the block that contains stack requires estimating the stack size. Typically, the block is allocated with a reasonable default size and an extra page protected against reading and writing is added below the end of the allocated block. Should the stack overflow, an attempt to access the protected page will be made, causing an exception. The operating system can handle the exception by growing the block that contains stack and retrying the machine code instruction that caused the exception.
A multithreaded program requires as many stacks as there are threads. This makes
placing the block that contains stack more difficult with respect to growing the block later, unless segmentation is used.

------------------------------------------------------------------------------------------------------------
7. Explain what is the function of a heap allocator.

The process heap is used for dynamically allocated variables. The heap is stored in one or several continuous blocks of memory within the virtual address space. These blocks include a data structure used to keep track of what parts of the blocks are used and what parts of the blocks are free. This data structure is managed by the heap allocator of the process.
In a sense, the heap allocator duplicates the function of the virtual memory manager, for they are both responsible for keeping track of blocks of memory. Typically, however, the blocks managed by the heap allocator are many, small, short-lived and aligned on cache boundaries, while the blocks managed by the virtual memory manager are few, large, long-lived and aligned on page boundaries. This distinction makes it possible to design the heap allocator so that it is better suited for managing blocks containing dynamically allocated variables than the virtual memory manager.
Usually, the heap allocator resides within a shared library used by the processes of the operating system. The kernel of the operating system has a separate heap allocator.

------------------------------------------------------------------------------------------------------------
8. Explain where the heap allocator implementation usually resides and why.

Usually, the heap allocator resides within a shared library used by the processes of the operating system. The kernel of the operating system has a separate heap allocator.

------------------------------------------------------------------------------------------------------------
9. List the similarities and differences of heap allocator and virtual memory manager as modules responsible for allocating memory.

In a sense, the heap allocator duplicates the function of the virtual memory manager, for they are both responsible for keeping track of blocks of memory. Typically, however, the blocks managed by the heap allocator are many, small, short-lived and aligned on cache boundaries, while the blocks managed by the virtual memory manager are few, large, long-lived and aligned on page boundaries. This distinction makes it possible to design the heap allocator so that it is better suited for managing blocks containing dynamically allocated variables than the virtual memory manager.

------------------------------------------------------------------------------------------------------------
10. Design an interface of a heap allocator.

void * malloc(size_t size);
void free(void *ptr);
size_t get_size(void *ptr);

------------------------------------------------------------------------------------------------------------
11. List three typical requirements on the implementation of a heap allocator.

Obvyklmi poadavky na aloktor jsou rychlost (schopnost rychle alokovat a uvolnit pamet), spornost (mal reie dat aloktoru a mal fragmentace) funkcnost (resizing, align, zero fill).
------------------------------------------------------------------------------------------------------------
12. Explain the advantages and disadvantages of representing free and used
blocks of memory using bitmaps in a heap allocator.

Bitmapy maj dobrou efektivitu pri alokaci bloku velikosti blzk jejich
granularite, nevhodou je intern fragmentace, taky se v nich blbe hled voln
blok poadovan dlky.

------------------------------------------------------------------------------------------------------------
13. Explain what are the advantages and disadvantages of representing free and
used blocks of memory using linked lists in a heap allocator.

U linked lists asi taky nen co dodat, reie na seznam, extern
fragmentace, sekvencn hledn, oddelen seznamy plnch a przdnch bloku,
zvltn seznamy bloku obvyklch velikost aka zones, scelovn volnch bloku.

------------------------------------------------------------------------------------------------------------
14. Explain the problems a heap allocator implementation must solve on multiprocessor hardware and sketch appropriate solutions.

Multiprocesorov systmy maj u aloktoru podobn problmy jako plnovace nad ready frontou, tedy prli mnoho soubehu je zpomaluje. Proto se delaj hierarchick aloktory, local free block pools, kter se v prpade potreby prelvaj do global free block poolu.

------------------------------------------------------------------------------------------------------------
15. Explain how the Buddy Allocator works. Discuss its strengths and weaknesses.

Pamt rozdlena na bloky o velikosti 2n. Bloky stejn velikosti v seznamu. Pi pidlen zaokrouhlit na nejbli 2n. Pokud nen voln, roztpnou se vt bloky na pslun men velikosti. Pi uvolnn pamti se sluuj sousedn bloky (buddy).

Klady - Rozdelenie aj zlucovanie rychle. Moze byt pouzity binary tree pre pamatanie si volnych a plnych blokov.
Zapory - internal (chcem 66kb - da mi 128kb) a external fragmentation (vela 64kb blokov roztrusenych ale ziadny 128kb blok).

------------------------------------------------------------------------------------------------------------
16. Describe what a heap allocator can do to reduce the overhead of the virtual
memory manager.

Statistiky overheadu pro konkrtn aplikace uvdej 4% pro best fist, 7% pro first fit na FIFO seznamu volnch bloku, 50% pro first fit na LIFO seznamu volnch bloku, 60% pro buddy system.

------------------------------------------------------------------------------------------------------------
17. Explain the function of a garbage collector.

A garbage collector replaces the explicit freeing of blocks with an automatic freeing of blocks that are no longer used.
A garbage collector needs to recognize when a block on the heap is no longer used.
A garbage collectors determines whether a block is no longer used by determining
whether it is reachable, that is, whether a process can follow a chain of references from statically or locally allocated variables, called roots, to reach the block.

------------------------------------------------------------------------------------------------------------
18. Define precisely the conditions under which a memory block can be freed by a
reference tracing garbage collector.

What is reachable object:
   1. A distinguished set of objects are assumed to be reachable -- these are known as the roots. Typically, these include all the objects referenced from anywhere in the call stack (that is, all local variables and parameters in the functions currently being invoked), and any global variables.
   2. Anything referenced from a reachable object is itself reachable. This is referred to as transitivity.
Predpokladam ze vsetko non-reachable moze ist do /dev/null

------------------------------------------------------------------------------------------------------------
19. Describe the algorithm of a copying garbage collector.

Vsetko sa alokuje v oblasti 1. Ked sa zaplni, tzn. "root" mnozina objektov sa skopiruje do oblasti 2, a vsetky objekty, na ktore sa da dostat z root setu sa tam skopiruju tiez, a tak dalej az po vsetky dosiahnutelne objekty. Potom sa alokuje uz iba do oblasti 2 (v oblasti 1 nam zostali objekty, ktore boli nedosiahnutelne, cela oblast sa oznaci za cistu), a ked sa 2ka zaplni, zase to iste do oblasti 1.

------------------------------------------------------------------------------------------------------------
20. Describe the algorithm of a mark and sweep garbage collector.

A "mark and sweep" garbage collector maintains a bit (or two) with each object to record whether it is white or black; the grey set is either maintained as a separate list or using another bit. As the reference tree is traversed during a collection cycle, these bits are manipulated by the collector to reflect the current state. The mark and sweep strategy has the advantage that, once the unreachable set is determined, either a moving or non-moving collection strategy can be pursued; this choice of strategy can even be made at runtime, as available memory permits. It has the disadvantage of "bloating" objects by a small amount.

------------------------------------------------------------------------------------------------------------
21. Describe the algorithm of a generational garbage collector.

It has been empirically observed that in many programs, the most recently created objects are also those most likely to quickly become unreachable (known as infant mortality or the generational hypothesis). A generational GC divides objects into generations and, on most cycles, will place only the objects of a subset of generations into the initial white (condemned) set. Furthermore, the runtime system maintains knowledge of when references cross generations by observing the creation and overwriting of references. When the garbage collector runs, it may be able to use this knowledge to prove that some objects in the initial white set are unreachable without having to traverse the entire reference tree. If the generational hypothesis holds, this results in much faster collection cycles while still reclaiming most unreachable objects.
