Subversion Repositories HelenOS-doc

Compare Revisions

Ignore whitespace Rev 34 → Rev 35

/design/trunk/src/ch_memory_management.xml
8,32 → 8,161
<title>Virtual memory management</title>
 
<section>
<title>Introduction</title>
 
<para>Virtual memory is a special memory management technique, used by
kernel to achieve a bunch of mission critical goals. <itemizedlist>
<listitem>
Isolate each task from other tasks that are running on the system at the same time.
</listitem>
 
<listitem>
Allow to allocate more memory, than is actual physical memory size of the machine.
</listitem>
 
<listitem>
Allowing, in general, to load and execute two programs that are linked on the same address without complicated relocations.
</listitem>
</itemizedlist></para>
</section>
 
<section>
 
<title>Paging</title>
 
 
<para>Virtual memory is usually using paged memory model, where virtual
memory address space is divided into the <emphasis>pages</emphasis>
(usually having size 4096 bytes) and physical memory is divided into the
frames (same sized as a page, of cause). Each page may be mapped to some
frame and then, upon memory access to the virtual address, CPU performs
<emphasis>address translation</emphasis> during the instruction
execution. Non-existing mapping generates page fault exception, calling
kernel exception handler, thus allowing kernel to manipulate rules of
memory access. Information for pages mapping is stored by kernel in the
<link linkend="page_tables">page tables</link></para>
 
 
<para>The majority of the architectures use multi-level page tables,
which means need to access physical memory several times before getting
physical address. This fact would make serios performance overhead in
virtual memory management. To avoid this <link linkend="tlb">Traslation
Lookaside Buffer (TLB)</link> is used.</para>
 
 
<para>At the moment HelenOS does not support swapping.</para>
 
- pouzivame vypadky stranky k alokaci ramcu on-demand v ramci as_area - na architekturach, ktere to podporuji, podporujeme non-exec stranky
</section>
 
<section>
<title>Address spaces</title>
 
<para />
<section>
<title>Address spaces and areas</title>
 
<para>- adresovy prostor se sklada z tzv. address space areas
usporadanych v B+stromu; tyto areas popisuji vyuzivane casti
adresoveho prostoru patrici do user address space. Kazda cast je dana
svoji bazovou adresou, velikosti a flagy (rwx/dd).</para>
 
<para>- uzivatelske thready maji moznost manipulovat se svym adresovym
prostorem (vytvaret/resizovat/sdilet) as_areas pomoci syscallu</para>
</section>
 
<section>
<title>Address Space ID (ASID)</title>
 
<para>- nektery hardware umoznuje rozlisit ruzne adresove prostory od
sebe (cilem je maximalizovat vyuziti TLB); dela to tak, ze s kazdou
polozkou TLB/strankovacich tabulek sdruzi identifikator adresoveho
prostoru (ASID, RID, ppc32 ???). Tyto id mivaji ruznou sirku: 8-bitu
az 24-bitu (kolik ma ppc32?)</para>
 
<para>- kernel tomu rozumi a sam pouziva abstrakci ASIDu (na ia64 to
je napr. cislo odvozene od RIDu, na mips32 to je ASID samotny);
existence ASIDu je nutnou podminkou pouziti _global_ page hash table
mechanismu.</para>
 
<para>- na vsech arch. plati, ze asidu je mnohem mene, nez teoreticky
pocet soucasne bezicich tasku ~ adresovych prostoru, takze je
implementovan mechanismus, ktery umoznuje jednomu adresovemu prostoru
ASID odebrat a pridelit ho jinemu</para>
 
<para>- vztah task ~ adresovy prostor: teoreticky existuje moznost, ze
je adresovy prostor sdilen vice tasky, avsak tuto moznost nepouzivame
a neni ani nijak osetrena. Tim padem plati, ze kazdy task ma vlastni
adresovy prostor</para>
</section>
</section>
 
<section>
<title>Virtual address translation</title>
 
<para />
</section>
<section id="page_tables">
<title>Page tables</title>
 
<para>Page tables. 4 level hierarchical and hash directly supported. B+
Tree can be implemented.</para>
<para>HelenOS kernel has two different approaches to the paging
implementation: <emphasis>4 level page tables</emphasis> and
<emphasis>global hash tables</emphasis>, which are accessible via
generic paging abstraction layer. This division was caused by the
major architectural differences between different platforms.</para>
 
<para>For paging there is an abstract layer</para>
<formalpara>
<title>4-level page tables</title>
 
<para>TLB shootdown implementation (update TLB upon mapping
update/remove). TLB shootdown ASID/ASID:PAGE/ALL. TLB shootdown requests
can come in asynchroniously so there is a cache of TLB shootdown requests.
Upon cache overflow TLB shootdown ALL is executed</para>
<para>4-level page tables are the generalization of the hardware
capabilities of the certain platforms. <itemizedlist>
<listitem>
ia32 uses 2-level page tables, with full hardware support.
</listitem>
 
<para>Address spaces. Address space area (B+ tree). Only for uspace. Set
of syscalls (shrink/extend etc). Special address space area type - device
- prohibits shrink/extend syscalls to call on it. Address space has link
to mapping tables (hierarchical - per Address space, hash - global
tables).</para>
<listitem>
amd64 uses 4-level page tables, also coming with full hardware support.
</listitem>
 
<listitem>
mips and ppc32 have 2-level tables, software simulated support.
</listitem>
</itemizedlist></para>
</formalpara>
 
<formalpara>
<title>Global hash tables</title>
 
<para>- global page hash table: existuje jen jedna v celem systemu
(vyuziva ji ia64), pozn. ia64 ma zatim vypnuty VHPT. Pouziva se
genericke hash table s oddelenymi collision chains</para>
</formalpara>
 
<para>Thanks to the abstract paging interface, there is possibility
left have more paging implementations, for example B-Tree page
tables.</para>
</section>
 
<section id="tlb">
<title>Translation Lookaside buffer</title>
 
<para>- TLB cachuji informace ve strankovacich tabulkach; alternativne
se lze na strankovaci tabulky (ci ruzne hw rozsireni [e.g. VHPT, ppc32
hw hash table]) divat jako na velke TLB</para>
 
<para>- pri modifikaci mapovani nebo odstraneni mapovani ze
strankovacich tabulek je potreba zajistit konsistenci TLB a techto
tabulek; nutne delat na vsech CPU; na to mame zjednodusenou verzi TLB
shootdown mechanismu; je to variace na algoritmus popsany zde: D.
Black et al., "Translation Lookaside Buffer Consistency: A Software
Approach," Proc. Third Int'l Conf. Architectural Support for
Programming Languages and Operating Systems, 1989, pp. 113-122.</para>
 
<para>- nutno poznamenat, ze existuji odlehcenejsi verze TLB shootdown
algoritmu</para>
</section>
</section>
</section>
 
<!-- End of VM -->