编程知识 cdmana.com

SYS.BASE -Operating system notes (Theory)

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 :

CPU:

  • 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 .)
  • Pattern :

    • 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

Memory

  • 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

  • I/0 equipment = Device controller + The device itself
  • Device controller

    • 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

Bus

  • 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 .
    • CPU

      • 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
    • 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
  • SCSI

    • 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 )
  • share

    • Mutually exclusive sharing ( Like audio devices The printer )
    • Simultaneous access ( Disk files )
  • fictitious

    • 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
  • asynchrony

    -  The criterion : No matter how fast or slow , The result is the same 
    

Process threads

process

  • Model

    • 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 
```
  • establish

    • 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 .
  • End

    • 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
  • hierarchy

    • 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

      • Processor status

        • General registers
        • Instruction counter
        • psw
      • Scheduling information

        • Process status
        • priority
        • Information needed for scheduling ( The process has been waiting CPU Time , The total amount of time a process has been executed )
      • Control information

        • 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

Threads

  • Concept

    • 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 )
  • Model

    • TCB
  • 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
  • Realization

    • In user mode

      • advantage

        • 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
      • shortcoming :

        • 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
    • Hybrid implementation

      • 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

Interprocess communication

  • 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 )
  • Semaphore

    • 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 .
  • The mutex

    • A simplified version of semaphore
  • Tube side

    • 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 )
  • The messaging

    • 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

    • (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 .
  • Avoid locks

    • read - Copy - to update (Read-Copy-Update, RCU), Add or delete reference nodes without locking .

Dispatch

  • 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

    • All systems

      • 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
    • Batch system

      • Huff and puff -- The maximum number of jobs per hour
      • Turnaround time -- Minimum time between submission and termination
      • CPU utilization -- keep CPU Always busy
    • Interactive system

      • 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

    • Batch system

      • First come, first served
      • The shortest assignment ( process 、 Threads ) first
      • The shortest remaining time is preferred
    • Interactive system

      • 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

memory management

  • address space

    • 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
      • programme :

        • 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
    • fifo
    • 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

file

  • file

    • name
    • structure

      • Byte sequence ; Record the sequence ; Trees
  • Catalog

    • 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

      • Block size

        • 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
      • Disk quota

        • 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 .
    • Backup

      • 1) To recover from an unexpected disaster .
      • 2) Recover from a bad operation .
    • Uniformity

      • Block consistency check and file consistency check
    • performance

      • Cache
      • Read in advance
      • Reduce arm movement
    • Defragmentation

Input and output

IO Hardware principle

  • IO equipment

    • classification :

      • 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 )
    • form :

      • 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
        • form :

          • 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
  • Realization

    • 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

  • Disk arm scheduling algorithm

    • 1. First come, first served
    • 2. Elevator algorithm
  • Error handling

    • 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
  • Stable memory

    • Write steadily
    • Steady reading
    • Crash recovery

The clock

  • Clock hardware

    • 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 .

Deadlock

  • resources

    • 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

    • 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 .)
  • Deadlock recovery

    • Use preemption to recover
    • Using rollback recovery
    • Recover... By killing the process
  • Deadlock avoidance

    • Resource trajectories
    • Unsafe status and insecurity
    • Banker's algorithm for a single resource
    • Banker algorithm for multiple resources
  • Deadlock prevention

    • Destroy one of the four necessary conditions
  • Other questions

    • Two stage locking
    • Communication deadlock
    • Live lock
    • hunger

Reference material

版权声明
本文为[season]所创,转载请带上原文链接,感谢

Scroll to Top