Unit6 - Subjective Questions

A file is an abstract data type. To define a file properly, the operating system maintains several attributes, which vary from one system to another. The common attributes are:

• Name: The symbolic file name is the only information kept in human-readable form.
• Identifier: A unique tag, usually a number, identifies the file within the file system (e.g., Inode number in Unix).
• Type: This is needed for systems that support different types of files (e.g., .txt, .exe, .c).
• Location: This is a pointer to a device and to the location of the file on that device.
• Size: The current size of the file (in bytes, words, or blocks) and possibly the maximum allowed size.
• Protection: Access-control information determines who can do reading, writing, executing, etc.
• 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.

The information about all files is kept in the directory structure, which is maintained on the disk.

File access methods determine how the information is read from the file.

Sequential Access

• Mechanism: Information in the file is processed in order, one record after the other. This is the most common method (based on the tape model).
• Operations: Read next, Write next, Rewind, Skip n records.
• Pros: Simple to implement.
• Cons: Inefficient for finding specific data in large files.

Direct (Random) Access

• Mechanism: A file is made up of fixed-length logical records that allow programs to read and write records rapidly in no particular order (based on the disk model).
• Operations: Read block , Write block , Position to block .
• Pros: Essential for databases where immediate access to large amounts of information is required.
• Cons: More complex to manage than sequential access.

Tree-Structured Directory

This is the most common directory structure. The directory contains a set of files or subdirectories. A directory is simply another file, but it is treated in a special way.

• Advantages:
  • Grouping: Users can create their own subdirectories and organize their files logically.
  • Naming: Efficient searching is possible, and the same file name can be used in different directories (path isolation).
• Disadvantages:
  • Accessing a file requires the full path name.

Acyclic-Graph Directory

An acyclic graph allows directories to share subdirectories and files. The same file or subdirectory may be in two different directories. This is typically implemented using links (hard links or symbolic links).

• Advantages:
  • Sharing: Allows files to be shared between users/groups easily without duplication.
• Disadvantages:
  • Traversal: Complexity increases; a file may have multiple absolute paths.
  • Deletion: Deleting a shared file is complex. If deleted by one user, does the file disappear for others? (Solved by reference counting or symbolic links).

Just as a file must be opened before it can be used, a file system must be mounted before it can be available to processes on the system.

• Mount Point: The location within the file structure where the file system is to be attached. Typically, this is an empty directory.
• Mechanism:
  1. The OS is given the name of the device and the mount point.
  2. The OS verifies that the device contains a valid file system.
  3. The OS notes in its directory structure that a file system is mounted at the specified mount point.
• Usage: Once mounted, the operating system traverses the directory structure, switching from the local file system to the mounted file system seamlessly when the mount point is accessed.
• Unmounting: The reverse process, detaching the file system, is called unmounting.

1. Contiguous Allocation:

• Concept: Requires each file to occupy a set of contiguous blocks on the disk.
• Pros: Best performance for sequential and direct access; simple implementation.
• Cons: External fragmentation; difficult to grow files.

2. Linked Allocation:

• Concept: Each file is a linked list of disk blocks; blocks may be scattered anywhere on the disk. The directory contains a pointer to the first and last blocks.
• Pros: No external fragmentation; file size can increase dynamically.
• Cons: Only sequential access is efficient (direct access is slow); space is wasted on pointers; reliability issues if a pointer is lost.

3. Indexed Allocation:

• Concept: Brings all pointers together into one location: the index block. Each file has its own index block, which is an array of disk-block addresses.
• Pros: Supports direct access efficiently; no external fragmentation.
• Cons: Wasted space for index blocks (overhead) for very small files.

The Access Matrix is a general model of protection that abstractly describes the protection mechanism.

• Rows: Represent domains (users or processes).
• Columns: Represent objects (files, printers, etc.).
• Entry : Defines the set of access rights that a process executing in domain has on object .

Implementation:
Since the matrix is usually sparse, it is rarely implemented as a full matrix. Instead, it is implemented via:

1. Access Control Lists (ACLs): Associated with objects (columns). Each file lists who can access it.
2. Capability Lists: Associated with domains (rows). Each user has a list of what they can access.

Since disk space is limited, the system must reuse space from deleted files. A free-space list records all free disk blocks.

1. Bit Vector (Bit Map):

• Each block is represented by 1 bit.
• If the block is free, the bit is 1; if allocated, the bit is 0.
• Example: If blocks 2, 3, 4 are free: $0011100...$
• Advantages: Simple to find the first free block or consecutive free blocks.
• Disadvantages: Requires hardware support (bit-manipulation instructions) and the vector must be kept in main memory, which can be large for big disks.

2. Linked List:

• Links together all free disk blocks. The head pointer is kept in a special location on the disk.
• Mechanism: The first free block contains a pointer to the next free block, and so on.
• Advantages: No wasted space (pointers are stored in free blocks).
• Disadvantages: Inefficient traversal; to find blocks, you must read the disk times.

The selection of directory allocation algorithms significantly affects the efficiency, performance, and reliability of the file system.

1. Linear List:

• Method: A linear list of file names with pointers to the data blocks. Requires a linear search to find a file.
• Pros: Simple to program.
• Cons: Time-consuming execution. To create a new file, the directory must be searched to ensure the name doesn't exist. Searching takes time.

2. Hash Table:

• Method: A linear list stores the directory entries, but a hash data structure is also used. The hash table takes a value computed from the file name and returns a pointer to the file name in the linear list.
• Pros: Decreases directory search time significantly ( on average).
• Cons: Implementation is more complex. Collisions (two file names hashing to the same location) must be handled. The hash table usually has a fixed size, requiring resizing or chaining if it fills up.

1. Dedicated Devices:

• These devices are assigned to only one job at a time. The job retains the device for the entire duration of execution.
• Example: Tape drives, Plotters.
• Drawback: Inefficient if the job does not utilize the device 100% of the time.

2. Shared Devices:

• These devices can be assigned to several processes concurrently. The OS manages the interleaving of requests.
• Example: Hard disks (Direct Access Storage Devices).
• Benefit: Increases system efficiency and resource utilization.

3. Virtual Devices:

• This is a combination of software and hardware that simulates a dedicated device on a shared device.
• Concept: Spooling (Simultaneous Peripheral Operations On-Line). For example, a printer is a dedicated device, but the OS converts it into a shareable device by writing print jobs to a disk buffer (spool) and printing them one by one.
• Benefit: Converts physical dedicated devices into logical shared devices.

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

1. FCFS (First-Come, First-Served)

The head moves in the exact order of the queue.

• Path:
• Calculation:
• Total Head Movement: cylinders.

2. SSTF (Shortest Seek Time First)

Selects the request with the minimum seek time from the current head position.

• Start at 53.
  1. Closest to 53 is 65 ().
  2. Closest to 65 is 67 ().
  3. Closest to 67 is 37 (). (vs 98 which is 31 away).
  4. Closest to 37 is 14 ().
  5. Closest to 14 is 98 ().
  6. Closest to 98 is 122 ().
  7. Closest to 122 is 124 ().
  8. Closest to 124 is 183 ().
• Path:
• Calculation:
• Total Head Movement: cylinders.

SCAN (Elevator Algorithm):

• Operation: The disk arm starts at one end of the disk and moves toward the other end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk. At the other end, the direction of head movement is reversed.
• Pros: Works like an elevator; provides a good variance of response time.
• Cons: If a request arrives just behind the head, it has to wait until the arm goes to the end and returns.

C-SCAN (Circular SCAN):

• Operation: Similar to SCAN, but provides 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.
• Pros: Treats the cylinders as a circular list that wraps around from the last cylinder to the first one. Provides more uniform wait times compared to SCAN.
• Cons: Wasted seek time during the "flyback" (return trip).

In mainframe and high-performance environments, the CPU does not communicate directly with the disk drive. Instead, I/O architecture is hierarchical.

1. I/O Channels:

• A Channel is a specialized processor dedicated to managing I/O operations. It runs its own program (Channel Command Words) independently of the main CPU.
• Function: It handles the data transfer between memory and the control unit, relieving the main CPU of the burden of moving data bit-by-bit. The CPU signals the channel, and the channel interrupts the CPU when finished.

2. Control Units (Disk Controllers):

• The Control Unit connects the Channel to the physical Disk Drives.
• Function: It handles the hardware-specific details of the drive (e.g., moving the head, selecting the sector, error correction, serial-to-parallel conversion).
• Relationship: One Channel can manage multiple Control Units, and one Control Unit can manage multiple Disk Drives.

1. Serial Access Devices:

• Definition: Data must be accessed in a linear sequence. To access data at position , the device must pass through positions $1$ to .
• Mechanism: Uses sequential media.
• Examples: Magnetic Tape, Cassettes, Punch cards.
• Use Case: Archival storage, backups where data is read/written in bulk.

2. Direct Access Devices:

• Definition: Data can be accessed directly at any location without traversing previous data. The access time is approximately independent of the data location.
• Mechanism: Uses addressable blocks/sectors.
• Examples: Hard Disk Drives (HDD), Solid State Drives (SSD), Optical Disks (CD/DVD), Flash drives.
• Use Case: Storing file systems, databases, and random-access applications.

Definition: IPC is a mechanism that allows processes to communicate with each other and synchronize their actions. The communication can be between related processes or unrelated processes, on the same system or different systems (network).

Need for IPC (Why allow process cooperation?):

1. Information Sharing: Several users may be interested in the same piece of information (e.g., a shared file or database).
2. Computation Speedup: To run a task faster, we can break it into sub-tasks that run in parallel. This requires multiple processing elements and IPC to exchange results.
3. Modularity: Constructing a system in a modular fashion (dividing system functions into separate processes/threads).
4. Convenience: Even a single user may work on many tasks at once (e.g., editing, listening to music, compiling) which may need to exchange data.

Pipes act as a conduit allowing two processes to communicate. In classic UNIX, a pipe is unidirectional (half-duplex).

1. Anonymous Pipes (Ordinary Pipes):

• Scope: Allow communication only between related processes (e.g., Parent and Child).
• Creation: Created typically by a parent process before forking a child. The child inherits the pipe.
• Persistence: They exist only while the processes are communicating. Once the processes finish, the pipe ceases to exist.
• Unidirectional: Data flows from the Write-end to the Read-end.

2. Named Pipes (FIFOs):

• Scope: Allow communication between unrelated processes.
• Creation: They exist as a special file in the file system.
• Persistence: They persist even after the process that created them has terminated. They must be explicitly deleted.
• Bidirectional: Depending on the OS implementation, they can support bidirectional communication.

The standard C library provides the popen() and pclose() functions to streamline IPC using pipes.

*1. `FILE popen(const char command, const char type);`**

• Function: It creates a pipe, forks a child process, and invokes the shell to execute the command.
• Modes (type):
  • "r": The calling process can read the standard output of the command (the pipe is connected to the command's stdout).
  • "w": The calling process can write to the standard input of the command (the pipe is connected to the command's stdin).
• Return: Returns a file pointer (FILE *) that can be used with standard I/O functions like fprintf or fscanf.

*2. `int pclose(FILE stream);`**

• Function: It closes the stream opened by popen(), waits for the command (child process) to terminate, and returns the exit status of the command.

Example:
FILE *fp = popen("ls -l", "r"); allows a C program to read the output of the ls command.

Shared Memory Concept:

• A region of memory is established that is shared by cooperating processes.
• Processes can then exchange information by reading and writing data to this shared region.
• Mechanism: Once the memory is shared, the data transfer occurs at the speed of memory access, without kernel intervention.
• Synchronization: The OS does not handle synchronization; the processes must ensure they are not writing to the same location simultaneously (usually handled via Semaphores).

Difference from Message Passing:

1. Performance: Shared Memory is faster than Message Passing because message passing requires a system call (kernel intervention) for every message sent/received.
2. Implementation: Message passing is easier to implement for distributed systems (across networks), while shared memory is typically restricted to the same machine.
3. Data Size: Shared memory is better for large amounts of data; message passing is better for smaller, event-driven data.

Message Queues provide a communication mechanism that allows processes to exchange data in the form of messages. Messages are stored in a queue managed by the kernel.

Characteristics:

1. Linked List: Internally, a message queue is a linked list of messages stored within the kernel's address space.
2. Identification: The queue is identified by a unique Message Queue ID.
3. Independence: The sender and receiver do not need to be connected simultaneously (asynchronous). Messages stay in the queue until read.
4. Message Structure: A message typically consists of a type (integer) and the data payload. The type allows the receiver to select specific messages (e.g., "Give me the first message of type 1").
5. Operations:
   • msgsnd(): Adds a new message to the end of the queue.
   • msgrcv(): Retrieves messages from the queue.

FIFOs, also known as Named Pipes, are an extension to the traditional pipe concept in UNIX/Linux systems.

• Persistence: Unlike anonymous pipes, a FIFO exists as a device special file in the file system. It has a name and persists even after the process that created it terminates.
• Semantics: It follows First-In, First-Out semantics.
• Creation: It is created using the mkfifo() system call or the mkfifo command line tool.
• Access: Processes access it like a regular file using open, read, write, and close.
• Synchronization:
  • Opening a FIFO for reading blocks the process until some other process opens it for writing.
  • Opening for writing blocks until another process opens it for reading.
• Use Case: Useful for IPC between unrelated processes (processes that do not share a parent-child relationship).

The Unix file system uses a modified Indexed Allocation method utilizing a structure called an Inode (Index Node).

Structure:
An inode contains the file's attributes (permissions, owner, timestamps) and pointers to disk blocks. To handle files of varying sizes efficiently, the pointers are structured hierarchically:

1. Direct Blocks (e.g., 10-12 pointers): Point directly to data blocks. This handles small files very quickly.
2. Single Indirect Block: Points to an index block, which in turn points to data blocks. Used for medium files.
3. Double Indirect Block: Points to an index block, which points to other index blocks, which then point to data blocks. Used for large files.
4. Triple Indirect Block: Adds another layer of indexing for very large files.

Advantage: This hybrid approach keeps the inode small but allows addressing extremely large files (terabytes) without wasting space for small files.