Computer Science 111 

Problem Set 6: Solution  

[provided by Austin Saypol]

1. [Storing files]

A) We now create FILE2 which requires 3 blocks.

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

6

<NONE>

6

7

0

7

8

6

8

9

7

9

10

8

10

<NONE>

9

1

2

<NONE>

2

<NONE>

1

3

4

<NONE>

4

5

3

5

<NONE>

4

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE1

2

1

FILE2

3

3

 

2. [Editing files]

A) Now, we edit FILE2 and need to add another block to store it.

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

7

<NONE>

7

8

0

8

9

7

9

10

8

10

<NONE>

9

1

2

<NONE>

2

<NONE>

1

3

4

<NONE>

4

5

3

5

6

4

6

<NONE>

5

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE1

2

1

FILE2

4

3

 

B) Next, we edit FILE1 and need to add another block to store it.

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

8

<NONE>

8

9

0

9

10

8

10

<NONE>

9

1

2

<NONE>

2

7

1

3

4

<NONE>

4

5

3

5

6

4

6

<NONE>

5

7

<NONE>

2

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE1

3

1

FILE2

4

3

 

3. [Deleting files]

A) Suppose the situation is as it was after Problem 1: FILE1 and FILE2 are both on disk, FILE1 is

2 blocks long, and FILE2 is 3 blocks long. Now we delete FILE2.

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

3

<NONE>

3

4

0

4

5

3

5

6

4

6

7

5

7

8

6

8

9

7

9

10

8

10

<NONE>

9

1

2

<NONE>

2

<NONE>

1

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE1

2

1

 

B) Again, suppose the situation is as it was after Problem 1: FILE1 and FILE2 are both on disk,

FILE1 is 2 blocks long, and FILE2 is 3 blocks long. This time we delete FILE1.

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

1

<NONE>

1

2

0

2

6

1

6

7

2

7

8

6

8

9

7

9

10

8

10

<NONE>

9

3

4

<NONE>

4

5

3

5

<NONE>

4

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE2

3

3

 

4. Suppose that we start with a clean disk and do the sequence of operations

 

A) create FILE1 of 2 blocks

 

FILE1 stored in blocks 1 & 2:

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

3

<NONE>

3

4

0

4

5

3

5

6

4

6

7

5

7

8

6

8

9

7

9

10

8

10

<NONE>

9

1

2

<NONE>

2

<NONE>

1

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE1

2

1

 

B) create FILE2 of 3 blocks

 

FILE2 stored in blocks 3,4,&5:

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

6

<NONE>

6

7

0

7

8

6

8

9

7

9

10

8

10

<NONE>

9

1

2

<NONE>

2

<NONE>

1

3

4

<NONE>

4

5

3

5

<NONE>

4

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE1

2

1

FILE2

3

3

 

C) create FILE3 of 3 blocks

 

FILE3 stored in blocks 6,7,&8:

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

9

<NONE>

9

10

0

10

<NONE>

9

1

2

<NONE>

2

<NONE>

1

3

4

<NONE>

4

5

3

5

<NONE>

4

6

7

<NONE>

7

8

6

8

<NONE>

7

  

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE1

2

1

FILE2

3

3

FILE 3

3

6

 

D) delete FILE2

 

Give blocks 3,4,&5 back to the free block list:

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

3

<NONE>

3

4

0

4

5

3

5

9

4

9

10

5

10

<NONE>

9

1

2

<NONE>

2

<NONE>

1

6

7

<NONE>

7

8

6

8

<NONE>

7

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE1

2

1

FILE3

3

6

 

E) create FILE4 of 2 blocks

FILE4 stored in blocks 3&4:

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

5

<NONE>

5

9

0

9

10

5

10

<NONE>

9

1

2

<NONE>

2

<NONE>

1

3

4

<NONE>

4

<NONE>

3

6

7

<NONE>

7

8

6

8

<NONE>

7

  

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE1

2

1

FILE3

3

6

FILE4

2

3

 

F) delete FILE1

 

Give blocks 1&2 back to the free block list:

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

1

<NONE>

1

2

0

2

5

1

5

9

2

9

10

5

10

<NONE>

9

3

4

<NONE>

4

<NONE>

3

6

7

<NONE>

7

8

6

8

<NONE>

7

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE3

3

6

FILE4

2

3

 

G) create FILE5 of 3 blocks Describe how the file system handles each of these operations.

 

FILE5 stored in blocks 1,2, & 5

 

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

9

<NONE>

9

10

0

10

<NONE>

9

1

2

<NONE>

2

5

1

5

<NONE>

2

3

4

<NONE>

4

<NONE>

3

6

7

<NONE>

7

8

6

8

<NONE>

7

  

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE3

3

6

FILE4

2

3

FILE5

3

1

 

5. A common operation done on a disk is to de-fragment the disk. When we do this, we scan the blocks of

each file on the disk and put them in contiguous locations. For the situation after all the actions of problem 4

have been taken, show the steps that would be gone through to defragment the disk. Your method has to

work step by step. At each step, you are able to switch the (data) contents of two blocks and then update

the information they contain about LAST and NEXT BLOCKs.

Transition process:

Let Xi is a block of the Xth file representing the ith block of the file:

Initial:

0

51

52

41

42

53

31

32

33

Free

Free

Step 1:

0

51

52

41

53

42

31

32

33

Free

Free

Final Step:

0

51

52

53

41

42

31

32

33

Free

Free

Snapshot after Step 1:

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

9

<NONE>

9

10

0

10

<NONE>

9

1

2

<NONE>

2

4

1

4

<NONE>

2

3

5

<NONE>

5

<NONE>

3

6

7

<NONE>

7

8

6

8

<NONE>

7

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE3

3

6

FILE4

2

3

FILE5

3

1

Snapshot after Final Step:

BLOCK NUMBER

NEXT BLOCK

PRIOR BLOCK

0

9

<NONE>

9

10

0

10

<NONE>

9

1

2

<NONE>

2

3

1

3

<NONE>

2

4

5

<NONE>

5

<NONE>

4

6

7

<NONE>

7

8

6

8

<NONE>

7

 

FILE NAME

FILE SIZE (in blocks)

FIRST BLOCK

FILE3

3

6

FILE4

2

4

FILE5

3

1

 

Comments? Questions? ------- Contact us at cs111@cs.princeton.edu