Aufgabe 4. Speicher

Question 1

Welche Art von TLB wird benötigt, um die Verwendung eines betriebssystemspezifischen Seitentabellenformats zur Übersetzung von virtuellen zu physischen Adressen zu erlauben? Begründen Sie Ihre Antwort. (1 pt) What type of TLB is required to support an operating system specific page table format for the translation of virtual to physical addresses. Explain your answer.

Accepted Answer

Ein Software-TLB (0,5 P) ist erforderlich. TLB-Fehlschläge werden an das betriebene System übergeben, das die Seitentabellen in der Software (0,5 P) ablaufen muss. Das Seitentabellenformat kann also vom Betriebssystem gewählt werden.A software-TLB (0.5 P) is required. TLB-misses are handed over to the operatingsystem, which has to walk the page tables in software (0.5 P). The page table formatcan thus be chosen by the operating system.

Question 2

Betrachten Sie ein System, das mittels Seitentabellen 24 bit virtuelle in 48 bit physische Adressen übersetzen soll. Jede Seite umfasst 4 KiB. Bewerten Sie folgende Seitentabellentypen nach ihrer Eignung für das gegebene System: (1) einstufige Seitentabelle, (2) mehrstufige Seitentabelle, (3) invertierte Seitentabelle. (3 pt) Consider a system that should translate 24 bit virtual addresses to 48 bit physical addresses using page tables. Each page is 4 KiB in size. Evaluate the following types of page tables for use in the given system: (1) single-level page table, (2) multi-level page table, (3) inverted page table.

Accepted Answer

Bei 24-Bit-virtuellen Adressen und 4 KiB-Seiten ist ein einziger Adressraum nur 16 MiBgroß, bestehend aus 4096 Seiten. Angenommen, bei einer PTE-Größe von 8 Bytes können wir 512 PTEs pro Seite speichern.Dies gibt insgesamt nur 8 Seiten, um den gesamten Adressraum abzubilden.Der virtuelle Adressraum ist also klein genug, um eine einstufige Seitentabelle zu rechtfertigenohne große Mengen an Speicher zu verschwenden (1 P). Im Gegensatz zur mehrstufigen Seitentabelle, benötigt die einstufige Seitentabelle nur einen Speicherzugriff, um das Problem eines fehlenden TLB zu lösen (1 P). Die invertierte Seitentabelle eignet sich nicht gut, um virtuelle zu physischerAdressenübersetzung als beteiligte lineare Suche umzuwandeln (1 P). Vor allem, wenn wir bedenken, dass das System offensichtlich entworfen wurde, um große Mengen an physischem Speicher zu unterstützen(Über viele kleine Adressräume).With 24 bit virtual addresses and 4 KiB pages, a single address space is only 16 MiBin size, comprising 4096 pages. Assuming a PTE size of 8 bytes, we can store 512PTEs per page. This gives a total of only 8 pages to map the whole address space.The virtual address space is thus small enough to justify a single-level page tablewithout wasting huge amounts of memory (1 P). In contrast to the multi-level pagetable, the single-level page table requires only one memory access to resolve a TLBmiss (1 P). The inverted page table is not well suited to perform virtual to physicaladdress translation as a linear search is involved (1 P). Especially, if we considerthat the system is obviously designed to support large amounts of physical memory(across many small address spaces).

Question 3

Gegeben ist folgende zweistufige, hierarchische Seitentabelle. Die Größe einer Seite betrage 8 KiB. Geben Sie die Große des virtuellen Adressraumes (VAS) in Bytes an. Zerlegen und Übersetzen Sie anschließend die virtuelle Adresse 0x04DA61FA. (5 pt) Consider the following two-level, hierarchical page table. The page size is 8 KiB. Give the size of the virtual address space (VAS) in bytes. Then, split and translate the virtual address 0x04DA61FA. Bitte Seitentabelle anschauen bei 03.03.2016 Aufgabe 4 c)!!!!!!!!!!

Accepted Answer

Die Tabellen der 1. und 2. Ebene enthalten jeweils 512 = 29 (0x1F F = 511) Einträge. Diesergibt 512 * 512 = 29 * 29 = 218 Seiten. Jede einzelne Seite ist 213 = 8 KiB Groß. Der Adressraum ist also 218 * 213 = 231 Bytes groß (1 P).Für 8 KiB-Seiten benötigen wir 13 Bits für das Offset. Die angegebene Seitentabelle benötigt 9 Bits für jeden der beiden indizes. Durch Aufteilung der virtuellen Adresse bekommen wir entsprechend:1. Level Seitentabellenindex: 0x013 (1 P)2. Level Seitentabellenindex: 0x0D3 (1 P)Offset: 0x01FA (1 P)Um die physische Adresse zu bekommen, folgen wir den Seitentabellen zum PFN: 0x402F (0,5P).Der PFN ist auf dem Bitlevel verkettet mit dem Offset: 0x0805E1FA (0,5 P)The 1st and 2nd level page tables contain512 = 29(0x1F F = 511) entries each. Thisgives 512 ∗ 512 = 29 ∗ 29 = 218 pages. Eachpage is 213 = 8 KiB in size. The addressspace is thus 218 ∗ 213 = 231 bytes large (1 P).For 8 KiB pages, we need 13 bits for theoffset. The given page table requires 9 bitsfor each of the two indices. By splitting thevirtual address accordingly, we get:1st Level Page Table Index: 0x013 (1 P)2nd Level Page Table Index: 0x0D3 (1 P)Offset: 0x01FA (1 P)To get the physical address, we follow thepage tables to the PFN: 0x402F (0.5 P).The PFN is than concatenated on the bitlevelwith the offset: 0x0805E1FA (0.5 P)

Question 4

Welche Information muss ein Seitentabelleneintrag mindestens enthalten, damit das Working-Set eines Prozesses bestimmt werden kann? (1 pt) What information must a page table entry contain at least to allow determining a process’ working-set?

Accepted Answer

Referenzbit (1 P)Reference bit (1 P)

Question 5

Wieso kann eine beliebige Zuweisung von physischen zu virtuellen Seiten zu einer verminderten Ausführungsgeschwindigkeit führen, wenn ein physically-indexed, physically-tagged Cache verwendet wird? Nennen Sie eine Strategie zur Allokation von physischen Seiten, die diesem Problem entgegenwirkt. (2 pt) An arbitrary assignment of physical pages to virtual pages can lead to reduced execution performance when working with a physically-indexed, physically-tagged cache. What might be the reason? What strategy for the allocation of physical pages can be used to mitigate the problem?

Accepted Answer

Ein physikalisch indizierter, physikalisch markierter Cache verwendet die physikalische Adresse, um die Position der Daten im Cache zu bestimmen. Virtuelle Seiten im Arbeitssatz eines Prozesses mit einer willkürlichen Zuordnung, sind eher auf physische Seiten zu kartieren.Wenn auf sie zusammen zugegriffen wird, entstehen Cache-Konflikte oder es entsteht nur eine partielle Cache-Nutzung(1 P). Es gibt auch eine hohe Chance, dass bei jedem Lauf des Programms, das OS verschiedene physikalische Seiten zuweißt, die zu weniger deterministischen Ausführungsleistungen führen können.Page coloring kann verwendet werden, um das Problem zu lindern (1 P).A physically-indexed, physically-tagged cache uses the physical address to determinethe position of data in the cache. With an arbitrary assignment, the virtualpages in the working set of a process are more likely to map to physical pages that,when accessed together, produce cache conflicts or lead to only partial cache use(1 P). There is also a high chance that with every run of the program, the OS allocatesdifferent physical pages, which can result in less deterministic execution performance.Page coloring can be used to mitigate the problem (1 P).

Question 6

Zerlegen Sie die virtuelle Adresse 0x58D4E004 wie es für eine Adressübersetzung mit einer zweistufigen, hierarchischen Seitentabelle notwendig ist. Geben Sie dabei für jeden Teil seinen Wert an, wozu er dient und wie viele Bits er umfasst. Gehen Sie davon aus, dass jede Stufe aus 1024 Eintragen besteht und eine Seite 4096 Bytes umfasst. (3 pt) Split the virtual address 0x58D4E004 into the parts that are necessary for an address translation with a two-level, hierarchical page table. For every part, give its value, denote its purpose and state its size in bits. Every level comprises 1024 entries. The page size is 4096 bytes.

Accepted Answer

Page Directory Index (10 Bits) Index im Seitenverzeichnis, um die Seitentabelle auszuwählen,die den Eintrag zur Adressübersetzung enthält. Wert: 0x163Page Table Index (10 Bits) Index in der Seitentabelle, die den richtigen Seitentabellenindex auswählt, um die Seitenrahmennummer zu erhalten. Wert: 0x14EOffset (12 Bits) Offset in die Seite, die mit der Seitenrahmennummer nach der Übersetzung verkettet ist. Wert: 0x004(1 P) jeweils ein halber Punkt wird für einen Fehler abgezogen.Page Directory Index (10 bits) Index into the page directory, to select the page table,which contains the entry for address translation. Value: 0x163Page Table Index (10 bits) Index into the page table, which selects the right pagetable index to get the page frame number. Value: 0x14EOffset (12 bits) Offset into the page, which is concatenated to the page frame numberafter translation. Value: 0x004(1 P) each. Half-points were deducted for mistakes.

Question 7

Nennen Sie je einen Vorteil von hardware- und softwaregesteuerten TLBs. (2 pt) Give one advantage for both hardware-managed and software-managed TLBs.

Accepted Answer

Hardware-verwaltete TLB:• Schnelleres TLB-Miss-Handling, durch das ablaufen der Seitentabellen und das Einfügen der richtigen Eintragung in das TLB in Hardware (dies beinhaltet eine Ersatzrichtlinie in Hardware)Software-verwaltete TLB:• Vollständige Flexibilität im Seitentabellenformat• Vollständige Flexibilität in der Ersatzpolice(1 P) Beachten sie jeweils, dass in einem Software-verwalteten TLB Einträge in der Hardware auch verglichen werden! Einfache "schnelle" - oder "flexiblere" - Antworten wurden im Allgemeinen als zu vage bewertet.Hardware-managed TLB:• Faster TLB-miss handling, by walking the page tables and inserting the correctentry into the TLB in hardware (this includes a replacement policy in hardware)Software-managed TLB:• Full flexibility in the page-table format• Full flexibility in the replacement policy(1 P) each. Note that in a software-managed TLB, entries are compared in hardware,too! Plain ”fast”- or ”more flexible”-answers were generally rated as too vague.

Question 8

Wann eignen sich einstufige Seitentabellen zur Übersetzung von virtuellen zu physischen Adressen? Erläutern Sie Ihre Antwort. (1 pt) When are single-level page tables suitable for the translation of virtual to physical addresses? Explain your answer.

Accepted Answer

Wenn die Breite des virtuellen Adressenraums klein ist (z.B. weniger als 32 Bits),die Seite groß ist oder der Adressraum weitgehend verwendet wird (d.h. nicht spärlich wie gewöhnlich).In diesen Fällen nimmt die einstufige Seitentabelle nicht zu viel Speicher auf oder sichert sogar Speicher im Vergleich zu hierarchischen Seitentabellen.(0,5 P) für ein Szenario, (0,5 P) aus dem GrundWhen the width of the virtual address space is small (e.g., less than 32 bits), the pagesize is large or the address space is extensively used (i.e. not sparsely as usually).In these cases, the single-level page table does not take up too much memory or evensaves memory compared to hierarchical page tables.(0.5 P) for a scenario, (0.5 P) for the reason

Question 9

Erläutern Sie das Konzept einer invertierten Seitentabelle. Warum sind sie beim Einsatz von gemeinsam genutztem Speicher (Shared Memory) von Vorteil? (3 pt) Explain the concept of inverted page tables. Why are they advantageous when using shared memory?

Accepted Answer

Inverted-Seitentabellen bilden physikalische Frames auf virtuellen Seiten anstatt auf andere Weise.Das System hat also nur eine einzige invertierte Seitentabelle für alle Prozesse miteinem Seitentabelleneintrag für jeden physischen Seitenrahmen. Beachten Sie, dass invertierte Seitentabellen keine Frames beschränken, die auf eine einzige virtuelle Seite abgebildet werden sollen. Ein Seitentabelleneintrag in der invertierten Seitentabelle kann mehrere Tupel enthalten.(1,5 P)Bei Verwendung von gemeinsam genutztem Speicher muss das Betriebssystem häufig (z. B. für Seitenersatz) für einen bestimmten Seitenrahmen wissen, ob es geteilt wird, und wenn ja, welche virtuelle Seiten-Karte der Frame. Diese Informationen können einfach in der invertierten Seitentabelle gespeichert werden. (1,5 P)Inverted page tables map physical frames to virtual pages instead of the other wayaround. The system thus has only a single inverted page table for all processes withone page table entry for each physical page frame. Note that inverted page tables donot limit a frame to be mapped to a only single virtual page. A page table entry in theinverted page table may hold multiple

tuples.(1.5 P)When using shared memory, the OS often (e.g., for page replacement) needs to knowfor a particular page frame whether it is shared, and if so, which virtual pages mapthe frame. This information can be easily stored in the inverted page table. (1.5 P)

Question 10

Welche Eigenschaft wird bei der FIFO, LRU und optimalen Seitenersetzung zur Auswahl der zu ersetzenden Seite jeweils herangezogen? Erläutern Sie für jede Eigenschaft, ob, und wenn ja, wie sie in einem Betriebssystem auf x86 (näherungsweise) gewonnen werden kann. (3 pt) What attribute is used for the FIFO, LRU and optimal page replacement to select the victim page? For each attribute, state whether, and if so, how it can be collected or approximated in an operating system running on x86 hardware.

Accepted Answer

FIFO Die Reihenfolge, in der Seiten dem System hinzugefügt wurden (d.h. die Zeit in dereine bestimmte Seite geholt wurde). Kann explizit gespeichert werden.LRU Die Reihenfolge, in der auf die Seiten zugegriffen wurden (d.h. die Zeit, in der auf einer bestimmten Seite zum letzten Mal zugegriffen wurde). Nicht direkt verfügbar, kann aber angenähert werden durch periodisches Abtasten des Referenzbits.Optimal Die Reihenfolge, auf die Seiten in der Zukunft zugegriffen werden (d.h. die Zeit, in der auf die jeweilige Seite das nächste Mal zugegriffen wird). Nicht verfügbar.(1 P) jeweils. Lösungen, die die jeweiligen Richtlinien beschreiben und darauf hinweisen, wie sie sind. Kann auf x86 implementiert werden auch akzeptiert werdenFIFO The order in which pages have been added to the system (i.e., the time aparticular page has been fetched). Can be stored explicitly.LRU The order in which pages have been accessed (i.e., the time a particular pagehas been accessed the last time). Not directly available, but can be approximatedby periodically scanning the reference bit.Optimal The order in which pages will be accessed in the future (i.e., the time aparticular page will be accessed the next time). Not available.(1 P) each. Solutions that described the respective policies and indicated how theycan be implemented on x86 were also accepted

Question 11

Betrachten Sie ein System, das mittels einer zweistufigen, hierarchischen Seitentabelle virtuelle in physische Speicheradressen übersetzt. Jede Stufe besteht aus 1024 ¨ Eintragen. Sowohl der virtuelle als auch der physische Adressraum sind 4 GiB groß, wobei jede Seite 4096 Bytes umfasst. Die Wortbreite des Prozessors betragt 4 Bytes. In welche Teile wird eine virtuelle Adresse im gegebenen System für die Adressübersetzung zerlegt? Nennen Sie jeweils die Breite in Bits. Consider a system that translates virtual addresses to physical addresses using twolevel, hierarchical page tables. Every level comprises 1024 entries. The size of both the virtual and the physical address spaces is 4 GiB. The page size is 4096 bytes. The word length of the CPU is 4 bytes. Into which parts is a virtual address in the given system split to perform address translation. For each part give its length in bits.

Accepted Answer

Seitenverzeichnisindex, Seitentabellenindex und Byteoffset (1 Pt).4 GiB Adressraum ⇒ 32 Bit Adressen. Die Längen sind: 10 Bits (PD), 10 Bits (PT),12 Bits (Offset) (1 Pt).Page directory index, page table index and byte offset (1 Pt).4 GiB address space ⇒ 32 bit addresses. The lengths are: 10 bits (PD), 10 bits (PT),12 bits (Offset) (1 Pt).

Question 12

Erklären Sie kurz, was man unter lokaler und globaler Seitenersetzung versteht. (2 pt) Shortly explain the terms local and global page replacement.

Accepted Answer

Local: Für den Austausch werden nur Frames des Fehlerprozesses berücksichtigt (1 Pt).Global: Alle Frames werden als Ersatz ausgelegt. Ein Prozess kann einen Frame von einem anderen nehmen(1 Pt).Local: Only frames of the faulting process are considered for replacement (1 Pt).Global: All frames are considered for replacement; one process can take a framefrom another (1 Pt).

Question 13

Wie viele physische Seiten werden mit Pre-Paging maximal benötigt um einen zusammenhangenden Puffer der Länge 4 MiB in einen bereits laufenden Benutzerprozess einzublenden? Gehen Sie davon aus, dass der Puffer an Wortgrenzen, nicht jedoch an Seitengrenzen ausgerichtet ist. (2 pt) How many physical pages are required in the worst case with pre-paging to map a 4 MiB contiguous memory buffer into a running user process? Assume that the buffer is word-, but not page-aligned.

Accepted Answer

4 MiB Puffer und 4 KiB Seiten ⇒ 1024 Frames, um den Puffer (0,5 Pt) zurücksetzen.Der Puffer ist nicht seiten-ausgerichtet. Wir brauchen also einen weiteren Frame um bei überlappung anpassungen vorzunehmen. Um den Puffer sichtbar in einem Benutzer-Prozess zu machen, benötigen wir zwei zusätzliche Frames für die Seitentabellen. Ein Rahmen für das Seitenverzeichnis wird nicht benötigt, da der Prozess bereits läuft (1,5 Pt).Gesamt: 1024 + 1 + 2 = 1027 Frames.4 MiB buffer and 4 KiB pages ⇒ 1024 frames to back the buffer (0.5 Pt).The buffer is not page-aligned. We therefore need another frame to accommodatefor overlap. Additionally, to make the buffer visible in a user process, we requiretwo extra frames for the page tables. A frame for the page directory is not neededbecause the process is already running (1.5 Pt).Total: 1024 + 1 + 2 = 1027 frames.

Question 14

Betrachten Sie ein System, das mittels einer zweistufigen, hierarchischen Seitentabelle virtuelle in physische Speicheradressen übersetzt. Jede Stufe besteht aus 1024 Einträgen. Sowohl der virtuelle als auch der physische Adressraum sind 4 GiB groß, wobei jede Seite 4096 Bytes umfasst. Die Wortbreite des Prozessors betragt 4 Bytes. Wie viele Speicherzugriffe muss die CPU maximal durchfuhren um diesen Puffer vollständig zu lesen, wenn weder TLB noch Cache vorhanden sind? Jeder Zugriff umfasst ein Wort. (2 pt) How many memory accesses does the CPU have to perform in the worst case to read this entire buffer without a TLB or cache, reading one word at a time?

Accepted Answer

4 MiB Puffer und 4 Byte Worte ⇒ 1 M greift auf den Puffer zu um ihn zu lesen (1 Pt).Für jeden Zugriff wird der Seitenverzeichniseintrag (PDE) und der Seitentabelleneintrag (PTE) benötigt um die Adressübersetzung zu lesen (1 Pt).Gesamt: 1M + (2 * 1M)Auch toleriert: 4M + (2 * 4M) wenn Leseadresse nur ein Byte (nicht Wort) zu einer bestimmten Zeit inkrementiert wird.4 MiB buffer and 4 byte words ⇒ 1 M accesses to read the buffer (1 Pt).For each access the page directory entry (PDE) and the page table entry (PTE) needto be read for address translation (1 Pt).Total: 1M + (2 ∗ 1M)Also tolerated: 4M + (2 ∗ 4M) if read address is incremented only one byte (not word)at a time.

Question 15

Würde der Einsatz eines TLB die Anzahl der benötigten Speicherzugriffe reduzieren? Begründen Sie Ihre Antwort. (1 pt) Would a TLB reduce the number of required memory accesses? Explain your answer

Accepted Answer

Ja (0,5 Pt). Mit einem TLB hätte nur der erste Zugriff auf eine Seite einen Lookup in derSeitentabellenhierarchie (0,5 Pt).Yes (0.5 Pt). With a TLB, only the first access to a page would require a lookup in thepage table hierarchy (0.5 Pt).

Question 16

Bewerten Sie folgende Aussage: Speicherallokation mit dem Buddy-System ist frei von Fragmentierung. Begründen Sie Ihre Antwort. (1 pt) Evaluate the following statement: Memory allocation with the buddy-system is free of fragmentation. Explain your answer.

Accepted Answer

Die Aussage ist falsch (0,5 Pt). Das Buddy-System leidet unter intern und externFragmentierung (0,5 Pt).The statement is wrong (0.5 Pt). The buddy system suffers from internal and externalfragmentation (0.5 Pt).

Question 17

Für jede CPU in einem Mehrprozessorsystem enthält die Struktur MyStruct einen Zähler, den die entsprechende CPU häufig aktualisiert. Obwohl die CPUs auf getrennten Zählern arbeiten, ist die Performance schlecht. Woran liegt das? Welche grundsätzliche Modifikation an MyStruct schlagen Sie vor? (2 pt) For each CPU of a multi-processor-system the structure MyStruct contains a counter, which the respective CPU updates frequently. The CPUs access different variables, though the performance is poor. Why? What general modification to MyStruct can you propose? struct MyStruct { int counterForCpu1 ; int counterForCpu2 ; } ;

Accepted Answer

Die Zähler werden auf der gleichen Cache-Zeile platziert. Das führt zu einem erfolgreichen Performance-Hit bei häufigen gegenseitigen Cache-Line-Invalidierungen bei Updates (1 Pt).Eine Lösung besteht darin, jedem Zähler eine Polsterung hinzuzufügen, um sie auf verschiedene Cache-Zeilen zu zwingen (1 Pt).Auch toleriert: Verwenden Sie separate Strukturen für jeden Zähler und Zeiger. Beachten Sie, dass das im allgemeinen nicht bedeutet, dass der Speicherzuweiser (z. B. malloc) dieZähler bei Adressenauf auf verschiedene Cache-Zeilen abbildet!The counters are placed on the same cache line. That leads to a performance hit dueto frequent mutual cache line invalidation on updates (1 Pt).A solution is to add padding to each counter to force them onto different cache lines(1 Pt).Also tolerated: Use separate structures for each counter and pointers. Note that ingeneral this does not guarantee that the memory allocator (e.g., malloc) positions thecounters at addresses mapping to different cache lines!

Question 18

Ausgehend von einem typischen Speicherlayout fur Prozesse: Für welche der folgenden Sektionen eines Prozesses wird anonymer Speicher alloziert? Wofür kann ein Betriebssystem beim Swapping das Wissen ausnutzen, dass es sich bei einer Seite um nicht-anonymen Speicher handelt? (2 pt) Assume a common memory layout for processes. For which of the following sections of a process is anonymous memory allocated? When swapping, how can an operating system take advantage of the knowledge that a page contains non-anonymous memory?

Accepted Answer

X StackX Heap TextX BSS• Anonymer Speicher ist nicht mit einer bestimmten Datei verknüpft er wird z.B. fürProzess-Stacks oder Heap Seiten benutzt, wenn eine Seite des anonymen Speichers vertrieben wird.Die Seite muss auf den Festplatten-basierten Swap-Speicherplatz für den späteren Abruf geschrieben werden.Deshalb, wenn eine Seite von nicht-anonymer Speicher gewählt wird, um vertrieben zu werden, kann die Seite verworfen und später wieder aus der entsprechenden Datei gelesen werden. So können unnötige schreiben zum austauschgebiet vermieden werden. (1P)• -0.5P für jeden falschen, fehlenden Eintrag Stack Heap Text BSS• Anonymous memory is not associated with a specific file. It is e.g. used forprocess stacks or heap pages. When a page of anonymous memory is evicted,the page has to be written to disk-based swap space for later retrieval.Therefore, when a page of non-anonymous memory is chosen to be evicted, thatpage can be discarded and later be read from the appropriate file again. Bydoing so, unnecessary writes to the swapping area can be avoided. (1P)• -0.5P fur jeden falschen, fehlenden Eintrag

Question 19

Erklären Sie knapp, was man unter interner und externer Fragmentierung im Kontext von Speicherallokation versteht. Beschreiben Sie jeweils eine Situation, in der dies auftreten kann. (2 pt) Briefly explain the terms internal and external fragmentation in the context of memory allocation. For each one, describe a situation in which it may occur

Accepted Answer

• Interne Fragmentierung (0.5P): Wenn nicht alle zugeteilten Speicher verwendet werden, ist der verbleibende Raum verschwendet.Der zugeordnete Speicher kann etwas größer sein als der angeforderte Speicherwegen den Ausrichtungsanforderungen oder der Verwendung von festen Trenngrößen. Das unbenutzte Fragment befindet sich in der zugewiesenen Partition.- Beispiele (0,5P):* Zuordnung mit Seitengranularität in einem Adressraum, z.B. Paging (nur für die letzte Seite)• Externe Fragmentierung (0.5P): Gesamtspeicherplatz existiert, um eine Anforderung zu erfüllen, aber es ist nicht zusammenhängend, während das Zuteilungsschema nur angrenzend die Zuweisung unterstützt. Die unbenutzten Fragmente sind zwischen zugeordneten Speicherblöcken.- Beispiele (0,5P):* Zusammenhängende Zuordnung, z.B. Segmentierung (zwei nicht aufeinanderfolgende freie Blöcke des Speichers, das in der Summe eine Anforderung befriedigen könnte, aber kann nicht weil der Speicher nicht zusammenhängend ist).• Internal Fragmentation (0.5P): Not all of the allocated memory is used, the remainingspace is wasted.Allocated memory may be slightly larger than requested memory because ofalignment requirements or the use of fixed partition sizes. The unused fragementis inside the allocated partition.– Examples (0.5P):∗ Allocation with page granularity in an address space, e.g. Paging (only for the last page)• External Fragmentation (0.5P): Total memory space exists to satisfy a request,but it is not contiguous while the allocation scheme only support contiguousallocation. The unused fragments are between allocated blocks of memory.– Examples (0.5P):∗ Contiguous allocation, e.g. Segmentation (two non-consecutive free blocksof memory that in sum could satisfy a request, but cannot because thememory is not contiguous).

Question 20

Erklären Sie knapp, was man unter Kompaktierung im Zusammenhang mit externer Fragmentierung versteht, und unter welcher Bedingung Kompaktierung anwendbar ist. (1 pt) Briefly explain the term compaction in the context of external fragmentation, and under which condition compaction is applicable.

Accepted Answer

• Reduzierung der externen Fragmentierung durch Verdichtung. Mischt Speicherinhalt um alle freien Speicher zusammen in einem großen Block zu platzieren. (0,5P)• Die Verdichtung ist nur möglich, wenn die Verlagerung dynamisch ist (d.h. die Speicherreferenzen müssen bei dem Verschieben eines Programms von einer Region zur anderen gültig bleiben) und ist fertig in der Ausführungzeit. (0,5P)• Reduce external fragmentation by compaction. Shuffle memory contents to placeall free memory together in one large block. (0.5P)• Compaction is possible only if relocation is dynamic (i.e. the memory referencesmust remain valid when moving a program from one region to another), and isdone at execution time. (0.5P)

Question 21

Beschreiben Sie die nötigen Schritte, um einen Seitenfehler im Addressraum einer Anwendung zu behandeln (typischerweise 6, inkl. Reaktivierung). (3 pt) Describe the steps necessary to handle a page fault in an application’s address space (typically 6, incl. reactivation).

Accepted Answer

• Wenn ein Seitenfehler auftritt, prüft der Seitenfehlerbehandler zunächst, ob ein Zugriffauf die entsprechende Seite legal ist oder nicht. (0,5P)• Ist dies nicht der Fall, wird die Anwendung wahrscheinlich abgebrochen. Wenn es legal ist, muss der Handler einen freien Frame finden und reservieren . (0,5P)• Wenn es keine gibt, wird der Seitenersatzalgorithmus aufgerufen, der einen Frame wählt, dessen Inhalt auf die Festplatte geschrieben ist und die danach für etwas anderes wiederverwendet werden kann. (0,5P)• Der Seitenfehlerbehandler muss dann den richtigen Inhalt in den Frame laden:In einigen Fällen (z. B. ein neuer Frame für einen wachsenden Stack oder Heap) genügt es, den Frame mit Nullen zu füllen; In anderen Fällen muss der richtige Inhalt von der Festplatte abgerufen werden (z. B. wenn die Seite zuvor ausgetauscht wurde). (0,5P)• Sobald der Frame mit den korrekten Daten gefüllt ist, muss der Seitenfehler-Handler seineSeitentabellen anpassen, indem Sie die neue Zuordnung erstellen und ein gültiges Bit setzen.(0,5P)• Die fehlerhafte Anwendung kann nun ihre Ausführung fortsetzen. (0,5P) • When a page fault occurs, the page fault handler first checks whether an accessto the appropriate page is legal or not. (0.5P)• If it is not, the application is probably aborted. If it is legal, the handler has tofind and allocate a free frame. (0.5P)• If there is none, the page replacement algorithm is invoked, which chooses aframe whose contents are written to disk and which can afterwards bereused for something else. (0.5P)• The page fault handler then has to load the correct contents into the frame:In some cases (e.g., a new frame for a growing stack or heap) it suffices to fillthe frame with zeros; in other cases, the correct contents have to be retrievedfrom disk (e.g., when the page was previously swapped out). (0.5P)• Once the frame is filled with the correct data, the page fault handler needs toadapt the page tables by inserting the new mapping and setting the valid bit.(0.5P)• The faulting application can now resume its execution. (0.5P)

Question 22

Wie groß ist der maximal adressierbare virtuelle Speicher bei einer dreistufigen Seitentabelle mit 1024 Einträgen pro Stufe? Gehen Sie davon aus, dass jede Seite 8 KiB umfasst und der Speicher byte-weise addressierbar sein soll. Wie viele Bits müssen virtuelle Adressen in diesem Fall mindestens lang sein, damit der Adressraum den gesamten Speicher abdeckt? (1 pt) How large is the maximally addressable virtual memory when using a threelevel page table with each level comprising 1024 entries? Assume that a page is 8 KiB in size and that the memory should be byte-addressable. What is the minimal length (in bits) for virtual addresses such that the address space covers the entire memory?

Accepted Answer

MaxAddressableVirtualMemory = 8 KiB × 1024 × 1024 × 1024 = 8 T iB (0.5P)MinVirtualAddressLength = 13 Bits + 10 Bits + 10 Bits + 10 Bits = 43 Bits (0.5P)

Question 23

Skizzieren Sie ein geeignetes minimales Format für virtuelle Adressen (für das System mit einer dreistufigen Seitentabelle). (1 pt) Sketch a suitable minimal format for virtual addresses (for the system with a threelevel page table.).

Accepted Answer

42 33 32 23 22 13 12 01st level index 2nd level index 3rd level index Page offsetDer TLB mit 4096 Eintragen basiert auf einem 4-Wege Satz-assoziativem Cache. Welche Bits dienen als Set-Index und welche als Tag, wenn eine Teilfolge derAdressbits als Set-Index genutzt wird. (1 pt)The TLB contains 4096 entries and is based on a 4-way set associative cache. Whichbits serve as the set index and which as the tag, if a sub-sequence of the addressbits is used as set index. .......................42 23 22 13Tag Index• Index: identifiziert den Satz im TLB• Tag: identifiziert den Eintrag im Set• Index: identifies the set in the TLB• Tag: identifies the entry in the set

Question 24

Was sind Aliase im Zusammenhang mit virtuell-indizierten Daten-Caches? Welche Bedingung muss ein Betriebssystem erfüllen, damit diese im Daten-Cache auftreten können? (1 pt) What are aliases in the context of virtually-indexed data caches? Which condition has to be satisfied by an operating system such that these can occur in the data cache?

Accepted Answer

• Alias: verschiedene virtuelle Adressen zeigen auf denselben physikalischen Speicherplatz.(0,5P)• Das Betriebssystem muss es erlauben, einem physischen Speicherplatz mehr zuzuordnenals einem virtuellen Speicherplatz: shared memory (0.5P)• Alias: different virtual addresses point to the same physical memory location.(0.5P)• The operating system must allow to map a physical memory location to morethan one virtual memory location: shared memory (0.5P)

Question 25

Vergleichen Sie die zwei Szenarien, reine Segmentierung und reines Paging (mit einer Seitengröße von 4 KiB). Betrachten Sie hierzu das Beispiel eines Programms mit 15 KiB Text-Segment, 5 KiB nur lesbaren Daten und 4 KiB Stack. Der physische Speicher ist zunächst leer. Dann wird das beschriebene Programm geladen. Die Segmente werden hierzu in der gegebenen Reihenfolge hintereinander im physischen Speicher abgelegt (beginnend bei Adresse 0). An welchen physischen Adressen beginnen Text-Segment, Daten und Stack in den beiden Szenarien? Tritt in der Speicherbelegung aus Teilaufgabeder obigen Teilaufgabe Fragmentierung auf? Wenn ja, welche Art und in welchem Umfang? (2 pt) Compare the two scenarios pure segmentation and pure paging (with 4 KiB page size). For this purpose, consider the example of a program with 15 KiB text segment, 5 KiB read-only data, and 4 KiB stack segment. Assume the physical memory is empty at first. Then, the program we described above is loaded. The segments are placed in physical memory consecutively in the given order (starting at address 0). What are the physical starting addresses of text segment, data, and stack in the two scenarios respectively? Is there fragmentation in the memory allocation from question a)? If yes, state the type and the amount of fragmentation. Segmentierung / Segmentation:

Accepted Answer

Segment Startadresse mit Segmentierung Startadresse mit Paging Starting address with segmentation Starting address with pagingText Segment 0 KiB 0 KiBDaten (data) 15 KiB 16 KiBStack Segment 20 KiB 24 KiB+0.5P for every correct start address (i.e., per table entry).-keine fragmentierung(+1P). Paging:-no fragmentation (+1P). Paging:Interne Fragmentierung (+ 0,5P) von insgesamt 4 KiB (+ 0,5P).Internal fragmentation (+0.5P) of 4 KiB in total (+0.5P).

Question 26

Welche Arten von Fragmentierung wurden in der Vorlesung vorgestellt? (1 pt) Which kinds of fragmentation have been introduced in the lecture?

Accepted Answer

Interne Fragmentierung (+ 0,5P) und externe Fragmentierung (+ 0,5P).Internal fragmentation (+0.5P) and external fragmentation (+0.5P).

Question 27

Komplettieren Sie die folgende einstufige Pagetable für den Start-Zeitpunkt des oben beschriebenen Programms gemäß den folgenden Kriterien: • Ein Prozess nutzt den virtuellen Adressraum im Bereich von 0 bis 3 GB. TextSegment und Daten werden am Anfang, der Stack am Ende dieses Bereichs platziert. • Zugriffsrechte seien so restriktiv wie möglich. • Das Betriebssystem verwende on-demand paging für den Stack und pre-paging für den Programm-Code und Daten. Physische Seiten werden in der Reihen- folge der Pagetable-Eintrage zugewiesen, beginnend bei Adresse 0. • Markieren Sie Eintrage, deren Inhalt nicht verwendet wird, mit einem Binde- strich (-). Markieren Sie Bits als gesetzt (1), nicht gesetzt (0), oder beliebig (-). (4 pt) Complete the following single-level pagetable for the start time of the program described above, according to these guidelines: • A process utilizes the virtual address space from 0 to 3 GB. Text and data are placed at the beginning, the stack at the end of that range. • Access rights have to be as constraint as possible. • The operating system uses on-demand paging for the stack and pre-paging for program code and data. Physical pages are assigned in the order of the pagetable entries, beginning at address 0. • Mark unused entries with a dash (-); mark bits as set (1), reset (0), or arbitrary (-).

Accepted Answer

Index Physical Frame Number read write execute valid 0 0 1 0 1 1 1 1 1 0 1 1 2 2 1 0 1 1 3 3 1 0 1 1 4 4 1 0 0 1 5 5 1 0 0 1 6 - - - - 0 ... ...786430 - - - - 0786431 - - - - 0 ... ...• Text hat die Bildnummern 0 bis 3 zugewiesen. (+0,5)• Die Daten haben die Bildnummern 4 und 5 (+0,5)• Stapel hat keine zugewiesene Seitennummer. (+0,5)• Text und Daten haben die gültigen Bits gesetzt. (+0,5)• Stack hat sein gültiges Bit unset. (+0,5)• pt Eintrag 6 hat - - - - 0. (+0.5)• Text hat Berechtigungen r-x. (+0,5)• Daten haben Berechtigungen r- -. (+0,5)• text has assigned frame numbers 0 to 3. (+0.5)• data has assigned frame numbers 4 and 5. (+0.5)• stack has no assigned page number. (+0.5)• text and data have the valid bits set. (+0.5)• stack has its valid bit unset. (+0.5)• pt entry 6 has - - - - 0. (+0.5)• text has permissions r-x. (+0.5)• data has permissions r- -. (+0.5)

Question 28

Welches Ereignis geschieht beim ersten Zugriff eines Prozesses auf seinen Stack, wenn das Betriebssystem on-demand paging verwendet? (2 pt) Wie reagiert das Betriebssystem darauf, damit der Prozess anschliessend weiterlaufen kann? Which event happens the first time a process accesses its stack if the operating system uses on-demand paging? How does the operating system react to this event, in order that the process continues to run afterwards?

Accepted Answer

Die CPU / MMU erzeugt einen Seitenvorsprung (+ 0,5P). Das Betriebssystem dann:• Zuweisungen physikalischen Speichers / eine physikalische Seite für die gerade zugegriffene Seite (+ 0.5P)• Aktualisiert die Pagetabelle des Prozesses, Einstellung des gültigen Bits der fehlerhaften Seite, (+ 0,5P)• und setzt die Ausführung des Prozesses fort, indem der fehlerhafte Befehle neu startet (+ 0,5P)The CPU/MMU generates a pagefault (+0.5P). The operating system then• assigns physical memory / a physical page for the page just accessed, (+0.5P)• updates the pagetable of the process, setting the valid bit of the faulting page,(+0.5P)• and continues the execution of the process by restarting the faulting instruction.(+0.5P)

Question 29

Nennen sind die zwei Ursachen für das Auftreten von Seitenfehlern aus Sicht der MMU. Erläutern Sie jeweils kurz wie das Betriebssystem diese üblicherweise behandelt. (3 p) Give the two causes for page faults from the MMU’s perspective. Briefly explain how the operating system typically handles each cause.

Accepted Answer

(A) Keine gültige Zuordnung für die zugegriffene Adresse (0,5 P). Das aktuelle / gültige Bit in der PTE ist nicht gesetzt. Wenn der Zugriff auf einen gültigen Speicherbereich gerichtet ist, wird ein Frame geladen mit entsprechenden Inhalten und auf der Seite (0,5 P) . Der Vorgang wird neu gestartet (0,5 P).(B) Gültige Zuordnung, aber der Zugriff nicht zulässig (0,5 P) (z. B. auf schreibgeschützte Seite schreiben).Der Vorgang wird beendet (1 P). Alternative Antwort: Die Ausnahme wird weitergeleitetan den Prozess.(a) No valid mapping for the accessed address (0.5 P). The present/valid bit in thePTE is not set. If the access is directed to a valid memory region, a frame is loadedwith appropriate contents and mapped to the page (0.5 P). The operation is restarted(0.5 P).(b) Valid mapping, but access not permitted (0.5 P) (e.g., write on read-only page).The process is terminated (1 P). Alternative answer: The exception is forwarded tothe process.

Question 30

Gegeben sei ein System mit vier physischen Seitenrahmen. Vervollständigen Sie die Übersetzungstabelle für einen Prozess der auf virtuelle Seiten in der unten angegebenen Reihenfolge zugreift. Verwenden Sie den Clock-Algorithmus zur Seitenersetzung. Nehmen Sie an, dass der zirkulare Puffer der Uhr in aufsteigender Reihenfolge der Rahmennummern sortiert ist (Rahmen 0, 1, 2, 3), die Hand der Uhr initial auf Rahmen 0 (unterstrichen) zeigt und das Referenzbit (R) für die Seite 0 gesetzt ist. (5 pt) Consider a system with four page frames. Complete the mapping table for a process that accesses virtual pages in the order given below with clock page replacement. Assume the circular buffer of the clock to be in ascending order (i.e., frame 0, 1, 2, 3), the clock hand to be initially positioned at frame 0 (underlined), and the reference bit (R) for page 0 to be set.

Accepted Answer

Frames Seiten (t0) Seiten (t1) Seiten (t2) Seiten (t3) Seiten (t4) Seiten(t5) 0 2 5 (R) 5 (R) 5 (R) 5 3 (R) 1 0 (R) 0 (R) 0 0 1 (R) 1 (R) 2 4 4 2 (R) 2 (R) 2 (R) 2 3 3 3 3 4 (R) 4 (R) 4Zugriffsfolge auf virtuelle Seiten / Virtueller Seitenreferenzstring: 5 2 4 1 3Referenzbit- und Taktpositionsmarkierungen wurden nicht benötigt. -0,5 P für jeden Fehler.Korrektes Ausfüllen der Tabelle für einen Algorithmus, der sich von der Uhr unterscheidetDer in der Vorlesung gelehrte Algorithmus wurde nicht akzeptiert!Frames Pages(t0) Pages(t1) Pages(t2) Pages(t3) Pages(t4) Pages(t5) 0 2 5 (R) 5 (R) 5 (R) 5 3 (R) 1 0 (R) 0 (R) 0 0 1 (R) 1 (R) 2 4 4 2 (R) 2 (R) 2 (R) 2 3 3 3 3 4 (R) 4 (R) 4Zugriffsfolge auf virtuelle Seiten/Virtual page reference string: 5 2 4 1 3Reference bit and clock position markings were not required. -0.5 P for each mistake.Correctly filling out the table for an algorithm that differs from the clockalgorithm taught in the lecture was not accepted!

Question 31

Geben Sie je ein Beispiel an, wann das Betriebssystem einzelne bzw. mehrere Einträge in einem TLB ohne Tagging invalidieren muss. (1 pt) When does the operating system need to invalidate individual entries in a non-tagged TLB? When does the operating system need to invalidate multiple entries? Give one example each.

Accepted Answer

Wenn die Abbildung (d.h. PTE) einer Seite geändert wurde (0,5 P) (z. B. ausgetauschte Seite,Änderung der Zugriffsrechte, neue Zuordnung usw.), muss der entsprechende TLB-Eintrag ungültig gemacht werden. Mehrere / alle Einträge müssen bei einem Adressraumwechsel ungültig gemacht werden. (0,5 P).If the mapping (i.e., PTE) of a page has been changed (0.5 P) (e.g., swapped page,change of access rights, new mapping, etc.), the corresponding TLB entry must beinvalidated. Multiple / all entries must be invalidated on an address space switch(0.5 P).

Question 32

Wie groß ist der maximal adressierbare virtuelle Speicher bei einer dreistufigen Seitentabelle mit 4 Einträgen in der oberste Seitentabelle und 512 Einträgen in den folgenden Stufen? Gehen Sie davon aus, dass jede Seite 4 KiB umfasst und der Speicher byte-weise adressierbar sein soll. Wie viele Bits muss die virtuelle Adresse mindestens lang sein, um den gesamten Adressraum abzudecken? (1 pt) What is the size of the maximally addressable virtual memory when using a threelevel page table hierarchy with 4 entries in the top-most level and 512 entries in each following level? Assume each page to be 4 KiB in size and that the memory should be byte-addressable. What is the minimal length (in bits) for a virtual address that can cover the entire address space?

Accepted Answer

MaxAddressableVirtualMemory = (22 ∗ 29 ∗ 29) ∗ 212 = 232 = 4 GiB (0.5 P)MinVirtualAddressLength = 32 (0.5 P)

Question 33

Diskutieren Sie Vor- und Nachteile von Demand-Paging und Pre-Paging. (2 pt) Discuss advantages and disadvantages of demand-paging and pre-paging.

Accepted Answer

Demand-Paging überträgt nur das, was benötigt wird (0,5 P) und braucht damit potentiell weniger Speicher (0,5 P). Pre-Paging kann auf der anderen Seite den I / O-Durchsatz durch lesen in größere Stücke verbessern (0,5 P), während die Nachfrage-Paging viele kleine Anfragen erzeugt wrden (füreinzelne Seiten). Kann Pre-paging jedoch die I / O-Bandbreite vergeuden, wenn Seiten nicht benötigt werden (0,5 P).Demand-paging only transfers what is needed (0.5 P) and thus potentially uses lessmemory (0.5 P). Pre-paging on the other side can improve I/O throughput by readingin larger chunks (0.5 P) while demand-paging produces many small requests (forindividual pages). Pre-paging may, however, waste I/O bandwidth if pages are notneeded (0.5 P).

Question 34

Betrachten Sie ein System, das mittels einer hierarchischen Seitentabelle virtuelle in physische Speicheradressen übersetzt. Eine Seitentabelle umfasst 512 Einträge, wobei jeder Eintrag 8 Bytes benötigt. Sowohl der virtuelle als auch der physische Adressraum sind 512 GiB groß, wobei jede Seite 4096 Bytes umfasst. Wie viel physischer Speicher wurde für eine volle Seitentabellenhierarchie benötigt? Erläutern Sie Ihre Rechnung. (4 p) Consider a system that translates virtual addresses to physical addresses using hierarchical page tables. Every page table comprises 512 entries, with each entry having a size of 8 bytes. The size of both the virtual and the physical address spaces is 512 GiB. The page size is 4096 bytes. How much physical memory is required for a full page table hierarchy? Explain your answer.

Accepted Answer

Die Anzahl der Seiten in einem 512 GiB Adressraum beträgt 512 GiB = 128 M i = 227. 4 KiBEin Pagetable hat 512 = 29 Einträge ⇒ 227 = 218 Seitentabellen (0,5 P). 29Um eine Hierarchie mit 512 Einträgen pro Tabelle zu erstellen benötigen wir zwei zusätzliche level die Seitentabellen zu beschriften: 218 = (29) 2 = 5122 (0,5 P). Das gibt uns 512 + 1 extra Seitentabellen für insgesamt 218 + 29 + 1 Seitentabellen in drei Ebenen (0,5 P).Eine einzelne Seitentabelle ist 512 * 8 Bytes = 4 KiB = 1 Seitengröße.Gesamt: 218 + 29 + 1 Seiten physikalischen Speicher (0,5 P).The number of pages in a 512 GiB address space is 512 GiB = 128 M i = 227. 4 KiB A pagetable has 512 = 29 entries ⇒ 227 = 218 page tables (0.5 P) .To form a hierarchy with 29512 entries per table we need two extra levels to addressthe page tables: 218 = (29)2 = 5122(0.5 P) . That gives us 512 + 1 extra page tables fora total of 218 + 29 + 1 page tables in three levels (0.5 P) .A single page table is 512 ∗ 8 bytes = 4 KiB = 1 page in size.Total: 218 + 29 + 1 pages of physical memory (0.5 P) .

Question 35

Nennen Sie einen Vor- und einen Nachteil von großen Seiten (4 MiB) gegenüber kleinen Seiten (4 KiB). (2 pt) Give one advantage and one disadvantage of huge pages (4 MiB) compared to small pages (4 KiB).

Accepted Answer

Pro: Weniger Platz für Seitentabellen (1 P), höhere TLB Reichweite (1 P), effizientere Festplattenzugriff beim Paging (1 P) .Contra: Interne Fragmentierung (1 P).Pro: Less space for page tables (1 P) , higher TLB reach (1 P) , more efficient diskaccesses when paging (1 P) .Contra: Internal fragmentation (1 P) .

Question 36

Bewerten Sie folgende Aussage: Der Heap-Allokator (malloc) ist Teil des Betriebssystemkerns. Begründen Sie Ihre Antwort. (1 pt) Evaluate the following statement: The heap allocator (malloc) is part of the operating system kernel. Explain your answer.

Accepted Answer

Die Aussage ist falsch (0,5 P). Ein Heap-verteiler befindet sich im Benutzerraum als Teil voneiner Systembibliothek. Es reserviert riesige Speicherblöcke aus dem Betriebssystem underfüllt Speicheranforderungen (malloc) durch Zuweisung aus diesen Regionen (0,5 P).The statement is wrong (0.5 P) . A heap allocator resides in user-space as part ofa system library. It reserves huge memory chunks from the operating system andsatisfies memory requests (malloc) by allocating from these regions (0.5 P) .

Question 37

Ein Prozess greift zum ersten Mal auf eine Seite einer in den Speicher eingeblendeten Datei zu. Das Betriebssystem verwendet Demand-Paging. Welche Schritte sind zur Behandlung des Seitenfehlers nötig? (3 pt) A process accesses a page of a memory-mapped file for the first time. The operating system uses demand-paging. What steps are necessary to handle the page fault?

Accepted Answer

• Überprüfen Sie, ob der Zugriff in einem gültigen Adressraum liegt (ja ist er) (0,5 P).• Holen Sie sich einen leeren Seiten-Frame, um die Daten der Seite der im Speicher erfassten Datei zuzuordnen. Dies beinhaltet möglicherweise die Vertreibung einer anderen Seite aus dem Speicher (0,5 P).• Laden des Inhalts der angeforderten Seite vom Datenträger in den Frame (0,5 P).• Passen Sie die Seitentabelle an, um die neue Zuordnung wiederzugeben. (0,5 P).• Setzen Sie das gültige Bit des Seitentabelleneintrags (0,5 P).• Starten Sie die Anweisung neu, die den Seitenfehler verursacht hat (0,5 P).Variation mit Seitencache auch gültig.• Check if access is in a valid address space region (yes it is) (0.5 P) .• Get an empty page frame to hold the data for the page of the memory-mappedfile. This potentially includes evicting another page from memory (0.5 P) .• Load contents of requested page from disk into frame (0.5 P) .• Adapt the page table to reflect the new mapping. (0.5 P) .• Set the valid bit of the page table entry (0.5 P) .• Restart the instruction that caused the page fault (0.5 P) .Variation with page cache also valid.

Question 38

Wie löst man das Problem der Bedeutungsgleichheit (Alias) in einem System mit einem virtually-indexed, virtually-tagged Cache? (1 pt) How do you solve the alias problem in a system with a virtually-indexed, virtuallytagged cache?

Accepted Answer

Alias-Problem: verschiedene virtuelle Adressen zeigen auf denselben physischen Speicherplatz, aber der voll-virtuelle Cache würde sie auf verschiedenen Cache-Zeilen abbilden.Wir können entweder das Caching für Seiten, die unter Aliasing leiden, deaktivieren (0,5 P) oder wir beschränken Zuordnungen zu solchen virtuellen Adressen, die alle Aliase auf die gleiche Cache-Zeile in einem direkt zugeordneten Cache abbilden. (0,5 P)Alias problem: different virtual addresses point to the same physical memory location,but the fully-virtual cache would map them to different cache lines.We can either disable caching for pages the suffer from aliasing, (0.5 P) or we restrictmappings to such virtual addresses that all aliases map to the same cache line in adirect-mapped cache. (0.5 P)

Question 39

Was versteht man unter dem Working Set eines Prozesses? (1 pt) What is the working set of a process?

Accepted Answer

Der Arbeitssatz ist die Menge von Seiten, auf den ein Prozess in einem vorgegebenen Zeitrahmen zugreift (1 P).The working set is the set of pages that a process accesses in a given time frame (1 P) .

Question 40

Betrachten Sie ein System, welches virtuelle Adressen mittels dreistufiger Seitentabellen auf physische Adressen übersetzt. Virtuelle Adressen sind 32 Bit lang, und physische Adressen sind 64 Bit lang. Die Seitengröße beträgt 4 KiB. Jede Seitentabelle besteht aus 8 Byte langen Einträgen. Die erste Stufe besteht aus nur 4 Einträgen, und die tieferen beiden aus je 512 Einträgen. Der Speicher ist byteadressierbar. Hinweis: Ergebnisse in Form von Zweierpotenzen sind ausreichend. a) In welche vier Teile muss eine virtuelle Adresse zerlegt werden, um eine Adressübersetzung durchführen zu können? Aus wie vielen Bits besteht jeder dieser Teile unter den oben genannten Voraussetzungen? b) Wie groß ist der adressierbare virtuelle Speicher (in GiB)? (1P) Consider a system that uses three-level page-tables to translate virtual addresses to physical addresses. Virtual addresses are 32 bit long, and physical addresses are 64 bit long. The page size is 4 KiB. Each page-table consists of 8 bytes long entries. The first level consists of only 4 entries, und the lower two consist of 512 entries each. Note: Results in form of powers of two are sufficient. a) Into which four parts must a virtual address be split so that it can be translated into a physical address? How many bits are required for each part under the assumptions stated above? a) How large is the addressable virtual Memory (in GiB)?

Accepted Answer

a)• 1-st Ebene Index (aka Seiten-verzeichnis-tabelle), 2 Bits• 2-nd-Level-Index (aka Seitenverzeichnis), 9 Bits• 3-ter Level-Index (aka Seitentabelle), 9 Bits• Einstiegsindex (aka offset), 12 Bits+ 0,5P für Nennung von lvl 1 bis 3 (zusammen, nicht jeweils),+ 0,5P für Nennung von Offset / Einstieg,Jeweils + 0,5P für korrekt angegebene Bit-Länge.• 1-st level index (aka page directory table), 2 bits• 2-nd level index (aka page directory), 9 bits• 3-rd level index (aka page table), 9 bits• entry level index (aka offset), 12 bits+0,5P für Nennung von lvl 1 bis 3 (zusammen, nicht jeweils),+0,5P für Nennung von offset/entry level,jeweils +0,5P für korrekt angegebene bit-Länge.b) • 232Byte = 4GiB (+1P)

Question 41

Wie viel Speicher benötigt die gesamte Seitentabelle eines Prozesses mindestens, falls diesem 1 GiB Speicher zugewiesen wurde? Ignorieren Sie den durch die erste Stufe belegten Speicher. (3 pt) How much memory does the entire page table of a process consume at least if the process has been allocated 1 GiB of memory? Ignore the consumption of the first level.

Accepted Answer

• # of pages = # of page table entries =1GiB = 230 = 218 (+1P) 4KiB 22x210 • min. # of page tables =218 = 29 (+1P) 29 • min. # of page directories = 29 = 1 (+0.5P) 29 • memory consumption = 29×4KiB + 1×4KiB = 210×2KiB + 4KiB = 2M iB + 4KiB(+0.5P

Question 42

Der TLB mit 4096 Einträgen basiert auf einem 8-Wege Satz-assoziativem Cache. a) Aus wie vielen Sätzen besteht der TLB? (0.5 pt) b) Welche Stufen der Seitentabelle werden durch den TLB beschleunigt? (0.5 pt) c) Welche Bits dienen als Set-Index und welche als Tag, wenn eine Teilfolge der Adressbits als Set-Index genutzt wird? The TLB contains 4096 entries and is based on a 8-way set associative cache. How many sets does the TLB consist of? Which levels of the page table are speed up by the TLB? Which bits serve as the set index and which as the tag, if a sub-sequence of the address bits is used as set index?

Accepted Answer

a) • 4096 = 512 sets (+0.5P) 8 b) • All three (+0.5P)c) 31 21 20 12 Tag Index• Index: identifiziert den Satz im TLB• Tag: identifiziert den Eintrag im Set+ 0,5P für Tag und richtige Bit-Grenzen + 0,5P für Index und richtige Bit-Grenzen• Index: identifies the set in the TLB• Tag: identifies the entry in the set+0,5P für Tag und richtige Bit-Grenzen +0,5P für Index und richtige Bit-Grenzen

Question 43

Bestimmen Sie die effektive Speicherzugriffszeit unter der Annahme, dass ein Lookup in unserem TLB 20 ns und ein Speicherzugriff 100 ns dauert und dass der TLB eine durchschnittliche Trefferrate von 75% hat. Nehmen Sie an, dass das System keine weiteren Caches außer dem TLB besitzt. Geben Sie den Rechenweg in nachvollziehbarer Form an, nicht nur das Ergebnis. (3 pt) Calculate the effective memory access time, assuming that a lookup in our TLB takes 20 ns, a memory access takes 100 ns, and that the TLB has an average hit ratio of 75%. Assume that the system uses no caches apart from the TLB. Include all calculation steps in your answer, not just the result.

Accepted Answer

• Grundformel: 0.75 × Hit + 0.25 × Miss (+0.5P)• Hit: 20ns + 100ns = 120ns (+1P)• Miss: 20ns + 100ns + 100ns + 100ns + 100ns = 420ns (+1P)• Ergebnis: 195ns (+0.5P)

Question 44

Betrachten Sie ein System, das mittels einer zweistufigen, hierarchischen Seitentabelle virtuelle in physische Speicheradressen übersetzt. Jede Stufe besteht aus 1024 Einträgen. Sowohl der virtuelle als auch der physische Adressraum sind 4 GiB groß, wobei jede Seite 4096 Bytes umfasst. a)Zerlegen Sie die virtuelle Adresse 0xD4008A40 wie es für eine Adressübersetzung im gegebenen System notwendig ist. Geben Sie dabei für jeden Teil an, wozu er dient und wie viele Bits er umfasst. Consider a system that translates virtual addresses to physical addresses using twolevel, hierarchical page tables. Every level comprises 1024 entries. The size of both the virtual and the physical address spaces is 4 GiB. The page size is 4096 bytes. a)Split the virtual address 0xD4008A40 into the parts that are necessary for an address translation in the given system. For every part, denote its purpose and state its size in bits.

Accepted Answer

4 GiB Adressräume ⇒ 32 Bit Adressen.1024 Einträge pro Seitentabelle ⇒ 10 Bits pro Level, um die Seitentabelleneinträge zu adressieren12 Bits für den Byte-Offset, um 4096 Bytes auf einer Seite zu adressieren.First-Level-Index: 0x350 = (0xD4008A40 >> 22) (1pt)Zweitniveau-Index: 0x008 = ((0xD4008A40 >> 12) & 0x3FF) (1pt)Byte-Offset: 0xA40 = (0xD4008A40 & 0xFFF) (1pt)4 GiB address spaces ⇒ 32 bit addresses.1024 entries per page table ⇒ 10 bits per level to address page table entries, leaving12 bits for the byte offset to address 4096 bytes in a page.First-level index: 0x350 = (0xD4008A40 >> 22) (1pt)Second-level index: 0x008 = ((0xD4008A40 >> 12) & 0x3FF) (1pt)Byte offset: 0xA40 = (0xD4008A40 & 0xFFF) (1pt)

Question 45

Betrachten Sie ein System, das mittels einer zweistufigen, hierarchischen Seitentabelle virtuelle in physische Speicheradressen übersetzt. Jede Stufe besteht aus 1024 Einträgen. Sowohl der virtuelle als auch der physische Adressraum sind 4 GiB groß, wobei jede Seite 4096 Bytes umfasst. a)Zerlegen Sie die virtuelle Adresse 0xD4008A40 wie es für eine Adressübersetzung im gegebenen System notwendig ist. Geben Sie dabei für jeden Teil an, wozu er dient und wie viele Bits er umfasst. b) Fuhren Sie mit Hilfe der gegebenen Seitentabellenhierarchie eine manuelle Übersetzung der aus Aufgabe a) bekannten Adresse durch und geben Sie die entsprechende physische Adresse an. (1 pt) Siehe Schaubild von 18.09.2012 Aufgabe 4 b)!!!!!!!!!!!!!!!!!!!!!!! Consider a system that translates virtual addresses to physical addresses using twolevel, hierarchical page tables. Every level comprises 1024 entries. The size of both the virtual and the physical address spaces is 4 GiB. The page size is 4096 bytes. a)Split the virtual address 0xD4008A40 into the parts that are necessary for an address translation in the given system. For every part, denote its purpose and state its size in bits. b) Based on the given page table hierarchy, perform a manual address translation of the virtual address from question a) and calculate the corresponding physical address.

Accepted Answer

a)4 GiB Adressräume ⇒ 32 Bit Adressen.1024 Einträge pro Seitentabelle ⇒ 10 Bits pro Level, um die Seitentabelleneinträge zu adressieren12 Bits für den Byte-Offset, um 4096 Bytes auf einer Seite zu adressieren.First-Level-Index: 0x350 = (0xD4008A40 >> 22) (1pt)Zweitniveau-Index: 0x008 = ((0xD4008A40 >> 12) & 0x3FF) (1pt)Byte-Offset: 0xA40 = (0xD4008A40 & 0xFFF) (1pt)b)Übersetzungsweg: 0x350 → 0x008 → 0x2F2Rahmen: 0x2F2 (0.5pt), Adresse: 0x002F2A40 (0.5pt) (führende Nullen sind optional)a)4 GiB address spaces ⇒ 32 bit addresses.1024 entries per page table ⇒ 10 bits per level to address page table entries, leaving12 bits for the byte offset to address 4096 bytes in a page.First-level index: 0x350 = (0xD4008A40 >> 22) (1pt)Second-level index: 0x008 = ((0xD4008A40 >> 12) & 0x3FF) (1pt)Byte offset: 0xA40 = (0xD4008A40 & 0xFFF) (1pt)b) Translation path: 0x350 → 0x008 → 0x2F2Frame: 0x2F2 (0.5pt), Address: 0x002F2A40 (0.5pt) (leading zeros are optional)

Question 46

Wie kann in einem System mit virtuellem Speicher und Demand Paging die Anzahl von Seitenfehlern durch das Hinzufugen von Pre-Paging reduziert werden? (1 pt) How can pre-paging reduce the number of page faults in a system with virtual memory and demand paging?

Accepted Answer

Pre-paging kann die Anzahl der Seitenfehler reduzieren, indem man Seiten von der Festplatte auf RAM überträgt, bevor ein Prozess auf sie zugreift. (1pt)Pre-paging can reduce the number of page faults by transfering pages from disk toRAM before a process accesses them. (1pt)

Question 47

Ist es möglich, dass es durch Pre-Paging zu mehr Seitenfehlern kommen kann? Wenn ja, wie? Wenn nicht, was verhindert dies? (1 pt) Is it possible that pre-paging leads to more page faults? If yes, how? If not, what prevents this?

Accepted Answer

Ja, Pre-Paging kann auch die Anzahl der Seitenfehler erhöhen, da es hoch spekulativ ist.Es kann zu einer Verwerbung von gebrauchten Seiten führen, obwohl die vorinstallierten Seiten nicht erforderlich sind. (1pt)Yes, pre-paging may also increase the number of page faults as it is highly speculative.It may lead to the eviction of used pages, although the pre-loaded pages are notneeded.(1P)

Question 48

Erklären Sie kurz, was man unter interner und externer Fragmentierung versteht. Geben Sie jeweils ein Beispiel an, wo diese auftreten können. (3 pt) Shortly explain the terms internal and external fragmentation. For each one, give an example where it may occur

Accepted Answer

Intern: Der zugeordnete Speicher kann etwas größer sein als der angeforderte Speicher (wegen der Ausrichtungsanforderungen); Die unbenutzte Fraktion befindet sich innerhalb der zugeordneten Partition.(1pt)Beispiel: Zuordnung mit Seitengranularität in einem Adressraum (0,5pt)Extern: Gesamtspeicherplatz existiert, um eine Anfrage zu erfüllen, aber es ist nicht zusammenhängend.(1pt)Beispiel: Heap (0,5pt)Internal: Allocated memory may be slightly larger than requested memory (becauseof alignment requirements); the unused fragement is inside the allocated partition.(1pt)Example: Allocation with page granularity in an address space (0.5pt)External: Total memory space exists to satisfy a request, but it is not contiguous.(1pt)Example: Heap (0.5pt)

Question 49

In der Vorlesung wurde eine Methode zur Reduktion von externer Fragmentierung vorgestellt. Um welches Verfahren handelt es sich? Eignet sich dieses Verfahren, um externe Fragmentierung im virtuellen Adressraum eines laufenden Prozesses zu verringern? Begründen Sie Ihre Antwort! (1 pt) In the lecture, a method has been presented that is capable of reducing external fragmentation. How is this method called? Is this technique suitable to reduce external fragmentation in the virtual address space of a running process? Justify your answer!

Accepted Answer

Die Methode heißt Verdichtung. (0,5pt)Die Technik ist nicht geeignet, da sie Speicherreferenzen im laufenden Prozess ungültig macht. (0,5pt)Alternative: Die Technik ist (nur) in verwalteten Ausführungsumgebungen geeignet.(0,5pt)The method is called Compaction. (0.5pt)The technique is not suitable, because it invalidates memory references in the runningprocess. (0.5pt)Alternative: The technique is (only) suitable in managed execution environments.(0.5pt)

Question 50

Bei Copy-On-Write werden die gleichen physischen Seiten (z.B. von Programmbibliotheken) in die Adressräume mehrerer Prozesse eingeblendet. Um die Speicherisolation zwischen den Prozessen zu gewährleisten, wird bei Schreibvorgängen auf diese Seiten durch das Betriebssystem eine private Kopie angelegt. Wie erkennt das Betriebssystem solche Schreibvorgänge? (1 pt) With copy-on-write, the same page frames (e.g. from libraries) are mapped into the virtual address spaces of multiple processes. To guarantee that the memory isolation between the processes remains intact, the operating system creates a private copy of pages on write operations. How does the operating system detect such write operations?

Accepted Answer

Die Seiten sind schreibgeschützt. (0,5pt)Bei Schreiboperationen löst die CPU einen Seitenfehler aus und ruft damit das Betriebssystem auf. (0,5pt)The pages are mapped read-only. (0.5pt)On write operations the CPU triggers a page fault and thereby invokes the operatingsystem. (0.5pt)

OS (Subject) / Aufgabe 4. Speicher (Lesson)