1) Base of hexadecimal number system? Answer : 16 2) Universal gate in digital logic? Answer : NAND 3) Memory type that is non-volatile? Answer : ROM 4) Basic building block of digital circuits? Answer : Gate 5) Device used for data storage in sequential circuits? Answer : Flip-flop 6) Architecture with shared memory for instructions and data? Answer : von Neumann 7) The smallest unit of data in computing? Answer : Bit 8) Unit that performs arithmetic operations in a CPU? Answer : ALU 9) Memory faster than main memory but smaller in size? Answer : Cache 10) System cycle that includes fetch, decode, and execute? Answer : Instruction 11) Type of circuit where output depends on present input only? Answer : Combinational 12) The binary equivalent of decimal 10? Answer : 1010 13) Memory used for high-speed temporary storage in a CPU? Answer : Register 14) Method of representing negative numbers in binary? Answer : Two's complement 15) Gate that inverts its input signal? Answer : NOT 16)...
File-System Implementation
Overview
* File systems store many important data structures on the disk:
• A boot-control block, the boot block in UNIX or the separation
boot sector in Windows contains details about how to boot the system off of this disk. This will generally be the first sector of the volume if there is a bootable system loaded on that volume, or the block will be left vacant otherwise.
• A volume control block, the master file table in UNIX or the superblock in Windows, which contains details such as the partition table, number of blocks on every file system, and pointers to free blocks and free FCB blocks.
• A directory structure ( per file system ), contains file names and pointers to
corresponding FCBs. UNIX uses index node numbers, and NTFS uses a master file table.
• The File Control Block, FCB, ( per file ) contains details about ownership, size,
permissions, dates, etc. UNIX stores this details in index nodes, and NTFS in the
master file table as a relational database structure.
* There are also many key data structures stored in memory:
• An in-memory mount table.
• An in-memory directory cache of currently accessed directory information.
• A system-wide open file table, contains a copy of the FCB for every currently open file in the system, as well as some other related information.
• A per-process open file table, contains a pointer to the system open file table
as well as some other information. ( For example the present file position pointer
may be either here or in the system file table, depending on the execution
and whether the file is being shared or not)
* Figure below illustrates some of the interactions of file system components when files are created and/or used:
• When a new file is built, a new FCB is allocated and filled out with important
information regarding the new file. The appropriate directory is edited with the
new file name and FCB information.
• When a file is processed during a program, the open( ) system call reads in the FCB information from disk, and stores it in the system-wide open file table. An
entry is added to the per-process open file table referencing the system-wide table,
and an index into the per-process table is backed by the open( ) system call.
UNIX refers to this index as a file descriptor, and Windows refers to it as a file handle.
• If another process already has a file open when a new request comes in for the
same file, and it is dividable, then a counter in the system-wide table is incremented and the per-process table is modified to point to the existing entry in the system-wide table.
• When a file is closed, the per-process table entry is cleared, and the counter in the system-wide table is lowered. If that counter reaches zero, then the system wide table is also freed. Any data currently stored in memory cache for this file is
written out to disk if necessary.
Partitions and Mounting
* Physical disks are commonly splitted into smaller units called partitions. They can also be combined into larger units, but that is most commonly done for RAID installations and is left for later chapters.
* Divisions can either be used as raw devices ( with no structure imposed upon them ), or they can be formatted to hold a file system ( i.e. populated with FCBs and initial directory structures as appropriate. ) Raw partitions are generally used for swap space, and may also be used for certain programs such as databases that choose to manage their own disk storage system. Partitions containing file systems can generally only be accessed using the file system structure by ordinary users, but can often be accessed as a raw device also by root.
* The boot block is processed as part of a raw partition, by the boot program prior to any operating system being loaded. Modern boot programs understand multiple OSes and file system formats, and can give the user a choice of which of several available systems to boot.
* The root partition contains the OS kernel and at least the key portions of the OS required to complete the boot process. At boot time the root partition is mounted, and control is transferred from the boot program to the kernel found there. ( Older systems required that the root partition lie completely within the first 1024 cylinders of the disk, because that was as far as the boot program could reach. Once the kernel had control, then it could access partitions beyond the 1024 cylinder boundary. )
* Continuing with the boot process, extra file systems get mounted, adding their information into the appropriate mount table structure. As a part of the mounting process the file systems may be checked for errors or inconsistencies, either because they are
flagged as not having been closed properly the last time they were used, or just for
general principals. File systems may be mounted either automatically or manually. In UNIX a mount point is indicated by setting a flag in the in-memory copy of the inode, so all future references to that inode get re-directed to the root directory of the mounted file system.
Virtual File Systems
* Virtual File Systems, VFS, provide a common interface to multiple different file systemtypes. In addition, it provides for a unique identifier ( vnode ) for files across the entire space, including across all file systems of different types. ( UNIX inodes are unique only across a single file system, and certainly do not carry across networked file systems. )
* The VFS in Linux is based upon four key object types:
• The index node object, representing an individual file
• The file object, representing an open file.
• The superblock object, representing a file system.
• The dentry object, representing a directory entry.
* Linux VFS provides a set of common functionalities for each file system, using function pointers accessed through a table. The same functionality is processed through the same table position for all file system types, though the actual functions pointed to by the pointers may be file system-specific.See/usr/include/linux/fs.h for full details. Common operations provided include open( ), read( ), write( ), and mmap( ).
Directory Implementation
Directories require to be fast to search, insert, and delete, with a minimum of wasted disk space.
Linear List
* A linear list is the basic and easiest directory structure to set up, but it does have some drawbacks.
* Detecting a file ( or verifying one does not already exist upon creation ) requires a linear search.
* Deletions can be completed by moving all entries, flagging an entry as deleted, or by moving the last entry into the newly vacant position.
* Arranging the list makes searches faster, at the expense of more complex insertions and deletions.
* A linked list makes insertions and deletions into a sorted list easier, with overhead for the links.
* More hard data structures, such as B-trees, could also be considered.
Hash Table
* A hash table can also be used to fasten up searches.
* Hash tables are normally executed in addition to a linear or other structure