Summary of operating system underlying knowledge (interview)

One 、 Introduction to operating system

What is an operating system ？

An operating system is an application that manages hardware and software . It provides an intermediate layer for computer hardware and software , Separation of application software and hardware . Usually , Many of these applications will run on the computer , They all need memory and CPU Interact , The purpose of the operating system is to ensure that these accesses and interactions can be carried out accurately . Common operating systems are ：windows、mac、Linux.

Main functions of the operating system ：

（1） Process management ： The main function of process management is task scheduling , On a single core processor , The operating system assigns a task to each process ; And in multicore processors , In addition to assigning tasks to processes, the operating system , We also need to solve the scheduling of processors 、 Distribution and recycling .

（2） memory management ： The operating system is mainly responsible for managing memory allocation 、 Recycling , Allocate memory when the process needs it and reclaim memory when the process finishes , Coordinate memory resources , Through a reasonable page replacement algorithm for page in and out .

（3） Equipment management ： Allocate the equipment according to the determined equipment allocation principle , Enable the device to work in parallel with the host , To provide users with a good interface to use the device .

（4） file management ： Effectively manage file storage space , Organize and manage file system reasonably , Provide more effective methods and means for file access and file protection .

（5） Provide user interface ： Provides interfaces to access applications and hardware , So that users can initiate system calls through the application to manipulate the hardware , Achieve the desired function .

The main purpose of the operating system ：

（1） Managing computer resources , Include CPU、 Memory 、 Disks, etc ;

（2） Provides a graphical interface , It provides a bridge between users and computers ;

（3） Services for other software , The operating system interacts with the software , So that it can allocate any necessary resources for operation .

I/O operation ：

Software accessing hardware is actually a kind of I/O operation ,I/O Operations fall into the following four categories ：

（1） Direct access ： Direct access is directly controlled by the user process CPU And peripheral devices . Direct program control is also called busy / The way to wait .
（2） Interrupt drive ： In order to reduce the number of programs under direct control CPU And improve the parallelism of the system , The system introduces interrupt mechanism . After the introduction of interrupt mechanism , The peripheral device will only send a signal to when the operation ends normally or abnormally CPU Make an interrupt request . stay I/O The device enters each data in the process , Because there is no need to CPU Intervention , To some extent CPU And I/O Parallel operation of devices .
（3）DMA Direct memory access ： In order to further reduce CPU Yes I/O Operational intervention , To prevent the parallel operation of too many devices CPU Too late to deal with or data loss caused by speed mismatch , Introduced DMA The control mode .
（4） Channel control mode ： passageway , Independent of CPU A special processor for I / O control , It controls the direct data exchange between the device and the memory .

Two 、 Processes and threads

What are processes and threads ？

process It's a running program , It will occupy the corresponding memory area , from CPU Execute and calculate .

Threads Is an execution task in the process , Responsible for the execution of programs in the current process . A process has at least one thread , A process can run multiple threads , Multiple threads can share data . So when the system generates a thread or switches between threads , The burden is much smaller than the process .

Difference between process and thread ：

Fundamental difference ： Process is the basic unit of operating system resource allocation , And thread is the basic unit of processor task scheduling and execution . Basically, the processes are independent , Threads are not necessarily .

Resource overhead ： Each process has its own code and data space , Switching between programs can be costly ; Threads can be thought of as lightweight processes , The same class of threads share code and data space , Each thread has its own running stack and program counter , The cost of switching between threads is small .

Inclusion relation ： If there are multiple threads in a process , The execution process is not a line , It is done by multiple threads ; Threads are part of the process .

Memory allocation ： Threads of the same process share the address space and resources of the process , The address space and resources between processes are independent of each other .

Influence relationships ： After a process crashes , No impact on other processes in protected mode , But when a thread crashes, the whole process dies , So multiprocessing is more robust than multithreading .

Execution process ： Each independent process has an entry to run the program 、 Sequential execution sequences and program exits . But the thread cannot execute independently , Must exist in the application , Multiple thread execution control provided by the application , Both can be executed concurrently .

Communication between processes ：

The messaging ： Message passing is a mechanism to realize communication and synchronous waiting between processes , Use messaging , Communication between processes does not require shared variables , You can communicate directly ; Message passing is divided into sender and receiver
First in first out queue ： FIFO queue refers to the communication between two unrelated processes , Two processes can communicate with each other , This is a full duplex communication mode
The Conduit ： Pipes are used for communication between two related processes , It's a half duplex communication , If you need full duplex , We need another pipe .
Direct communication ： In this way of process communication , There is only one link between processes , The names of the communication parties should be specified between processes .
Indirect communication ： Indirect communication means that the two sides of communication will not establish a direct connection , It's about finding an intermediary , The intermediary may be an object and so on , The process can place messages in it , And you can delete messages from it , In order to achieve the purpose of inter process communication .
Message queue ： Message queue is a list of messages stored in the kernel , It is identified by the message queue identifier , This way can provide full duplex communication between different processes .
Shared memory ： Shared memory is the use of memory between all processes to establish a connection , This type requires synchronous process access to protect each other .

Three state model of process ：

 

Ready state ： The process has obtained the required resources other than the processor , Waiting to allocate processor resources ;

Running state ： Occupy processor resources to run , The number of processes in this state is less than or equal to CPU Count ;

Blocked state ： The process waits for some condition , Cannot execute... Until the conditions are met .

Five state model of process ：

New status ： The new state of a process is just when the process is created

Termination state ： The termination state of a process means that the process has been executed , To the end , Or you have to abort the process because of an error .

3、 ... and 、 memory management

What is paging on demand ？

In the operating system , Processes are loaded into memory on a page by page basis , Paging on demand is a kind of Virtual memory Management style . In systems that use request paging , Only if you try to access the disk where the page is located and the page is not already in memory , And that's what happened Page missing exception , The operating system will copy the disk page into memory .

What is virtual memory ？

Virtual memory Is a memory allocation scheme , Is a mechanism that can be used to assist memory allocation . For virtual memory , The operation that a computer can perform is to look at areas of memory that have not been used recently , And then copy it to the hard disk . Virtual memory is realized through replication technology .

How to implement virtual memory ：

Request paging storage management .

Request staging Management .

Request segment page storage management .

Segment storage management It is a memory allocation management scheme in line with the user's perspective . In segmented storage management , Divide the address space of a program into segments （segment）, Such as code snippet , Data segment , stack segment ; So each process has a two-dimensional address space , Are independent of each other , Mutual interference . The advantage of segment management is ： No internal debris （ Because the segment size is variable , Change segment size to eliminate internal fragmentation ）. But segment in and out , Debris will form outside （ such as 4k Segment change of 5k Section of , Will produce 1k The outer fragment of ）

Page storage management The scheme is a memory allocation management scheme that separates the user view memory from the physical memory . In page storage management , Divide the logical address of a program into fixed size pages （page）, Physical memory is divided into frames of the same size , When the program is loaded , You can put any page into any frame in memory , These frames don't have to be continuous , So discrete separation is realized . The advantage of paged storage management is ： There is no outer fragment （ Because the size of the page is fixed ）, But it produces internal debris （ A page may not be filled with ）.
 

Why is memory segmented ？

（1） Memory is a random access device , For memory , There's no need to start from scratch , Just give the address directly . The segmentation of memory is from 8086 CPU At the beginning ,8086 Of CPU still 16 Bit register width ,16 The range of digits that can be stored in the register of bits is 2 Of 16 Power , namely 64 KB,8086 Of CPU Not yet Virtual address , Only physical address , in other words , If two identical programs compile at the same address , So these two programs can't run at the same time . To solve this problem , The operating system designers proposed to let CPU Use Section base address + Offset within segment To access any memory in the same way .
（2）8086 Of CPU Yes 20 Root address bus , The biggest addressing capability is 1MB, The width of the register where the segment base address is located is only 16 position , The biggest is for you 64 KB The ability to address ,64 KB Obviously can't satisfy 1MB The maximum addressing range of , So we need to segment the memory , The maximum addressing capacity of each segment is 64KB, But it still can't reach the maximum 1 MB The ability to address , So it's time to Auxiliary of offset address , The offset address is also stored in the register , For the same 64 KB The ability to address , I can't be satisfied with that 1MB Addressing , therefore CPU The designer of the address unit has tampered with it , Move segment base left 4 position , And then with 16 Add the offset addresses within the segment , That's it. 1MB The ability to address . therefore The second purpose of memory segmentation is to be able to access all memory .

What are the page replacement algorithms ？

1.OPT Page replacement algorithm （ The best page replacement algorithm ） ： The best (Optimal, OPT) The obsolete page selected by the replacement algorithm will never be used in the future , Or pages that are no longer visited for the longest time , In this way, we can guarantee the minimum page missing rate . But at present, it is impossible to predict which of the thousands of pages in memory will not be accessed for the longest time in the future , So the algorithm can't be implemented . Generally as a measure of other permutation algorithms .
2.FIFO（First In First Out） Page replacement algorithm （ First in first out page replacement algorithm ） : Always weed out the first pages in memory , That is, select the page with the longest stay time in memory to be eliminated .
3.LRU （Least Currently Used） Page replacement algorithm （ The most recent page replacement algorithm not used ） ：LRU The algorithm gives each page an access field , Used to record the time of a page since it was last visited T, When a page has to be eliminated , Select one of the existing pages T The most valuable , That is, the most recent unused page to be eliminated .
4.LFU （Least Frequently Used） Page replacement algorithm （ At least use page replacement algorithm ） : The permutation algorithm selects the least pages used in the previous period as the elimination page .

  Four 、 Deadlock

What is a deadlock ？

The so-called deadlock , A deadlock in which several processes compete for resources while running , When the process is in this stalemate , If there is no external force , They will not be able to move forward . So let's take an example to describe , If there is a thread at this time A, Lock it first a Get the lock again b The order of getting locks , And there's another thread at the same time B, Lock it first b Relock a The order to get the lock .

The necessary conditions for deadlock ：

1. mutual exclusion ： Processes require exclusive control of allocated resources , That is, in a period of time, a resource is occupied by only one process .
2. Request and hold conditions ： When a process is blocked by a request for resources , Keep the acquired resources .
3. Conditions of non deprivation ： The resources obtained by the process are not used up , Can't deprive , It can only be released by itself after use .
4. Loop wait condition ： In the life and death lock , There must be a process – Circular chain of resources .

The solution to deadlock ：
1. One time allocation of resources ： Allocate all resources at once , So there will be no more requests ：（ Break request condition ）
2. As long as one resource is not allocated , No other resources are allocated to this process ：（ Please keep the condition ）
3. Deprivable resources ： That is, when a process gets some resources , But there are no other resources , Then release the occupied resources （ The destruction of the inalienable conditions ）
4. Orderly allocation of resources ： The system assigns a number to each type of resource , Each process requests resources in ascending order , Release is the opposite （ Destroy the loop waiting condition ）