Aa r} p @ P ` HH $ @ d HHHH̀̀̀ff@
d Footnote
TableFootnote** .\t.\t/ - :;,.!? /8 cN -0d; TOCHeading1Heading2 P EquationVariables BV ;` < < =7 =P =i = ;B ;D ;F ;H AyI AT AY <$lastpagenum> <$monthname> <$daynum>, <$year> "<$monthnum>/<$daynum>/<$shortyear> J<$hour>:<$minute00> <$ampm> on <$dayname>, <$monthname> <$daynum>, <$year> "<$monthnum>/<$daynum>/<$shortyear> <$monthname> <$daynum>, <$year> "<$monthnum>/<$daynum>/<$shortyear> <$fullfilename>
<$filename> <$paratext[Title]> <$paratext[Heading1]>
<$curpagenum>
<$marker1>
<$marker2> (Continued) + (Sheet <$tblsheetnum> of <$tblsheetcount>) Heading & Page <$paratext> on page<$pagenum> Pagepage<$pagenum> See Heading & Page%See <$paratext> on page<$pagenum>. Table All7Table<$paranumonly>, <$paratext>, on page<$pagenum> Table Number & Page'Table<$paranumonly> on page<$pagenum> Heading <$paratext> E HTML Headings ++ A 33 55 7i A << >> @@ A ;b ;d ;f ;h ;j ;l ;n ;p ;r ;t ;v ;x ;z ;| ;~ ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; < < < < < <
< < < < < < < < < < < < <" <$ <& <( <* <, <. <0 <2 <4 <6 <8 <: << <> n B?n B@n BAn BBn BC i d q 5+ d A> d ;] d ;L HmR ;M HmRHR HR Footnote Hr@ ;N Hr@HzHz Single LineH ;O Footnote
;P
HD ;Q
HDHH Double LineH ;R
Double Line ;S
;T
H ;U
Single Line ;V
HZ ;W
TableFootnote d 5p 77 EGxR ;X EGxREPwEPw
TableFootnote d ;^ d E l d ;_ d 1 Q RUX[^adgjmpsvy| %).1 W/ Bm } d ;a d W aHTML Mapping Table }Hd ;c Hd W a }Hd ;e Hd W a }Hd ;g Hd W a }Hd ;i Hd W a } H ;k H ! FrameMaker P A Source Item }H ;m H W a
HTML Item } H ;o H W a } H ;q H W aInclude Auto# } H ;s H W
a Comments } H ;u H W a }HH ;w HH W aElement } H ;y # H W
a New Topic? } H ;{ H W a } H ;} H W a } H ; $ H W a P:Date Line }HH ; #% HH W aP } H ; $& H W aN } H ; %' H W aN } H ; &( H W a } EH ; ') EH W a
P:Reading }HEH ; (* HEH W aP } EH ; )+ EH W aN } EH ; *, EH W aN } EH ; +- EH W a } QH ; ,. QH W aP:Title }HQH ; -/ HQH W aH* } QH ; .0 QH W aN } QH ; /1 QH W aN } QH ; 02 QH W a } ]H ; 13 ]H W aP:Body }H]H ; 24 H]H W aP } ]H ; 35 ]H W! aN } ]H ; 46 ]H W" aN } ]H ; 57 ]H W# a } iH( ; 68 iH( W$ a P:Numbered1 }HiH( ; 79 HiH(( % aLI
& a Parent = OL
Q' a
Depth = 0 } iH( ; 8: iH( W( aN } iH( ; 9; iH( W) aY } iH( ; :< iH( W* a } H ; ;= H W+ a P:Heading1 }HH ; <> HH W, aH* } H ; =? H W- aN } H ; >@ H W. aN } H ; ?A H W/ a } H( ; @B H(
W0 a P:Numbered }HH( ; AC HH((
1 aP
2 a Parent = OL
Q3 a
Depth = 0 } H( ; BD H(
W4 aN } H( ; CE H(
W5 aY } H( ; DF H(
W6 a } H ; EG H W7 a P:CellBody }HH ; FH HH W8 aP } H ; GI H W9 aN } H ; HJ H W: aN } H ; IK H W; a } H ; JL H W< aP:CellHeading }HH ; KM HH W= aP } H ; LN H W> aN } H ; MO H W? aN } H ; NP H W@ a } H ; OQ H
WA a P:Footnote }HH ; PR HH
WB aP } H ; QS H
WC aN } H ; RT H
WD aN } H ; SU H
WE a } H( ; TV H( WF a P:Bulleted }HH( ; UW HH(( G aLI
H a Parent = UL
QI a
Depth = 0 } H( ; VX H( WJ aN } H( ; WY H( WK aN } H( ; XZ H( WL a } H ; Y[ H WM a P:Heading2 }HH ; Z\ HH WN aH* } H ; [] H WO aN } H ; \^ H WP aN } H ; ]_ H WQ a } H ; ^` H R ! P:HeadingRuP AnIn }H H ; _a H H WS aP } H < `b H WT aN } H < ac H WU aN } H < bd H WV a } 7H < ce 7H WW a P:Indented }H7H < df H7H WX aP } 7H < eg 7H WY aN } 7H <
fh 7H WZ aN } 7H < gi 7H W[ a } CH < hj CH \ ! P:TableFootP Anote }HCH < ik HCH W] aP } CH < jl CH W^ aN } CH < km CH W_ aN } CH < ln CH W` a } ]H( < mo ]H( Wa a
P:TableTitle }H]H( < np H]H(( b aLI
c a Parent = OL
Qd a
Depth = 0 } ]H( H "W4 a } ©H < =? ©H # W5 a }H©H < >@ H©H #W6 a } ©H < ?A ©H #W7 a } ©H < @B ©H #W8 a } ©H < AC ©H #W9 a } »d < BF »d $ W: aHTML Options Table }D»d < D»d $W; a }D»d < D»d $W< a } D < CG D % W= a }DH < FH DH %W> a } H < GI H %W? a } D < HJ D & W@ a
Image Format }DH < IK DH &WA aIMAGGIF } H < JL H &WB a } D < KM D ' WC aBanners }DH < LN DH 'WD aN } H < MO H 'WE a } D < NP D ( F !
Banner ReferP A ence Frame }DH < OQ DH (WG a } H < P H (WH a } D( < D S D((F ) I ! Copy Files Imported by P A Rerefernce }D H( < DRT D H( F )WJ a } H( < DSU H( F )WK a } DD < DTV DD F * WL a }DDH < DUW DDH F *WM a } DH < DVX DH F *WN a } Vd < DW[ Vd F + WO aSystem Macros }?Vd < D ?Vd F +WP a }?Vd < D ?Vd F +WQ a } f? < DX\ f? F , WR a Macro Name }?fH < D[] ?fH F ,WS a
Replace With } fH < D\^ fH F ,WT a Comments } r? = D]_ r? F - WU a StartOfDoc }?rH = D^` ?rH F -WV a } rH = D_a rH F -WW a } ~? = D`b ~? F . WX a EndOfDoc }?~H = Dac ?~H F .WY a } ~H = Dbd ~H F .WZ a } ? =
Dce ?F / [ ! StartOfSubP ADoc }? H = Ddf ? H F /W\ a } H = Deg H F /W] a } ? = Dfh ?F 0 ^ ! EndOfSubP ADoc }? H = Dgi ? H F 0W_ a } H = Dhj H F 0W` a } ? = Dik ?F 1 a !
StartOfFirstP ASubDoc }? H = Djl ? H F 1Wb a } H = Dkm H F 1Wc a } ? = Dln ?F 2 d ! EndOfFirstP ASubDoc }? H =! Dmo ? H F 2We a } H =# Dnp H F 2Wf a } ? =% Doq ?F 3 g ! StartOfLastP ASubDoc }? H =' Dpr ? H F 3Wh a } H =) Dqs H F 3Wi a } ? =+ Drt ?F 4 j !
EndOfLastP ASubDoc }? H =- Dsu ? H F 4Wk a } H =/ Dtv H F 4Wl a } & ? =1 Duw & ? F 5 Wm a }?& H =3 Dvx ?& H F 5Wn a } & H =5 Dwy & H F 5Wo a } 8 d =8 Dx| 8 d F 6 Wp aCross-Reference Macros }?8 d =: D ?8 d F 6Wq a }?8 d =< D ?8 d F 6Wr a } H ? => Dy} H ? F 7 Ws a Macro Name }?H H =@ D|~ ?H H F 7Wt a
Replace With } H H =B D} H H F 7Wu a Comments } T ? =D D~ T ? F 8 Wv a See Also }?T H =F D ?T HF 8w !
See Also: P A <$paratext> } T H =H D T H F 8Wx a } n ? =J D n ? F 9 Wy a }?n H =L D ?n H F 9Wz a } n H =N D n H F 9W{ a } d =Q D d F : W aGeneral Macros }? d =S D ? d F :W a }? d =U D ? d F :W a }? d =W D ? d F :W a } ? =Y D" ? F ; W a Macro Name d = d =
d l d =
d o
W Bm } d =
d < W| aHeadings Table }Hd =
Hd <W} a }Hd =
Hd <W~ a } H =
H = !Paragraph ForP Amat }HH =
HH =W aHeading Level } H =
H =W a Comments } H =
H > W aTitle }HH =
HH >W a } H =
H >W a } KH =
KH ? W a Heading1 }HKH =
HKH ?W a } KH =
KH ?W a } WH =
WH @ W a Heading2 }HWH =
HWH @W a } WH =
WH @W
a } cH =
cH A W a }HcH =
HcH AW a } cH =
cH AW
a HH A? HH 3 3 ^ dThe Stages of Compilation
_, e
Introduction
` eOThis describes the basic stages of compilation in a very non-traditional way
cI e
fW e*From: Mateo.Burtch@Eng.Sun.COM (Room 101)
k e.Subject: YADFH (Yet Another D*** Friday Hack)
e
! %OHi. This isn't exactly a hack, and thus probably doesn't deserve to be called Ia "Friday Hack," but SOOOOO many people have been coming up to me in the Kshower, saying, Please, tell us the secrets of how the compilation process EKworks, that I finally decided to share with you the old family recipe for:
e
eTHE STAGES OF COMPILATION
e
!
%OSOURCE FILE: This is the basic "code" that the engineer writes. The compiler Ewill take code such as
e
edweeble(flab, krimjaw)
e&sneet flab *(**smicknat[])(blugnut);
eblook krimjaw;
e{
e!blark snapdaddle liederhosen ;
e
eif (fleb <= OAK_TREE)
e!while (trousers(liederhosen))
e
thud;
eelse
ebrick(flab);
e}
e
! %Pand turn it into output that means, roughly, "point the hose away from yourself Ewhile watering."
e
e6Obviously, the compiler is a lot smarter than we are.
e
! %LPREPROCESSOR: The preprocessor takes all sorts of special directives, like L#ifdefs, and converts them into conditional statements (known as "#ifdefs") Pthat the compiler uses to prepare the file (or "#ifdef") for processing. (This EKis a technical simplification that is in most, if not all, aspects wrong.)
e
! %MThe preprocessor also strips the source file of comments (not to be confused Owith #ifdefs), leaving it a shaken husk of its former self. These comments are Pthen pieced together by a separate function and used for insulation in Building E12.
e
!! %LCOMPILER: The heart of the whole process. The compiler takes the language Owords, such as "if," "for," and "help!" and turns it into the bits, bytes, and EPsubroutines that give employment to a whole host of socially challenged people.
" e
a# %NOPTIMIZATION: This stage makes the generated code as efficient as possible. NThe optimizer does this by carefully trimming the odd and dangly parts off of HH AA HH L9 l d AB 99
}? H =[ D # ? H F ;W a
Replace With } H =] D"$ H F ;W aHead } H =_ D#% H F ;W! a Comments } ? =a D$& ? F C W" a }? H =c D%' ? H F CW# a } H =e D&( H F CW$ a } H =g D') H F CW% a } d =j D(. d F D W& aCharacter Macros HH ;" HH + G e HH ;$ 3 HH ** l }? d =l D ? d F DW' a }? d =n D ? d F DW( a } ? =p D)/ ? F E W) a Macro Name }? H =r D.0 ? H F EW* a
Replace With } H =t D/1 H F EW+ a Comments } ? =v D0B ? F F W, a HUV
;. HUV
3 G e HUV
;0 5+ HUV
22 l H$
;1 H$
5 G e H$
;3 3 H$
44 l HH ;4 HH L 3 3 7 `Memory Management
vGoal: CPU gains related to scheduling require that many processes be in memory; so, memory must be shared. @kThe selection of which memory management algorithm(s) to use depends especially on the hardware available.
2Bt `"How Programs Interact With Memory
3 ` compile, assemble, link, load
[D> ` absolute (physical) addresses
`Ebare machine, resident monitor, fence addresses, and fence registers
5s ` Relocation
6 `0binding program addresses to absolute addresses
`transient monitor code
0 `0monitor and user stacks grow towards each other
1 `dynamic relocation
4 `dswapping: swap device (backing store), swapped processes, effect of swap time on switching contexts
!n koptimizations: swapping part of the job, speeding up the backing stores performance, overlap with process @
execution
o ` when you can and cannot swap
8* `!Simple Memory Management Schemes
9 `multiple partitions
7wa `bounds registers
p `base and limit registers
;+ `Fixed Regions (MFT)
< `job scheduling
:) `memory allocation
= `roll in-roll out
>A] `Variable Regions (MVT)
? `Dallocation schemes: best fit, worst fit, first fit, next fit, buddy
@Y `job scheduling
q `$internal vs. external fragmentation
r ` compaction
s ` swapping
t ` reducing external fragmentation
BP `Paging
C `&page numbers and offsets, page frames
DD `job scheduling effects
A `page table implementation
FƐ `Optimizations
E `cache, hit ratio
uݮ ` effective memory access time
v `.sharing, protection, illegal address handling
H*x `Views of Memory
I `'program vs . operating system
GwB `address translation
J `global frame table
K' `
Segmentation
L `.segments: segment name, offset, segment table
M@ `.implementation: registers vs . table
P `#sharing, protection, fragmentation
NX] `"Combining Segmentation and Paging
O `*segmented paging (segment the page table)
wpj `'paged segmentation (page the segments)
QQ|5 `What Is Virtual Memory
HH ;6 HH L66 l HH AC ! HH 5 9 # @Inumerals like "5" and "9" until all the numbers are either "1"s or "0"s.
$ `
1% OASSEMBLER: The assembler takes "machine code" (low-level instructions done by Kpoorly-paid workers in windowless sweatshops called "assembler lines") and @does something with it.
& `
!' OLINKER: Before we're done, we must link together all the various object files Pwith libraries containing macros and canned routines. Don't ask why--it's like @4salmon swimming upstream to spawn. You just do it.
( `
!) LThese libraries perform a special job in the grand pageant known as program Nming. The pre-written macros and functions they contain allow the programmer Nto save valuable time when writing a program, while the arcane linker options Oand obscure environment variables slow the programmer down just as much. This Nis known as "run-time equilibrium" and is rather similar to horizontal bungee- @ jumping.
* `
!+ OEXECUTABLE: This is the final product, the finished masterpiece, the piece de Mresistance of the whole process. This file is what the engineer had in mind @ when he or she started out.
, `
- `It's called "core."
. `
/ `--Mateo
0 `
A1 `
HH AE ! HH H88 l d Ak HH d ;; <@ H$
;< ; > H$
== l H$
;= ; H$
< W h9February 9, 2000ECS 150 Winter 2000Page 13 HUV
;> ;<@ HUV
?? l HUV
;? ; HUV
> W h@Last modified at
2:48 pm on Wednesday, March 1, 2000 HH ;@ ;> HH AA
l HH ;A ; HH @ W ` }? H =x D1C ? H F FW- a } H =z DB H F FW. a d =~ EE d = D d FF
l d = D d RCE RUX[^adgjmpsvy| %).1 HH Al : HH
& & H 2 ` Static and Dynamic Relocation
3, `
Introduction
4 pThis shows the basic hardware instruction cycle for a machine that uses static relocation and for one that uses I @dynamic relocation.
5b `Static Relocation
6t uStatic relocation refers to address transformations being done before execution of a program begins. A typical hard @(ware instruction cycle looks like this:
7 `loop
8 `N w := M [ instr_ctr ];(* fetch instruction *)
9 `0 oc := Opcode ( w );
: `2 adr := Address ( w );
; `1 instr_ctr := instr_ctr + 1;
< `% case oc of
= `L1: reg := reg + M [ adr ];(* add *)
> `@2: M [ adr ] := reg ;(* store *)
? `:3: instr_ctr := adr ;(* branch *)
@ `
A `
end
B `end (* loop *)
C) `Dynamic Relocation
D; uDynamic relocation refers to address transformations being done during execution of a program. In what follows, the G zfunction NL_map (for Name Location map) maps the relocatable (virtual) address va given in the program into the @.real (physical) storage address pa :
E `*pa := NL_map ( va )
F `:So, a typical hardware instruction cycle looks like this:
G `loop
H `` w := M [ NL_map ( instr_ctr )];(* fetch instruction *)
I `0 oc := Opcode ( w );
J `2 adr := Address ( w );
K `1 instr_ctr := instr_ctr + 1;
L `% case oc of
M `_1: reg := reg + M [ NL_map ( adr )];(* add *)
N `S2: M [ NL_map ( adr )] := reg ;(* store *)
O `M3: instr_ctr := NL_map ( adr );(* branch *)
P `
Q `
end
R `end (* loop *)
CS `
HH An : HH 9PGG l cC Az N MM O
d @ LL HH @ J HH " " L R d-executing processes not completely in memory
x d overlays
y d/demand paging, page faults, pure demand paging
z dperformance issues
{ d,page replacement and victims and dirty bits
SBq d page replacement algorithms
|] dfirst in first out
}[D; doptimal
~ dleast recently used
d;stack algorithms, inclusion property, used (reference) bit
dclock
dsecond chance
d least and most frequently used
dnot used recently
dssecond-chance cyclic: (1,1) (0,1); (1,0) (0,0); (0,1) (0,0)*; (0,0) victim
a d,Ad Hoc Techniques for Improving Performance
b d frame pool
d dPage Allocation Algorithms
e dreserve some free frames
Tw_ duse all before replacing
U d$minimum number of pages per process
V d&global vs . local allocation
W d equal, proportional allocation
g ' dWorking Set Policies
h_R d!thrashing, principle of locality
i5 dCworking set model: working set, window size, working set principle
j@ d@approximations: WSCLOCK, Working Set Size, Page Fault Frequency
lM] d Other Considerations for Paging
mR?K d
prepaging
Xe dI/O interlock
Y_ dchoosing page size
Z dprogram restructuring
[ ddata structures and paging
A\ d%arrangement of routines when loading
HH @ J HH 7 KK l
A{ I
=QuickDraw PICT
#%v , , N MSWD O
N
4 8 & , Geneva
. N ( *CPU a{j 0 " t 4 Si 8 i 4i4 " Si # # # #
# # #
# & ( p "b ` & (&o & @ (E{p a7R 0 !` "% ae 0 ! aV1 0 "t "`vK ! 4 SWF 8 & ( physical
? + Bmemory & ( ?y
page table & 3@ (frame T = X & * ( V+ 4 8 & } ( PTBR a j 0 " t " b a *C } 0 ! SG & ( frame 4;$z 8 & w@ (qAframe "; K & )o & 4 @ (physical address 4= 8 &
@ (Qp o " K &
(virtual
ѯ (address
=EndInset
d A PP HH A N HH | II P T ` Paging and Address Translation
U, `
Introduction
V qThis shows the function used to map a logical address to a physical address for some paging schemes. Throughout I this handout, an address in virtual memory is a pair ( logical_page , offset ) where logical_page is the page number 0W within the logical address space and offset the offset into that page. Also, page_size is the size of the page (which is a tmultiple of 2). We will assume the entire program is in memory, so no error handling is given; were this assumption sfalse, the situation where the requested address were not in memory would need to be handled (by generating a page @'fault and loading the necessary page):
W `-Paging Address Translation by Direct Mapping
X vThis method stores the page table in main memory and the address of this table in the process control block, in a reg ister called the page table base register. Let the page table base register be called pt_base_register , and let memory @0represent the main store of the computer. Then:
Y `hfunction NL_map (( logical_page , offset )): physical_address ;
Z `begin
[ ` NL_map := memory [ pt_base_register + logical_page ] * page_size + offset ;
\ `end (* NL_map *)
] "h,In pictures, here is what is going on:
^ `2Paging Address Translation by Associative Mapping
_ zIn this algorithm, assoc_page_table represents an associative memory. This function can check a type of memory ocalled "associative memory" (or "cache" or "lookaside memory") which stores both a frame number and a page num0UUT {ber. The search is done in parallel, and is much faster than a linear (or binary) search. The function returns the frame @%number associated with its argument:
` `^function NL_map(( logical_page , offset )): physical_address ;
a `begin
b `r NL_map := assoc_page_table ( logical_page ) * page_size + offset ;
c `end (* NL_map *)
dg `HPaging Address Translation with Combined Associative and Direct Mapping
Wey {This combines the above two methods. The array page_table is a small associative store that can hold only a few HH A N HH HSOO l d A SS
HH A Q HH S e ypage numbers; there is also a page table kept in memory. For this method, we shall assume that if there is no entry for logical_page in the associative memory, assoc_page_table returns 1. Taking everything else as in the previous two @
sections:
f `hfunction NL_map (( logical_page , offset )): physical_address ;
g `4var frame_number : integer ;
h `begin
i `O frame_number := assoc_page_table ( logical_page );
j `^ if frame_number = -1 then (* not in associative memory *)
k `\ NL_map := memory [ pt_base_register + logical_page ]
l `1* page_size + offset ;
m ` else
n `W NL_map := frame_number * page_size + offset ;
o `end (* NL_map *)
p `NThis is the most common method, and is used in modern computers with paging.
Aq `
HH A Q HH PXRR l c7 A V UU W
A T
=QuickDraw PICT
#%v , , MSWD
4; 8 & , Geneva
. (q *CPU a6j 0 "` t & (qM(s,d) 4i? 8 i i ; "i # # # # # # # # & (js & +dqbase & ] (qlimit "; #p #K "gCK "CKK " KK & (,7< a q 0 # ) & ( trap & @ (d & (&s "i a q 0 !C & (wXno aE
0 &
(yes Tkz X & V@ (, + + aX 0 !+ a1d 0 ";t " vK !; 4W 8 & (q physical
? + Bmemory & , ( G
segment table & (Klimit & @ (base Tb X & ;@ ({+ 4 8 & ( STBR a{= 0 A " # "ӵ "=K "ZK & ( {> a C8 0 #t &
+S&yes a *b } 0 " & ( Eno &
( >Qtrap 4 8 8 & 7@ ( STLR a 8j 0 " t
=EndInset
d A XX HH A V HH TT X r `%Segmentation and Address Translation
s, `
Introduction
t lThis shows the function used to map a logical address to a physical address for some segmentation schemes. I Throughout this handout, an address in virtual memory is a pair ( segment , offset ) where segment is the segment num0W ber within the logical address space and offset the offset into that segment. We will assume the entire program is in vmemory, so no error handling is given; were this assumption false, the situation where the requested address were not @fin memory would need to be handled (by generating a segment fault and loading the necessary segment):
u `
Segmentation
v tAs with paging address translation with direct mapping, the segment table is stored in memory, and a pointer to its base in a register called the segment table base register. Let the segment table base register be called st_base_register , @?and let memory represent the main store of the computer. Then:
w `cfunction NL_map (( segment , offset )): physical_address ;
x `begin
y `j NL_map := memory [ st_base_register + segment ] + offset ;
z `end (* NL_map *)
{ "hIn pictures:
Q| `
HH A V HH S]WW l ^ Q A ^ ZZ _
Aџ Y
=QuickDraw PICT
#%v , , MSWD
a;9 0 "e u , Geneva
. ((s,d)
4C 8 ? " # # # #
# # #
# (s "? (s " a?% 0 !e aS 0 W 4x 8 (a physical
? +Bmemory , ( P
segment table T X (+ 4^
8 ( STBR a^ 0 b "^ " "^K "^K (4> a e= 0 #u +X&yes a . 0 " ( Ano ( ?Rtrap 4
= 8
7@ ( !STLR a 9= 0 " u " (PTBR 4 8 k k " # # # #
# # #
# (gp @ (RV(p,o) a pN 0 FF T X )+ @ (-p ! (q
page table "k q ! # +f )(f,o) "
(wd a pU 0 "FO 4
8 (u 6CPU
=EndInset
d A ]] HH A [ HH F + + ] } `!Segmentation and Paging Combined
~, `
Introduction
qThis shows the function used to map a logical address to a physical address for schemes combining paging and segI mentation. Throughout this handout, page_size is the size of the page (which is a multiple of 2), seg_tbl_base_reg 0W ~contains the address of the base of the segment table, and memory is the main store of the computer. We will assume tthe entire program is in memory, so no error handling is given; were this assumption false, the situation where the qrequested address were not in memory would need to be handled (by generating a fault and loading the appropriate @data structure).
`Segmented Paging
In this algorithm, the page tables are segmented. The virtual address is represented as a pair ( logical_page , offset ), but the logical_page consists of a pair ( seg_number , seg_offset ) indicating which segment number seg_number of the 0
page table the frame number frame_no is stored in, and the offset seg_offset from the base of that segment table. As {usual, an associative memory is first checked; this will be represented by the funcetion assoc_page_table , which @Areturns the frame number if that is in the table, and 1 if not:
`hfunction NL_map (( logical_page , offset )): physical_address ;
`Jvar frame_no : integer ;(* number of frame *)
`Q pg_tbl_base : integer ;(* addr. of page table segment *)
`begin
`K frame_no := assoc_page_table ( logical_page );
`@ if frame_no = -1 then begin
`` pg_tbl_base := memory [ seg_tbl_base_reg + seg_number ];
`X frame_no := memory [ pg_tbl_base + seg_offset ];
` end ;
`R NL_map := frame_no * page_size * offset ;
`end (* NL_map *)
q `Paged Segmentation
In this algorithm, the segments are paged. The virtual address is represented as a pair ( seg_number , offset ), but the offset consists of a pair ( page_number , page_offset ), indicating which page number page_number of the segment U\ seg_number the frame number frame_no is stored in, and the offset page_offset from the base of that page. As usual, " an associative memory is first checked; this will be represented by the funcetion assoc_page_table , which returns the @oframe number if that is in the table, and 1 if not. Note it takes the segment number as an argument as well:
`ffunction NL_map (( seg_number , offset )): physical_address ;
`Jvar frame_no : integer ;(* number of frame *)
`Q pg_tbl_base : integer ;(* addr. of page table segment *)
`begin
`` frame_no := assoc_page_table ( seg_number , page_number );
`@ if frame_no = -1 then begin
`` pg_tbl_base := memory [ seg_tbl_base_reg + seg_number ];
`Y frame_no := memory [ pg_tbl_base + page_number ];
` end ;
`W NL_map := frame_no * page_size * page_offset ;
`end (* NL_map *)
C `
In pictures:
HH A [ HH X`\\ l d A `` HH A ^ HH YYY `
W "h
HH A ^ HH ]c__ l d BF cc HH BG a HH ~ - - c ` Page Replacement Algorithms
, `
Introduction
sThis handout shows how the various page replacement algorithms work. We shall call the pages of the program a, b, I @5c, to distinguish them from the time (1, 2, 3, ).
b `Fixed Number of Frames
t |We shall demonstrate these algorithms by running them on the reference string w = cadbebabcd and assume that, ini tialy, pages a, b, c, and d occupy frames 0, 1, 2, and 3 respectively. When appropriate, the little arrow indicates the @\location of the pointer which indicates where the search for the next victim will begin.
! `First In/First Out (FIFO)
" `>This policy replaces pages in the order of arrival in memory.
# ` time012345678910
$ ت ` w cadbebabcd
% ``frame 0 a a a a aeeee ed
& `?frame 1bbbbb b baaa a
' `)frame 2ccccccc cbbb
( `)frame 3dddddddd dcc
) `page fault12345
* ` page(s) loadedeabcd
+ ` page(s) removedabcde
,: `Optimal (OPT, MIN)
-J `mThis policy selects for replacement the page that will not be referenced for the longest tile in the future.
.V ` time012345678910
/ UE ` w cadbebabcd
0 ` frame 0aaaaaaaaaad
1 ` frame 1bbbbbbbbbbb
2 ` frame 2ccccccccccc
3 ` frame 3dddddeeeeee
4 `page fault12
5 ` page(s) loadeded
6 ` page(s) removedda
7 `Least Recently Used (LRU)
8ߪ `dThis policy selects for replacement the page that has not been used for the longest period of time.
9몐 ` time012345678910
: ŅU/ ` w cadbebabcd
; ` frame 0aaaaaaaaaaa
< ` frame 1bbbbbbbbbbb
= ` frame 2ccccceeeeed
> ` frame 3dddddddddcc
? `page fault123
@ ` page(s) loadedecd
A ` page(s) removedcde
B `!stack (top)cadbebabcd
C `cadbebabc
D `caddeeab
AE `$stack (bottom)caaddea
HH BI a HH `fbb l d BJ ff HH BK d HH w 0 0 f F a2Not-Recently-Used or Not Used Recently (NRU, NUR)
G !tThis policy selects for replacement a random page from the following classes (in the order given): not used or modi0 vfied, not used but modified, used and not modified, used and modified. In the following, assume references 2, 4, and Ae7 are writes. The two numbers written after each page are the use and modified bits, respectively.)
H a time012345678910
I a w ca*db*eba*bcd
J a: . f @
$ . H . l . . . . . . D . h .
CodePseudo . f @
$ . H . l . . . . . . D . h .
CodePseudo . f @
Q Body . @ @
Q Header Double Line . f @ Q CellFooting . f @ Q
CellHeading . f @ Q
CellBody . @ @ Q Mapping Table Cell . @ @ / Mapping Table Cell . @ @ / Mapping Table Cell . @ @ Q Mapping Table Cell . f @
Q Body . f @
Q
BodySpaced . f @
Q Bulleted \t . f @
Q . . . Date . m f @
Q l . DateProject . @ @
Q Header Double Line . f @ T Q Heading1 Body. f @
Q NumberedSpaced .\t . f @
Q . Reading . f @ P Q Title Body. f @ $ Q . Line Single Line . f @ Q CellBody . f @ Q CellHeading . f @
Q Footnote . f @ T Q Heading2 Body. f @ T Q HeadingRunIn Body. f @ Q Indented . f @
Q
TableFootnote . f @ T Q
TableTitle T:Table : .
f @ P Q Title Body. f @ N E
Q Numbered1 N:.Numbered. L̀Lf @ N
Q Numbered
N:.< =1> . $ f @ L
Q $ . Lettereda L:. . $ f @ L
Q $ . Lettered L:. . f @ NE
Q Numbered1 N:.Numbered. $ f @ L
Q $ . Lettereda L:. . $ f @ L
Q $ . Lettered L:. . L̀Lf @ N
Q Numbered
N:.< =1> . 6$ f @ R
Q 6 . Romani R:. . 6$ f @ R
Q 6 . Roman R:. . 6$ f @ R
Q 6 . Romani R:. . f @ T Q Heading1 Body. f @
Body . f @
H l Body . f @ T Q Heading2 Body. f @
Q Z . ~ . . . . . 2 . V . z . . . Body . f @
Q
BodyIndent . f @ $ . 6 . Z . u . . CodeASM . H f @
Q H . . CodeComment .
Q Q Q /
Q ڝ Q Q Emphasis Q EquationVariables ڝ Q
/
BoldItalic
Q Italic
Q Bold Q / Q
Q
Q
Q
M Symbol M Symbol
Computer
M Z Z Thin Medium Double Thick @ Very Thin H H H H H Format A H
Mapping Table H H H H H Format B H
Mapping Table h *| # H H H H H f $* D H H +5 ? H H & 69 ? H H :C ? H H H DF ? H H *6 ? @ h ( A
B
C
D
E
h
F G H I J h
K L M N O h P
Q
R
S
T
h (
U V W X Y h Z [ \ ] ^ h _ ` a b c 7h d e f g h Ch i j k l m ]h ( n o p q r h s t u v w h x y z { | h ( } ~ h h
h
h h h )h ! " # $ 5h % & ' ( ) Oh * + , - . [h ! / 0 1 2 3 uh " 4! 5! 6! 7! 8! h !# 9" :" ;" <" =" ©h " ># ?# @# A# B# » % C$ D$ E$ $& F% G% H% %' I& J& K& &( L' M' N' ') O( P( Q( ( (*F R) S) T) D ) F U* V* W* V ,F X+ Y+ Z+ f +-F [, \, ], r ,.F ^- _- `- ~ -/F a. b. c. .0F d/ e/ f/ /1F g0 h0 i0 02F j1 k1 l1 13F m2 n2 o2 24F p3 q3 r3 35F s4 t4 u4 & 4 F v5 w5 x5 8 7F y6 z6 {6 H 68F |7 }7 ~7 T 79F 8 8 8 n 8 F 9 9 9 ;F : : : : :CF ; "; #; $; =
< < < <> = = = =? > > > K >@ ? ? ? W ?A @ @ @ c @ A A A ; F %C &C 'C (C EF )D ,D -D DFF .E /E 0E E F 1F BF CF Comment ;C
;G d Black T! White dd A Red dd Green d d Blue d Cyan d Magenta d Yellow Header/Footer $1Header/Footer $1Header/Footer $2Header/Footer $2IndexIndexCommentCommentSubjectSubjectAuthorAuthorGlossaryGlossaryEquationEquation Hypertext Hypertext Cross-Ref Cross-Ref
Conditional TextConditional TextPositionFMPrivatePositionFMPrivate RangeEndFMPrivateRangeEndFMPrivate
HTML Macro
HTML Macro M.Times.P Times-Roman
FrameRoman M.Courier.B Courier-Bold
FrameRoman M.Courier.PCourier
FrameRoman M.Times.B
Times-Bold
FrameRoman
M.Helvetica.BHelvetica-Bold
FrameRoman M.Helvetica.BIHelvetica-BoldOblique
FrameRoman M.Times.I Times-Italic
FrameRoman
M.Symbol.PSymbol
FrameRoman
FrameRoman
FrameRoman M.Courier.ICourier-Oblique
FrameRoman b Courier. HelveticaLSymbolPTimes!Regular$Roman MediumBoldRegular
ObliqueItalic ` ޒSǬ,K7_ xи7 0 W# 7];G]۱!Dm.tVU'O'5&]R4DP;
EWn-owK7J$y`s؇ֈc28'дuOOo.鵃Qd !@2^9:51\s|PA ^]˚չK (7ʥЯMۥך{6a8du?\ ;2{T;a[M?r'RΊWRQW4;