Please enable JavaScript.

Coggle requires JavaScript to display documents.

OS (Lectures 10, 11 and 12, Lectures 8 and 9, Lecture 6 and 7), Lecture 6,…

- - - - Memory is a very important resource that needs clear management.
      - Memory without using abstractions
        
        The simplest abstraction of memory can be considered the complete absence of any abstraction. Early general purpose machines (before 1960), early minicomputers (before 1970), and early personal computers (before 1980) did not use memory abstractions.
        
        Each program simply saw physical memory.
        
        When the program executed the following instruction MOV REGISTER1, 1000 the computer simply moved the contents of physical memory location 1000 into REGISTERS Thus, the memory model provided to the programmer was simple physical memory, a set of addresses from 0 to some maximum value, where each address corresponded to a cell containing some number of bits, usually eight.
        
        Under such conditions, keeping two working programs in memory at once was not possible.
        
        Even in conditions where the physical memory itself acts as a memory model, several variants of memory usage are possible.
        
        1 more item...
        
        Running multiple programs without memory abstractions
        
        However, even in the absence of memory abstractions, the simultaneous launch of several programs is quite possible. To do this, the operating system must save all the contents of memory in a file on disk, and then download and run such a program. Since there is only one program in memory at a time, there are no conflicts.
        
        This concept is called data swapping.
        
        In the presence of some special additional equipment, it is possible to run several programs in parallel even without using swapping.
      - Memory abstraction: address spaces
        
        Ultimately, providing physical memory to processes has a number of serious drawbacks.
        
        First, if programs can access every byte of memory for the user, they can easily or intentionally corrupt the operating system, fragment its code, and bring it to a halt. This problem is present even when running only one user program.
        
        Secondly, when using this model, it is quite difficult to organize the simultaneous (alternating, if there is only one central processor) operation of several programs. On personal computers, it is quite natural to have several programs open at the same time (word processor, e-mail program, web browser), with one. Of which the user is currently interacting, and the work of others is resumed with a mouse click. This is difficult to achieve in the absence of abstractions based on physical memory.
        
        Concept of address space
        
        An address space is a set of addresses that can be used by a process to access memory. Each process has its own address space, independent of the address space owned by other processes (except in those special circumstances where processes need to share their address spaces).
      - Basic and limiting registers
        
        A simple solution uses a rather primitive version of dynamic memory reallocation. At the same time, the address space of each process is simply projected onto different parts of physical memory.
        
        The classic solution, used on machines from the CDC 6600 (the world's first supercomputer) to the Intel 8088 (the heart of the first IBM PC), is to equip each CPU with two special hardware registers, commonly called base and limit registers.
        
        When using these registers, programs are loaded into sequentially located free areas of memory without modification of addresses during the loading process. When the process is started, the physical address is loaded into the base register, from which the placement of the program in memory begins, and the length of the program is loaded into the limiting register.
      - Swapping
        
        If the computer has enough memory to accommodate all the processes, then all the schemes considered so far will be functional to one degree or another. But in practice, the total amount of RAM required to accommodate all processes often significantly exceeds the available amount of RAM.
        
        On a typical Windows or Linux system, there may be about 40-60 or more processes running when the computer starts up.
        
        Over the years, two main approaches have been developed to deal with memory congestion. The simplest of them, the so-called swapping, consists of placing the entire process in memory, running it for a while, and then dumping it to disk. Idle processes most of the time are stored on the disk and do not take up RAM space when idle. (Although some of them are activated periodically to do their job, then shut down again).
        
        When several free areas are created in memory as a result of swapping, they can be combined into one large one by moving all processes to lower addresses at the first opportunity. This technology is known as memory compression.
        
        Free memory management
        
        1 more item...
        
        The second approach is called virtual memory, and it allows programs to run even if they are only partially in RAM.
        
        Virtual memory
        
        In the 60s, it was decided to break programs into small parts, called overlays. When the program started, only the overlay download manager was loaded into memory, which immediately loaded and started the overlay with sequence number 0. When this overlay completed its work, it could tell the overlay download manager that it needed to load overlay 1, or above overlay 0 , which is in memory (if there was enough space for it), or over overlay 0 (if there was not enough memory). Some overlay systems had a rather complex device, allowing many overlays to be in memory at the same time. Overlays were stored on disk and were swapped from disk to memory and back again by the overlay download manager.
        
        1 more item...
        
        Page organization of memory
        
        1 more item...
        
        Tables of pages
        
        2 more items...
  - - - When a page-missing error occurs, the operating system must choose a page to be removed from memory in order to make room for the desired page to be loaded. If the page intended for deletion has been changed during its time in memory, it must be overwritten on disk so that the disk copy corresponds to the original. If the page was not changed, the disk copy corresponds to the original, and its rewriting is not necessary. Then the read page is simply written over the previous one.
      - Optimal page replacement algorithm
        
        The best page replacement algorithm is easy to describe, but absolutely impossible to implement. In it, everything happens like this: at the time of the page missing error, there is a certain set of pages in memory. Some of these pages will be accessed literally from the following commands (these commands are contained on the page). Other pages may not be accessed after 10, 100, or perhaps even 1,000 commands. Each page can be marked with the number of commands that must be executed before the page is first accessed.
        
        The optimal page replacement algorithm indicates that the page with the highest value mark should be deleted. If some page has not been used for 8000000 commands, and some other page has not been used for 6000000 commands, then deleting the first will result in a page missing error, which will cause it to be re-selected from disk in the very distant future. Computers, like people, try to postpone unpleasant events as much as possible.
      - The recently used page exclusion algorithm
        (NRU, Not Recently Used)
        
        To allow the OS to collect useful page usage statistics, most computers using virtual memory have two status bits associated with each page. The R bit is set each time the page is accessed (read or write). The M bit is set when a page is written to (that is, when it is modified). These bits are present in each page table entry. It is important to learn that these bits must be updated every time the memory is accessed, so it is necessary that their values are set by the hardware. Once a bit is set to 1, it retains that value until it is reset by the operating system.
        
        When a page missing error occurs, the operating system looks at all pages and, based on the current values of the R and M bits corresponding to them, divides them into four categories:
        
        Class 0: There have been no recent calls or modifications.
        
        Class 1: There have been no recent hits, but the page has been modified.
        
        Although at first glance there can be no class 1 pages, they appear if the R bit of class 3 pages is reset by a timer interrupt. These interrupts do not reset the M bit because it contains the information needed to know whether the page stored on disk needs to be overwritten or not. Resetting the R bit without resetting the M bit results in class 1 pages.
        
        Class 2: There have been recent appeals but no modifications.
        
        Class 3: recently there were appeals and modifications.
      - Algorithm "First in - first out" (First-In - First-Out, FIFO)
        
        Another low-cost paging algorithm is the FIFO algorithm. The operating system keeps a list of all the pages that are currently in memory, and the pages that arrived very recently are in the tail, and those that arrived before all are at the head of the list, Fig. 13.3. When a missing page error occurs, the page at the head of the list is deleted, and a new page is added to its tail. Such an algorithm can lead to the deletion of a frequently used page, so the FIFO principle in its pure form is rarely used.
      - The "second chance" algorithm
        
        A simple modification of the FIFO algorithm that eliminates the problem of removing a page, which is often needed, can be to check the R bit of the oldest page. If its value is zero, it means that the page is not only old, but also unclaimed, so it is deleted immediately. If the R bit is set to 1, it is reset and the page is placed at the end of the page list and its load time is updated as if it had just entered memory. Then the search continues. The "second chance" algorithm searches for a previously loaded page that has not been accessed during the timer interval that has just passed. If all pages were accessed, the "second chance" algorithm turns into a simple FIFO algorithm.
      - The "clock" algorithm
        
        For all its logic, the "second chance" algorithm is too inefficient because it constantly moves pages in its list. It is better to contain all page blocks in a cyclic list in the form of a clock.
        
        When a page missing error occurs, the page indicated by the arrow is checked. If its R bit is 0, the page is evicted, a new page is inserted in its place in the "dial", and the hand moves forward one position. If the value of the R bit is 1, then it is reset and the arrow moves to the next page. This process is repeated until a page with R=0 is found. That is why this algorithm is called a clock.
      - Least Required Page Replacement Algorithm (LRU)
        
        In a machine that has 4 page blocks, LRU (Last Recently Used) hardware can support a 4 by 4 bit zero-first matrix. As soon as page block k is accessed, the hardware first sets all bits of row k to 1 and then resets all bits of column k to zero. At any given time, the row with the lowest binary value belongs to the least requested page, the row with the next lowest value belongs to the next least requested page, and so on.
      - Algorithm "Working set"
        
        The basic idea is to find a page that does not belong to the working set and remove it from memory. Since only pages in memory are considered candidates for eviction, pages that are not in memory are ignored by this algorithm. Each record consists of (at least) two key pieces of information: the (approximate) time the page was last used and the R bit (Referenced - circulation bit). Empty white rectangles indicate other fields that are not needed for this algorithm, such as the page block number, protection bits and the modification bit - M (Modified).
        
        Consider the operation of the algorithm. It is assumed that the hardware, as discussed earlier, sets the R and M bits. It is also assumed that periodic interrupts from the timer trigger a program that clears the access bit R. At each page-out error, the page table is scanned to find a page suitable for removal
        
        Each time a write is processed, the state of the R bit is checked. If its value is 1, the current virtual time is written to the page table's last-use time field, indicating that the page was used when the page-out error occurred. If a page is accessed during the current time clock, it is clear that it belongs to the working set and is not a candidate for deletion (T is assumed to span multiple system clocks). If the value of A is 0, it means that the page has not been accessed in the current time cycle and it can be a candidate for deletion.
        
        To understand whether it should be deleted or not, its age (current virtual time minus its last use time) is calculated, which is compared to the value of t. If the age exceeds the value t, then the page no longer belongs to the working set and is replaced by a new page.
        
        The scan continues and all other records are updated. But if the value of R is 0, but the age is less than or equal to t, then the page still belongs to the working set. The page temporarily avoids deletion, but the page with the largest age (the smallest last used time value) is noted. If the entire page table is scanned and no candidate page for deletion is found, then all pages are included in the working set.
        
        1 more item...
      - "WSClock" algorithm
        
        An improved algorithm based on the clock algorithm but also using working set information is called WSClock. Due to the ease of implementation and good performance, it is quite widely used in practice. The necessary data structure is reduced to a cyclic list of page blocks, as in the "clock" algorithm. Initially, this list is empty. When the first page is loaded, it is added to the list. As subsequent pages are loaded, they fall into the list, forming a closed ring. Each record contains the last use time field from the basic working set algorithm, as well as an R bit and an M bit.
        
        As in the clock algorithm, for each missing page error, the page pointed to by the arrow is checked first. If the R bit is set to 1, then the page has been used during the current clock, so it is not an ideal candidate for deletion. Then the R bit is set to 0, the arrow moves to the next page, and the algorithm is repeated already for it. The state resulting from this sequence of events. Now let's see what happens if the page pointed to by the arrow has bit R = 0, as shown in Fig. If its age exceeds t and the page has not been modified, it does not belong to the working set and its exact copy is present on disk. Then a new page is simply placed in the page block. On the other hand, if the page has been changed, its block cannot be immediately claimed, since there is no exact copy of it on disk.
        
        To avoid switching the process, the disk write is scheduled, and the arrow moves further and the algorithm continues its work on the next page. In the end, you should get an old, unchanged page, which you can use right away. In principle, a disk I/O operation for all pages can be scheduled in one clockwise rotation. To reduce the flow of data exchange with the disk, a limit can be set, which allows a maximum of n pages to be dumped to the disk. After this limit is reached, no more writes to the disk are scheduled.
        
        And what to do if the arrow goes full circle and returns to the initial position?
        
        Then you should consider two options:
        
        2 more items...
- - - - File systems can be considered at two levels: logical and physical. Logical defines the display of the file system intended for application programs and users, physical — features of the location of system data structures on the disk and algorithms used when accessing information.
        
        Logical file organization
        systems
        
        The concept of a file
        
        A file is a collection of data that can be accessed by name. Files are organized into file systems. From the user's point of view, a file is the minimum volume of file system data that can be worked with independently. For example, a user cannot save data to an external medium without accessing the file. Let's consider the features of using files.
        
        Files provide the easiest way for different applications to share data.
        
        Concept of file system
        
        A file system is an OS subsystem that maintains an organized set of files, mostly in a specific area of disk space (a logical structure); low-level data structures used to organize this space in the form of a set of files (physical structure); the program interface of the file system (a set of system calls that implement operations on files).
        
        3 more items...
        
        Files are the most common means of storing information in non-volatile memory.
      - Organization of information in the file system
        
        Sections
        
        Partitions implement a logical mapping of a physical disk.
        
        A partition is a part of the physical disk space intended for placing the structure of one file system on it and from a logical point of view is considered as a single unit.
        
        A partition is a logical device that functions as a separate disk from the point of view of the OS. Such a device can correspond to an entire physical disk (in this case, the disk is said to contain one partition); most often it corresponds to a part of the disk (this part is also called a physical partition); it also happens that such logical devices combine several physical partitions that may be on different disks (such devices are also called logical volumes).
        
        Each partition can have its own file system (and possibly be used by different OSes). A special utility, often called fdisk, is used to partition disk space. To generate a file system on a partition, you need to use a high-level disk formatting operation. In some operating systems, a volume is a section with a file system installed on it.
        
        1 more item...
        
        Catalogs
        
        Partitions are the basis of organizing large volumes of disk space for deploying file systems. To organize files within a section with an installed file system, the concept of a file directory (file directory) or simply a directory was proposed.
        
        A directory is an object (most often implemented as a special file) that contains information about a set of files. Such files are said to be contained in a directory. Files are entered into directories by users based on their own criteria, some directories may contain data required by the operating system or its program code.
        
        The directory can be imagined as a symbolic table that implements the mapping of file names to directory elements (usually such elements store low-level information about files). Let's see how such a mapping can be implemented.
        
        Tree-like directory structure. The basic idea behind organizing data using directories is that they can contain other directories. Nested directories are called subdirectories. In this way, a directory tree is formed. The first directory created in the file system installed in the partition (the root of the directory tree) is called the root directory.
        
        1 more item...
        
        Relationship of sections and directory structure
        
        It remains to clarify an important question about the relationship between partitions and the directory structure of file systems. There are two main approaches to implementing such a relationship, which differ significantly from each other.
        
        A single directory tree. Mounting file systems.
        
        The first approach is mainly used in the UNIX file system and consists in the fact that partitions with mounted file systems on them are combined into a single OS directory tree. The standard UNIX directory organization is represented as a tree with a single root, the root directory, denoted by "/". The file system on which the root directory is located is called the boot or root. In most implementations, it should contain the OS kernel file. Additional file systems are combined with the root using the mount operation. During mounting, the selected directory of one file system becomes the root directory of the other. The directory intended for mounting the file system is called a mount point. The entire contents of a mounted file system appear to users of the system as a set of subdirectories of the mount point.
      - Connections
        
        Hard connections
        
        The name of the file is not always uniquely related to its data. With the support of hard links (hard links), multiple names are allowed for a file. All hard links define the same data on disk, they are indistinguishable to the user: it is impossible to tell which ones were created earlier and which ones were created later.
        
        The system call 1ink () is intended for creating hard links in POSIX. It takes the name of the source file as the first parameter, and the name of the hard link that will be created as the second.
        
        Support for hard connections in Windows XP. Hard links are mostly implemented in UNIX-compatible systems, they are also supported in systems of the Windows XP line for the NTFS file system. To create a hard link in this system, you need to use the Create-HardLink() function, the link name is specified as the first parameter, the file name is the second, and the third is zero.
        
        Symbolic connections
        
        A symbolic link is a link physically separated from the data it points to. In fact, it is a special file containing the name of the file it points to.
        
        The source file is accessed through such a connection.
        
        When removing the connection, the original file will not disappear.
        
        If the source file is moved or removed, the connection will be broken and access through it will become impossible, if the file is then renewed in the same location, the connection can be used again.
        
        Symbolic links can point to directories and files located on other file systems (on another partition of the hard disk). For example, if you create a system-docs link in the current directory that points to the /usr/doc directory, then changing to the system-docs directory will lead to a change to the /usr/doc directory.
        
        Support for symbolic links at the level of system calls
        
        To specify a symbolic link in POSIX, the symlink() system call is defined, the parameters of which are similar to those of link().
        
        Symbolic links first appeared in UNIX file systems, in Windows XP they are supported by the NTFS file system called junction points, but the API tools for their use are not defined.
      - File attributes
        
        Each file has a set of characteristics — attributes. The set of attributes varies depending on the file system.
        
        The name of the file, discussed in detail earlier.
        
        A file type that is usually specified for special files (directories, links, etc.).
        
        The size of the file (usually you can define the file's current size, and sometimes its maximum size).
        
        Security attributes that define access rights to this file.
        
        Time attributes that include the time the file was last modified and last used.
      - Operations on files and directories
        
        Approaches to the use of files by processes
        
        Approaches to using files from the process are as follows: stateful and stateless.
        
        In the case of saving state, there are special operations that prepare the file for use in the process (open it) and cancel this readiness (close it). Other operations use data structures prepared when the file is opened and can only be performed until the file is closed. The advantage of this approach is high performance, since the required data structures are loaded into memory when the file is opened.
        
        If the state is not saved, each operation of working with the file (reading, writing, etc.) is accompanied by a complete preparation of the file for work (each operation begins with opening the file and ends with closing). Although this approach suffers in performance, it can be used to improve system reliability when there is a high probability that a file operation will fail, leaving open file data structures in an incorrect state. This can be done in the case when the file system is used over the network, because the network connection can be broken at any moment. Later in this section, we will look at the stateful approach.
        
        General information about file operations
        
        Opening a file. After opening the file, the process can work with it (for example, read and write). Opening a file usually involves loading into RAM a special data structure — a file descriptor that defines its attributes and location on disk. Subsequent calls will use this structure to access the file.
        
        Closing the file. After finishing work with the file, it must be closed. At the same time, the data structure created during its opening is removed from memory. All unsaved changes are written to disk.
        
        Creating a file. This operation causes a new zero-length file to be created on disk. After creation, the file is opened automatically.
        
        File extraction. This operation causes the file to be extracted and the disk space occupied by it to be freed. It is usually not valid for open files. In section 3, it was noted about the peculiarities of the implementation of this operation in a system with support for hard connections.
        
        Reading from a file. This operation usually boils down to forwarding a certain number of bytes from the file, starting from the current position, into a previously allocated user mode memory buffer.
        
        Writing to a file. Executed from the current position, data is written to a file from a previously allocated buffer. If there is already data at this position, it will be overwritten. This operation may change the file size.
        
        Move the current position pointer. Before reading and writing operations, you should determine where the required data is located in the file or where it should be written, specifying the current position in the file with this operation. Note that if you move the file pointer past its end and then perform a write operation, the length of the file will increase.
        
        Getting and setting file attributes. These two operations allow you to read the current values of all or some file attributes, or set new values for them.
        
        POSIX file operations
        
        Opening and creating files - system call open (), the first parameter of which is the path to the file.
        
        The oren() call returns an integer value — a file descriptor. It should be used in all calls that require an open file. In case of an error, this call will return – 1, and the value of the errno variable will correspond to the error code.
        
        Closing a file is a system call c1ose () that accepts a file descriptor. Reading and writing data - system call read(). Moving the pointer of the current position (offset) in the file is the lseek() system call. Collecting information about file attributes (contents of its index descriptor) - call stat()
        
        The first parameter is the path to the file, the second is the structure to which the attributes will be written as a result of the call.
        
        File operations Win32 АРИ
        
        Win32 API contains a set of functions for working with files, in many respects analogous to POSIX system calls. Let's stop at this set.
        
        Opening and creating files - CreateFile() function. The first parameter is the file name. The amode parameter sets the file opening mode and can take the values GENERIC_READ (reading) and GENERIC_WRITE (writing). The smode parameter specifies the possibility of simultaneous access to the file: 0 means that access is not possible.
        
        Unlike POSIX, in Win32 open file handles are not inherited by the process's descendants by default, even if inherit_handles is set to TRUE when CreateProcess() is called. It is necessary to additionally allow such inheritance for each descriptor when it is opened.
        
        To get access to the attributes of an open file by its descriptor, use the function. GetFileInformationByHandle()It allows you to get more complete information from a file (in particular, the number of its hard links).
        
        Operations on directories
        
        Creating a new directory. This operation creates a new directory. It is usually empty, some implementations automatically add "." elements to it. and"..".
        
        Removing the directory. At the system call level, this operation is only allowed for empty directories.
        
        Opening and closing the directory. A directory, like a normal file, must be opened before use and closed after use. Some operations related to access to elements are valid only for open directories.
        
        Reading a directory item. This operation reads one element of the directory and moves the current position to the next element. By using a directory element read in a loop, the entire directory can be traversed.
        
        Go to the beginning of the directory. This operation moves the current position to the first element of the directory.
  - - - Basic information about disk devices
        
        The principle of operation of the hard disk
        
        Storage on hard magnetic disks (HDDs) consists of a set of disk plates (platters), which are covered with magnetic material and rotated by a motor at high speed. Two heads correspond to each plate, one reads information from above, the other from below. The heads are attached to a special disk manipulator (disk arm). The manipulator can move along the radius of the disk — from the center to the outer edge and back, thus positioning the heads.
        
        Each track during low-level formatting is divided into sectors, the data volume of a sector for most architectures is 512 bytes (it must be equal to the power of 2). The number of sectors for all tracks is the same (in the range from 16 to 1600).
        
        Efficiency of disk access operations
        
        The main characteristics of disk access are:
        
        seek time - the time it takes to move the manipulator to position the head on the desired track (on average, it is from 10 to 20 ms);
        
        rotational delay (rotational delay) — waiting time until the plate turns so that the desired sector is under the track (8 ms on average);
        
        data transmission bandwidth (transfer bandwidth) — the amount of data transferred from the device to the memory per unit of time; for modern disks, this characteristic is comparable to the bandwidth of RAM (200 MB/s), the transfer time of one sector is measured in nanoseconds. The time required to read the sector is obtained by adding the search time, the rotational delay and the transmission time (at the same time, the transmission time can be considered very small). Obviously, the reading time of one sector is practically the same as the reading time of several adjacent sectors, and the time of reading an entire track in one operation will be less than the time of reading one sector due to the lack of rotational delay.
        
        The heads read information from the tracks, which have the form of concentric circles. The minimum number of tracks on the surface of the plate in modern discs is 700, the maximum is more than 20,000. The set of all tracks of the same radius on all surfaces of the plates is called a cylinder.
      - Placing information in file systems
        
        The file system usually builds a base mapping of data on top of the one provided to it by disk device drivers. First of all, the OS allocates disk space not by sectors, but by special units of placement — clusters or disk blocks (disk blocks, the term "disk block" is more common in UNIX systems). Determining the size of the cluster and placing the information necessary for the functioning of the file system occurs during the high-level formatting of the partition. It is this formatting that creates a file system in a partition.
        
        Physical organization of partitions on the disk
        
        The initial (zero) sector of the disk is called the master boot record (Master Boot Record, MBR). At the end of this entry, there is a partition table of this disk, where the starting and ending addresses are stored for each partition.
        
        One of the disk partitions can be marked as bootable or active. After booting the computer, the hardware accesses the MBR of one of the disks, determines the boot partition from its partition table and tries to find a special small program in the first cluster of this partition — the OS boot loader. It is the OS bootloader that is responsible for searching the disk and initially loading the operating system kernel into memory. The file system data structures are located inside the section.
        
        Basic requirements for the physical organization of file systems
        
        From the user's point of view, a file with a given name (hereafter we assume that the path information is included in the name) is an unstructured sequence of bytes, and from the point of view of the physical structure of the file system, the file is a set of disk blocks containing its data. The task of the file system is to ensure the transformation of the combination of the file name and the logical shift in it to the physical address inside the corresponding disk block.
        
        3 more items...
  - - - Optimizing performance when developing file systems
        
        A traditional UNIX file system consists of a superblock (containing file system block numbers, the current number of files, a pointer to a list of free blocks), a section of index descriptors, and data blocks. The block size is fixed and is 512 bytes. Free blocks are combined into a list.
        
        Such a system is an example of a simple and elegant solution that turned out to be unacceptable from the point of view of productivity. In practice, this file system could achieve a bandwidth of only 2% of the disk's capacity when transferring data. Let's name some reasons for such low productivity.
        
        The size of the disk block turned out to be insufficient, as a result of which a large number of blocks were needed to accommodate the file data; index descriptors, even for small files, required several levels of indirect addressing, switching between which slowed down access; forwarding data in one block led to a decrease in bandwidth.
        
        To solve these problems, the size of the disk block was increased in this system (FFS usually used two block sizes: 4 and 8 KB). In order to avoid internal fragmentation (which always increases as the block size increases), it was proposed to split unused blocks into smaller pieces if necessary - fragments that can be used to accommodate small files. The minimum size of a fragment is equal to the size of a disk sector, usually fragments of 1 KB were used.
        
        In addition, much attention was paid to the grouping of interdependent data. Given that the largest time losses occur during head movement, it has been proposed to place such data within a cylinder group that combines one or more adjacent cylinders. When accessing the data of one such group, it was not necessary to move the head, or its movement was minimal.
        
        Each such group in its structure repeated the file system: it had a superblock, a section of index descriptors and a section of disk blocks allocated for files. Therefore, the index descriptor of each file was placed in the same cylinder as its data, all the index descriptors of the same directory were also placed in one group of cylinders. Consecutive blocks of the file tended to be placed in adjacent sectors.
        
        1 more item...
        
        Related objects were often distant from each other and could not be read together, in particular, index descriptors were located far from data blocks and were not together for the directory; consecutive blocks for the file were also not contained together (this happened because during the operation of the system, due to the removal of files, the list of free blocks became "scattered" on the disk, as a result of which files received blocks distant from each other during creation).
        
        Disk access caching
        
        The most important means of increasing the performance of file systems is the organization of the disk cache.
        
        A disk cache is a special area in the main memory that is used for caching disk blocks. When an attempt is made to access a disk block, it is placed in the cache, with the expectation that it will be used again soon. On the next reuse, you can avoid accessing the disk. Disk cache management occurs at a lower level compared to the file system implementation. The cache must be transparent to the file system: the blocks in it from the point of view of the file system are located on the disk, the differences are only in the speed of access.
        
        To speed up the search for the desired block, a hash function is usually used, which translates the block number into a hash code. A hash table is stored in memory, the elements of which correspond to individual values of the hash code. All blocks with the same hash code value are combined into linked lists. To search for a block with a specific number in the cache, it is enough to calculate the value of the hash function and view the corresponding list.
        
        Disk cache size
        
        When determining the size of the disk cache, it is important to remember that it, together with the virtual memory manager, are two main competing subsystems in terms of main memory usage. There are two types of cache in terms of managing its size: a fixed-size cache and a variable-size cache.
        
        2 more items...
        
        Reliability of file systems
        
        Let's consider what problems can arise when a computer system crashes and what happens to file system data.
        
        If the disk cache is used, the data in it will be lost after the power is turned off. If they have not been written to disk by this point, changes to them will be lost. Moreover, when such changes have been partially written to disk, the file system may be in a conflicting state.
        
        A file system may be in a conflicting state due to partial file operations. So, if the file extraction operation deletes the corresponding entry from the catalog and the index descriptor, but due to a failure, it does not have time to move the corresponding disk blocks to the list of free blocks, they will be "lost" for the file system, since the system will not be able to place new data in them.
        
        To ensure recovery from a system failure, you can
        
        create a backup copy of all (or most important) file system data in advance in order to restore them from this copy;
        
        during the first boot after a failure, examine the file system and correct the inconsistencies caused by this failure (at the same time, the file system should strive to make changes so that the scope of such research is minimal);
        
        save information about the last operations performed and repeat these operations during the first boot after a failure.
        
        Disk planning
        
        Disk scheduling algorithms are necessary because one physical resource (in this case, a disk manipulator) has many usage requests (this is similar to CPU time scheduling algorithms, where the physical resource is the processor). The main goal of disk planning algorithms is to optimize the mechanical characteristics of disk access, primarily to minimize the search time (moving the manipulator to position the head on the desired track).
        
        Backup
        
        The most well-known way to increase system reliability is data backup. Backup or archiving is the process of creating a copy of the entire file system or part of it on an external medium for the purpose of restoring data in the event of a crash or user error. Accidents include hard disk failure, physical damage to the computer, virus attack, etc., user errors usually result in the removal of important files. Backups are usually made on inexpensive, high-volume storage media, most commonly magnetic tape drives or CD-ROMs.
        
        One of the main tasks of backup is to identify the subset of file system data that needs to be archived.
        
        Usually backup copies are not created of the entire system, but only a certain subset of its directories. For example, directories with temporary files do not need to be archived. OS system directories are often not archived either, if they can be restored from the distribution disk.
        
        In addition, in the case of regular backups, it makes sense to organize incremental archiving (increment backup), when only the data that has changed since the last copy was created is saved. There are different approaches to organizing incremental archives. You can make a full backup copy after a longer period of time (for example, after a week), and incremental copies - additionally with a shorter interval (for example, after a day); you can make a full copy once, and then limit yourself to incremental copies only. The main problem here is the complication of the data recovery procedure.
        
        At the time of creating a backup copy, it is important to ensure the consistency of the file system. Ideally, a backup copy should be created when the data of the file system does not change (no other processes work with it). In practice, this is difficult to achieve, so special tools are used that "fix" the state of the system for some time.
        
        Physical and logical archiving
        
        There are two basic approaches to creating backup copies: physical and logical archiving. During physical archiving, a full copy of the entire physical structure of the file system is created, all disk data is copied to the backup medium cluster by cluster. The advantages of this approach are its simplicity, reliability and high speed, the disadvantages include inefficient use of space (all free clusters are also copied), the inability to archive a given part of the file system, create incremental archives and restore individual files.
        
        Logical archiving works at the level of logical mapping of the file system (files and directories). With its help, you can create a copy of a specified directory or an incremental copy (at the same time, the time of file modification is monitored), based on such an archive, you can restore a directory or a specific file. Note that in order to implement the correct recovery of individual files in the case of incremental archiving, it is necessary to archive the entire chain of directories that constitute the path to the changed file, even if none of these directories itself has been modified since the last archiving. The standard utility for creating logical backup copies in UNIX systems is called tar.
        
        Conflict prevention and crash recovery
        
        Backups are an important means of increasing the reliability of file systems. However, it is an external tool for the file system. Let's consider internal means of increasing reliability. They are mainly related to changing algorithms for performing file operations and performing low-level recovery operations.
        
        Methods of increasing the reliability of file systems can be divided into two main groups.
        
        Pessimistic predicts that every file system operation can potentially fail, leaving the system in a conflicting state. It is proposed to modify operations in such a way as to prevent this. Productivity may decrease, but reliability will increase. Recovery time after a global crash will be short.
        
        Optimistic predicts that when operations fail, they are rare, and it is not worth sacrificing file system performance to ensure the reliability of each operation. Errors, if any, remain in the file system. If recovery is necessary after a failure, the procedure for checking and restoring the integrity of the entire file system is started, which can last quite a long time. Most OSes offer utilities that perform this check; in UNIX systems, this utility is most often called fsck, in Windows XP — chkdsk or chkntfs. It is necessary, however, to bear in mind that not all errors can be corrected in this way.
        
        File system consistency
        
        The easiest way to prevent file system contention is to ensure that write operations are synchronous. The idea is simple: when writing a block to disk, you need to wait for confirmation from the disk before writing the next block.
        
        In reality, this approach cannot be applied to all write operations (otherwise the performance would decrease unacceptably, for example, caching would stop working). It is necessary to understand for which subset of operations its application does not lead to unacceptable results. To do this, consider what inconsistencies there may be in the file system. As an example, let's take indexed placement of files.
        
        Journal file systems
        
        The large volume of disks makes the execution of the verification and recovery program during booting after a failure a rather long process (for a disk with a size of tens of GB, such a verification can take several hours). In some situations (for example, on database servers with operational information), such delays in restoring the system to work after each failure may not be acceptable.
        
        It is necessary to organize the preservation of information in such a way that recovery after a failure does not require checking all the data structures on the disk. Attempts to solve this problem led to the emergence of logging file systems.
        
        The main purpose of the log file system is to provide an opportunity after a failure, instead of a global check of the entire partition, to perform recovery based on the information of the log (log) - a special area on the disk that stores a description of the latest changes. The use of logging is based on an important observation: when recovering from a failure, only the information that was in the process of being changed at the time of the failure should be corrected. This is the information that did not manage to be completely saved on the disk (usually it occupies only a small part of it).
        
        Data is always read from the file system, the log never takes part in this operation.
- - - - Transmission of messages
      - Allocated memory
      - Mapped memory
    - - A race condition or a race condition occurs when the result of the execution of programs (processes) depends on the sequence of execution of flows in the system (in one situation, the code may work, in another - not, and it is impossible to predict the appearance of an error in the general case).
      - Critical section (critical section) - a fragment of code that causes a problem, converted into an atomic operation, that is, one that is guaranteed to be executed completely without the intervention of other threads.
        
        Properties of critical sections:
        
        Mutual exclusion: at a specific moment in time, the code of the critical section can be executed by only one thread.
        
        Progress: if several threads simultaneously requested entry to the critical section, one of them must enter it (they cannot all block each other).
        
        The waiting limit: a process trying to enter a critical section is bound to enter it sooner or later.
      - Locking
        
        This is a mechanism that prevents more than one thread from executing critical section code.
  - - - If such facilities are the minimal building blocks for building multithreaded programs, they are called synchronization primitives.
  - - - Processes can receive and send messages, while their forwarding is automatically ensured between the address spaces of the processes of the same computer or over the network.
    - - Send (for sending messages through the channel)
      - Receive (to receive a message from the channel).
      - Indirect exchange is carried out through a special object (mailbox, port); processes can put (messages into) the mailbox and receive them from there.
  - - - Only one process has access to the channel at a given time.
    - - It is an abstract connection endpoint through which a process can send or receive messages.
        
        Data exchange between two processes is carried out through a pair of sockets, one for each process. The abstractness of the socket lies in the fact that it hides the peculiarities of the implementation of message transmission — after the socket is created, working with it does not depend on the data transmission technology, so the same code can be used without major changes to work with different communication protocols.
- - - - Minimum response time. This is the most important criterion for interactive systems. The countdown time is the time between the start of the stream (or the user entering an interactive command) and receiving the first response. For modern systems, 50-150 ms is considered an acceptable response time.
    - - This is the number of tasks that the system can perform per unit of time (for example, per second). Such a criterion should be used in batch systems; in interactive systems it can be used for background tasks.
  - - - Also known as Job Scheduler. It selects the processes that are to be placed in the ready queue. The long-term scheduler basically decides the priority in which processes must be placed in main memory. Processes of long term scheduler are placed in the ready state because in this state the process is ready to execute waiting for calls of execution from CPU which takes time that’s why this is known as long term scheduler.
    - - Also known as CPU Scheduler. It places the blocked and suspended processes in the secondary memory of a computer system. The task of moving from main memory to secondary memory is called swapping out. The task of moving back a swapped out process from secondary memory to main memory is known as swapping in. The swapping of processes is performed to ensure the best utilization of main memory.
    - - It decides the priority in which processes is in the ready queue are allocated the central processing unit (CPU) time for their execution. The short term scheduler is also referred as central processing unit (CPU) scheduler.
- - - - All information about each process, except for the contents of its own address space, is stored in the OS table, which is called the process table and is an array (or linked list) of structures, one for each of the currently existing processes.
        
        The process consists of its own address space (memory image), and an entry in the process table, with the contents of its registers, as well as other information necessary for further recovery of the process.
    - - The address space contains the executable program, the program's data, and its stack.
  - - - Background processes are processes that are not related to specific users, but perform a number of specific functions. Most of the time, such processes are spent in sleep mode, activating only as active activity appears (e-mail, web pages, printing information, etc.). Such background processes are often called daemons.
    - - Execution of a system call designed to create a process by a running process.
        
        User request to create a new process.
        
        Batch task initiation.
  - - - Exit when an error occurs (the system asks whether to end the process);
        
        The occurrence of a fatal error (it is not possible to influence the completion process);
        
        Знищення іншим процесом (через системний виклик kill у
        Linux та Terminate Process у Windows).
  - - - A kernel thread is a sequence of instructions in the kernel address space. Kernel threads are managed by the OS, they can be switched only in privileged mode. There are kernel threads that match user threads and threads that don't.