-
Notifications
You must be signed in to change notification settings - Fork 1
/
M3_Review-Chapter9
234 lines (191 loc) · 11.5 KB
/
M3_Review-Chapter9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
# CSC360
Operating Systems
Midterm #3 review.
Virtual Memory - Chapter 9
Slides: Virtual Memory
Virtual memory:
\-> involves the separation of logical memory as perceived by users from physical memory.
\-> Benefits:
□ program would no longer be constrained by the amount of physical memory that is
available. Users would be able to write programs fro extremely large vertual addres
space, simplifuing the programming task.
□ Because each user program could take less physical memory, more programs could be run at the same time, with
corresponding increase in CPU utilization and throughput but with no increase in response time or turnaround time
□ Less I/O would be needed to load or swap user programs into memory, so each user program would run faster
□ benefiticial for both system and user
□ faster swap in/out
\-> virtual memory asslows files and memory to be shared by two or more processes through page sharing.
Virtual Address Space:11
\-> refers to the logical (or virtual) view of how a process is stored in memory
□ typically, this view is that a process begins at a certain logical address and exists in contiguous memory
\-> address spaces that include holes are know as sparse address spaces.
□ benificial because the holes can be filled as the stack or heap segments grow or if we wish to dynamically link
libraries during execution time
Demand Paging:
\-> only load pages as they are needed during execution.
\-> pages that are never accessed are never loaded into physical memory
Lazy Pager:
\-> never swaps page into memory unless it is going to be used.
valid/invalid bit:
\-> used to determine whether a corresponding page is legal and in memory.
Invalid:
□ The page either is not valid (that is not in the logical address space of the process) or is valid but is currently
on the disk.
Valid bit:
□ The associated page is both legal and in memory
Page Faults:
\-> process tries to access a page that was not brought into memory. (invalid bit is true)
\-> steps to handle a page fault:
1) We check and internal table (usually kept with the proess control block) for this process to determine whether the
reference was a vaild or an invalid memory access
2) If the reference was invalid, we terminate the process. if it was valid but we have not yet brought that page, we
now page it in
3) We find a free frame (by taking on from the free-frame list, for example)
4) we schedule a disk operation to read the desired page into the newly allocated frame
5) When the disk read is complete, we modify the internal table kept with the process and the page table to indicate
that the page is now in memory
6) We restart the instruction that was interrupted by the trap. The process can now access the page as though it and
always been in memory.
Pure demand paging:
\-> never bring a page into memory until its needed.
\-> brings in a page only when a page fault occurs. eventually will have all needed pages in memory thus no more faults.
Hardware:
\-> page table:
□ this table has the ability to mark an entry invalid through a valid-invalid bit or a special value of protection bits
\-> secondary memory:
□ This memory holds those pages that are not present in main memory. The secondary memory is usually a high-speed disk.
it is known as the swap device, and the section of disk used for this purpose is known as swap space.
Paging Performance:
\-> Page fault Rate 0 <= p <= 1.0
□ if p = 0 then no page faults
□ if p = 1 then all references result in a fault
□ increase in page-fault rate -> effective access time increases therfore dramatically slowing down process execution
time
\-> Effective Access Time = (1-p) x memory access + p x (pagefault time + swap page out + swap page in + restart overhead)
\-> page fault causes the following sequence to occur
Copy-on-write:
\-> works by allowing the aprent and child proecsses initially to share the same pages.
\-> These shared pages are marked as copy-on-write pages. Meaing if either process writes to a shared page, a copy of
the shared page is created.
Memory Mapped Files:
\-> memory-mapped file I/O allows file I/O to be treated as routine memory access by mapping a disk block to a page in
memory.
\-> A file is initially read using demand paging. A page-sized portion of the file is read from the file system into
the physical page. subsequent reads/writes to/from the file are trearted as ordinary memory accesses.
\-> Simplifies file access by treating file I/O through memory rather than read() write() system calls
\-> Also, allows several processes to map the same file allowing the pages in memory to be shared.
Slides: Replacement
Page Replacement:
\-> used when over-allocation of memory occurs. multiple processes try to load all there pages but the exists a limited
amount of space.
Basic Page Replacement:
\-> If no frame is free, we find on that is not currently being used and free it.
\-> we can free a frame by writing its contents to swap space adn changing the apge table (and all other tables) to
indicate that the page is no longer in memory.
\-> the newly freed frame can now be used to hold the page for which the process faulted.
\-> we modify the page-fault service routine to include page replacement
Procedure:
1) Find the location of the desired page on the disk.
2) find a free frame:
a) if there is a free frame use it
b) if there is non free frame, use a page-replacement algorithm to select a victim frame
□ NOTICE: twp page transfers are required (out/in)
c) write the victim frame to the disk; change the page and frame tables accordingly
3) Read the desired page into the newly freed frame; change the page and frame tables
4) continue the user process from where the apge fault occured.
\-> reduce overhead by using a modify bit (or dirty bit)
□ if present page has been modified need to write it to disk else no need to.
\-> reduces the fault rate
□ number of frames increases thus the number of faults decreases.
FIFO Page Replacement:
\-> associated the time a page was brought into memory.
\-> when a page needs to be replaced the oldest page is chosen. (can use a queue to hold page table order)
\-> performance not always good.
Belady's Anomaly:
\-> some page-replacement algorithms, the page-fault rate may increase as the number of allocated frames increases.
Optimal Page-Replacement:
\-> Replace page that will not be used for the longest period of time
□ lowest page-faut rate of all alorithms
□ never suffers from Belady's Anomaly
\-> guarantees the lowest possible page-fault reate for a fixed number of frames
Least Recently Used Algoritm:
\-> replace the least recently used.
can be implemented with 2 ways:
1) Counter:
□ simplest associate each page-table entry a time of use field and add to the CPU a logical clock or counter.
□ clock is incremented for every memory reference. Whenever a reference to a page is made, the contents of the
clock register are copied to the time of use field in the apge table entry for that page.
□ search for smallest time value and replace.
2) Stack:
□ Keep a stack of page numbers.
□ when a page is referenced it is removed from the stack and placed on the top. thus the least recently used is on
the bottom of the stack.
\-> does not suffer from Belady's Anomaly.
LRU-Approximation Page Replacement:
\-> Most systems do not provide sufficient hardware support for true LRU page replacement.
\-> counter:
□ number of references
\-> Replace the one with the smallest counter.
□ aging necessary
\-> Most Frequently used (MFU)
□ new page has smaller counter and might be referenced soon
Slides: Page Allocation
Page Buffering:
□ Keep a pool of free pages.
□ speed up swapping in desired pages
□ no need to wait for a page to become "free"
□ Keep a list of modified pages
□ synch with disk when pagin is idle
□ reduce overhead whe swapping out.
Page Allocation:
□ 2 major allocation schemes:
fixed allocation:
□ equal allocation:
□ M free pages
□ N requesting processes
□ Allocation: floor(M/N) each
□ some processes may requet less than M/N
□ EG. if there are 93 frames and 5 processes each process gets 18 frames.
□ leftover frames can be used as free-frame buffer pool
□ Proportional Allocation:
□ each process requests s_i: all request S=sum s_i
□ Allocation: s_i/S*M
priority allocation:
□ allocates available memory to each process according to its size.
□ Allocation proportional to priority
□ higher priority process gets more pages allocated when necessary
□ on page fault
□ select for replacement one of its frames.
□ select for replacement a frame from a process with lower priority number.
□ if multiprogramming level is increased each process will lose some frames to provide the memory needed for the
new process. The opposite goes for the other hand. multiprogamming decreases -> frames increase.
Global versus Local Replacement:
Global replacement:
□ allows a process to select a replacement frame from the set of all frames, even if that frame is currently
allocated to some other process; that is, one process can take a frame from another.
Local Replacement:
□ requires that each process select from only its own set of allocated frames.
Thrashing:
□ More time on paging than executing
□ busy I/O, idle CPU
□ more process admitted, more page faults
□ more processes in thrashing!
□ limit the effects of thrashingby using local replacement algorithm or priority replacement algorithm
□ local replacement thrashing:
□ if one process starts thrashing, it cannot steal frames from another process and cause the latter to thrash
as well
□ if thrashing, processes wil be in the queue for the apging device most of the time. The average service time for
a page fault will increase because of the longer average queue for paging device.
□ effective access time will incerase even for a process that is not thrashing
□ Prevent thrashing:
□ must provide a process with as many frames as it needs.
□ many methods to determine number of needed frames.
□ local replacement
□ sufficient provisioning
□ working-set model:
□ working-set window:
□ most recent page references.
□ window-set size:
□ number of unique page references.
□ if a page is in active use it will be in the working set. else it wont be
if sum WSSi>M reduce multiprogramming