pot of gold
7
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
7
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
- cours - matière potentielle : equivocation
- exposé
- expression écrite
- clause 1.1.2.1 defines
- employer with the legal implications
- construction contracts
- interpretation of contracts
- clause
- law
- employer
- engineer
- contract
CS-471 OPERATINGSYSTEM CONCEPTSHW5
CS 471: Operating System ConceptsSpring 2009Lecture: T 1910-2150 HW #5Points: 20Due: Mar 24 , 2009Question 1: [3 Points]
Consider the two-dimensional array A: intA[][] = new int[100][100]; where A[0][0] is at location 200 in a paged memory system with pages of size 200. A small process that manipulates the matrix resides in page 0 (locations 0 to 199). Thus, every instruction fetch will be from page 0.
For three page frames, how many page faults are generated by the following array-initialization loops, using LRU replacement and assuming that page frame 1 contains the process and the other two are initially empty a. for (int j=0;j<100;j++)
for (int i=0;i<100;i++)
A[i][j] = 0;
b. for(int i=0;i<100;i++) for(int j=0;j<100;j++) A[i][j]=0;
a) There are 50 pages and 100 faults per page.
Hence We have, 50 x 100 = 5000 Page faults.
b) 50 Page faults.
- 1 -
CS-471 OPERATINGSYSTEM CONCEPTSHW5
Question 2: [3 Points] Consider the following page reference string: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6(20) How many page faults would occur for following replacement algorithms assuming one, two, three, four, five, six and seven frames? Remember that all frames are initially empty, so your first unique pages cost one fault each.
LRU 1 FRAME 2 FRAME 3 FRAME 4 FRAME 5 FRAME 6 FRAME 7 FRAME
1 1 1 1 1 1 1 1
2 2 1 2 1 2 1 2 1 2 1 2 1 2
3 3 3 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
4 4 3 4 4 2 3 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
2 2 2 4 4 2 1 1 2 5 4 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 1 2 1 5 2 1 1 2 5 6 1 2 6 4 5 1 2 3 4 5 6 1 2 3 4 5 6
5 5 5 1 5 6 1 1 2 3 6 1 2 6 3 5 1 2 3 7 5 6 1 2 3 7 5 6 7
6 6 5 6 5 6 2 1 2 3 7 1 2 6 3 7
2 2 2 6 1 6 2 6 2 3 7
1 1 2 1 1 3 2 6 2 3 1
- 2 -
2 2 2 3 7 3 2
3 3 7 3 7 3 6
7 7 7 6 2 3 6
6 6 3 6 2 3 1
3 3 3 2 2 3 6
2 2 1 2
1 1 3 2
2 2 3 6
3 3
6 6
PAGE FAULTS 20 18 15 10 8 7 7
CS-471 OPERATINGSYSTEM CONCEPTSHW5
FIFO 1 FRAME 2 FRAME 3 FRAME 4 FRAME 5 FRAME 6 FRAME 7 FRAME
1 1 1 1 1 1 1 1
2 2 1 2 1 2 1 2 1 2 1 2 1 2
3 3 3 2 1 2 3 1 2 3 1 2 3 4 1 2 3 1 2 3
4 4 3 4 4 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 1 2 3 4
2 2 2 4 4 1 3 5 2 3 4 6 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 1 2 1 4 1 5 5 6 3 4 6 1 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6
5 5 5 1 6 1 5 5 6 2 4 6 1 2 4 5 7 2 3 4 5 6 1 2 3 4 5 6 7
6 6 5 6 6 2 5 5 6 2 1 6 1 2 3 5 7 1 3 4 5 6
2 2 2 6 6 2 1 3 6 2 1 6 1 2 3 7 7 1 2 4 5 6
1 1 2 1 3 2 1 3 7 2 1 7 1 2 3 5 6
- 3 -
2 2 2 3 3 7 1 3 7 6 1
3 3 7 3 3 7 6 3 7 6 2
7 7 7 6 2 7 6 1 7 6 2
6 6 3 6 2 1 6 1 3 6 2
3 3 3 2 2 1 3
2 2 1 2 6 1 3
1 2 3 6 PAGEFAULTS1 2 3 620 1 618 3 316 14 9 10 7
CS-471 OPERATINGSYSTEM CONCEPTSHW5
OPTIMAL 1 FRAME 2 FRAME 3 FRAME 4 FRAME 5 FRAME 6 FRAME 7 FRAME
1 1 1 1 1 1 1 1
2 2 1 2 1 2 1 2 1 2 1 2 1 2
3 3 3 2 1 2 3 1 2 3 4 1 2 3 1 2 3 1 2 3
4 4 4 2 1 2 4 1 2 3 5 1 2 3 4 1 2 3 4 1 2 3 4
2 2 1 2 1 2 5 1 2 3 6 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 1 5 2 1 2 6 7 2 3 6 1 2 3 6 5 1 2 3 4 5 6 1 2 3 4 5 6
5 5 6 2 3 2 6 1 2 3 6 1 2 3 6 7 1 2 3 7 5 6 1 2 3 4 5 6 7
6 6 1 2 3 7 6
2 2 3 2 3 2 6
- 4 -
1 1 3 7 3 2 1
2 2 3 6 6 2 1
3 3 3 2
7 7 1 2
6 6 3 2
3 3 3 6
2 2
1 1
2 2
3 3
6 6
PAGE FAULTS 20 15 11 7 7 7 7
CS-471 OPERATINGSYSTEM CONCEPTSHW5
Question 3: [3 Points] Consider the page table for a system with 12-bit virtual and physical addresses with 256-byte pages. The list of free page frames is D, E, F (that is, D is at the head of the list, E is second and F is last). Pa ePa eFrame 0 -1 2 2 C 3 A 4 -5 4 6 3 7 -8 B 9 0 Convert the following virtual addresses to their equivalent physical addresses in hexadecimal. All numbers are given in hexadecimal. (A dash for a page frame indicates that the page is not in memory) Answer:
#
1.2.3.4.
Virtual addresses
9EF 111 700 0FF
Physical addresses
0EF 211 D00 EFF
Question 4: [4 Points] Consider a file currently consisting of 100 blocks. Assume that the file-control block (and the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguous-allocation case, assume that there is no room to grow at the beginning but there is room to grow at the end. Also assume that the block information to be added is stored in memory. a.The block is added at the beginning. b.The block is added in the middle. c.The block is added at the end. d.The block is removed from the beginning. e.The block is removed from the middle.
- 5 -
CS-471 OPERATINGSYSTEM CONCEPTSHW5
The block is removed from the end. f.Answer: a) Contagious = 201 Linked= 1 Indexed= 1 b) Contagious = 101 Linked= 52 Indexed= 1 c) Contagious = 1 Linked= 3 Indexed= 1 d) Contagious = 198 Linked= 1 Indexed= 0 e) Contagious = 98 Linked= 52 Indexed= 0 f) Contagious = 0 Linked= 100 Indexed= 0
Question 5: [ 3 Points ] Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the three allocation strategies (contiguous, linked and indexed), answer these questions: a)How is the logical-to-physical address mapping accomplished in this system? (for the indexed allocation, assume that a file is always less than 512 blocks long.) b)If we are currently at logical block 10 (the last block accessed was block 10) and want to access logical block 4, how many physical blocks must be read from the disk Answer: a) Contagious: Logical Address/512 = (x, y) Here x = quotienty = reminder Physical block address = x + starting block address Y = displacement
- 6 -
CS-471 OPERATINGSYSTEM CONCEPTSHW5
Linked: Logical address/511 = (x, y) Traverse the link list (x+1 blocks) Displacement = y + 1 Indexed: Logical address = (x, y) X = Location of the index block. Y = Displacement b) Contagious = 1 Linked = 4 Indexed = 2 Question 5: [ 4 Points ] Consider a file system that uses inodes to represent files. Disk blocks are 8 KB in size, and a pointer to a disk block requires 4 bytes. This file system has 12 direct disk blocks, as well as single, double and triple indirect disk blocks. What is the maximum size of a file that can be stored in this file system? 12 direct disk blocks *8KB = 96KB 1 single disk block= 2048 * 8KB = 16384KB 1 double disk block= 2048^2 * 8 KB = 33554432 KB 1 triple disk block= 2048^3 * 8 KB = 68719476736 KB Total =64.03 TB
- 7 -
