Unit6 - Subjective Questions

A file is an abstract data type that provides a mechanism for storing data on a storage device. To manage files, the operating system associates attributes (or metadata) with each file.

Common File Attributes:

1. Name: The symbolic file name is the only information kept in human-readable form.
2. Identifier: A unique tag (usually a number) identifies the file within the file system; it is the non-human-readable name for the file.
3. Type: This information is needed for systems that support different types of files (e.g., text, binary, executable).
4. Location: A pointer to a device and to the location of the file on that device.
5. Size: The current size of the file (in bytes, words, or blocks) and possibly the maximum allowed size are included in this attribute.
6. Protection: Access-control information determines who can do reading, writing, executing, and so on.
7. Time, date, and user identification: This information may be kept for creation, last modification, and last use. These data are useful for protection, security, and usage monitoring.

Sequential Access:

• Definition: Information in the file is processed in order, one record after the other.
• Operation: Read moves the file pointer forward; Write appends to the end.
• Analogy: Similar to a cassette tape.
• Efficiency: Efficient for applications that need to process all data (e.g., compilers).
• Seeking: No arbitrary seeking; to get to the middle, you must pass the beginning.

Direct (Relative) Access:

• Definition: A file is made up of fixed-length logical records that allow programs to read and write records rapidly in no particular order.
• Operation: Operations are performed on a specific block number (e.g., read block 10).
• Analogy: Similar to a vinyl record or CD.
• Efficiency: Essential for databases where immediate access to large amounts of information is required.
• Seeking: Allows arbitrary seeking to any block number.

Tree-Structured Directory:

• This generalizes the directory structure to a tree of arbitrary height.
• It has a root directory, and every file in the system has a unique path name.
• A directory (or subdirectory) contains a set of files or other subdirectories.
• Disadvantage: While it allows grouping, it does not naturally support the sharing of files or directories between different users.

Acyclic-Graph Directory:

• An acyclic graph allows directories to share subdirectories and files.
• The same file or subdirectory may be in two different directories.
• Implementation: Usually implemented via links (symbolic or hard links).

Problem Solved:
The Acyclic-Graph structure solves the file sharing problem. In a strict tree structure, a file belongs to exactly one parent directory. If two users need to work on a project file, a tree structure forces duplication of the file, leading to consistency issues. An acyclic graph allows the same file to be effectively "present" in multiple directories via linking.

Contiguous Allocation:
This method requires each file to occupy a set of contiguous blocks on the disk. Disk addresses define a linear ordering on the disk.

Advantages:

1. Performance: It provides excellent performance for sequential and direct access. For sequential access, the head moves minimal distance. For direct access to block , the location is simply .
2. Simplicity: Only the starting location (block number) and length (number of blocks) need to be stored in the directory.

Disadvantages:

1. External Fragmentation: As files are allocated and deleted, free space is broken into little pieces. Compaction is required to fix this.
2. File Growth: It is difficult to determine how much space a file typically needs. If a file needs to grow but the adjacent blocks are occupied, the file must be moved to a larger hole.

Linked Allocation:

• Each file is a linked list of disk blocks; the disk blocks may be scattered anywhere on the disk.
• The directory contains a pointer to the first and last blocks of the file.
• Drawback: Direct access is extremely inefficient because to find the -th block, pointers must be traversed from the beginning. Also, pointers consume space within the block.

Indexed Allocation:

• Indexed allocation solves the direct access problem by bringing all the pointers together into one location: the index block.
• Each file has its own index block, which is an array of disk-block addresses.
• The -th entry in the index block points to the -th block of the file.

Resolution:
Indexed allocation supports direct access without suffering from external fragmentation. Unlike linked allocation, where you must traverse the chain, the index block allows immediate lookup of the address for any specific file block.

To keep track of free disk space, the system maintains a free-space list. The list records all free disk blocks.

1. Bit Vector (Bit Map):

• Free space is implemented as a map of bits where each bit represents a block.
• If the -th bit is 0, the block is allocated; if it is 1, the block is free.
• Advantage: Efficient for finding the first free block or consecutive free blocks. Hardware support often exists for bit manipulation.
• Disadvantage: Bit vectors must be kept in main memory for speed, which can consume significant memory for large disks.

2. Linked List:

• All free blocks are linked together.
• The system keeps a pointer to the first free block in a special location on the disk (and in memory).
• Advantage: No waste of space; the pointers are stored in the free blocks themselves.
• Disadvantage: Inefficient for traversing the list (requires significant I/O) and does not support finding contiguous space easily.

File System Mounting:

• Just as a file must be opened before it is used, a file system must be mounted before it can be available to processes on the system.
• The operating system is given the name of the device and the mount point—the location within the file structure where the file system is to be attached.
• Typically, a mount point is an empty directory.
• Process:
  1. The OS verifies that the device contains a valid file system.
  2. The OS notes in its directory structure that a file system is mounted at the specified mount point.
  3. Traversing the directory structure essentially switches to the root directory of the mounted volume when the mount point is accessed.

Linear List:

• Method: A linear list of file names with pointers to the data blocks. Requires a linear search to find a file.
• Operations: Creation involves searching for duplicates and appending to the end. Deletion involves searching, releasing space, and possibly moving the last entry to the gap.
• Complexity: Search is , where is the number of files. This can be slow for large directories.

Hash Table:

• Method: A linear list stores directory entries, but a hash data structure is also used. The hash function takes the file name and returns a value pointing to the entry in the linear list.
• Complexity: Search is effectively .
• Issue: Collisions (two filenames hashing to the same location) must be handled, typically using chained overflow (linked lists for collisions). While faster, it is more complex to implement than a linear list.

1. Dedicated Devices:

   • Assigned to only one job at a time.
   • Examples: Tape drives, Plotters, Card readers.
   • Disadvantage: Inefficient if the job does not utilize the device 100% of the time during allocation.

2. Shared Devices:

   • Assigned to several processes concurrently.
   • The OS interleaves requests from different processes.
   • Examples: Hard disks, Optical drives.
   • Mechanism: Requires complex scheduling algorithms (like disk scheduling) to manage concurrent requests.

3. Virtual Devices:

   • A combination of dedicated devices and software that creates the illusion of a shared device.
   • Example: Spooling (Simultaneous Peripheral Operation On-Line) for printers. A dedicated printer is converted into a shared virtual device by writing print jobs to a disk buffer first.

Initial Head Position: 53
Queue: 98, 183, 37, 122, 14, 124, 65, 67

1. FCFS (First-Come, First-Served):
Order: 53 98 183 37 122 14 124 65 67

• Total Head Movement: cylinders.

2. SSTF (Shortest Seek Time First):
Start at 53. Select closest request.
Order: 53 65 67 37 14 98 122 124 183

• Total Head Movement: cylinders.

SCAN Algorithm:

• The disk arm starts at one end of the disk and moves toward the other end, servicing requests as it reaches each cylinder.
• At the other end, the direction of head movement is reversed, and servicing continues.
• Analogy: An elevator processing requests up and down.
• Advantage: Prevents starvation better than SSTF.

C-SCAN (Circular SCAN) Algorithm:

• Designed to provide a more uniform wait time.
• The head moves from one end of the disk to the other, servicing requests.
• When it reaches the other end, it immediately returns to the beginning of the disk without servicing any requests on the return trip.
• Concept: Treats the cylinders as a circular list that wraps around from the last cylinder to the first.

DASD (Direct Access Storage Devices):
Devices like magnetic disks, optical disks, and flash drives where each physical record has a discrete location and unique address, allowing direct access without sequential searching.

Access Architecture:

1. I/O Channels:
   • The CPU does not communicate directly with the control unit. It communicates with a Channel, which is a specialized processor dedicated to I/O.
   • The channel executes channel programs (I/O commands) in its own memory independent of the main CPU, allowing the CPU to perform other tasks while I/O is in progress.
2. Control Units:
   • The I/O Channel communicates with a Control Unit.
   • The Control Unit interfaces with the specific physical device (the drive).
   • It handles the electronics of the device, error correction, and converting logical commands from the channel into physical signals for the read/write heads.

Flow: CPU Channel Control Unit Device.

Definition:
IPC is a mechanism that allows processes to communicate with each other and synchronize their actions. It enables the exchange of data and information between cooperating processes.

Why is it necessary?

1. Information Sharing: Several users may be interested in the same piece of information (e.g., a shared file).
2. Computation Speedup: Breaking a task into subtasks that run in parallel (requires multi-core).
3. Modularity: Constructing a system in a modular fashion (e.g., separate database process and web server process).

Common IPC Methods:

• Pipes (Ordinary and Named)
• Shared Memory
• Message Queues
• Sockets
• Semaphores (primarily for synchronization)

Pipes:
A pipe acts as a conduit allowing two processes to communicate. It is typically a section of shared memory that the OS treats as a file. Ordinary pipes are unidirectional (half-duplex).

Functions:

1. popen() (Pipe Open):
   • Syntax: FILE *popen(const char *command, const char *type);
   • It creates a pipe, forks a child process, and invokes the shell to execute command.
   • If type is "r", the calling process can read the standard output of the command via the returned file stream.
   • If type is "w", the calling process can write to the standard input of the command.
2. pclose() (Pipe Close):
   • Syntax: int pclose(FILE *stream);
   • It closes the I/O stream associated with the pipe, waits for the child process to terminate, and returns the exit status of the command.

This high-level library interface simplifies the lower-level pipe(), fork(), dup2(), exec() sequence.

Shared Memory:
A region of memory that is mapped into the address space of more than one process. Once established, processes can read and write to this region effectively as if it were their own memory, making it the fastest form of IPC.

Producer-Consumer Problem:

• Scenario: A Producer process generates data, and a Consumer process uses it. They share a buffer.
• Shared Buffer: Implemented in the shared memory region.
• Variables: in (next free position), out (first full position).

Logic:

• Producer:
  c
  while (((in + 1) % BUFFER_SIZE) == out); // Wait if full
  buffer[in] = next_produced;
  in = (in + 1) % BUFFER_SIZE;

• Consumer:
  c
  while (in == out); // Wait if empty
  next_consumed = buffer[out];
  out = (out + 1) % BUFFER_SIZE;

• Note: Synchronization (semaphores/mutex) is usually required to prevent race conditions when updating pointers.

Ordinary Pipes (Anonymous Pipes):

• Existence: Exist only while the processes are communicating.
• Scope: Only accessible by processes that have a common ancestor (parent-child relationship). Created via pipe().
• Persistence: Once the processes finish, the pipe ceases to exist.
• Communication: Unidirectional (standard).

Named Pipes (FIFOs):

• Existence: Exist as a special file in the file system.
• Scope: Can be used by unrelated processes. Any process with appropriate permissions can open the FIFO for reading or writing.
• Persistence: They persist in the file system even after the creating process has terminated. Must be explicitly deleted.
• Communication: Bidirectional (though usually used strictly unidirectionally in practice).

Message Queues:

• A message queue is a linked list of messages stored within the kernel and identified by a message queue identifier.
• Processes can send messages to and receive messages from the queue.
• Unlike pipes, messages have a type associated with them. A receiving process can request a message of a specific type (allowing priority handling) or just read in FIFO order.

Operations:

1. Send: Places a message in the queue. Can be Blocking (wait if queue is full) or Non-Blocking.
2. Receive: Retrieves a message. Can be Blocking (wait if queue is empty) or Non-Blocking.

Advantages:

• No need for processes to be synchronized in time (asynchronous communication).
• Portable and flexible compared to shared memory (no need to worry about memory layout).

Access Control List (ACL):

• To provide granular protection, we can associate an Access Control List with each file and directory.
• The ACL specifies the names of users (or groups) and the types of access allowed for each user.
• Structure: A list of pairs: .
• Example:
  • File: Report.txt
  • ACL: Alice: Read/Write, Bob: Read, Charlie: None.
• Operation: When a user requests access to a particular file, the OS checks the ACL attached to that file. If the user is listed and the requested access is permitted, access is granted. Otherwise, it is denied.
• Pros: Very flexible.
• Cons: Constructing and maintaining the list can be tedious. The list can be variable length, complicating directory structures.

1. Serial Access Devices:

• Access Mechanism: Information must be accessed in a specific linear sequence.
• Seek Time: To reach data at location , the device must pass through locations $1$ to .
• Access Time: Highly dependent on the current location of the read/write head relative to the data.
• Example: Magnetic Tape drives. Good for archival storage and backups.

2. Direct Access Devices:

• Access Mechanism: Blocks of data have unique addresses and can be accessed directly without traversing preceding blocks.
• Seek Time: The read/write head can move directly to the cylinder containing the data.
• Access Time: Much faster and relatively uniform compared to serial access.
• Example: Magnetic Disks (HDD), Solid State Drives (SSD), Optical Disks (CD/DVD). Essential for random-access applications like databases and operating systems.

Memory-Mapped Files:
Memory mapping a file allows a part of the virtual address space to be logically associated with a file.

Advantages:

1. Performance: Accessing the file involves simple memory instructions (load/store) rather than system calls (read() and write()). This reduces overhead.
2. Coding Simplicity: Programmers can manipulate file data using pointers and arrays, just like standard memory variables.
3. Data Sharing: If multiple processes map the same file into their memory, they effectively share the data. One process writes to the memory, and others see the change (handled by the OS virtual memory manager).
4. Demand Paging: The OS automatically handles loading pages of the file into physical memory only when they are accessed, optimizing memory usage.