operating system learning notes (ten) operating system knowledge points

Posted on Edited on In Waline:

Recently just read the entire operating system book, while there is a general impression, first sort out the knowledge points

Operating system

Computer overview

  • Operating System Features

    • Concurrency
    • Share
    • Virtual
    • Asynchronous

Operating System Objectives and Functions

- Computer system resource manager

	- Processor management
	- Storage management
	- Document management
	- Facility Management

Interface between user and hardware
- Expansion of computer resources

  • History of operating system development

    • Manual operation stage

    • Batch processing system

      • Single-channel batch processing
      • Multichannel batch processing

    • Time-sharing operating system

      • Simultaneity
      • Interactivity
      • Independence
      • Timeliness

    • Real-time operating system

    • Network operating system

    • Distributed computer systems

  • Operating system operating environment

    • Processor operation mode

      • Privileged instructions
      • Non-privileged instructions

    • Operating system kernel

      • Clock management

      • Interrupt mechanism

      • Primitive
        Data structure and processing of system control

        • Process management
        • Storage management
        • Facility Management

    • Interruptions and exceptions

      • Internal exceptions (not masking)

        • Malfunction (software)
        • Self-trapping (software)
        • Termination (hardware)

      • External interrupts (hardware)

        • Masked interrupt INTR
        • Non-maskable interrupt NMI

    • System call

      • Facility Management
      • Document management
      • Process control
      • Process communication

  • Operating system structure

    • Layering method

    • Modularization

    • Macro kernel

    • Microkernel

      • Divided into microkernel and server

      • Basic functions of microkernel

        • Process management
        • Low-level memory management
        • Interrupt and stuck processing

      • Microkernel Features

        • Scalability and flexibility
        • Reliability and safety
        • Portability
        • Distributed computing

    • Outer core

  • Operating system boot process

  • Virtual machine

    The first type of virtual machine
    The second type of virtual machine

Processes and threads

  • Process and thread

    • Concept and characteristics of the process

      • The concept of process

        • PCB is the only sign of process existence
          Process is the process entity running process, which is an independent unit of the system for quota and scheduling

      • Characteristics of the process

        • Dynamic
        • Concurrency
        • Independence
        • Asynchronous

    • Process state and transitions

      • Running state
      • Ready state
      • Blocked state (waiting state)
      • Create state
      • End state

    • Organization of the process

      • PCB

        • Included

          • Process description information
          • Process control and management information
          • List of quotas
          • Processor related information

        • Organization

          • Link method
          • Indexing method

      • Program segment

      • Data segment

    Control of the process

      - Creation of processes
  Termination of the process
  - Process blocking and wakeup

    • Process communication

      • Shared storage (requires the use of synchronous mutual exclusion tools such as PV)

        • Low-level method: sharing based on data structures
        • Advanced method: sharing based on storage area

      • Messaging

        • Direct communication method
        • Indirect means of communication

      • Pipeline communication

    • Thread and multithreaded models

      • Basic concepts of threads

        • The purpose of introducing threads

      • Comparison of threads and processes

        • Dispatch
        • Concurrency
        • Have the resources
        • Independence
        • System overhead
        • Support multiprocessor

      • Properties of threads

      • state transitions of threads

        • Execution status
        • Ready status
        • Blocked state

      • Thread organization and control

        • thread control block TCB

          • thread identifier
          • A set of registers
          • Thread running state
          • Priority
          • Thread-specific storage area
          • stack pointer

        • Creation of threads

        • Termination of thread

      • Thread implementation

        • User-level thread ULT, also known as coroutine
        • Kernel level threads KLT
        • Combination method

      • Multithreaded model

        • Many-to-one model: multiple user-level threads are mapped to one kernel-level thread
        • One to one model
        • Many-to-many model

  • Processor scheduling

    • The concept of scheduling

      • Basic concept: Select a process from the Ready Queue according to a certain algorithm and assign a processor to run it

      • Hierarchy of scheduling

        • Advanced Scheduling (Job Scheduling)
        • Intermediate scheduling (memory scheduling)
        • Low-level scheduling (process scheduling)

    • Dispatch target

      • CPU utilization
      • System throughput
      • Turnaround time
      • Wait time
      • Response time

    • Scheduling implementation

      • Scheduler

        • Queuing machine
        • Dispatcher
        • Context switcher

      • Scheduling timing, switching and process

        • Cannot be dispatched

          • During interrupt processing
          • The process is in the critical section of the operating system kernel
          • Atomic operations that require complete masking of interruptions

        • Should be dispatched

          • A scheduling condition occurred and the current process cannot proceed
          • End of interrupt processing or end of self-trapping processing

      • Process scheduling method

        • Non-Preemptive Scheduling
        • Preemptive Scheduling

      • Wandering process

      • Scheduling of two threads

        • User level thread scheduling
        • Kernel-level thread scheduling

    • Scheduling algorithm

      • FCFS
      • Short homework priority SJF
      • Priority scheduling algorithm
      • High response ratio priority
      • Time slice rotation scheduling
      • Multi-level queue scheduling
      • Multi-level feedback queue scheduling

    • Process switching

      • Context switch
      • Consumption of context switch
      • Context toggle and mode toggle

  • Synchronization and mutual exclusion

    • Basic concept

      • Critical resources
      • Sync
      • mutual exclusion

    • Basic approach to mutual exclusion of critical zones

      • Software implementation method

        • Single sign method
        • Double marking method
        • Double mark post inspection method
        • Peterson’s Algorithm

      • hardware implementation methods (low-level methods, meta-methods)

        • Interrupted shielding
        • hardware instruction method (TestAndSet/Swap)

    • mutual exclusion

      • Implemented by hardware mechanism
      • The main drawback is busy waiting

    • Signal volume

      • Shaped semaphore
      • Recording type semaphore
      • Synchronization with semaphore
      • Use semaphores for mutual exclusion of processes
      • Use semaphore to achieve precursor relationship

    • Pipe path

      • Definition

        • Composition

          • The name of the tube
          • Shared data structure description that is local to the inside of the tube
          • A set of processes that operate on the data structure
          • statements that set initial values for shared data local to the inside of the tube

      • Conditional variable

    • Classic sync issue

      • Producer-consumer issues
      • Reader-writer question
        The Philosopher’s Meal Problem
      • The smoker problem

  • Deadlock

    • Concept

      • Definition

      • Reason

        • System resource competition

        • Process advance sequence is illegal

        • Necessary conditions for deadlock generation

          • mutual exclusion
          • without deprivation
          • Request and hold conditions
          • Loop wait condition

      • Deadlock handling strategy

        • Deadlock Prevention

          • Breaking mutual exclusion conditions
          • Break the non-deprivation condition
          • Destroy requests and keep conditions
          • Break loop wait condition

        • Avoid deadlock

          • System security status
          • Banker algorithm

        • Deadlock detection and release

          • quota chart
          • Deadlock theorem
          • Deadlock lifted

Memory management

  • Memory management concepts

    • Main functions of memory management

      • Memory Space Allocation and Recovery
      • Address translation
        Expansion of Memory Space
      • Memory sharing
      • Storage protection

    • Basic principles of process operation

      • Program linking and loading

        • compile

        • Link

          • Static links
          • Dynamic linking when loading
          • Dynamic linking at runtime

        • Load in

          • Absolutely loaded
          • Relocatable loading (static relocation)
          • Enter when running dynamically

      Logical address and physical address

    • Memory image of the process

      Code snippet: The binary code of the program, read-only, can be shared by multiple processes
      Data segment: Objects processed during program runtime processing, including global variables and static variables.

      • Process Control Block (PCB)
      • Heap: used to store dynamically allocated variables, using the malloc function to dynamically allocate space to high addresses
      • Stack: used to implement function calls, growing from the largest address in user space to the lowest address

    • Memory protection

      • Set a pair of upper and lower limit registers in the CPU
      • Use relocation register and boundary address register

    • Memory sharing

    • Memory allocation and reclamation

      • Continuous distribution

        • Single continuous distribution

        • Fixed partition allocation

        • Dynamic partition allocation

          • First adaptation algorithm
          • Proximity adaptation algorithm
          • Optimal adaptation algorithm
          • Worst adaptation algorithm

      • Discrete distribution

        • paginated storage

          • Concept

            • Page and page size
            • Address structure
            • Page table

          • Basic address translation mechanism

          • Address conversion mechanism with fast meter

          • Two-level page table

        • Segmented storage

          • Sections
          • Segment table
          • Address translation mechanism
          • Sharing and protection of segments

        • Segmented page type

  • Virtual memory management

    • Basic concept

      • Characteristics of traditional storage management methods

        • One time
        • Residual

      • Principle of locality

      • Definition and characteristics of virtual storage

        • Definition

        • Features

          • Multiple sex
          • Conversion
          • Virtuality

      • Implementation of virtual memory

        • Request paging storage management
        • Request segmented storage management
        • Request segment paged storage management

Document management

  • Documents

    The concept of documents

      - Composition of documents

  	- Storage space
  	- Classification and indexing information
  	- Information on access rights

  - Structure of documents

  	- Data items
  	- Record
  	- Documents

    • File control blocks and index nodes

      • Properties of the file

        • Name
        • Types
        • Creator
        • Owner
        • Location
        • Size
        • Protection
        • Creation time

      • File Control Block (FCB)

      • Indexes (i-nodes)

        • disk index node
        • Memory Index Node

    • Basic operation of files

      • Create files
      • Writing documents
      • Read the file
      • Relocate files
      • Delete files
      • Truncate files

    • File opening and closing

      • Open the file table

        • process open file table
        • System Open File Table

      • Open the index of the file table (file descriptor/file handle)

        • File pointer
        • File open count
        • File disk location
        • Access permissions

    • File protection

      • Password protection
      • Encryption protection
      • Access control

    Logical structure of the document

      - Unstructured files (streaming files)
  - Structured files (recorded files)

  	- Sequential file

  		- Storage method

  			- Sequential storage
  			- Chain storage

  		- Structure

  			- string structure
  			- Sequential structure

  	- Index file

  		- Fixed-length record file, the address of the record can be directly calculated based on the length and index number
  		- Variable-length record file: Establish an index table containing record pointers, lengths, and sort by keywords. The index table itself is also a fixed-length record file

  	- Index sequential files

  		- Divide all records in the sequential file into several groups and establish an index table for the sequential file

  	- Hash file

    Physical structure of the document

      - File allocation method: management of non-free blocks

  	- Continuous distribution
  	- Link distribution

  		- Implicit link: only suitable for sequential access
  		- Explicit link: FAT

  	- Index allocation

  		- Link scheme
  		- Multi-level index
  		- Mixed Index

  	- Mixed Index Allocation

  - File storage space management: management of free disk blocks

  • Directory

    • Directory structure

      • Single-level directory structure
      • Two-level directory structure
      • Tree directory structure
      • acyclic graph directory structure

    • Directory Operations

      • Search
      • Create files
      • Delete files
      • Create a directory
      • Delete Directory
      • Move Directory
      • Show Directory
      • Modify Directory

    • Directory implementation

      • Linear list
      • Hash table

    • File sharing

      • Hard link: sharing method based on index nodes
      • Soft link: Use symbol chain to achieve file sharing

  • File system

    • File system structure hierarchy

      • I/O control
      • elementary file system
      • File organization module
        Logical file system

    • File system layout

      Structure of the file system on disk

        - Master Boot Record (MBR)
  - boot block
  - super block
  Free blocks in the file system

      • Structure of the file system in memory

        • Installation table in memory
        • Cache of directory structure in memory
        • Open file table for the entire system
        • Open file table for each process

    • External free space management

      • Idle table method

        • First adaptation algorithm
        • Proximity adaptation algorithm
        • Optimal adaptation algorithm
        • Worst adaptation algorithm

      • Idle linked list method

        • Free disk blockchain
        • Free extent chain

      • Potential mapping

      • Group linking method

        • Allocation of disk blocks
        • Recycling of disks

    Virtual File System (VFS)

I/O management

  • Overview

    • I/O devices

      • Classification

        • By unit of information exchange

          • Block device
          • Character devices

        • by transmission rate

          • Low speed equipment
          • Medium speed equipment
          • High speed equipment

      • I/O interface (device controller)

        • Composition

          • Interface between device controller and CPU
          • Interface between device controller and device
          • I/O logic

        • Main functions

          • Accept and recognize commands sent by the CPU
          • Data exchange
          • Identification and reporting equipment
          • Address recognition
          • Data buffering
          • Error control

      • I/O ports (registers in the interface that can be accessed directly by the CPU)

        • Classification

          • Data register: implement data buffering between CPU and peripherals
          • Status Register: Get execution results and device status information
          • Control registers: written by the CPU to start a command or change the device mode

        • Method of communication

          • Independent addressing
          • Unified addressing (memory mapped I/O)

    • Control mode

      • Program direct control
      • Interrupt drive mode
      • DMA
      • Channel control

    • I/O software hierarchy

      • User layer I/O software
      • Device independent software
      • Device drivers
      • Interrupt handler
      • The hardware

    • Application I/O interface (the interface between the I/O system and the higher layer)

      • Character device interface
      • Block device interface
      • Network device interface
      • Blocking/non-blocking I/O

  • Device independent software

    • Device-independent software, including software that performs all device-owned operations

    • Cache and buffer

      • disk cache (logically belonging to the disk, physically a disk block residing in memory)

        • Form

          • Open up a separate space in memory as a cache with a fixed size
            Use unused space as a cache pool for paging requests and disk I/O sharing

      • Buffer zone

        • Purpose

          • Mitigate speed mismatch between CPU and I/O devices
          • Reduce CPU interrupt frequency and relax CPU interrupt response time limit
          • Resolved the issue of base data unit size mismatch
            Improved parallelism between CPU and I/O devices

        • Method

          • hardware buffer
          • Buffer (in memory)

        • Buffer technology

          • Single buffer, data processing time max (C, T) + M
          • Double buffering, data processing time max (C + M, T)
          • Cyclic buffering
          • Buffer pool

    • Equipment distribution and recycling

      • Classified according to usage

        • Exclusive use of equipment
        • Time-sharing shared use of equipment
        • Virtual Device (SPOOLing)

      • Data structure for device allocation

        • Device control table DCT
        • Control its control table COCT
        • Channel control table CHCT
        • System Device Table SDT

      • Device allocation strategy

        • Principle: not only to give full play to the efficiency of equipment use, but also to avoid deadlock

        • Way

          • Static allocation: Once assigned, it is always occupied by the job
          • Dynamic allocation

        • algorithm

          • Static distribution

          • Dynamic allocation

            • Request first, assign first
            • The highest priority is preferred

      • Security (preventing deadlock)

        • Safe allocation method: the process enters a blocking state when it issues I/O requests
        • Unsafe allocation method: It can continue to run after issuing an I/O request, and issue a second or third I/O request

      Logical device name to physical device name mapping

        - There is only one LUT table for the entire system
  - Each user logs in, the system establishes a process for it, and establishes a LUT into the PCB of the process

    • SPOOLing technology (spooling technology) alleviates the contradiction between the high speed of CPU and the low speed of I/O devices, and transforms exclusive devices into shared devices

      • Composition

        • Input and output wells
        • Input buffer and output buffer
        • Input process and output process

      • Features

        Increased I/O speed

        • Convert exclusive devices into shared devices
        • Implemented virtual device function

    • Device driver interface

  • disks and solid state drives

    • disk

      • Track
      • Cylindrical
      • Plate
      • sector (disk block)

    • disk management

      • disk initialization
      • Zoning
      • Guide block
      • Bad block

    • disk scheduling algorithm

      • Read and write time

        • seek time
        • Rotation delay
        • Transmission time

      • algorithm

        • First-Come First-Service
        • Shortest search time is preferred
        • Scan algorithm (elevator algorithm)
        • Cycle scan

    • Solid state drives

      • Features

      • Wear leveling

        • Dynamic wear equalization
        • Static wear leveling