Month: December 2017

Operating Systems: File System Implementation

Operating Systems: File System Implementation

 

File System Structure

The file system is made of two things: the logical storage unit and the collection of related informations. It resides on secondary storage (disks), providing efficient and convenient access to them (disks) for storing and retrieving data. Also provide a user interface to the storage, mapping logical to physical with the purpose to create an abstraction level for the user.

The structure contains also:

  • the file control block, the storage structure to collect file informations;
  • the device driver, to control the physical device.

The organization of the file-system is layers-based:

Layered Organization for File System Implementation

Starting from the end the device drivers manage the IO devices at the IO control layer. The basic file system once received a command such as “retrieve block 123” translate this sentence into something more device driver compatible. The file-organization module understand files, logical addresses, and physical blocks. The logical file system managed metadata information.

 

Virtual File System

It provides an object-oriented way of implementing file systems, allowing the same system call inferface (API) to be used for different types of file systems. With the VFS it is important to notice the concept of vnode which holds inode of network file details.

Directory Implementation

The implementation of the directories can be done following two strategies:

  • Linear List
  • Hash Table

Let us focus on the pros and the cons of both of them. The Linear List is simple to develop but for search operations is time-consuming. A typical improvement is the B+ Tree option, an  alphabetically ordered list: in fact, in this case, when a miss occurs it is not needed to scan the whole list.

The other option is the Hash Table, which is good for search operations but collisions can occur. This second strategy is useful when the entries are of fixed size.

Allocation Method

The allocation method refers to how disk blocks are allocated for files.

  • CONTIGUOUS: in this case the file occupies a set of contiguous blocks.
    • best performance in many cases;
    • simple;
    • Problems:
      • find space for file;
      • know the file size;
      • external fragmentation;
      • need for compaction off-line or on-line;
    • Variation (Extent-Based Systems, Veritas File System):
      • allocation in extents;
      • an extent is a contiguous block of disks.

 

  • LINKED: each file is a linked list of blocks.
    • no ext. fragmentation;
    • each pointer contains pointer to next block;
    • file ends at null pointer;
    • free space management system (FSMS) called when new block needed;
    • improve efficiency by clustering blocks into groups;
    • Problems:
      • clustering blocks into groups increases internal fragmentation;
      • no reliability-oriented;
      • locate a block can take many IOs and disk seeks.
    • Variation (FAT, File Allocation Table):
      • At the beginning of the volume there is this table, indexed by block number;
      • it looks like a linked list, but faster and cachable;
      • new block allocation simple.

 

  • INDEXED: each file has its own index block(s) of pointers to its data blocks
    • needs index table;
    • random access;
    • dynamic access without external fragmentation, but have overhead of index block;

UNIX File System (UFS) Case Study

It is a file system that combine the schemes:

  • it is composed by a main 4kB block table by 32-bit addresses;
  • there are portion of the table that works as an index allocation scheme with:
    • direct indexing;
    • single indexing;
    • double indexing.

Allocation Methods: summary

The contiguous allocation method is good for sequentiality and randomness. Instead, the linked allocation method is good for sequential but not for randomness. Last but not least, the indexed is a bit more complex because a single block access could require two index block read, and then, a data block read. However, for the indexing, a possible improvment is the clustering which is always a way to improve the throughput reducing the CPU overhead.

The Sun NFS (Network File System)

It is an implementation of a software system for access remote files accross LANs (or WANs). It uses an unreliable datagram protocol (UDP).

Interconnected workstations are viewed as a set of independent machines with independent file system, which allows sharing among these file systems in a transparent manner. In fact, a remote directory is mounted over a local file system directory. With the right permissions (access-right accreditation), any file system (or directory within the file system) can be mounted remotely to a local directory.

It has been developed to operate in a heteogenous environment of different machines, oerating system, and network architectures; and this independence is achieved through the use of RPC primitives built on top of XDR.

The mount procolol is:

  1. establish connection between server and client
  2. mount operation that needs of
    1. name of remote directory
    2. name of server
  3. after a mounting request the server reply with a file hande
  4. the moun operation terminates and changes the view of the client and not the server.

This protocol does not provide concurrecncy-control mechanisms.

The NFS servers are stateless: each request has to provide a full set of arguments. Possible modificaiton has to be committed to the server’s disk before resuls are returned to the client.

 

 

Operating Systems: IO Systems

Operating Systems: IO Systems

The io systems management is an important component of file systems because allows extendibility. Since the I/O devices vary greatly, there are various methods needed to interact with them. In fact the same ports and busses can be linked to different devices.

I/O Hardware

Through the huge variety of I/O devices let us focus on the common concepts:

  • port
  • bus
  • controller

Normally, a device is identified by an address, which is used by:

  • Direct I/O instructions
  • Memory-Mapped I/O

Port

port serves as an interface between the computer and other computers or peripheral devices. Electronically speaking, they can be divided into parallel and serial ports. Functionally speaking, they can be identified as:

  1. DVI (Digital Visual Interface)
  2. Display Port
  3. eSATA
  4. PS/2
  5. Serial
  6. DB/9
  7. SCSI

Bus

The bus can be built either by daisy chain or by shared direct access. The possible busses are:

  1. PCI
  2. PCIe
  3. Expansion bus

Controller

A very useful component because it operates ports, busses and devices, and contains processor, microcode, and private memory. It can be:

  1. integrated
  2. separated (host adapter)

Polling

The steps are:

  1. Read busy bit from status register until 0;
  2. Host sets read bit or write bit, and if write copies data into data-out register;
  3. Host sets command-ready bit;
  4. Controller sets busy bit, executes transfer;
  5. Controller clears busy bit, error-bit, command-ready bit when transfer done.

Step 1 – important to notice – is a busy-wait cycle for I/O from device, which is reasonable if device is fast, and very inefficient if device is slow.

Interrupts

Basing our study on the polling, it can happen in three instruction cycles:

  1. read status;
  2. logical-and to extract status bit;
  3. branch if not 0.

But if not 0, this three-instruction cycle cycles over them; so, how can we improve this? With interrupts.

The I/O device can trigger the CPU with an interrupt-request line (the processor checks this after each instruction) and wait that an interrupt handler receives the interrupt and manage the connection.

Two common scheme:

  • Interrupt-Driven I/O Cycle

i_o for I/O Systems

  • DMA (Direct Memory Access)
    Used to avoid programmed I/O for large data movement, because in that case is transferred one byte at a time. Here, instead, with the support of a DMA controller, we bypass the CPU to transfer data between I/O device and memory.
    The DMA has three modes of operation: burst mode, cycle stealing mode, transparent mode. In the cycle stealing mode the DMA controller steals the bus from the CPU.An improvement for the DMA, is the DVMA, a version which is aware of the virtual addresses.

 

Application I/O Interface

I/O system calls encapsulate the device behaviours into generic classes, creating in this way a layer of device drivers that hide all the I/O controllers. This management avoid new devices from extra work bacause they speak already-implemented protocols.

The I/O devices vary basing on:

  • Character or Block;
  • Sequential or Random Access ;
  • Synchronous or Asynchronous;
  • Sharable or Dedicated
  • Speed of operation;
  • Read-only, Write-only, Read & Write.

Common I/O devices can be grouped into:

  • Block
  • Character
  • Memory-Mapped File Access
  • Network Sockets

Block

They includes the disk driver where read, write and seek operations are allowed. They permit, also, the memory-mapped file access.

Character

The Character devices includes keyboard, mice, serial ports.

Network Devices

The network devices vary from character to block and usually they have their own interface. For example Unix, Linux and Windows OSes include the socket interface.

Systems integrate clocks and timers, basically for synchronization. The modes for I/O can be distinguished among:

  • blocking
  • nonblocking
  • asynchronous

There is also an other I/O mechanism called Vectored I/O where one single system call performs multiple I/O operations. This mechanisms, also known as Scatter-Gather Method, is better than using multiple individual I/O calls: in fact decreases context switching and system call overhead, and even some versions include the atomicity protection to avoid multiple threads from chaning data after read/write operations on a shared resource.

Kernel I/O Subsystem

Three common techniques used by the Kernels are:

  • Caching: when a faster device holds a copy of data;
  • Spooling: when the output of a process is kept because the device can handle one request at a time;
  • Device Reservation: that provides exclusive access to a device.

Error handling

A OS can recover a read or a write from disks or recover a device unavailable. Most OS return an error code when an I/O operation fails, although. For example, these errors are kept in memory in a system error log.

I/O Protection

Since a user process can accidentally or purposefully attempt to disrupt operations with illegal instruction two basic rules have been added:

  • I/O instructions have to be provileged;
  • I/O instructions can be executed only via system calls.

Kernel Data Structures

Normally, a Operative System keep in memory open file tables, network connections, character device state.

Power Management

Operative Systems can help to manage and improve power management.

Examples:
  • Cloud Computing Environment OS can move virtual machine between servers and then evacuate a whole system, before shutting it down.
  • Android implements
    • Component-Level Power Management, to power off component not used;
    • Wake Locks, to prevent the device to sleep when held by lock;
    • Power Collapse, to reduce at minimum energy and awakable by external stimuli like physical buttons, or incoming calls.

Transforming I/O Requests to Hardware Operations

//TODO: Life Cycle of an I/O Request

Streams

The streams are built as a full-duplex communicaiton channel to exchange data between user-level process and a device.

Performance

If we would to improve performance there are a bunch of common rules that we can follow:

  • Reduce the number of context switches;
  • Reduce data copy;
  • Reduce interrupts by using large transfer;
  • Use DMA
  • Move User-mode processes or deamons to kernel threads.