ch9
54 pág.

ch9


DisciplinaSistemas Operacionais I8.353 materiais171.770 seguidores
Pré-visualização3 páginas
Galvin and Gagne \uf6d920029.21Operating System Concepts
Address Translation Architecture
Silberschatz, Galvin and Gagne \uf6d920029.22Operating System Concepts
Paging Example
Silberschatz, Galvin and Gagne \uf6d920029.23Operating System Concepts
Paging Example
Silberschatz, Galvin and Gagne \uf6d920029.24Operating System Concepts
Free Frames
Before allocation After allocation
Silberschatz, Galvin and Gagne \uf6d920029.25Operating System Concepts
Implementation of Page Table
\ufffd Page table is kept in main memory.
\ufffd Page-table base register (PTBR) points to the page table.
\ufffd Page-table length register (PRLR) indicates size of the
page table.
\ufffd In this scheme every data/instruction access requires two
memory accesses. One for the page table and one for
the data/instruction.
\ufffd The two memory access problem can be solved by the
use of a special fast-lookup hardware cache called
associative memory or translation look-aside buffers
(TLBs)
Silberschatz, Galvin and Gagne \uf6d920029.26Operating System Concepts
Associative Memory
\ufffd Associative memory \u2013 parallel search
Address translation (A´, A´´)
\u2726 If A´ is in associative register, get frame # out.
\u2726 Otherwise get frame # from page table in memory
Page # Frame #
Silberschatz, Galvin and Gagne \uf6d920029.27Operating System Concepts
Paging Hardware With TLB
Silberschatz, Galvin and Gagne \uf6d920029.28Operating System Concepts
Effective Access Time
\ufffd Associative Lookup = \u3b5 time unit
\ufffd Assume memory cycle time is 1 microsecond
\ufffd Hit ratio \u2013 percentage of times that a page number is
found in the associative registers; ration related to
number of associative registers.
\ufffd Hit ratio = \u3b1
\ufffd Effective Access Time (EAT)
EAT = (1 + \u3b5) \u3b1 + (2 + \u3b5)(1 \u2013 \u3b1)
= 2 + \u3b5 \u2013 \u3b1
Silberschatz, Galvin and Gagne \uf6d920029.29Operating System Concepts
Memory Protection
\ufffd Memory protection implemented by associating protection
bit with each frame.
\ufffd Valid-invalid bit attached to each entry in the page table:
\u2726 \u201cvalid\u201d indicates that the associated page is in the process\u2019
logical address space, and is thus a legal page.
\u2726 \u201cinvalid\u201d indicates that the page is not in the process\u2019 logical
address space.
Silberschatz, Galvin and Gagne \uf6d920029.30Operating System Concepts
Valid (v) or Invalid (i) Bit In A Page Table
Silberschatz, Galvin and Gagne \uf6d920029.31Operating System Concepts
Page Table Structure
\ufffd Hierarchical Paging
\ufffd Hashed Page Tables
\ufffd Inverted Page Tables
Silberschatz, Galvin and Gagne \uf6d920029.32Operating System Concepts
Hierarchical Page Tables
\ufffd Break up the logical address space into multiple page
tables.
\ufffd A simple technique is a two-level page table.
Silberschatz, Galvin and Gagne \uf6d920029.33Operating System Concepts
Two-Level Paging Example
\ufffd A logical address (on 32-bit machine with 4K page size) is
divided into:
\u2726 a page number consisting of 20 bits.
\u2726 a page offset consisting of 12 bits.
\ufffd Since the page table is paged, the page number is further
divided into:
\u2726 a 10-bit page number.
\u2726 a 10-bit page offset.
\ufffd Thus, a logical address is as follows:
where pi is an index into the outer page table, and p2 is the
displacement within the page of the outer page table.
page number page offset
pi p2 d
10 10 12
Silberschatz, Galvin and Gagne \uf6d920029.34Operating System Concepts
Two-Level Page-Table Scheme
Silberschatz, Galvin and Gagne \uf6d920029.35Operating System Concepts
Address-Translation Scheme
\ufffd Address-translation scheme for a two-level 32-bit paging
architecture
Silberschatz, Galvin and Gagne \uf6d920029.36Operating System Concepts
Hashed Page Tables
\ufffd Common in address spaces > 32 bits.
\ufffd The virtual page number is hashed into a page table. This
page table contains a chain of elements hashing to the
same location.
\ufffd Virtual page numbers are compared in this chain
searching for a match. If a match is found, the
corresponding physical frame is extracted.
Silberschatz, Galvin and Gagne \uf6d920029.37Operating System Concepts
Hashed Page Table
Silberschatz, Galvin and Gagne \uf6d920029.38Operating System Concepts
Inverted Page Table
\ufffd One entry for each real page of memory.
\ufffd Entry consists of the virtual address of the page stored in
that real memory location, with information about the
process that owns that page.
\ufffd Decreases memory needed to store each page table, but
increases time needed to search the table when a page
reference occurs.
\ufffd Use hash table to limit the search to one \u2014 or at most a
few \u2014 page-table entries.
Silberschatz, Galvin and Gagne \uf6d920029.39Operating System Concepts
Inverted Page Table Architecture
Silberschatz, Galvin and Gagne \uf6d920029.40Operating System Concepts
Shared Pages
\ufffd Shared code
\u2726 One copy of read-only (reentrant) code shared among
processes (i.e., text editors, compilers, window systems).
\u2726 Shared code must appear in same location in the logical
address space of all processes.
\ufffd Private code and data
\u2726 Each process keeps a separate copy of the code and data.
\u2726 The pages for the private code and data can appear
anywhere in the logical address space.
Silberschatz, Galvin and Gagne \uf6d920029.41Operating System Concepts
Shared Pages Example
Silberschatz, Galvin and Gagne \uf6d920029.42Operating System Concepts
Segmentation
\ufffd Memory-management scheme that supports user view of
memory.
\ufffd A program is a collection of segments. A segment is a logical
unit such as:
main program,
procedure,
function,
method,
object,
local variables, global variables,
common block,
stack,
symbol table, arrays
Silberschatz, Galvin and Gagne \uf6d920029.43Operating System Concepts
User\u2019s View of a Program
Silberschatz, Galvin and Gagne \uf6d920029.44Operating System Concepts
Logical View of Segmentation
1
3
2
4
1
4
2
3
user space physical memory space
Silberschatz, Galvin and Gagne \uf6d920029.45Operating System Concepts
Segmentation Architecture
\ufffd Logical address consists of a two tuple:
<segment-number, offset>,
\ufffd Segment table \u2013 maps two-dimensional physical
addresses; each table entry has:
\u2726 base \u2013 contains the starting physical address where the
segments reside in memory.
\u2726 limit \u2013 specifies the length of the segment.
\ufffd Segment-table base register (STBR) points to the
segment table\u2019s location in memory.
\ufffd Segment-table length register (STLR) indicates number of
segments used by a program;
 segment number s is legal if s < STLR.
Silberschatz, Galvin and Gagne \uf6d920029.46Operating System Concepts
Segmentation Architecture (Cont.)
\ufffd Relocation.
\u2726 dynamic
\u2726 by segment table
\ufffd Sharing.
\u2726 shared segments
\u2726 same segment number
\ufffd Allocation.
\u2726 first fit/best fit
\u2726 external fragmentation
Silberschatz, Galvin and Gagne \uf6d920029.47Operating System Concepts
Segmentation Architecture (Cont.)
\ufffd Protection. With each entry in segment table associate:
\u2726 validation bit = 0 \ufffd illegal segment
\u2726 read/write/execute privileges
\ufffd Protection bits associated with segments; code sharing
occurs at segment level.
\ufffd Since segments vary in length, memory allocation is a
dynamic storage-allocation problem.
\ufffd A segmentation example is shown in the following
diagram
Silberschatz, Galvin and Gagne \uf6d920029.48Operating System Concepts
Segmentation Hardware
Silberschatz, Galvin and Gagne \uf6d920029.49Operating System Concepts
Example of Segmentation
Silberschatz, Galvin and Gagne \uf6d920029.50Operating System Concepts
Sharing of Segments
Silberschatz, Galvin and Gagne \uf6d920029.51Operating System Concepts
Segmentation with Paging \u2013 MULTICS
\ufffd The MULTICS system solved problems of external
fragmentation and lengthy search times by paging the
segments.
\ufffd Solution differs from pure segmentation in that the
segment-table entry contains not the base address of the
segment, but rather the base address of a page table for
this segment.
Silberschatz, Galvin and Gagne \uf6d920029.52Operating System Concepts
MULTICS Address Translation Scheme
Silberschatz, Galvin and Gagne \uf6d920029.53Operating System Concepts
Segmentation with Paging \u2013 Intel 386
\ufffd As shown in the following diagram,