For the operating system, according to the interview key points and some reference on the network, the operating system interview knowledge points summary and learning.

One, operating system knowledge map





Two, the interview question summary

Operating systems, Computer networks, Design patterns

  1. Four features of an operating system.
  2. The main functions of the operating system.
  3. The states of the process, the state transition diagram, and the events leading to the transition. 4. The difference between processes and threads. 5. Several ways of process communication. 6. Several ways of process synchronization 7. Differences between user mode and core state. The concept of deadlocks, causes of deadlocks. 10. Four ways to handle deadlocks. 11. Methods to prevent deadlocks, methods to avoid deadlocks. 12. Process scheduling algorithm. 13. Several algorithms of continuous memory allocation and their advantages and disadvantages. 14. Basic paging storage management mode. 15. Basic segmented storage management. 16. Compare the advantages and disadvantages of segmented paging. 17. Several page replacement algorithms, will calculate the number of pages needed 18. Virtual memory definition and implementation.

Iii. Summary of key and difficult points

1. Four features of the operating system

2. Sharing: Resources in a system that can be used by multiple concurrent threads in memory to virtualize: Virtual asynchrony of a physical entity through TDM (such as time-sharing systems) and space dm (such as virtual memory) : processes in the system execute in a stop-and-go fashion, advancing at unpredictable speeds

2. Main functions of the OPERATING system

Processor management: Processor allocation is on a process basis, so processor management is also referred to as process management. Memory management (or memory management) : memory allocation, memory protection, address mapping, memory expansion device management: management of all peripherals, including the completion of user IO requests; Assign IO devices to user processes. Improve I/O device utilization; Improve IO speed; Convenient I/O file management: Manages user files and system files for easy use and security. Including: disk storage space management, directory management, file read and write management, and file sharing and protection Provides user interfaces: program interfaces (such as API) and user interfaces (such as GUI)

3. Process status and transition




Running status: The process is running on the processor. In a uniprocessor environment, at most one process is running at any one time.

Ready state: the state in which the process is ready to run, that is, the process has all the resources it needs except the processor and can run once it has the processor.

Blocked state, also known as wait state: a process is suspended while waiting for an event, such as waiting for a resource to become available (excluding a processor) or for input/output to complete. The process cannot run even if the processor is idle.

Note the distinction between ready state and wait state: Ready state refers to the process only lacks the processor, as soon as the processor resources to execute; A wait state is when a process needs another resource (other than the processor) or is waiting for an event.

Ready state -> Running state: when a process in the ready state is scheduled, it obtains processor resources (allocates processor time slices) and transitions from the ready state to running state.

Running state -> Ready state: The running process has to relinquish the processor after the time slice runs out, thus the process transitions from running state to ready state. In addition, in a deprivable operating system, when there is a higher priority process, the degree of scheduling shifts the executing process to a ready state for the higher priority process to execute.

Running state -> Blocked state: When a process requests the use and allocation of a resource (such as a peripheral) or waits for an event (such as the completion of an I/O operation), it transitions from the running state to blocked state. A process requests services from the operating system in the form of a system call, which is a special form of operating system kernel procedure called by running a user-mode program.

Blocked state -> Ready state: When the process is waiting for an event, such as the end of an I/O operation or the end of an interrupt, the interrupt handler must change the state of the corresponding process from blocked to ready state.

4. The difference between processes and threads

Process: A process is the running process of a process entity. It is an independent unit of the system for resource allocation and scheduling (it has dynamic, concurrent, independent and asynchronous features, and three states: ready, executing and blocking). Processes are introduced to enable concurrent execution of multiple programs to improve system resource utilization and throughput.

Thread: a basic unit smaller than a process that can run independently. It can be considered a lightweight process (with attributes such as lightweight entities, independent dispatch units, concurrent execution, shared process resources, etc.). The purpose of the introduction is to reduce the overhead of the program in the process of concurrent execution, so that the OS concurrency efficiency is higher.

A comparison of the two:

  1. Scheduling: In thread-introduced OS, threads are independent units of scheduling and dispatching, while processes are the unit of ownership of resources (equivalent to separating the two properties of processes in traditional OS without threading). Since threads do not own resources, concurrency can be significantly improved and switching overhead reduced.

  2. Concurrency: the introduction of threads in the OS, the process can be concurrent, and a process can be concurrent between multiple threads, which makes the OS has better concurrency, effectively improve the utilization of system resources and throughput.

  3. Owning resources: Regardless of whether the OS supports threads or not, a process is the basic unit of resource ownership. Threads have very few basic resources, but they can access the resources of the process they belong to (code segments, data segments, and owned system resources such as fd).

  4. System overhead: PCB and system resources are created or reclaimed when a process is created or destroyed, and the CPU environment is saved and restored when a process is switched over. However, thread switching only needs to save and restore a small number of registers, and does not involve memory management, so the cost is small. In addition, multiple threads in the unified process share the address space, so communication and synchronization are more convenient.

5. Process communication

Process communication refers to the exchange of information between processes. PV operation is a low-level communication mode, and high-level communication mode refers to the communication mode that transmits a large amount of data with high efficiency. There are three main classes of advanced communication methods.

Shared storage

There is a shared space that can be directly accessed between the communicating processes. The processes can exchange information by writing/reading the shared space. When performing write/read operations on the shared space, you need to use synchronization and mutual exclusion tools, such as P and V operations, to control the write/read operations on the shared space. Shared storage can be divided into two types: low-level sharing based on data structure; The advanced approach is based on shared storage. The operating system is only responsible for providing the communication process with shareable storage space and synchronous mutually exclusive tools, while the data exchange is completed by the user’s own read/write instructions.

It is important to note that the user process space is generally independent and can be shared by two user processes only through a special system call, whereas the threads within the process naturally share the process space.

The messaging

In a messaging system, data exchange between processes is in units of formatted messages. If there is no shared space that can be accessed directly between the communicating processes, the message passing method provided by the operating system must be used to realize the process communication. Processes exchange data by sending message and receiving message primitives provided by the system.

1) Direct communication: the sending process directly sends the message to the receiving process and hangs it on the message buffer queue of the receiving process, and the receiving process obtains the message from the message buffer queue.

2) Indirect communication: the sending process sends the message to an intermediate entity, and the receiving process obtains the message from the intermediate entity. This intermediary entity is generally called mailbox, and this communication mode is also called mailbox communication mode. This communication mode is widely used in computer network, and the corresponding communication system is called E-mail system.

Pipeline communication

Pipe communication is a special form of message delivery. A “pipe” is a shared file, also known as a pipe file, used to connect a reading process and a writing process for communication between them. A sending process (that is, a writing process) that provides input to a pipe (a shared file) and streams large amounts of data into the pipe (a write) as a character stream; The receiving process that receives the output of the receiving pipe (that is, the reading process) receives (reads) data from the pipe. In order to coordinate communication between two parties, the pipeline mechanism must provide coordination capabilities in three aspects: mutual exclusion, synchronization, and determination of the presence of the other party.

6. Synchronize processes

Although multi-process improves system resource utilization and throughput, it may cause system chaos due to process asynchrony. The task of process synchronization is to coordinate the execution sequence of multiple related processes, so that the concurrent execution of multiple processes can effectively share resources and cooperate with each other, and ensure the reproducibility of program execution

The synchronization mechanism follows the following principles:

  1. Idle concession: When no process is in a critical section, other processes should be allowed to apply for access to the critical section
  2. Busy wait: If a process is in the critical zone and other processes apply to enter the critical zone, the process must wait to ensure mutually exclusive access to the critical zone
  3. Finite wait: For processes that require access to critical resources, a finite amount of time is required to enter the critical section to prevent deadbeats
  4. Idle wait: when a process cannot enter a critical section, the processor needs to be released, an edge is busy, etc

The classic process synchronization problem: producer-consumer problem; Philosophers eat; The reader-writer problem

Synchronized solutions: pipe side, semaphore.

7. User state and core state




When a program is running at privilege level 3, it can be said to be running in user mode, because this is the lowest privilege level, which is the privilege level of ordinary user processes. Most programs directly faced by users are running in user mode.

Conversely, when a program is running at the level of privileges, it is said to be running in kernel mode.

Although there are many differences between user-mode and kernel-mode programs, the most important difference is the difference in privileges, or power. Programs running in user mode cannot directly access the operating system kernel data structures and programs.

When we run a program on the system, most of the time it runs in user mode, switching to kernel mode when it needs the operating system to do something it doesn’t have the authority or ability to do.

Three modes for switching from user mode to kernel mode

1) System call: this is a way for the user-mode process to actively request switching to the kernel mode. The user-mode process applies for using the service program provided by the operating system to complete its work through the system call. The core of the system call mechanism is to use an interrupt specially opened by the operating system for users to achieve, such as Int 80H interrupt of Linux.

2) Exception: when the CPU is executing the program running in user mode, some unknown anomalies occur in advance, which will trigger the switch from the current running process to the kernel-related program dealing with this exception, and then turn to the kernel state, such as page missing exception.

3) Interruption of peripheral devices: After the peripheral equipment to complete the operation of the user request, will send a corresponding to the CPU interrupt signal, the CPU will be suspended for the next article is going to execute commands to perform and interrupt signals corresponding handler, if previously executed instructions are under the user mode application, then the transformation process also occurs naturally from user mode to kernel mode switch. For example, after a disk read/write operation is complete, the system switches to the disk read/write interrupt handler for subsequent operations.

8. A deadlock

Deadlock refers to a deadlock caused by competing for resources during the running of multiple processes. If there is no external push, the process in deadlock cannot continue to execute.

Deadlock cause:

  1. Competing for resources: The number of processes requesting the same limited resource exceeds the number of available resources
  2. Illegal process advance sequence: During process execution, resources are requested and released in an inappropriate sequence, for example, resource waiting chain

The necessary conditions for a deadlock to occur:

  1. Mutual exclusion: A process makes exclusive use of allocated resources
  2. Request and hold conditions: the lock is not released when the process is blocked
  3. Inalienable condition: a process cannot be deprived of a resource that has already been claimed until its use is complete
  4. Loop wait condition: a process-resource loop wait chain that exists when a deadlock occurs

Deadlock handling:

  1. Deadlock prevention: Breaking one or more of the four necessary conditions for deadlock prevention. It is relatively simple to implement, but too restrictive can reduce system resource utilization and throughput

  2. Deadlock avoidance: In the dynamic allocation of resources, prevent the system from entering an insecure state (a state that could produce deadlocks)- such as the banker algorithm

  3. Deadlock detection: allows the system to create deadlocks during operation. After deadlocks occur, certain algorithms are used to detect them, and resources and processes related to deadlocks are determined. Related methods are adopted to clear detected deadlocks. Difficult to implement

  4. Unlock deadlock: In conjunction with deadlock detection, the system is freed from deadlock (revoking processes or depriving resources). For deadlock-related processes and resources detected, release some resources and allocate them to the blocked process by canceling or suspending it, making it become ready. Difficult to implement

9. Process scheduling algorithm

First come first service scheduling algorithm FCFS: can be used as job scheduling algorithm or process scheduling algorithm; Schedule jobs or processes in order of arrival; Therefore, it is more favorable for long operation;

Short Job first scheduling algorithm SJF: Job scheduling algorithm, the algorithm selects the job with the shortest estimated time from the ready queue for processing, until the result is obtained or cannot continue to execute; Disadvantages: not conducive to long operation; Failure to consider the importance of the operation; The uptime is estimated and unreliable;

High response ratio algorithm HRN: Response ratio =(waiting time + required service time)/ required service time;

Time slice rotation scheduling RR: put the processes in the queue according to the sequence of arrival, and then allocate CPU time slices to the first process in the queue. When the time slices are used up, the timer will interrupt, suspend the current process and put it to the end of the queue, and cycle.

Multi-level feedback queue scheduling algorithm: currently recognized as a good scheduling algorithm; Set up multiple ready queues and set different priorities for each queue, with the first queue having the highest priority and the rest successively decreasing. The queue with a higher priority will allocate a shorter time slice. When the process arrives, it will be put into the first queue according to FCFS. If the scheduling is not completed after execution, it will be put into the tail of the second queue to wait for scheduling. . Processes in the next queue are scheduled only if the current queue is empty.

10. Continuous memory allocation

It mainly refers to several algorithms used when dynamic partition allocation. Dynamic partition allocation, also known as variable partition allocation, is a dynamic memory partition method. This partition method does not pre-partition memory, but dynamically creates partitions according to the size of the process when it is loaded into memory, and makes the partition size just fit the needs of the process. Therefore, the size and number of partitions in the system are variable.





First Fit algorithm: Free partitions are linked in increasing address order. When allocating memory, search for the first free partition whose size meets the requirement.

Best Fit algorithm: the partition chain is formed by increasing the capacity of the idle partition, and the first one that can meet the requirements is found.

Worst Fit algorithm: Also known as Largest Fit algorithm, free partitions are linked in decreasing order of capacity. Find the first free partition that meets the requirements, that is, pick the largest partition.

11. Basic paging storage management mode

The main storage space is divided into equal and fixed blocks, which are relatively small and used as the basic unit of main storage. Each process is divided into blocks. When a process executes, it applies for block space in main storage one by one.

Because the program data is stored in different pages, and pages are distributed in memory discreetly, a page table is needed to map the logical address to the actual storage address to achieve the mapping from page number to physical block number.

Since the page table is also stored in memory, accessing memory data in a paging system requires two memory accesses compared to storage without paging management (one accesses the page table from memory to find the specified physical block number, plus the in-page offset to get the actual physical address; The second time is to access the memory based on the physical address obtained in the first time.





In order to reduce the influence caused by twice the memory access efficiency, paging fast table is introduced in the management mechanism, contained in the fast table mechanism of memory management and when to allow access to memory data, will first page number in a table in the query, if find the instructions to access the page table entries in a table, then directly from table reads the corresponding physical block; If not, access the in-memory page table, get the physical address from the page table, and add the mapping entry from the page table to the fast table (there may be a fast table swap algorithm).

On some computers, if the logical address of memory is large, the program will have a large number of page table items, and the page table is stored in memory contiguously, so the corresponding large contiguous memory space is required. To solve this problem, two-level or multi-level page tables can be used, in which the outer page table is called into memory once and stored continuously, and the inner page table is stored discretely. The corresponding access to the memory page table requires an address transformation, and the access to the physical address corresponding to the logical address also needs an address transformation, and a total of three times to access the memory to read a data.

12. Basic segmented storage management

Paging is to improve memory utilization, while segmentation is to meet the logical needs of programmers when writing code (such as data sharing, data protection, dynamic linking, etc.).

In segmented memory management, the address is two-dimensional, one dimension is the segment number, one dimension is the segment address; Each segment has a different length, and each segment is internally addressed from 0. In segment management, memory is allocated continuously within each segment, but among segments is allocated discretely. Therefore, there exists a mapping relationship between logical addresses and physical addresses, which is the corresponding segment table mechanism. Each entry in the segment table records the start address and length of the segment in memory. Segment tables can be placed in memory or registers.





During memory access, the location of the current access segment in the segment table is calculated according to the segment number and the length of the segment entry. Then, the segment table is accessed to obtain the physical address of the segment. The memory to be accessed can be obtained according to the physical address and the offset of the segment. Since there are also two memory accesses, associative registers are also introduced in segment management.

Comparison of segmented paging methods

Page is the physical unit of information, which is a discrete allocation mechanism proposed from the perspective of system memory utilization. Segments are logical units of information, and each segment contains a group of complete information, which is a memory management mechanism proposed from the perspective of users

The page size is fixed and determined by the system; The segment size is indeterminate and is determined by the user

Virtual memory

If there is a program that requires more memory than the computer can actually provide, the program will not run because it cannot fit into memory. Simply increasing physical memory solves only part of the problem, but there is still the problem of not being able to load a single program or multiple programs simultaneously. However, the above two problems can be solved by logically expanding the memory capacity.

Based on the principle of locality, when the program is loaded, part of the program can be loaded into memory, and the rest can be left in external memory, and the program execution can be started. During program execution, when the accessed information is not in memory, the operating system calls the required part into memory and continues to execute the program. On the other hand, the operating system moves temporarily unused content out of memory to make room for information that will be called into memory. In this way, the system appears to provide the user with a memory much larger than the actual memory, called virtual memory.

Characteristics of virtual storage:

  1. Multiple: A job can be loaded into memory more than once. Repeatability is a property unique to virtual storage
  2. Commutation: there is a process of switching in and out during the operation of the job (switching out temporarily unused data for needed data)
  3. Virtuality: Virtuality is defined by its logical expansion of memory capacity (the ability to run applications that require more real memory than physical memory). Virtuality is the most important feature of virtual memory and its ultimate goal. Virtuality is based on multiplicity and commutation, which in turn are based on discrete distribution
14. Page replacement algorithm

Best replacement algorithm: an algorithm of theoretical significance only, used to evaluate other page replacement algorithms. The replacement strategy is to swap out the pages in the current page that will not be accessed for the longest time in the future.

First-in, first-out (FIFO) replacement algorithm: a simple and crude replacement algorithm that does not consider the frequency of page access information. Each time the earliest page is eliminated.

LRU: The algorithm entrusts each page with a access field, which is used to record the time t experienced by the last page to be visited until now. Each time the displacement of the page with the largest t value is replaced out (register or stack can be used to achieve the realization).

Clock (also known as the recently unused algorithm NRU) : The page is set to an access bit, and links the page into a ring queue, the access bit is set to 1 when the page is accessed. When a page is swapped, if the current pointer points to a page access value of 0, then it is swapped, otherwise it is set to 0, and the loop continues until a page access bit 0 is encountered.

Improved Clock algorithm: add a modified bit on the basis of the Clock algorithm, and judge the access bit and the modified bit comprehensively during replacement. Pages with access bit 0 and change bit 0 are replaced first, followed by pages with access bit 0 and change bit 1.

Least-used algorithm LFU: Register is set to record the number of times the page is accessed, and the least number of times is replaced each time.

Four,

The above is just a summary of the key points of the operating system, if there is no corresponding operating system foundation, it may not be very easy to understand, the following recommended their own learning operating system process reference some information.

Recommended courses:The operating system




A teacher of Tsinghua University spoke, spoke very methodical, simple, patient to listen to, harvest a lot.

Recommended information:Computer operating system tutorial

Is the C language Chinese online information, a total of five chapters, systematically organized and explained the key and difficult points of the operating system, if you do not understand some of the above key points, you can refer to the corresponding.