# Problem Set 6: Solution

[provided by Austin Saypol]

1. [Storing files]

A) We now create FILE2 which requires 3 blocks.

# 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.

# 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.

# 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.

# 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.

# 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:

# 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:

# 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:

# 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:

# 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:

# 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:

# 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

# 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:

# 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:

# 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