Excercise 4 Memory and Virtual Memory - Cơ sở dữ liệu | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

Question 1:
- Page size = 1KB = 210 byte  No. bits for offset: 10
- No. frames = 32 = 25  5 bits for storing f  15 bit for storing physical address
- Size of the program P = No.page * Page size = 8 * 1KB = 8KB
- Size page = Size frame  Size frame = 1KB  Size of the physical memory =
No.frames * Size frame = 32 * 1KB = 32KB

Tài liệu được sưu tầm giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kì thi sắp tới. Mời bạn đọc đón xem !

22 11 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cơ sở dữ liệu (HCMUS)

Trường: Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

Thông tin:

5 trang 1 tháng trước

Tác giả:

Profile Phạm Thị Huyền
lOMoARcPSD|46342985
lOMoARcPSD|46342985
Họ tên: Nguyễn Văn Đăng Huỳnh
MSSV: 21127063
Lớp: 21CLC10
OPERATING SYSTEM COURSE
EXERCISE#4: MEMORY AND VIRTUAL MEMORY
Question 1:
- Page size = 1KB = 2
10
byte No. bits for offset: 10
- No. frames = 32 = 2
5
5 bits for storing f 15 bit for storing physical address
- Size of the program P = No.page * Page size = 8 * 1KB = 8KB
- Size page = Size frame Size frame = 1KB Size of the physical memory =
No.frames * Size frame = 32 * 1KB = 32KB
Question 2:
- A byte-addressable memory of 320MB = (2
26
* 5) byte
- Page size = 8KB = 2
13
byte
a) No. frames = (2
26
* 5) / 2
13
= 2
13
* 5
b) Number of pages in logical address spaces: 2
48
/ 2
13
= 2
35
Maximum no. pages =
2
35
pages
c) No. offset of each page = 2
13
= 8192
offsets 1892 <0, 1892> 15296 <1, 7104>
20300 <2, 3916>
Question 3:
a) No. bits for storing d = 32 – 9 – 11 = 12 No. offsets = 2
12
Word-addressable memory 1 offset points a word of 4 bytes
Size of a page = 2
12
* 4 = 2
14
bytes = 16KB
b) Frame size = Page size = 16KB
No. frames = 10GB / frame size = 10GB / 16KB = 2
17
frames
c) Maximum size of process space supported in this system = 2
32
* 4 = 2
34
bytes
= 2
4
GB = 16GB
d) A program of 3GB can be divided into 3GB / 16KB = (3 * 2
20
) KB / 2
4
KB
= 3 * 2
16
pages integer value no fragmentation
e) Internal fragmentation
Question 4:
lOMoARcPSD|46342985
- h = 0.75, tc = 25 ns, tm = 132 ns, L = 3
- EAT = h * (tc + tm) + (1 – h) * (tc + (L + 1) * tm)
= 0.75 * (25 ns + 132 ns) + (1 – 0.75) * (25 ns + (3 + 1) * 132 ns)
= 0.75 * 157 ns + 0.25 * 552 ns = 255.75 ns
Question 5:
- EAT = 225 ns, tc = 25 ns, tm = 150 ns, L = 1
- EAT = h * (tc + tm) + (1 – h) * (tc + (L + 1) * tm)
225 ns = h * (25 ns + 150 ns) + (1 – h) * (25 ns + 2 * 150 ns)
225 ns = h * 175 ns + (1 – h) * 325 ns
-100 ns = -150h h = 2/3 = 0.66
Question 6:
- tm = 100 ns, tc = 15 ns, tp = 150000 ns, h = 0.75, p = 0.0005
- EAT = h * (tc + tm) + (1 – h) * [(1 – p) * (tc + 2 * tm) + p * tp]
= 0.75 * (15 ns + 100 ns) + (1 – 0.75) * [(1 – 0.0005) * (15 ns + 2 * 100 ns) +
0.0005 * 150000 ns]
= 0.75 * 115 ns + 0.25 * (0.9995 * 215 ns + 75 ns)
= 86.25 ns + 72.473125 ns = 158.723125 ns
Question 7:
a) FIFO, Optimal, LRU, Second chance
FIFO: no.page fault = 13, page fault hit ratio = 13/21 = 61.9%
EAT = (1 – 0.619) * 102 ns + 0.619 * 192 ns = 157.71 ns
9 4 8 1 4 9 2 9 4 5 4 5 3 4
6
4 3
7
4 9 4
F 9 9 9 1 1 1 1 1 4 4 4 4 4 4
6
6 6
6
6 9 9
1
F 4 4 4 4 9 9 9 9 5 5 5 5 5
5
4 4
4
4 4 4
2
F 8 8 8 8 2 2 2 2 2 2 3 3
3
3 3
7
7 7 7
3
fi 9 9 9 4 4 8 1 1 9 2 2 2 4 4
5
3 3
6
6 4 4
f 4 4 8 8 1 9 9 2 4 4 4 5 5
3
6 6
4
4 7 7
o 8 1 1 9 2 2 4 5 5 5 3 3
6
4 4
7
7 9 9
OPTIMAL: no.page fault = 10, page fault hit ratio = 10/21 = 47.6%
lOMoARcPSD|46342985
EAT = (1 – 0.476) * 102 ns + 0.476 * 192 ns = 144.84 ns
9 4 8 1 4 9 2 9 4 5 4 5 3 4 6 4 3 7 4 9 4
F1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 6 6 6 6 6 9 9
F2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
F3 8 1 1 1 2 2 2 5 5 5 3 3 3 3 3 7 7 7 7
LRU: no.page fault = 11, page fault hit ratio = 11/21 = 52.4%
EAT = (1 – 0.524) * 102 ns + 0.524 * 192 ns = 149.16 ns
9 4 8 1 4 9 2 9 4 5 4 5 3 4 6 4 3 7 4 9 4
F1 9 9 9 1 1 1 2 2 2 5 5 5 5 5 6 6 6 7 7 7 7
F2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
F3 8 8 8 9 9 9 9 9 9 9 3 3 3 3 3 3 3 9 9
Second chance: no.page fault = 13, page fault hit ratio = 13/21 = 61.9%
EAT = (1 – 0.619) * 102 ns + 0.619 * 192 ns = 157.71 ns
9 4 8 1 4 9 2 9 4 5 4 5 3 4
6
4 3
7
4 9 4
F 9 9 9 1 1 1 1 1 4 4 4 4 4 4
4
4 4
7
7 7 7
1
F 4 4 4 4 4 2 2 2 2 2 2 3 3
3
3 3
3
4 4 4
2
F 8 8 8 9 9 9 9 5 5 5 5 5
6
6 6
6
6 9 9
3
fi 9 9 9 4 4 1 9 9 2 4 4 4 5 5
4
4 4
3
6 9 9
f
4 4 8 8 4 1 1 9 2 2 2 4 4
3
3 3
6
7 7 7
o
8 1 1 9 2 2 4 5 5 5 3 3
6
6 6
7
4 4 4
R
9 9 9 1 1 1 2 2 2 4 4 4 5 5
6
6 6
7
7 7 7
bi
4 4 4 9 9 9 4 5 5 5 3 3 4 4 4 4 4
t 8 4 3 9 9
b) OPTIMAL has the smallest EAT but in reality, this algorithm is impractical so
the best solution in this scenario would be the second smallest algorithm which is
LRU.
Question 8:
lOMoARcPSD|46342985
a) No. frames = 512MB / 4096 bytes = 2
29
/ 2
12
= 2
17
= 131072 frames
b) No. offsets = 4096 = 2
12
Use 12 bits for storing d
Use 32 – 12 = 20 bits for storing p
Maximum number of pages = 2
20
pages
c) Explain what happens if the processes generate below virtual
addresses: P2 – address 13000 p = 3, d = 712
references page 3, offset 712 which is represented in the frame
#400 P1 – address 13000 p = 3, d = 712
references page 3, offset 712 which is not in the memory
page fault need to load page 3 of P1 into memory free frame #0 load
page 3 of P1 into frame #0, update valid bit = 1
Page
Frame
Valid bit
0
#300
1
1 0
2
#301
1
3
#0
1
Page
Frame
Valid bit
0
#300
1
1
0
2
#302
1
3
#400
1
Page
Frame
Valid bit
0
0
1
0
2
0
3
0
P1 – address 16383 p = 3, d = 4095
references page 3, offset 4095 which has been loaded into memory
at frame #0
P3 – address 4096 p = 1, d = 0
references page 1, offset 0 which is not in the memory
page fault need to load page 1 of P3 into memory free frame NO page
replacement: LRU, queue of referenced page: P2.3, P1.3
move P2.3 out and move P3.1 into memory at frame #400
Page
Frame
Valid bit Page
Frame
Valid bit
Page
Frame
Valid bit
0
#300
1 0
#300
1
0
0
1 0 1
0
1 #400
1
2
#301
1 2
#302
1
2
0
3
#0
1 3
0
3
0
P3 – address 13000 p = 3, d = 712
references page 3, offset 712 which is not in the memory
page fault need to load page 3 of P3 into memory free frame NO page
replacement: LRU, queue of referenced page: P1.3, P3.1
move P1.3 out and move P3.3 into memory at frame #0
lOMoARcPSD|46342985
Page
Frame
Valid bit Page
Frame
Valid bit
Page
Frame
Valid bit
0
#300
1 0
#300
1
0
0
1 0 1
0
1 #400
1
2
#301
1 2
#302
1
2
0
3 0 3
0
3 #0
1
P2 – address 16383 p = 3, d = 4095
references page 3, offset 4095 which is not in the memory
page fault need to load page 2 of P3 into memory free frame NO page
replacement: LRU, queue of referenced page: P3.1, P3.3
move P3.1 out and move P2.3 into memory at frame #400
Page
Frame
Valid bit Page
Frame
Valid bit
Page
Frame
Valid bit
0
#300
1 0
#300
1
0
0
1 0 1
0
1
0
2
#301
1 2
#302
1
2
0
3 0 3
#400
1
3 #0
1
| 1/5
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

lOMoARcPSD|46342985 lOMoARcPSD|46342985
Họ tên: Nguyễn Văn Đăng Huỳnh MSSV: 21127063 Lớp: 21CLC10 OPERATING SYSTEM COURSE
EXERCISE#4: MEMORY AND VIRTUAL MEMORY Question 1:
- Page size = 1KB = 210 byte No. bits for offset: 10
- No. frames = 32 = 25 5 bits for storing f 15 bit for storing physical address
- Size of the program P = No.page * Page size = 8 * 1KB = 8KB
- Size page = Size frame Size frame = 1KB Size of the physical memory =
No.frames * Size frame = 32 * 1KB = 32KB Question 2:
- A byte-addressable memory of 320MB = (226 * 5) byte
- Page size = 8KB = 213 byte
a) No. frames = (226 * 5) / 213 = 213 * 5
b) Number of pages in logical address spaces: 248 / 213 = 235 Maximum no. pages = 235 pages
c) No. offset of each page = 213 = 8192
offsets 1892 <0, 1892> 15296 <1, 7104> 20300 <2, 3916> Question 3:
a) No. bits for storing d = 32 – 9 – 11 = 12 No. offsets = 212
Word-addressable memory 1 offset points a word of 4 bytes
Size of a page = 212 * 4 = 214 bytes = 16KB
b) Frame size = Page size = 16KB
No. frames = 10GB / frame size = 10GB / 16KB = 217 frames
c) Maximum size of process space supported in this system = 232 * 4 = 234 bytes = 24 GB = 16GB
d) A program of 3GB can be divided into 3GB / 16KB = (3 * 220) KB / 24 KB
= 3 * 216 pages integer value no fragmentation e) Internal fragmentation Question 4: lOMoARcPSD|46342985
- h = 0.75, tc = 25 ns, tm = 132 ns, L = 3
- EAT = h * (tc + tm) + (1 – h) * (tc + (L + 1) * tm)
= 0.75 * (25 ns + 132 ns) + (1 – 0.75) * (25 ns + (3 + 1) * 132 ns)
= 0.75 * 157 ns + 0.25 * 552 ns = 255.75 ns Question 5:
- EAT = 225 ns, tc = 25 ns, tm = 150 ns, L = 1
- EAT = h * (tc + tm) + (1 – h) * (tc + (L + 1) * tm)
225 ns = h * (25 ns + 150 ns) + (1 – h) * (25 ns + 2 * 150 ns)
225 ns = h * 175 ns + (1 – h) * 325 ns -100 ns = -150h h = 2/3 = 0.66 Question 6:
- tm = 100 ns, tc = 15 ns, tp = 150000 ns, h = 0.75, p = 0.0005
- EAT = h * (tc + tm) + (1 – h) * [(1 – p) * (tc + 2 * tm) + p * tp]
= 0.75 * (15 ns + 100 ns) + (1 – 0.75) * [(1 – 0.0005) * (15 ns + 2 * 100 ns) + 0.0005 * 150000 ns]
= 0.75 * 115 ns + 0.25 * (0.9995 * 215 ns + 75 ns)
= 86.25 ns + 72.473125 ns = 158.723125 ns Question 7:
a) FIFO, Optimal, LRU, Second chance
FIFO: no.page fault = 13, page fault hit ratio = 13/21 = 61.9%
EAT = (1 – 0.619) * 102 ns + 0.619 * 192 ns = 157.71 ns 9 4 8 1 4 9 2 9 4 5 4 5 3 4 6 4 3 7 4 9 4 F 9 9 9 1 1 1 1 1 4 4 4 4 4 4 6 6 6 6 6 9 9 1 F 4 4 4 4 9 9 9 9 5 5 5 5 5 5 4 4 4 4 4 4 2 F 8 8 8 8 2 2 2 2 2 2 3 3 3 3 3 7 7 7 7 3 fi 9 9 9 4 4 8 1 1 9 2 2 2 4 4 5 3 3 6 6 4 4 f 4 4 8 8 1 9 9 2 4 4 4 5 5 3 6 6 4 4 7 7 o 8 1 1 9 2 2 4 5 5 5 3 3 6 4 4 7 7 9 9
OPTIMAL: no.page fault = 10, page fault hit ratio = 10/21 = 47.6% lOMoARcPSD|46342985
EAT = (1 – 0.476) * 102 ns + 0.476 * 192 ns = 144.84 ns 9 4 8 1 4 9 2 9 4 5 4 5 3 4 6 4 3 7 4 9 4 F1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 6 6 6 6 6 9 9 F2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 F3 8 1 1 1 2 2 2 5 5 5 3 3 3 3 3 7 7 7 7
LRU: no.page fault = 11, page fault hit ratio = 11/21 = 52.4%
EAT = (1 – 0.524) * 102 ns + 0.524 * 192 ns = 149.16 ns 9 4 8 1 4 9 2 9 4 5 4 5 3 4 6 4 3 7 4 9 4 F1 9 9 9 1 1 1 2 2 2 5 5 5 5 5 6 6 6 7 7 7 7 F2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 F3 8 8 8 9 9 9 9 9 9 9 3 3 3 3 3 3 3 9 9
Second chance: no.page fault = 13, page fault hit ratio = 13/21 = 61.9%
EAT = (1 – 0.619) * 102 ns + 0.619 * 192 ns = 157.71 ns 9 4 8 1 4 9 2 9 4 5 4 5 3 4 6 4 3 7 4 9 4 F 9 9 9 1 1 1 1 1 4 4 4 4 4 4 4 4 4 7 7 7 7 1 F 4 4 4 4 4 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 2 F 8 8 8 9 9 9 9 5 5 5 5 5 6 6 6 6 6 9 9 3 fi 9 9 9 4 4 1 9 9 2 4 4 4 5 5 4 4 4 3 6 9 9 f 4 4 8 8 4 1 1 9 2 2 2 4 4 3 3 3 6 7 7 7 o 8 1 1 9 2 2 4 5 5 5 3 3 6 6 6 7 4 4 4 R 9 9 9 1 1 1 2 2 2 4 4 4 5 5 6 6 6 7 7 7 7 bi 4 4 4 9 9 9 4 5 5 5 3 3 4 4 4 4 4 t 8 4 3 9 9
b) OPTIMAL has the smallest EAT but in reality, this algorithm is impractical so
the best solution in this scenario would be the second smallest algorithm which is LRU. Question 8: lOMoARcPSD|46342985
a) No. frames = 512MB / 4096 bytes = 229 / 212 = 217 = 131072 frames
b) No. offsets = 4096 = 212 Use 12 bits for storing d
Use 32 – 12 = 20 bits for storing p
Maximum number of pages = 220 pages
c) Explain what happens if the processes generate below virtual
addresses: P2 – address 13000 p = 3, d = 712
references page 3, offset 712 which is represented in the frame
#400 P1 – address 13000 p = 3, d = 712
references page 3, offset 712 which is not in the memory
page fault need to load page 3 of P1 into memory free frame #0 load
page 3 of P1 into frame #0, update valid bit = 1 Page Frame Valid bit Page Frame Valid bit Page Frame Valid bit 0 #300 1 0 #300 1 0 0 1 0 1 0 1 0 2 #301 1 2 #302 1 2 0 3 #0 1 3 #400 1 3 0
P1 – address 16383 p = 3, d = 4095
references page 3, offset 4095 which has been loaded into memory at frame #0
P3 – address 4096 p = 1, d = 0
references page 1, offset 0 which is not in the memory
page fault need to load page 1 of P3 into memory free frame NO page
replacement: LRU, queue of referenced page: P2.3, P1.3
move P2.3 out and move P3.1 into memory at frame #400 Page Frame Valid bit Page Frame Valid bit Page Frame Valid bit 0 #300 1 0 #300 1 0 0 1 0 1 0 1 #400 1 2 #301 1 2 #302 1 2 0 3 #0 1 3 0 3 0
P3 – address 13000 p = 3, d = 712
references page 3, offset 712 which is not in the memory
page fault need to load page 3 of P3 into memory free frame NO page
replacement: LRU, queue of referenced page: P1.3, P3.1
move P1.3 out and move P3.3 into memory at frame #0 lOMoARcPSD|46342985 Page Frame Valid bit Page Frame Valid bit Page Frame Valid bit 0 #300 1 0 #300 1 0 0 1 0 1 0 1 #400 1 2 #301 1 2 #302 1 2 0 3 0 3 0 3 #0 1
P2 – address 16383 p = 3, d = 4095
references page 3, offset 4095 which is not in the memory
page fault need to load page 2 of P3 into memory free frame NO page
replacement: LRU, queue of referenced page: P3.1, P3.3
move P3.1 out and move P2.3 into memory at frame #400 Page Frame Valid bit Page Frame Valid bit Page Frame Valid bit 0 #300 1 0 #300 1 0 0 1 0 1 0 1 0 2 #301 1 2 #302 1 2 0 3 0 3 #400 1 3 #0 1