10 - Storage

Question 1

Main components of file system

Answer 1

1. Directory service

2. Storage service

Question 2

Directory service : what

Answer 2

1. Map file names => file identifiers

2. Handle access and existence control

Question 3

Storage service : what

Answer 3

1. Provide mechanism to store data on disk

2. Means to implement directory service

Question 4

What is a file?

Answer 4

1. Abstraction for non-volatile storage
2. User abstraction ???
3. Different types : data (numeric, character, binary), program (source, object, executable), documents.
4. Typically comprises a single contiguous logical address space

Question 5

Internal structure of file

Answer 5

Can be:

1. None : simple sequence of words / bytes
2. Simple record structure : lines, fixed length, variable length
3. Complex internal structure : formatted document, relocatable object file.

Question 6

Difference between text and binary

Answer 6

Text vs binary ??

1. Sequence of lines, each terminated by a special character
2. Explicit EOF character

Can map anything to a byte sequence by insertion of control characters, and interpretation in code.

Question 7

Compare programmer / OS deciding control characters

Answer 7

1. OS : may be easier for programmer but will lack flexibility (e.g. ?)
2. Programmer : has to do more work (why?) but can evolve and develop format (how?).

Question 8

State two ways of naming files

Answer 8

At least two kinds:

1. System file ID (SFID)
   - typically a unique integer value associated with a file, used within file system itself.
2. Human name
   - e.g. hello.java, what users like to use
3. User file ID
   - used to identify open files in applications

Question 9

Purpose of the directory data structure [not directory service as a whole]

Answer 9

1. Store mapping from human name to SFID

=> Provide means to translate (user) name to location of file on disk.

more purposes?

Question 10

Storage of directories

Answer 10

1. Directories are also non-volatile,
   .: store on disk with files
2. Storage system sits “below” directory service (since storage system prerequisite to directory service).

Question 11

Information contained in file metadata

Answer 11

What : any data about file excluding the contents of the file
EG
1.

Question 12

File control block :

Answer 12

Directory resolves name to SFID, then need to map from SFID to FCB (file control block) – this mapping is file specific [diagram]

FCB:
- Contents, name(s)

Metadata

• Location : ptr to file location on device
• Size in bytes
• Time, date of creation,
• User / owner identification : data for access permissions, security and usage monitoring.
• Protection : controls who can read, write
• Type : e.g. file vs directory

Question 13

Requirements of directory datastructure

Answer 13

=> Purpose: Provide means to translate (user) name to location of file on disk.

Requirements:
EFFICIENCY : locate physical location of file with user name quickly
NAMING : user convenience
- Allow two ( … N) users to have same name for different files.
- Allow one file to have several different names
GROUPING
- Logical grouping of files by properties, e.g. “all Java programs”.

Question 14

Evaluate single level directory

Answer 14

What : one directory shared between all users

• Naming problem : why
• Grouping problem : why

Question 15

Evaluate two level directory

Answer 15

One directory per user
- Access via pathname (e.g. bob : hello.java )
- Can have same filename for different user
- But still no grouping capability.
=> add a general hierarchy for more flexibility.

Question 16

Describe : tree structure hierarchies

Answer 16

1. Directories hold files, OR further directories,
2. Reflect structure of organisation, users’ files …. (etc ?)
3. Creation/ deletion of files is relative to given directory
4. Can search efficiently.
5. Arbitrary grouping capability
6. Human name = full path name, but can get unwieldy (separate qn)

Question 17

How to resolve user name = long path name problem with tree structured directories.

Answer 17

1. Resolve with
   - relative naming
   - login directory
   - current working directory
   [how?]
2. Sub-directory deletion either by requiring that the directory is empty, or by recursively deleting. [what ?]

Question 18

Describe : DAG directory structure

Answer 18

1. Hierarchy is useful but tree only allows one name per file.
2. Extend tree to DAG structure - allow shared subdirectories and files,
3. Allow multiple aliases for same file.
4. Manage dangling references - using back references or reference counts.

Question 19

Issues with DAG directory structure

Answer 19

1. Deletion [more generally, permission - why?]
2. Knowing when OK to free disk blocks [why?]
3. Accounting - who gets “charged” for disk usage;
4. Cycles, and how we prevent them

[slide needs work]

Question 20

Explain how directories are implemented

Answer 20

1. Directories are non-volatile
   .: store as “files” on disk
   - each directory has own SFID.

[slide needs significant work]

Question 21

State basic operations which can be performed on files

Answer 21

1. Open
   - UFID = open ( < pathname > )
   - UFID = create ( < pathname > )

=> Directory service recursively searches directories for components of

• Eventually get SFID for file => SFID used to create UFID and returned.
• Various modes can be used [e.g.?]

2. Use
   - info here?
3. Close
   - Closing a file
   => status = close (UFID)
   - copy new FCB back to HDD and invalidate UFID [where?]

[split into smaller cards]

Question 22

Discuss implementation of files

Answer 22

1. Associate file position with each open file (i.e associate file position with UFID)
   - initialise cursor / file posn to start of file.
2. Basic operations : read next or write next few bytes …
   => read (UFID, buf , nbytes)
   => read (UFID, buf, nrecords)

Question 23

Types of file access patterns

Answer 23

1. Sequential : adds rewind (UFID) to above [what is this?]
2. Direct access : [what?]
   - read (N)
   - write (N)
   using
   - seek (UFID, pos)
3. Maybe others including append-only, indexed sequential access mode (ISAM) [what?]

Question 24

Outline how file system provides access controls

Answer 24

1. File owner / creator should have control over WHAT can be done, and by WHOM.

=> file usually only accessible IF user has :
a. Directory access rights (lookup process: can’t look it up => can’t open it)
AND
b. File access rights

Assuming a DAG structure, do we use the presented or absolute path [what?]

Access control normally provided by the directory service, so checks done at file-open time. EG read, write, execute, append, delete, list, rename. [what?]

More advanced schemes are possible [see later??]

Question 25

Explain issues of existence control

Answer 25

What do we do if user deletes a file?
=> Probably want to keep file in existence while a valid pathname referencing it exists.
=> Need to check entire FS periodically for garbage.
=> Existence control can also be a factor when file is renamed / moved [why]

Question 26

Issues : concurrency control

Answer 26

=> Need locking to handle simultaneous access

1. Can be mandatory or advisory
2. Locks may be shared or exclusive
3. Granularity may be file or subset.