Operating Systems of Mobile Devices (OSMZ)

Week VI. (15.3.-19.3.2021)

The main study text will again be a chapter in A. S. Tanenbaum's book Modern Operating Systems. In a shorter form, you will find a summary of issues and approaches for implementing file systems.

Within mobile devices, we will be mainly interested in the family of EXT2/3/4 file systems, which are still the most used Linux / Android file systems, and the FAT file system, which is due to its simplicity and non-patent litigation format used in the simplest embedded devices, digital cameras, etc. and, last but not least, the JFFS2 file system used mainly on network devices with a small capacity of flash memory.

FAT16/32
For a basic description of the FAT implementation, see the Microsoft documentation. Implementing the access to the FAT file system will also be the task of our practical exercises. For a more detailed description, including implementation details, does MSDN offer specifications.

One of the problems that FAT partitions face is data fragmentation. This occurs when the volume is full and a contiguous cluster block cannot be found to allocate a new file, and free clusters located at different locations on the disk must be used. Data fragmentation then causes slower access to data in conventional harddrives, because the head must be set more often to the positions of differently scattered data clusters of files. That is why Microsoft products have had a defrag tool, which is used to defragment such a file system. In 2006, the FAT file system was revised in the form of exFAT. The use of exFAT is found where old file systems (most often FAT) cease to suffice for file storage requirements (especially in terms of capacity, but also the number of files, cluster size), it also brings several new functions (allocation of new space, transactions).

EXT2/3/4
ext4 (fourth extended filesystem) is a journaling filesystem and is a backward compatible successor to ext3 (it takes all its benefits). Ext4 brings many innovations typical of modern file systems, such as removing ext3 limits (file system size, files, number of files in directory), extent support, disk space reallocation, deferred allocation, log checksum, online defragmentation, faster scanning, multiblock allocator and increased accuracy of stored time data and much more. A description of these filesystems can be found directly in the documentation of the utilities used to manipulate these volumes.

JFFS/JFFS2
JFFS and JFFS2 are simple file systems for NAND flash memory. Data and metadata are written in a continuous stream called a log. Newer records thus replace the previous ones without having to overwrite the original ones. The log is thus a sequential structure into which data is written. This structure increases write performance, eliminates almost all search times, and sequencing also helps fix data faster after errors. Writing is done by writing a node to the end of the log (log tail). The oldest nodes with data are at the beginning of the log (log head). Data is removed using a garbage collector, which deletes data from the beginning of the log. Thanks to this technique, the so-called "wear-leveling" is implemented, which prolongs the life of rewrittable media.

PRESENTATION

LITERATURE

Andrew S. Tanenbaum - Modern operating systems. 4th edition:

  • Chapter 4 - File Systems (pp. 263-331)

ADDITIONAL READINGS

Video showing how the file is divided into data clusters and the whole sequence is written to the FAT table. You can practically try the implementation of your own defragmentation algorithm on the following link.

QUESTIONS

After reading the above texts, you should be able to answer following questions from the topics for the exam, specifically:

  • How the data is stored in the EXT2/3/4 file system, what information the inode contains.
  • How data is stored in the FAT file system, creating the FAT table.
  • How data is stored in the JFFS file system when the block is overwritten.
  • How are files and directories implemented (for example FAT, EXT2, etc.)
  • What is symbolic link and hard link, how are they implemented.
  • Describe the file system scan mechanisms and the most common errors.