operating system ： Provides the application with a basic abstraction of the resource set , Orderly control of processors between competing programs 、 Memory and so on I/O Allocation of interface equipment （ Resource management ： Time reuse 、 Spatial reuse ）.
computer hardware ：
- Every CPU In the basic cycle , Fetching instructions from memory - decode ( To determine its type and operation )- perform , So again and again .
Because access to memory is slow ,CPU There are registers in it :
- General registers : Used to hold key variables and temporary data
Special register ：
- Program counter ： The memory address of the next instruction
- Stack pointer ： Current stack top
- Program status word （PSW): Conditional code point （ Set by the compare command ）、 CPU priority 、 Pattern （ User mode or kernel mode ） Wait for the control bit
modern CP Design ：
- Assembly line ： There is a separate finger retrieval unit 、 Decoding unit and execution unit , It can take out multiple instructions at the same time .
- Superscalar ： More advanced , There are multiple execution units （ As long as one execution unit is idle , Just check if there are any instructions that can be processed in the buffer , If there is , Just take the instruction out of the buffer and execute it .）
- User mode ： User program coding can solve
Kernel mode ： Unable to encode , User programs must use system calls （ Internal interruption ） Get into the kernel and call the operating system .
Internal interruption （ abnormal ）
- error (fault): Save the instruction that points to the trigger exception （ example ： Page missing exception ）
- fall into （trap)： Save the next instruction to the instruction that triggered the exception （ example ： debugging ）
- External interruption
- CPU register 1ns <1k:32 position CPU yes 32\32 64 position CPU yes 64\64
- Cache 2ns 4M
- Main memory 10ns 1-8G RAM ROM Flash CMOS
- disk 10ms 1-4T Low end hard disk speed 50MB/s, High speed hard disk 160 MB/s
- I/0 equipment = Device controller + The device itself
- Provides a simple interface for the operating system . A small embedded computer is often installed in the controller , Run programs that are specially designed to perform these tasks .
- Most device drivers （ Talk specifically to the controller , Software that issues commands and receives responses ） You need to run in kernel mode
- The device itself ： The device itself has a relatively simple interface , This is because interfaces can't do much work , It's been standardized again .
- Realization IO The way ： Busy waiting 、 interrupt 、 Direct memory access
Most important PCIe Bus
- brief introduction ：10+Gb/s It's a serial bus architecture , Instead of traditional PCI Parallel bus architecture of , A message that combines all bits is delivered over a link called a data path , It's very much like a network packet .PCIe 2.0 Standard 16 Data paths provide 64Gb/s The speed of , Upgrade to PCIe 3.0 It will speed up later 2 times , and PCIe 4.0 It's going to speed up again 2 times .
- adopt DDR3 Bus and memory conversation
- adopt PCie The bus communicates with peripheral graphics devices
- adopt DMI The bus communicates with all other devices through the integration center
- Through universal serial bus and USB Device conversation
- adopt SATA Bus and hard disk DVD Drive dialog
- adopt PCle Transmit Ethernet frames
USB Used to put all the slow I/0 equipment （ Like keyboard and mouse ） The connection to the computer
- USB 1.0 12Mb/s
- USB 2.0 480Mb/s
- USB 3.0 5Gb/s
- A high speed bus is used in High speed hard disk 、 Scanner 、 Servers and workstations 640MB/s
- Plug and play ： The system automatically collects information about 1/0 Device information , Focus on giving interrupt levels and I/0 Address , Then inform each card of the value used .
Start the computer
BIOS Check the installed RAM Number , Keyboards and other basic devices
- scanning PCie and PCI Bus and find all the devices connected to it
- Try to store in CMOS The list of devices in the memory decides to start the device
- The operating system asks BIOS, To get configuration information
- Check the ready device driver , The operating system calls them into the kernel
- Create any background processes you need , Start the login program or GUI
Basic features of the operating system
Concurrent ： In the same period of time
- parallel ： At the same time （ Multiprogramming deals with macro concurrency , On the micro level, it is executed alternately ）
- Mutually exclusive sharing （ Like audio devices The printer ）
- Simultaneous access （ Disk files ）
- cpu: Each user （ process ） Of “ Virtual processors ”
- Memory ： The address space occupied by each process （ Instructions + data + Stack ）
- Display device ： Multi window or virtual terminal
- Printing equipment ： Access to critical resources at the same time
- The criterion ： No matter how fast or slow , The result is the same
- A process is an instance of an executing program , Including program counter 、 The current values of registers and variables .
Multiprogramming ：（ false ） The set of processes that run in parallel ``` CPU utilization = 1-p^n One Processes waiting I/0 The ratio of the operation time to the time spent in memory is p n It's called multiprogramming ```
- 1) System initialization ．
- 2) The running program executed the system call to create the process .
- 3) User requests to create a new process .
- 4) Initialization of a batch job .
- 1) The normal exit （ voluntary ）.
- 2) Error exit （ voluntary ）.
- 3) Serious mistakes （ Involuntarily ）.
- 4) Killed by other processes （ Involuntarily ）.
- Blocking block
- Wake up the wakeup
- Hang up suspend
- UNIX The process and all its children and descendants form a process group . After the user sends a signal, each process can capture the signal separately 、 Ignore the signal or take the default action , Killed by the signal . In the whole system , All the processes are thousands of init A tree for the root
- Windows All processes have the same status
The state and transition of a process
- state ： be ready （ready) perform (running) Blocking (blocked)
- Has a pending state ： perform , Activity ready , Activity jam , Stand still , Static blocking
Process control block
Information in the process control block
- General registers
- Instruction counter
- Process status
- Information needed for scheduling （ The process has been waiting CPU Time , The total amount of time a process has been executed ）
- Program 、 Data address
- Synchronization and communication （ Message queue pointer Semaphore ）
- List of occupied resources
- Link pointer （ This process PCB The next process in the queue PCB The first address ）
- Family relations Child process parent process identifier
Light entity ： Only have essential resources , Such as ： Thread state 、 Register context and stack
- The basic unit of independent scheduling and dispatching
- Ready to block execution 3 A basic state
- establish 、 The termination time is shorter than the process
- The thread switching time in the same process is shorter than that in the process , Small overhead
- Can be executed concurrently
- Share process resources （ Such as memory file ）
POSIX Threads (IEEE 1003.lc Thread standard )
- Thread package pthread
- pthread_create Create a new thread
- pthread_exit End calling thread
- pthread_join Wait for a specific thread to exit
- pthread_yield Release CPU To run another thread
- pthread_attr_init Create and initialize a thread's property structure
- pthread_attr_destroy Delete a thread's property structure
In user mode
- quick （ There's no need to get into the kernel , Context switch , Refresh memory high Cache ）
- It allows each process to have its own custom scheduling algorithm
- If the core blocks the process , All threads in the process will be blocked
- In the same process 2 Threads cannot run on at the same time 2 On processors
- In the kernel state
- Using kernel level threads , Then multiplexing user level threads with some or all kernel threads
Scheduler activation mechanism
- The goal is ： Simulate the function of kernel thread , Provides better performance and flexibility for thread packages that are usually implemented in user space .
Pop up threads
- Concept ： The arrival of a message causes the system to create a thread that processes the message
- advantage ： Quick creation . There are no registers to store 、 Stack
A critical region ： A fragment of a program that accesses shared memory .
- Mutually exclusive ： Prevent multiple processes from reading and writing shared data at the same time
A good concurrency scheme needs to satisfy ：
- 1) No two processes can be in the critical region at the same time .
- 2) Should not CPU The speed and the number of addresses to make any assumptions .
- 3) Processes running outside the critical area must not block other processes .
- 4) Do not allow the process to wait indefinitely for access to critical areas .
Busy waiting mutex
- Mask interrupt : Each process blocks all interrupts immediately after entering the critical region , Turn on interrupts before leaving , You can't avoid competition
- Lock variables : You can't avoid competition
- Strict rotation ： spinlocks (spin lock ) A violation of the 3）
- Peterson solution ： A software mutual exclusion algorithm without strict rotation .
- TSL Instructions ： Need hardware support (test and set lock The test well is locked )
- XCHG： Atomic exchange of contents between two positions
- shortcoming ： priority inversion problem
sleep （sleep） And wake up （wakeup） Interprocess communication primitives block when critical areas cannot be reached
- producer － consumer (producer-consumer) problem （ Bounded buffer ）
Achieve mutual exclusion or synchronization .
- down（P） and up(V) ( They are generalized sleep and wakeup) To the county of Yihuan down operation , Is to check whether the value is large 0. It's worth a thousand 0, Then subtract its value 1 ( That is to use a saved wake-up signal ） And continue ; If the value is 0, The process will sleep , And at this point down The operation is not over . Check value 、 Modify the variable batch value and possible sleep operations as a single 、 The indivisible atomic operation is completed .
- A simplified version of semaphore
- An advanced synchronization primitive , There is only one active process in the process at any time , The compiler is responsible for the mutex that enters the program , Usually a mutex or semaphore .
- Introduce conditional variables and 2 Operations （wait signal） To ensure that processes are blocked when they cannot run .
- Limit ： It's too low , Cannot be used outside of a few programming languages .（ Distributed systems, multiple CPU Each has its own private memory , These primitives are invalid ）
- 2 Primitive language .send: Call to send a message to a given target ,receive: Call from a given source （ Or any source , If the recipient doesn't mind ） Receive a message . If there is no message available , The receiver may be blocked , Until a message arrives , Or return immediately with an error code .
- （barrier） For process groups , Unless all the processes are in place to prepare the people One Stages , Otherwise, no process can go to the next stage .
- read - Copy - to update (Read-Copy-Update, RCU), Add or delete reference nodes without locking .
Scheduling time ：
- 1. After creating a new process , You need to decide whether to run the parent process or the child process .
- 2. When a process exits .
- 3. When a process is blocked in 1/0 And when it's blocked by a thousand other reasons , You must select another process to run .
- 4. In a I/O When the interruption occurs
Scheduling algorithm classification and objectives
- fair -- Give each process a fair CPU share
- Policy enforcement -- Ensure that the prescribed strategy is implemented
- Balance -- Keep all parts of the system busy
- Huff and puff -- The maximum number of jobs per hour
- Turnaround time -- Minimum time between submission and termination
- CPU utilization -- keep CPU Always busy
- response time -- Respond quickly to requests
- Equilibrium -- Meet user expectations
Real time systems
- Meet the deadline -- No loss of data
- Predictability -- Avoiding quality degradation in multimedia systems
Typical scheduling algorithm
- First come, first served
- The shortest assignment （ process 、 Threads ） first
- The shortest remaining time is preferred
- Time slice rotation scheduling algorithm
- Priority scheduling algorithm
- Multilevel feedback queue scheduling algorithm
- The shortest process takes precedence
- Guaranteed dispatch
- lottery scheduling
- Fair share scheduling
- Real time systems
- High response priority scheduling algorithm
Strategy and mechanism
- The scheduling mechanism is separated from the scheduling strategy , Yes, the scheduling algorithm is parameterized , It can be changed by the user .
- IPC problem
- The dining problem of philosophers
- The reader writer question
- address space ： Memory abstraction , A process used for memory addressing
- Base register ： Program start physical address
- Limit register ： The length of the program
- Switching technology ： Put a process into memory completely , Make the process run for a while , And then save it back to disk .
- Free memory management ： Dynamic allocation of memory is usually managed by bitmap and free area list
A page table
- Virtual address = Virtual page number （ High position ）+ Offset （ Status Part ）
Speed up paging
There are two main issues to consider ：
- 1) The mapping of virtual address to physical address must be very fast .
- 2) If the virtual address space is large , Page tables can also be large
- 1） Convert detection buffer （ Associative memory / Watch it ）： Set up a small hardware device for the computer , Mapping virtual addresses directly to physical addresses , Without having to visit the page table .
- 2） Software TLB management ： TLB As big as （ Such as 64 Table items ） Can reduce the failure rate
Page table for large memory
- Multi level page table
- Inverted sheet ： Each page box in actual memory corresponds to a table item , Instead of one table entry per virtual page .
Page replacement algorithm
- The optimal
- Not used recently
- Second chance
- The clock
- Recently at least use
Working set model ：
- Concept ： Paging systems try to track the working set of processes , To make sure that before you let the process run , Its working set is already in memory .
- Algorithm ： When a page break occurs , Eliminate a page that's not in the working set .
Working set clock
- You don't have to scan the entire page table to determine which pages are obsolete
- The required data structure is a circular table with page frames as elements
- Byte sequence ; Record the sequence ; Trees
- Hierarchical directory system
File system implementation
- Continuous distribution
- List allocation
- Using the list in memory for linked list allocation
Manage and optimize
Disk space management
- Historically speaking , The file system sets the size to 1~4KB Between , But now, with the disk passing 1TB, Or increase the size of the block to 64KB And it's better to accept wasted disk space
Record free blocks
- Disk block list Each piece needs to use 32 position
- Bitmap Each block is identified by only one binary bit 1TB disk It takes about 130 000 individual 1KB
- The maximum number of files and blocks assigned to each user by the system administrator , The operating system ensures that each user does not exceed their quota .
- 1) To recover from an unexpected disaster .
- 2) Recover from a bad operation .
- Block consistency check and file consistency check
- Read in advance
- Reduce arm movement
Input and output
IO Hardware principle
- Block device ： Store information in fixed size blocks , Each block has its own address （ disk ）
- Character device ： Send or receive a stream of characters in units of characters .（ The printer Network interface mouse ）
- Mechanical parts （ The device itself ）
Electronic components （ Device controller / Adapter ）
- Mission ： Convert a serial bit stream into a byte block , And carry out necessary error correction
There are several registers to use with CPU communicate , The operating system writes it to send | receive | Turn on | close
The way ：
- Memory mapping I/O
- Direct memory access （DMA）
- Data buffers that can be read and written
IO Software principle
The goal is
- Equipment independence ： You can access any I/0 Equipment without having to specify the device in advance
- Unified name ： The name of a file or device should be a simple string or integer , Independent of the device
- Error handling ： As close to the hardware level as possible
Program control I/O：
Print examples :
- 1. The software first assembles strings in a buffer in user space
- 2. The user process obtains the printer for writing by issuing a system call such as opening the printer
- 3. operating system （ Usually ） Copy the string buffer to an array in kernel space （ Such as p) in
- 4. The operating system checks to see if the printer is currently available （ polling 、 Busy waiting ）
- 5. Once the printer is available , The operating system copies the first character into the printer's data register （ Memory mapping 1/0）, Activate the printer
6. The printer's second register indicates its status
- When a character is written to a data register, the state becomes not ready
- Set a bit or put a value in the status register after processing the current character to indicate that it is ready
- 7. repeat 5 It's done until it's printed , Back to the user process
- shortcoming ： Busy waiting will be inefficient
Interrupt drive I/O
Print examples :
- When the printer has finished printing the character and is ready to receive the next character , It will generate an interrupt . This interrupt will stop the current process and save its state .
- shortcoming ： Interrupts occur on every character
DMA Of I/O
Print examples ：
- Give Way DMA The controller supplies the printer with one character at a time , Without disturbing CPU.
- DMA The controller is program controlled I/O, from DMA instead of CPU Do all the work
- Reduce the number of interrupts from printing each character once to printing each buffer once
IO Software level
The top-down 4 layer ：
- 1. User level IO Software
- 2. Device independent operating system software
- 3. Device driver
- 4. Interrupt handler
Disk arm scheduling algorithm
- 1. First come, first served
- 2. Elevator algorithm
- Processing in the controller : For every bad sector , Replace it with a spare sector
- Processing in the driver : Send out a recalibrate ( Recalibrate ） command , Move the disk arm as far out as possible , And reset the current cylinder inside the controller to 0
Advanced disk controller
- Quite powerful multicore ARM processor , There are enough resources to run easily Linux
- Write steadily
- Steady reading
- Crash recovery
2 Types ：
- Simple clock ： Each voltage cycle produces an interruption , The frequency is 50Hz or 60Hz
- 3 Component composition ： Crystal oscillator 、 Counters and memory registers ,1000MHz Even higher frequency
Programmable clock operation mode ：
- Completion mode ：one-shot mode
- Square wave mode ：square-wave mode
Clock software （ Clock driver ）
- 1) Maintenance day time .
- 2) Prevent processes from running out of time .
- 3) Yes CPU The usage of the account .
- 4) Handle user process requests alarm system call .
- 5) Provide monitoring timers for all parts of the system itself .
- 6) Complete the profile 、 Monitoring and statistical information collection .
- Preemptible resources : It can be preempted from the process that owns it without any side effects ( Such as Memory )
- Non preemptive resources ： Without causing the relevant calculation failure , It can't be snatched from the process that owns it （ Such as Blu ray disc recorder ） Deadlock is related to non preemptive resources
- Definition ： Each process in a process collection is waiting for events that can only be raised by other processes in the process collection
happen （ resources ） Four necessary conditions for deadlock ：
- 1. mutual exclusion
- 2. Conditions of possession and waiting
- 3. Conditions that cannot be preempted
- 4. Loop waiting condition
- Deadlock detection of one resource of each type ： Detecting whether a digraph has loops 、
- Deadlock detection of multiple resources of each type ： The comparison between the two （ Each process is initially unmarked . The algorithm starts by marking the process , Processes are marked to indicate that they can be executed , No deadlock . When the algorithm ends , Any unmarked process is a deadlock process .）
- Use preemption to recover
- Using rollback recovery
- Recover... By killing the process
- Resource trajectories
- Unsafe status and insecurity
- Banker's algorithm for a single resource
- Banker algorithm for multiple resources
- Destroy one of the four necessary conditions
- Two stage locking
- Communication deadlock
- Live lock
- 《 Modern operating system The Fourth Edition 》
- Basic course of computer entrance examination 《 operating system 》