Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS3106: Operating Systems > File System Implementation > Flashcards

File System Implementation Flashcards

1
Q

How does the OS implement a file system?

A

Disks provide the bulk of secondary storage.

Data transferred block at a time from disk.

File system imposed on secondary storage for convenience.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What types of File System data structures are there?

A

On-disk structures
- Arrangement of data on the physical storage device

In-memory structures.
- OS structures held in memory.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

List the on-disk structures?

A
  • Boot control block
  • File control Block
  • Directory
  • Volume
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the Boot control block?

A

Contains the information needed to boot an OS from a disk

Collection of blocks holding a memory image.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a Volume Control Block

A

Structure describing how storage device is separated

Contains partition size, location of free blocks and FCBs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What does the directory structure do?

A

Organises files.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the FCB?

A

File control block, describes individual file.

Contains:
Permissions, dates, owner, group, ACL, size and data block numbers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the in-memory structures?

A

Table listing storage volumes in use, and cache of recently accessed directories.

System-wide open file table and Per-Process file table

Fastest structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How are files created?

A
  1. Allocate new FCB
  2. Read appropriate directory into memory
  3. Update with file name and FCB.
  4. Write directory back to disk.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How are files opened?

A
  1. Traverse directory structure to obtain FCB with file name/dir path given.
  2. Copy FCB from disk into System-wide open file table.
  3. Add pointer to per-process open file table.
  4. Return File Descriptor
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How are files read?

A

Transfer data blocks in secondary storage to memory by finding them from the System-wide open-file table.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does a Virtual File System do?

A

Allows UNIX/linux to support the use of multiple different file systems.

Require concurrent access to multiple file systems, data can be stored on a number of different devices and can have different implementations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does the VFS allow for?

A

The same system call interface can be used for different types of file system.

Defines file system operations and semantics

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How does VFS abstract the file system?

A

Builds a single directory tree composed of multiple file systems.

Distinguishes local files from remote ones, activating local file-system-specific operations on ones it knows.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are the objects that make up the VFS?

A
  • Inode
  • File
  • Superblock
  • Dentry
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is an Inode

A

Represents an individual file in a file system

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is a file object (VFS)

A

Represents an open file

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is a superblock object?

A

Represents an entire file system

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a Dentry object?

A

Represent an individual directory entry.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

How does the DFS allow access to it’s objects?

A

Defines an interface for each object type, and a set of operations on the object. This is an abstraction over each file system’s implementation.

21
Q

List the disk allocation methods.

A
  • Contiguous allocation
  • Linked allocation
  • Indexed allocation
22
Q

How is data accessed sequentially when using contiguous allocation

A

Usually no head movement to get next block, assuming nothing else is using the disk.

Move one track when switching cylinders

23
Q

How is data accessed directly when using contiguous allocation

A

Access i’th block of file starting at block b, b+i

24
Q

How are files created when using contiguous allocation?

A

Dynamic storage allocation problem, find first/best fit.

25
Q

How are files expanded when using contiguous allocation?

A

Have to copy whole file to a larger space, may run up against other files in the sequential memory space.

26
Q

What is the effect on external fragmentation when using contiguous allocation?

A

Need to compact information in sequential space, very expensive.

Performed off-line and relatively infrequently.

27
Q

How is data accessed sequentially when using linked allocation?

A

Need to move head in order to get next block, which can be anywhere on the disk.

28
Q

How is data accessed directly when using linked allocation?

A

Not possible, have to read file sequentially to get to required position. Location of i’th block stored in block i - 1.

29
Q

What are the advantages of linked allocation?

A

File creation and expansion are easy. No external fragmentation problem.

30
Q

What are the disadvantages of linked allocation?

A

Slower access time because linked list has to be traversed in order to find the node.

31
Q

What is clustering in linked allocation?

A

Allocate blocks in sequential cluster, reducing space overhead and head movement.

Increased internal fragmentation as not every file may fit into space.

32
Q

What is the File Allocation Table?

A

Variation on linked allocation.

Section of disk at beginning of volume holds FAT, one entry per disk block and indexed by block number.

33
Q

How does FAT help find files?

A

Directory contains block number of first block of file.

Table entry indexed by that block number and contains block number of next block.

Last block has EOF value.

(Basically jumps around LL to each node that is in the same file)

34
Q

How are blocks accessed sequentially when using indexed allocation?

A

Same as linked allocation. Head movement overhead.

35
Q

How are blocks directly accessed when using indexed allocation?

A

Address of any block can be calculated from the index.

Address of block i in the i’th entry of the index.

36
Q

When happens when files are created when using indexed allocation?

A

Index block allocated, keeps the mapping between index and memory location.

37
Q

What are the the drawbacks of using indexed allocation?

A

There is unused space in each index block

38
Q

How is file expansion done when using indexed allocation?

A

Select free block and update index block.

Index block may fill up.

Can have have linked list of index blocks or multi-level index.

39
Q

What is multi-level indexing?

A

n level block points to n+1 blocks.

Number of levels, n, determines maximum file size.

40
Q

What is a hybrid-scheme?

A

Combination of indexing and multi-level indexing.

FCB implementation. First 15 pointers of index block stored in file’s inode.

First 12 point to direct blocks. Next three point to indirect blocks.

  • Single indirect block
  • Double indirect block.
  • Triple indirect block
41
Q

How is maximum file size calculated?

A

block size * 2^10 (for 32-bit block addresses)

42
Q

How does the file system inode table work?

A

Entry for each inode

inodes are addressed by their index in the table.

43
Q

What is a (hard) link?

A

When more than one directory entry exists for a single inode.

Link count kept in inodes. When count == 0 block can be freed. This only works on Acyclic structures.

Cant make hard link to dir.

44
Q

What is a symbolic link?

A

Soft link, file containing the path to the link target.

45
Q

When can consistency issues arise?

A

As file systems read, modfy and ptentially delay write-back for some time then if the system crashes there can be consistency issues.

fsck checks consistency of files.

46
Q

What are the features of a journaling file system?

A

Meta-data updates are written sequentially to journal, a log stored in disk. Write occurs before updating the file system.

Transaction-oriented approach

47
Q

What happens when a transaction written to the journal is committed?

A

System call returns and log entries are replayed across the actual file system structures.

Completed transaction are removed from the log

48
Q

How does a journaling file system recover from a crash?

A

> = 0 transactions in log, replay log entries to make file system consistent and undo changes made by partially executed transaction.

49
Q

What is the drawback of journaling?

A

Overheads - write meta-data twice.

CS3106: Operating Systems (20 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions