This is the seventh day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.


This series full text in 10 w +, the full text is the note in his own dry, soft test involves many basic computer, data structure and algorithm analysis and programming ideas, development process and so on, not only suitable for soft people learn, also suit to broaden their knowledge to learn, each article will be focused bold processing, especially easy to fault point, It is easy to remember wrong in exams. Please watch carefully! If you like this series, be sure to follow this column and leave a little like!

Chapter comb

  1. Operating system has four basic characteristics: concurrency, sharing, virtuality and uncertainty
  2. The types of operating systems are: batch operating system, time-sharing operating system, real-time operating system, network operating system, distributed operating system, microcomputer operating system, embedded operating system
  3. Processes typically consist of programs, data, and process control blocks (PCBS). There are three basic three-state models: run, ready, and blocked. The diagram below:

  1. Synchronization and mutual exclusion: Synchronization is a direct restriction between cooperative processes and mutual exclusion is an indirect restriction between processes applying for critical resources.
  2. Synchronization between processes: Cooperative processes need to coordinate their work at certain points where one process has to stop and wait until the other process has completed certain operations. (With speed matching requirements)
  3. Critical resources: In a multiprogram system, processes can share various resources, but some resources can only be used by one process at a time. (Indirectly creating the problem of constraints — mutual exclusion). A critical section is the part of a process that performs operations on critical resources. Mutually exclusive critical area management principle is: empty namely enter, no empty then, limited wait, let the right to wait.

  1. P, V operation is a common method to achieve process synchronization and mutual exclusion.
  2. Definition of P operation: S: = s-1, if S is greater than equal to 0, then the process executing P operation continues to execute; Otherwise, if S is less than 0, the process is set to block and inserted into the blocking queue.
  3. The definition of V operation is as follows: S: =S+1, if S is greater than 0, the process executing V operation continues to execute; Otherwise, if S is less than or equal, a process is woken from the blocked state and inserted into the ready queue, and the process performing the V operation continues.

  1. The arrow starts at the V operation, and the arrow points to the P operation

  1. Deadlock: A situation in which two or more processes cannot run because they are claiming resources already owned by each other. Deadlock is an error state of the system, so it should be avoided and prevented as much as possible.
  2. Deadlocks are caused by resource competition and an illegal process order.
  3. Deadlocks produce four necessary conditions: mutex condition, request hold condition, inalienable condition, and loop condition
  4. Deadlock handling: the most famous is the banker algorithm (*) as shown below:

  1. Partitioned storage management:! Fixed partition! Variable partition (dynamic partitioning methods, the division of the storage space is in the work loads, so the number of the partition can change the size of the partition size just equal to the job, but produce more pieces, system use idle idle partition in the partition table to manage main memory, request and release partition optimal adaptive algorithm can be used, the worst adaptation algorithm, adaptive algorithm for the first time, Cycle first adaptive algorithm 4 kinds of allocation)! Relocatable partitions

  1. Paged storage organization (Paged storage management) : The system divides the address space of a process into equal-sized areas called pages. Similarly, the main memory space is divided into physical blocks of the same size as the page, called blocks or page frames. Page table: The system establishes a page mapping table for each process, which is used to realize the address mapping from the page number to the physical block number.

  1. Fast table: Add a small capacity associative register (associative memory) to address mapping wit, which consists of a group of high-speed memory, called a fast table. Fast tables are used to hold information about the few active pages that are currently most frequently accessed.

  1. Segmented storage management (segmental storage) : The job address space is divided into several program segments according to the logical relationship of the program itself, and each segment is a complete set of logical information. Each segment has its own segment name and has a segment number. The segment number starts from 0, and each segment is addressed from 0. The addresses in the segment are continuous and vary in length.

  1. Segmented page storage management: Combines the advantages of segmented storage management and paged storage management to overcome the disadvantages of both. (Cons: As management software increases, so does complexity and overhead, so does the amount of hardware and content required.)
  2. Page replacement algorithm: The core problem of the request paging system is to choose the appropriate page replacement algorithm. There are four commonly used algorithms: 1. Optimal algorithm, an idealized algorithm, has the best performance, but is difficult to implement in practice, and is often used to evaluate other algorithms. 2, first in first out (FIFO) replacement algorithm: the algorithm is always the first to eliminate the most advanced main memory page, that is, to choose the longest resident time in main memory page elimination. This is the most intuitive and the least performing algorithm. It has a Belady exception. 3, the most recent unused (LRU) replacement algorithm: this algorithm is to choose the most recent unused page elimination, in the implementation of the need for hardware support (register or stack) 4, the most recent unused replacement algorithm: this algorithm will be the most recent period of time unused page swap out, is a kind of LRU approximate algorithm.
  3. “Not using fast tables”; Each read requires the table to be read, and each block requires two memory accesses.
  4. The instruction produces only one missing interrupt, and the operand produces two missing midpage.
  5. Physical structure of the file: continuous structure, link structure, index structure. The UNIX file system uses a three-level index structure. The inode is the basic component of the file system. It represents the nodes of the file system. UNIX has four addressing modes: direct, first level indirect, second level indirect, and third level indirect.

  1. File access methods: 1, sequential access 2, random access 3, key access
  2. File storage space management: Common free space management methods include free area table, bitmap (*), free block chain, and group linking.

  1. Shown in figure:
  2. Features of bitmap: The size of bitmap is determined by the disk space (total number of physical blocks). Bitmap has strong description ability and is suitable for various physical structures.

Wrong topic integration

Disk block size/disk block number = Index block contains N Disk block number Conversion of logical address and physical address: The logical address/page size is equal to the physical address first. (generally, both page size and logical address should be converted to binary, 2^13=8192 (8k) 2^12=4096 (4k)) bitmap size calculation :(disk capacity * (1024/ physical block size))/system word length real-time operating system is an operating system that guarantees to complete certain functions within a certain time limit. Divided into hard real-time and soft real-time, hard real-time requirements in the specified hard press must complete the operation, which is guaranteed in the design of the operating system; In soft real-time, you only need to complete the operation as long as possible according to the priority of the task. When a process is running and other processes access the semaphore, the semaphore is subtracted by one. The keyboard device acts as the input device and generates an interrupt whenever a key is pressed or released by the user. Single buffer and the calculation of double buffer: {each disk block read time + to the users area} * file size + processing time double: each plate piece read time * file size, sent to the user time and processing time system initialization process is divided into three main parts, in accordance with the bottom-up, from hardware to software, in the order of the order Chip level initialization, board level initialization, system level initialization. There is no need to consider the implementation of the language compiler when designing the operating system. (*) When the semaphore value is less than 0, no resource is available, and its absolute value indicates the number of processes waiting for the resource in the blocking queue. PV operations are function-specific primitives provided by the operating system. The use of PV operations can achieve mutually exclusive use of resourcesCopy the code