Operating System Principles

directory

• Operating System Principles
• One level
• • The secondary directory
  • • Three directories
  • The basic concept
  • • Computer hardware system
    • • composition
      • • Central processing unit
        • • Processor and register
        • Main memory
        • Peripheral equipment
        • • Device type
          • Equipment control mode
        • The bus
        • • Introduction to the
          • Bus type
      • Von Neumann structure
      • • structure
      • The organizational level of storage
    • Computer software system
    • • Different layers of software development
      • The execution of a computer program
    • The operating system
    • • Components of an operating system
      • type
      • Resource management
      • • Mask the low-level details of resource usage
        • Resource Sharing Mode
        • Resource Allocation Policy
      • System control
      • • Realization of multi – channel program system
        • The control mode
        • • Offline operation control mode
          • Online job control mode
        • Command interpreter
        • • The process
      • The system interface
      • • implementation
      • The system structure
      • • The structure design
        • The kernel
  • Processor management
  • • Processor and register
    • • Processor unit
      • User program visibility register
      • Control and status registers
      • • The program status word PSW
    • Instruction and processor
    • • Machine instructions
      • • Instruction execution process
        • Instruction execution cycle and instruction pipeline
        • Privileged and non-privileged directives
        • Processor mode
        • • Processor mode switch
    • interrupt
    • • concept
      • Interrupts, exceptions, and system exceptions
      • The interrupt source
      • • Processor hardware failure interrupt event
        • A procedural interrupt event
        • Voluntary interruption events
        • I/O interruption event
        • External interrupt event
      • The interrupt system
      • • Interrupt response processing and instruction execution cycles
        • Interrupt device
        • • Interrupt controller
          • Traps and system traps
        • Interrupt response procedure
        • Interrupt handler
        • • Interrupt handling procedure
        • Multiple interrupt response and handling
        • • Interrupt mask
          • Interrupt priority
          • Nested handling of interrupts
    • process
    • • Process status
      • • Process a hang
        • • Process suspension selection and recovery
      • Data description
      • • Process control block
        • • Identity information
          • The site information
          • Control information
        • Process image
        • Process context
      • Process management
      • • Queue management module
        • Control and management
        • Primitives and process control primitives
        • Process switching
        • • The mode switch
          • Process switch working process
          • The time when a process switch occurs
      • Multithreading technology
      • • Traditional processes are single-threaded structured processes
        • Multithreaded structured process
        • advantages
        • Implementation of multithreading
        • • KLT, kernel-level Threads
          • ULT, User-level Threads
          • Hybrid multithreading
    • Processor scheduling
    • • Scheduling hierarchy
      • • Advanced scheduling
        • Intermediate scheduling
        • Low-level scheduling
      • Scheduling algorithm
      • • Principles for selecting processor scheduling algorithms
        • Priority number scheduling algorithm
        • • classification
          • The number of priorities related to the time of entry to the system
        • Time slice rotation scheduling algorithm
        • Hierarchical scheduling algorithm
        • • The basic idea
        • Lottery scheduling algorithm
        • • The basic idea
  • Storage management
  • • Main mode
    • • Logical addresses
      • • Block programming
      • Physical address
      • • Reuse of main memory
        • • Reuse by partition
          • Reuse by page shelf
      • Basic mode of storage management
    • function
    • • Address translation
      • • Static relocation
        • Dynamic heavy position
        • Allocation and disallocation
        • • distribution
          • Go to the match
      • The Shared space
      • • Storage protection
      • Expansion of space
    • Virtual memory
    • • Put forward
      • The basic idea
      • • Implementation approach
    • Hardware support for storage management
    • • Storage Objects involved in storage management
      • • Cache Memory
        • • Composition of cache storage
          • Organization of cache storage
    • Single-partition storage management
    • • Single-user continuous storage management
      • Fixed partition storage management
      • • Main memory allocation
        • Address translation
      • Variable partition storage management
      • • Memory allocation
        • Dynamic relocation
        • Fraction of memory
        • • Mobile technology (program float technology)
    • Page storage management
    • • Address in page storage management
      • • Logical addresses
        • Physical address
        • Address translation
        • • The price
          • Fast table
          • Address translation process
          • A process schedule in a multiprogram environment
          • Address translation in multiprogram environment
      • Memory allocation/de-allocation
      • Pages of Shared
      • Page virtual storage management
      • • Page table of virtual storage management
        • Implementation of pager virtual storage management
        • paging
        • • Page – missing interruption rate
          • OPT page scheduling algorithm
          • FIFO page scheduling algorithm
          • LRU page scheduling algorithm has not been used for the longest time
          • Least commonly used LFU page scheduling algorithm
          • CLOCK page scheduling algorithm
      • The inverted page table
      • • Why reverse page tables
        • How to implement reverse page table
        • • Reverse the page entry of the page table
          • Hash table of reverse page table
          • Address translation process
    • Segment storage management
    • • Block programming
      • The basic idea of segmental storage management
      • • Period of Shared
    • Segment-page storage management
    • • Address translation for segment-page storage management
  • Equipment management
  • • The basic concept
    • • I/O devices
      • • Divided by device management
        • Equipment management objectives
        • Device management functions
        • Layers of device management
    • I/O control mode
    • • Device manager
      • Polling mode
      • The interrupt way
      • Direct memory access (DMA)
      • • Cycle stealing in DMA mode
      • A comparison of the three ways
      • • The device controller adopts polling mode
        • A device controller that uses interrupt mode
        • Direct memory control via DMA
      • I/O channels
      • • process
      • I/O channels and DMA
      • Single bus
      • Traditional three-level bus
      • Multi – stage bus of north – south bridge is adopted
      • A multistage bus using I/O channels
    • I/O software
    • • Implementation level
      • • Design goals
        • Design ideas
        • The main consideration
      • I/O software implementation
      • • I/O interrupt handler
        • • function
        • Device driver
        • • function
          • level
        • Device-independent I/O software
        • • function
        • User space I/O software
    • The I/O buffers
    • • purpose
      • The buffer
      • operation
      • A single buffer
      • double-buffering
      • Circular buffer
    • Equipment independence
    • • advantages
    • Device allocation method
    • • allocation
      • Device allocated data structure
      • • Device class table
        • Equipment list
    • disk
    • • The physical structure
      • • Read and write data
        • process
      • Driven scheduling
      • • Move the arm scheduling
        • • First in first out
          • Minimum search time is preferred
          • One-way scan
          • Two-way scanning
          • The elevator dispatching
        • Rotation scheduling
        • • Cycle sorting
          • To optimize the distribution of
    • Virtual device
    • • A classic SPOOLing system
      • • composition
        • role
  • File management
  • • The file system
    • • function
      • • User-oriented functions of the file system
    • File storage
    • File structure
    • • Logical structure of the file
      • • Streaming file
        • Recording document
      • The physical structure of the file
      • • Sequential file
        • Connection file
        • The file directly
        • Index file
        • • access
          • The characteristics of
    • File directory
    • • File directory structure
      • • Primary directory structure
        • Secondary directory mechanism
        • Tree directory structure
      • Directory Management
      • • To find the
        • • File search
          • Directory entry lookup
        • File directory processing
        • • Active file list
    • File security and protection
    • • File sharing
      • • Concurrency control
        • Security measures
      • File protection
      • • Dynamic multiple copy technology
        • Dump, backup, and restore
      • The file is confidential
      • • File access control matrix
        • Access control table
        • • File protection based on Access control matrix/table
        • File attributes
    • File access
    • • Sequential access
      • Direct access
      • Indexed access
    • Use of files
    • • Set up files
      • Cancel the file
      • Open the file
      • Close the file
      • Read/write files
      • • Locate the file
    • Use of auxiliary storage space
    • • allocation
      • Management of free blocks
      • • Shown in figure
        • Free block group join method
    • The implementation hierarchy of the file system
  • Concurrent programming
  • • concept
    • • Sequential programming
      • • Characteristics of the
      • Concurrent execution of processes
      • • Concurrent programming
        • • features
      • Constraints between concurrent processes
      • • Time-related errors
        • Process mutual exclusion synchronizes with process
    • A critical region
    • • Description of critical region
      • Three requirements for critical area management
      • Nested use of critical sections
      • Critical area management
      • • Test and set up instructions
        • Exchange instructions
        • interrupt
    • PV operation
    • • Recording semaphore
      • PV operation primitive
      • • P Operation primitives (applying for resources)
        • V Operation primitives (free resources)
      • PV operation to solve the process mutually exclusive framework
      • PV operation solves process synchronization
      • • 1 Producer 1 Consumer 1 buffer problem
        • 1 Producer 1 consumer N Buffer problem
        • N producer n consumer n buffer
        • Apples and oranges! [image-20200501174030588](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/8aad034a22e94808936e8f8db38be25b~tplv-k3u1fb pfcp-zoom-1.image)
    • Process of communication
    • • Direct process communication
      • Process indirect communication
      • • Mailbox for indirect communication
        • Process of sending letter primitives
        • • If the specified mailbox is not full
          • If the specified mailbox is full
        • Process of receiving letter primitives
        • • If there are letters in the specified mailbox
          • If there is no letter in the specified mailbox
      • Advanced process communication mechanism
      • • Stream-based process communication
        • Rpc-based process communication
    • A deadlock
    • • Deadlock prevention
      • • Static allocation (preallocation)
        • Level distribution
      • Deadlock avoidance
      • • Banker’s algorithm
      • Deadlock detection
      • • detection
        • To deal with

One level

The secondary directory

Three directories

The basic concept

Computer hardware system

composition

Central processing unit

The CENTRAL processing Unit (CPU) is the computing Core and Control Unit of a computer.

• Arithmetic logic unit: one or more arithmetic units
• Register components: including general purpose registers, control and status registers, and Cache
• Control unit: an internal bus for data, control, and state of connection between components; The part responsible for decoding instructions, sending out control signals for the operation to be performed for each instruction, and realizing data transmission, etc

Processor and register

Main memory

DRAM

Peripheral equipment

Device type

• Input devices

  Keyboard mouse

• Output devices

  display

• The storage device

  1. Hard disks such as solid state disks, mechanical disks, and USB flash drives

  2. drive

     …

• Network communication equipment

  The network card etc.

Equipment control mode

The bus

Introduction to the

Bus type

Internal bus: used to connect the CPU chip internal components

System bus: used to connect CPU, memory and various I/O modules and other major components

The system bus also has tiers, as shown in the figure below

Communication bus: Used for communication between computer systems

Von Neumann structure

structure

The organizational level of storage

Computer software system

Different layers of software development

The execution of a computer program

The operating system

Components of an operating system

• Process scheduling subsystem
• Process communication subsystem
• Memory management subsystem
• Equipment management subsystem
• File management subsystem
• Network communication subsystem
• Job control subsystem

type

Resource management

Computer resources contain

• Hardware resources Processor, memory, peripherals
• Information resources data, procedures

Mask the low-level details of resource usage

Resource Sharing Mode

• Exclusive mode of use
• Concurrent usage mode

Resource Allocation Policy

System control

The mismatch between CPU speed and I/O speed is striking. Only by allowing multiple programs to enter the memory at the same time to compete for the CPU, can the CPU and peripheral devices fully parallel, thus improving the efficiency of the computer system

Realization of multi – channel program system

The control mode

Offline operation control mode

Online job control mode

1. Computer: Provide terminal (keyboard/monitor)
2. User: Log in to the system
3. OS: Provides command interpreters
4. User: Input commands online to directly control the execution of job steps

Example: the interactive control mode of time-sharing OS

Command interpreter

The process

1. OS starts command interpreter, outputs command prompt, waits (keyboard interrupt/mouse click/multi-channel recognition)
2. Request an interrupt whenever the user enters a command (a command buffer exists temporarily) and presses Enter to wrap
3. When the CPU responds, it gives control to the command interpreter, reads the contents of the command buffer, analyzes the command, accepts the parameters, and executes the processing code
4. After the foreground command is executed, it outputs the command prompt again and waits for the next command
5. After background command processing starts, the next command can be received

Foreground commands: Enter commands only after they are executed

Background commands: After a command is started, the next command can be started without affecting the execution of the command in the background

The system interface

implementation

• Write a system call handler

  The operating system provides these system call handlers ahead of time

• Design a system call entry address table, each entry address points to a system call handler, and contains the number of system call parameters

  Through software initiation, the system looks up the system call entry address table and finds the corresponding system call handler

• Trapped processing requires a field preserve to preserve the processor scene when a system call occurs

  The current state of the processor is stored before the system call is called so that the processor scene can be restored after the call

The system structure

The structure design

OS component kernel, process, thread, pipe, etc

Kernel design is the most complex part of OS design

Modular design concept, hierarchy, virtualization

The kernel

Processor management

Processor and register

Processor unit

Instruction decoder ID: responsible for the execution of specific interpretation instructions

Instruction register IR: Is responsible for the storage of instructions

Program counter PC: points to the address where the instruction is to be executed at the next hop

After the arithmetic logic unit completes the calculation, it summarizes the contents into the Flag register

MAR, MDR: Used to access memory data

User program visibility register

Control and status registers

Used to control the operation of the processor; Used primarily by privileged operating system programs to control program execution

• Program counter PC: Stores the address of the instruction to be fetched
• Instruction register IR: Stores recently used instructions
• CC: a bit set by the CPU for the result of an instruction operation, indicating positive/negative/zero/overflow, etc
• Flag bit: interrupt bit, interrupt permit bit, interrupt mask bit, processor mode bit, memory protection bit,… , etc.

The program status word PSW

Instruction and processor

Machine instructions

Instruction execution process

The CPU takes out the instruction according to the PC (program counter), puts it into IR, decodes the instruction, and then issues various control commands to execute the microoperation series, thus completing the execution of an instruction

One instruction is executed as follows

1. Fetch: Fetch instructions from memory or cache to IR according to PC
2. Decode: Interprets instructions in IR to determine their execution behavior
3. Execution: connect to CPU component, perform operation, produce result and write back, at the same time set operation conclusion flag in CC; Jump instructions operate on PC, other instructions increment THE VALUE of PC

Instruction execution cycle and instruction pipeline

Privileged and non-privileged directives

Not all machine instructions can be used by user programs. Special instructions related to the core resources of the computer are protected. Instructions related to the core resources can only be used by operating system programs

Such as: start I/O instructions, PC instructions, and so on

Suppose program A wants to output 123, while program B wants to output 456. If the I/O control is handed over to the computer, the output is likely to be 142536, which does not meet the requirements

So instructions are classified as privileged and non-privileged

• Privileged directives: Directives that can only be used by the operating system kernel
• Nonprivileged instruction: an instruction that can be used by all programs

Processor mode

Processor mode switch

Including “user mode → kernel mode” and “kernel mode → user mode” conversion

Events such as interrupts, exceptions, or system exceptions cause user programs to switch to the OS kernel, triggering user mode → kernel mode

• The program requests operating system services
• An exception occurred while the program was running
• Interrupts occur and respond to program execution

After the OS kernel processing is complete, the call interrupt return instruction (such as Intel IRET) is triggered: kernel mode → user mode

interrupt

concept

Interrupt refers to the process of temporarily suspending the running of the current program on the CPU when an event needs to be dealt with urgently in the process of program execution, switching to the execution of the corresponding event handler, and then returning to the place where the original program was interrupted or scheduling the execution of other programs after the processing is completed

Operating systems are “interrupt-driven”; In other words, interrupts are the only way to activate the operating system

For example, when a user program is running, it can only be switched by interrupting

Interrupt has broad sense and narrow sense points, the interrupt refers to the broad sense interrupt

Interrupts, exceptions, and system exceptions

The interrupt source

Processor hardware failure interrupt event

A procedural interrupt event

Caused by the processor executing machine instructions

• Arithmetic exceptions, such as zero divisor and operand overflow, are handled simply and reported to the user. It can also be handled by user – written intermittent procedures
• Illegal instruction, user mode privilege instruction, address out of bounds, and illegal access instruction Exception: The process is terminated
• Termination process instruction: Terminates a process
• If the virtual address is abnormal, execute the command again after adjusting the memory

Voluntary interruption events

I/O interruption event

Interrupt event from peripherals reporting I/O status

• I/O completed: Adjusts the process status and releases the waiting process
• I/O error: Wait for human intervention
• I/O exception: Wait for manual intervention

External interrupt event

The interrupt system

Interrupt system is the system which responds and deals with interrupt in computer system, including hardware subsystem and software subsystem

The interrupt response is done by the hardware subsystem

Interrupt reason software subsystem complete

Interrupt response processing and instruction execution cycles

Interrupt device

A hardware device in a computer system that detects and responds to interrupts/anomalies is called an interrupt device. Due to the diversity of interrupt sources, there are various interrupt devices implemented by hardware to handle different types of interrupts. These interrupt devices vary from computer to computer, and usually include:

• Out-of-processor interrupts: Detected and responded to by the interrupt controller
• Exceptions within the processor: detected and responded to by the control logic and implementation circuit of the instruction, the corresponding mechanism is called trap
• System exception requesting OS services: triggered directly when processor execution falls into instruction, the corresponding mechanism is called system trap

Interrupt controller

Traps and system traps

Traps and system traps: The logic of instructions and part of the implementation circuit

• If an exception occurs during command execution, the system turns to the exception handler of the operating system based on the exception
• After the virtual address exception occurs, the instruction needs to be re-executed, often bypading the trap of setting the page exception handler independently
• After executing the trap instruction, the trap processing is passed, triggering the system trap and activating the system call handler

This process is synchronous, an interruption that occurs during the execution of an instruction

Interrupt response procedure

Interrupt handler

An operating system control program for handling interrupt events. Its main task is to handle the interrupt events and restore normal operations

Interrupt handling procedure

Multiple interrupt response and handling

Interrupt mask

Interrupt priority

When the computer detects multiple interrupts at the same time, the interrupt device responds to the interrupt in the order of priority

One possible processing order:

1. Processor hardware failure interrupt event
2. Voluntary interruption events
3. A procedural interrupt event
4. External interrupt events such as clock interruption
5. Input/output interrupt event
6. Restart and shutdown interruption events

Different types of operating systems have different interrupt priorities

Nested handling of interrupts

process

Process is a program with a certain independent function about a data set running activities, but also an independent unit of the operating system for resource allocation and scheduling

A process consists of five physical parts

1. The data structure in which the OS manages running programs P
2. Memory code C for running a program
3. Memory data D of a running program
4. General register information R (for running a program)
5. (OS control program execution) program status word information PSW

Different programs

• Run on different data sets: constitute two unrelated processes
• Running on the same data set: Constitute two communicative processes that share data

The same procedure

• Running on different data sets: Independent processes that make up two shared code

Process status

Process a hang

The OS cannot predict the number of processes and resource requirements, and the computer system may run out of resources

Insufficient running resources are manifested as low performance and deadlock

Solution: Deprive some processes of memory and other resources, switch to the SWAP zone managed by the OS, do not participate in the process scheduling, wait until the appropriate time to transfer memory, restore resources, participate in the running, this is suspended process

The pending state is essentially different from the pending state. The pending state occupies the applied resources and is waiting, while the pending state has no resources

Process suspension selection and recovery

Data description

Process control block

Identity information

Stores information that uniquely identifies the process

• System assigned id
• Id of a process group assigned by the system
• User-defined process name
• User-defined process group name

The site information

Control information

Stores information related to management and scheduling processes

1. Scheduling information: status, waiting event/cause, and priority
2. Process composition information: code/data address, external memory image address
3. Queue Pointers: process queue Pointers, parent and child process Pointers
4. Communication related information: message queue, semaphore, lock
5. Process privilege information: such as memory access permission, processor privilege
6. Processor usage information: occupied processor, time slice, processor usage time/total time executed, billing information
7. Resource list information: such as occupied resources, used resources

Process image

Process context

Process execution requires environment support, including the execution information in the CPU field and Cache, process physical entities in the OS, and the environment that supports process running. Process context includes the following:

• User-level context: user block/user data area/user stack/user shared memory
• Register context: PSW/ stack pointer/universal register
• System-level context: PCB/ memory area table/core stack

Process context describes the execution of a process

Process management

Queue management module

The operating system establishes multiple process queues, including ready queue and wait queue, which are organized into first-in, first-out queue and priority queue. A process in a queue can connect with a single/double guide or index through a queue guide in the PCB. Process and resource scheduling revolves around process queues.

Control and management

Primitives and process control primitives

The process control process involves the modification of OS core data structures (process schedule /PCB pool/queue/resource table). To prevent time-related errors, primitives should be used

A primitive is a program composed of several instructions to complete a specific function, and its execution is indivisible. Execution of primitives can be achieved by a close interrupt

The primitives used for process control are called process control primitives. Another common class of primitives are process communication primitives

Process switching

The mode switch

Mode switching, also known as processor state switching, includes:

1. User mode to kernel mode is triggered by an interrupt/exception/system call that interrupts user process execution

   1. Switch from processor mode to kernel mode
   2. Saves the PC/PSW value of the current process to the core stack
   3. Turn to interrupt/exception/system call handlers

2. Kernel to user mode triggered when the OS executes an interrupt return instruction to return control to the user process

   1. Eject the PSW/PC value from the core stack of the pending process
   2. Switch from processor mode to user mode

Process switch working process

The time when a process switch occurs

A process switch must occur during an interrupt/exception/system call.

• Blocked system calls and abnormal virtual addresses cause the interrupted process to enter the wait state
• A process with a higher priority is found after the time slice or I/O is interrupted, and the interrupted process enters the ready state
• Terminates an exception that cannot continue with a system call, causing the interrupted process to enter the terminated state

Some interrupts/exceptions do not cause a process state transition, do not cause a process switch, and just hand back control to the interrupted process after processing is complete.

1. (Interrupt/exception triggered) Forward mode switch pressing into PSW/PC
2. Saves site information about interrupted processes
3. Handle interrupts/exceptions
4. Restores site information about the interrupted process
5. (Interrupt return instruction triggered) Reverse mode conversion pops PSW/PC

Multithreading technology

Traditional processes are single-threaded structured processes

Problems with concurrent programming for single-threaded processes:

• Process switching costs a lot
• Process communication costs a lot
• Limits the granularity of process concurrency
• It reduces the efficiency of parallel computing

The operating system restricts the communication between processes from the perspective of security, and the cost of scheduling between processes is higher

Multithreaded structured process

advantages

• Fast thread switching
• Reduce administrative overhead
• Communication is easy to implement
• Increased parallelism
• Save memory space

Implementation of multithreading

KLT, kernel-level Threads

All the work of thread management is done by the OS kernel

The characteristics of

• If a thread in a process is blocked, the kernel can schedule other threads in the same process to occupy the processor
• In a multiprocessor environment, the kernel can schedule concurrent execution of multiple threads in the same process
• The kernel itself can also be implemented by multi-threading technology, which can improve the execution speed and efficiency of the operating system
• Application thread runs in user mode, and thread scheduling and management are implemented in the kernel. In the same process, mode switching is required when the control is transferred from one thread to another, and the system overhead is large

ULT, User-level Threads

Hybrid multithreading

Multiple ULT for a single application can be mapped to several KLTS, which can be adjusted to achieve better parallelism

Thread state under the thread hybrid policy

• Active ULT represents the three states bound to KLT
• The active ULT runtime activates user scheduling
• A non-blocking system call can use Jacketing to initiate user scheduling and adjust active ULT

Processor scheduling

Scheduling hierarchy

Advanced scheduling

Intermediate scheduling

Also known as balanced load scheduling, determines the set of processes available in main memory

• Intermediate scheduling was introduced to improve memory utilization and job throughput
• Intermediate scheduling determines which processes are allowed to reside in main memory to compete for processors and other resources, serving as short-term adjustments to system load
• Intermediate scheduling smoothes the load on the system by swapping some processes out of main memory so that they enter a “pending” state and do not participate in process scheduling

Low-level scheduling

Scheduling algorithm

Principles for selecting processor scheduling algorithms

Priority number scheduling algorithm

Processes are run based on the number of priorities assigned to them

classification

The number of priorities related to the time of entry to the system

• Short computation time (job/process) is preferred
• The process with short remaining calculation time is preferred
• High response ratio (job/process) priority response ratio = wait-wait time incoming time response ratio = {wait time \over incoming time} Response ratio = Incoming time Waiting time
• First come, first served: First team selected
• Used for advanced scheduling; In low-level scheduling, computation-oriented processes are too superior

Time slice rotation scheduling algorithm

Hierarchical scheduling algorithm

Also known as multi-queue strategy, feedback loop queue

The basic idea

Lottery scheduling algorithm

The basic idea

Storage management

Main mode

Logical addresses

Also known as relative address, that is, the address space used by user programming

Logical addresses are numbered from 0 and can be in one of two forms:

• One-dimensional logical address (address)
• 2-d logical address (segment number: in-segment address)

Block programming

Physical address

Also known as absolute address, that is, the address space used by the program execution, processor execution instructions according to the physical address

Reuse of main memory

Reuse by partition

• Main memory is divided into multiple fixed/variable size partitions
• One program/program segment occupies one partition

Reuse by page shelf

Basic mode of storage management

If you compare logical addresses with physical addresses, there are 2 x 2=4 basic storage management modes

• Single-contiguous storage management: Programs with a one-dimensional logical address space occupy a fixed or variable partition of main memory
• Segment storage management: programs with a segment 2-d logical address space occupy multiple main memory variable partitions
• Page storage management: programs with one dimensional logical address space occupy multiple main memory page shelves
• Segmented page storage management: programs with segmented 2-d logical address space occupy multiple main memory page shelves

function

Address translation

Also weighing localization, that is, the logical address into absolute address

Static relocation

Dynamic heavy position

Address translation occurs when the CPU executes the program

For efficiency, it depends on hardware address translation mechanism

Allocation and disallocation

distribution

When processes are installed into main storage, the storage management software allocates main storage space and sets a table to record the allocation of main storage space

Go to the match

The Shared space

Multiple processes sharing main memory resources: Multiprogramming enables several programs to enter main memory simultaneously, each occupying a certain amount of storage space, and sharing the same main memory

Multiple processes share certain areas of main memory: several cooperating processes have a common block of main memory or data

Storage protection

Expansion of space

Storage expansion: Disk expansion as main storage, only part of the process or part of the process into memory

1. Swap technique: call out part of a process that is not running
2. Virtualisation: Only part of the process is called in

This work requires hardware and software collaboration

1. The swap process decides to swap, and the hardware mechanism calls in
2. When the CPU detects an address that is not in main memory, the VIRTUAL address is abnormal. The OS calls in the virtual address and re-executes the command

Virtual memory

Put forward

• The main storage capacity limit brings many inconveniences

  • Users must consider main memory limits when writing programs
  • The number of tracks in multichannel programming is limited

• User programming behavior analysis

  • Taking all things into account, execution is mutually exclusive
  • Spatial locality, such as sequence and cycle
  • The time locality of the execution of a phase

Consider partial call-in process content

The basic idea

Implementation approach

Two address Spaces need to be established and automatically managed

• (Auxiliary) Virtual address space: holds process loading
• (Main storage) Actual address space: hosts process execution

For the user, the computer system has a much larger main storage space, called virtual memory. Virtual memory is an address space extension technology that is generally transparent to user programming

Hardware support for storage management

Storage Objects involved in storage management

• In order to obtain better processing performance, some main memory programs and data (especially key performance data) are transferred to Cache. Storage management needs to manage them, even the management of associative memory
• To obtain a larger virtual address space, storage management needs to manage virtual storage files stored on hard disks, solid state disks, and even network hard disks

Cache Memory

Composition of cache storage

• Cache memory usually consists of high-speed memory, associative memory, address translation unit, replacement logic and so on
• Associative memory: memory that is addressed by content
• Address conversion component: through the association memory to establish a directory table to achieve fast address conversion. Cache is directly accessed upon a hit. On a miss, read from memory and add to Cache
• Replace parts: Replace data blocks according to certain policies and modify address translation parts when the cache is full

Organization of cache storage

Single-partition storage management

Each process occupies a physically completely contiguous storage space (area)

Single-user continuous storage management

Fixed partition storage management

• Support for multiple partitions
• The number of partitions is fixed and the size is fixed
• Static relocation is available
• Hardware implementation cost is low
• Early OS adoption

Main memory allocation

Address translation

Variable partition storage management

Memory allocation

• The allocation algorithm is used first
• Neighborhood adaptive allocation algorithm
• Optimal adaptive allocation algorithm
• Worst adaptive allocation algorithm

Dynamic relocation

Fraction of memory

• Fixed partition will result in memory oddment
• Variable partitioning also creates small unusable memory partitions, known as out-of-memory odbs, as the process allocates memory
• The optimal adaptive algorithm is most likely to produce external oddment
• Any adaptation algorithm cannot avoid the occurrence of external oddment

Mobile technology (program float technology)

Page storage management

• Paged memory divides main memory into equal-sized page shelves
• Limited by the size of the page holder, the logical address of the program is naturally divided into pages
• Different pages can be placed in different page frames and do not need to be contiguous
• Page tables are used to maintain the main memory integrity of processes

Address in page storage management

Logical addresses

The logical address for page storage management consists of the page number and cell number. The logical address is as follows:

Physical address

Address translation

The price

Fast table

In order to improve the speed of address translation, a special high-speed memory is set up to store part of the page table, which is the fast table

Quick table entry: page number, page rack number

This high-speed memory is associative memory, which addresses by content rather than by address

Because you want to find the page number corresponding to the page holder number, know the page number, do not know the address, so it is content addressing

Eg: Assume that the main memory access time is 200 nanoseconds, the fast table access time is 40 nanoseconds, and the fast table lookup hit rate is 90%

The average address translation cost is $(200+40)*90%+(200+200)*10% =256 nanoseconds $

That’s 36% less than the time it took to access main memory twice (400 nanoseconds)

Address translation process

A process schedule in a multiprogram environment

A page table for each process is registered in the process table. When a process occupies a processor, its page table start address and length are entered into the page table control register

Address translation in multiprogram environment

Memory allocation/de-allocation

A bitmap can be used to record the allocation of main memory, and a process page table can be established to maintain the logical integrity of main memory

Use 1 bit for each page to record whether the page is occupied

Pages of Shared

Page virtual storage management

All the pages of the process are loaded into virtual memory, and part of the pages are loaded into real memory first. Then, according to the execution behavior, the pages that are not in main memory are dynamically called in, and the necessary pages are called out at the same time

For the first time, only the first page of process information is loaded into main storage, which is called request page storage management

Page table of virtual storage management

Implementation of pager virtual storage management

CPU processing address

• If the page resides, the block number is obtained to form the absolute address
• If the page is not in memory, the CPU issues a page-missing interrupt

OS handles missing page interrupts

• If there is a free page frame, according to the auxiliary address to call in the page, update the page table and fast table, etc
• If there is no free page holder, it decides to eliminate the page, call out the modified page, call in the page, update the page table and fast table

paging

Page – missing interruption rate

Assume that process P has n pages and the system allocates m page racks. P The number of successful accesses is S, and the number of unsuccessful accesses is F. The total number of accesses is A=S+F. Page – missing interruption rate is defined as f=F/A

Factors affecting page – missing interruption rate

• Number of frames allocated to a process: The more frames available, the lower the page-missing break rate
• Page size: The larger the page size, the lower the rate of missing pages
• User programming method: in the case of large data volume, it also has a great impact on the page – missing interrupt rate

Eg: The program sets the array to “0”, assuming that there is only one main memory page rack, the page size is 128 words, the array elements are stored in line, the first page is in main memory at the beginning

Procedure 1:

int A[128] [128];
for(int j=0; j<128; j++)for(int i=0; i<128; i++) A[i][j]=0;
Copy the code

The inner loop traverses by marching, resulting in a page-missing interrupt for every assignment, a total of (128× 128-1) page-missing interrupts

Program 2:

int A[128] [128];
for(int i=0; i<128; i++)for(int j=0; j<128; j++) A[i][j]=0;
Copy the code

The inner loop traverses the column, generating (128-1) page – missing interrupts

OPT page scheduling algorithm

FIFO page scheduling algorithm

Always eliminate the first page that is added to main memory, or the page that is in main memory the longest (unless resident)

Simulation is the sequence of the execution of the program, there is a certain rationality

LRU page scheduling algorithm has not been used for the longest time

Least commonly used LFU page scheduling algorithm

Weeding out pages that have been visited less frequently in a recent period of time simulates OPT better than LRU

Based on the interval interruption, and set a counter for each page, after the interval interruption occurs, all counters clear 0 every visit page 1 times to add 1 to the counter to select the smallest value of the page eliminated

CLOCK page scheduling algorithm

The inverted page table

Memory management unit (MMU) : THE CPU manages the control line of virtual and physical storage, maps virtual addresses to physical addresses, provides storage protection, and determines the elimination of pages when necessary. MMU is a specialized hardware organization configured for page storage management.

Inverted page table IPT: Data structure used by MMU

Why reverse page tables

How to implement reverse page table

An entry is set for each physical page in the memory, which stores the process number and page number. Finally, the system maintains only one inverted page table.

Reverse the page entry of the page table

Hash table of reverse page table

If it is to use the page table can be directly from the process of the page table query to the page frame number, and now the use of reverse page table, in the page table to the page frame number mapping need to use hash query, so to maintain a hash table.

Hash function input: process number and page number

Hash function output: pointer to reverse page table entry

Address translation process

Segment storage management

Sections of storage is geared to the needs of developers, developers, according to their own need to program, the program of different parts in different period of address management, and physical of memory management is based on the variable partition storage management, only the variable partition storage management is a process of a paragraph, and sections of storage management is a process of multiple segments.

It is also different from page management, management is transparent to the developer, the system automatically on the software memory according to the cut. And page management each page is equal in size, evenly distributed. The size and location of a segment management segment are uncertain.

Block programming

The basic idea of segmental storage management

Segment storage management is based on variable partition storage management. A process occupies multiple partitions

The hardware needs to add a set of user-visible segment address registers (code segment, data segment, stack segment, additional segment) for address translation

You need to set a segment table for storage management. Each segment occupies a segment entry, including the start address of the segment, the segment length limit, and the flags for storage protection, portability, and scalability

Period of Shared

Segment-page storage management

Section storage management can be implemented based on page storage management

Page management for each paragraph

Address translation for segment-page storage management

Equipment management

The basic concept

I/O devices

Modern computer systems are usually equipped with a large number of I/O devices for information exchange or storage between the computer system and the external world (such as users, other computers or electronic devices, etc.)

Divided by device management

Equipment management objectives

• Overcome the problem caused by the mismatch between the speed of the device and that of the CPU, so that the host and the device can work in parallel and improve device efficiency

• Abstract devices, mask physical details and operation processes of devices, configure drivers, and provide a unified interface for users and high-level software

  • Nodes in a file system are abstracted and managed in a unified manner

    Input and output to the device are abstracted to read and write files

  • Raw device: the device is not directly managed by the operating system and is read and written by applications, which improves I/O efficiency

Device management functions

Layers of device management

• I/O hardware

  • I/O devices and their interface lines
  • Control unit
  • channel

• I/O software

  • System I/O software
  • User space I/O software

I/O control mode

Device manager

A device controller is an entity in a computer whose primary responsibility is to control one or more I/O devices for data exchange between THE I/O devices and the computer. It is the interface between THE CPU and the I/O device, it receives the command from the CPU, and to control the I/O device work, so that the processor from the complex device control affairs. A device controller is an addressable device that has a unique device address when it controls only one device. If the control can be connected to more than one device, it shall contain more than one device address and make each device address correspond to one device.

Data exchange refers to data exchange between cpus and controllers and between controllers and devices. For the former, data is written to or read from the controller in parallel by the CPU through the data bus. In the latter case, it is the device that inputs data to and from the controller to the device.

Polling mode

The interrupt way

1. The processor issues an I/O command to the controller and continues to execute subsequent instructions

   • If the process does not need to wait for the I/O to complete, subsequent instructions can remain instructions in the process
   • Otherwise, the process hangs on the interrupt and the processor performs other work

2. The controller checks the device status and initiates an interrupt when it is ready

3. The CPU responds to the interrupt and turns to the interrupt handler

4. Interrupt handlers perform data reads and writes

5. Resume execution of the original program

Direct memory access (DMA)

Cycle stealing in DMA mode

When DMA and CPU access memory across the bus at the same time, the CPU always cedes ownership of the bus to the DMA for one or more main memory cycles

• Periodic stealing has little effect on data exchange between delayed CPU and main memory
• The data transfer process is discontinuous and irregular
• In most cases, the CPU exchanges data with the Cache

A comparison of the three ways

The device controller adopts polling mode

The CPU waits for the device to be ready and participates in data transfer

A device controller that uses interrupt mode

Direct memory control via DMA

The CPU participates at the beginning and end of data transfer, but not during data exchange with main memory

I/O channels

process

1. When the CPU encounters an I/O request, it starts the specified channel. Once successfully started, the channel starts to control the I/O device to operate.
2. The CPU performs other tasks
3. After the I/O operation is complete, the I/O channel is interrupted. The CPU stops working and processes the EVENT that the I/O operation is complete

The CPU works in parallel with the channel

I/O channels and DMA

Single bus

Connect the CPU, main memory, and I/O modules to the same set of buses

Advantages: Simple structure, easy to expand

Disadvantages: Main memory needs to share bus with I/O module; The increase of devices will make the bus longer, which will increase the transmission delay. Not suitable for a large number of high-speed equipment

Traditional three-level bus

Multi – stage bus of north – south bridge is adopted

Through the storage bus, PCI bus, E(ISA) bus respectively connected to the main memory, high-speed I/O devices and low-speed I/O devices

Advantages: Supports I/O devices with different data rates

A multistage bus using I/O channels

I/O software

Implementation level

Design goals

• High efficiency: Improve the efficiency of equipment, especially disk I/O operations
• Versatility: use uniform standards to manage all equipment

Design ideas

The main consideration

• Device independence: Writing programs to access files is device-independent
• Error handling: Errors handled by low-level software are not perceived by higher-level software
• Synchronous/asynchronous transmission: support blocking and interrupt drive two working modes
• Buffering technology: establish data buffer to improve throughput

I/O software implementation

I/O interrupt handler

Located at the bottom of the operating system, closely related to the hardware, with as little contact as possible with the rest of the system

When a process requests an I/O operation, it is usually suspended until after the data transfer ends and an I/O interrupt occurs, the operating system takes over the CPU and turns to the interrupt handler

When the device makes an interrupt request to the CPU, the CPU responds to the request and goes to an interrupt handler

function

Device driver

Includes all code that is closely related to the device, receives and executes I/O requests from software that is independent of the device

• Converts logical I/O requests submitted by users into the startup and execution of physical I/O operations
• Monitor the correct execution of equipment, manage data buffers, and correct errors as necessary

function

level

Each device driver deals with only one device, or a class of closely related devices

Device drivers are divided into integral drivers and layered drivers

• The overall driver provides interfaces and control hardware directly to the operating system

  • It is suitable for simple drivers with high efficiency but difficult to migrate

• Layered drivers divide drivers into multiple layers and put them on the stack. When the system receives an I/O request, it calls the driver on the top of the stack first. The driver on the top of the stack can directly process the request or call the driver on the lower level until the request is processed

  • It is used for drivers with complex functions and high reuse requirements. The structure is clear and easy to transplant, but it will increase part of the system overhead

Device-independent I/O software

function

• Device naming: Addresses devices by path name
• Device protection: Checks whether the user has the right to access the device
• Provides device-independent data units: number of characters, block size
• Buffering technology: transmission rate, time constraint, cannot reach destination directly
• Device allocation and status tracking: Assign different types of devices
• Error handling and reporting: Errors that the driver cannot handle

User space I/O software

The I/O buffers

purpose

The buffer

A storage area in memory used to temporarily store data for I/O operations

operation

A single buffer

The operating system creates a buffer in the system area of main memory

Input: Reads data to the buffer, the system sends the buffer data to the user area, the application processes the data, and the system reads the next data

Output: Copies data from the user area to the buffer, and after the system outputs the data, the application continues to request output

double-buffering

Circular buffer

The operating system allocates a set of buffers, each with a link pointer to the next buffer, to form a circular buffer

Resolve device and process speed mismatch.

These caches are common system resources that are shared by processes and uniformly allocated and managed by the system

Equipment independence

advantages

• The application program is independent of physical devices. When the system adds or changes devices, the source program does not need to be modified
• Easy to handle I/O device faults and improve system reliability
• Increase the flexibility of equipment allocation, more effective use of equipment resources to achieve multi-channel programming

Device allocation method

allocation

• Static allocation Allocates resources before programs run. This method is simple to implement and prevents system deadlocks, but reduces device utilization
• Dynamic allocation improves device utilization

Device allocated data structure

Device class table

• Each type of device corresponds to a column in the device class table
• Includes device type, total number of devices, number of idle devices, and start address of device table
• It is used to support device independence

Equipment list

disk

The physical structure

Read and write data

When reading or writing data, the magnetic head must be positioned at the beginning of the specified sector on the specified track

process

Driven scheduling

Move the arm scheduling

First in first out

• The moving arm moves randomly and the seeking performance is poor
• Process requests in order, fair to all processes

Minimum search time is preferred

One-way scan

• The mobile arm always sweeps in one direction and does not provide service on the way home
• Suitable for continuous large number of uniformly distributed cylinder requests

Two-way scanning

The elevator dispatching

• When there is no request, the moving arm stops, and when there is a request, it moves according to the rule of the elevator
• Each time the nearest cylinder is selected along the moving direction of the moving arm
• Change the direction of movement if there is no request in the current direction but there is a request in the opposite direction

Rotation scheduling

Cycle sorting

• By optimizing I/O request ordering, access requests located on the same cylinder are completed within the minimum number of turns
• Rotation position measurement hardware and multi-head simultaneous reading and writing technology can improve the efficiency of rotation scheduling

To optimize the distribution of

Virtual device

The use of one physical device to simulate another

Eg: Memory card emulates disk, block device emulates character device

A classic SPOOLing system

composition

• Preinput program: transfers data from input devices to disk input Wells
• Slow output program: transfer data from disk output Wells to output equipment
• Well management program: Controls the exchange of data between operations and Wells

role

File management

The file system

function

User-oriented functions of the file system

File storage

Volume and block

• A volume is a physical unit of storage media, corresponding to a tape, a floppy disk, a CD-ROM, and a hard disk partition

• A block is an area of continuous information on a storage medium, also known as a physical record

  Block The physical unit of information exchange between main and auxiliary storage, always exchanging one or an integer block of information at a time

  For the requirement of starting and stopping mechanical action or identifying different blocks, there must be a gap between two adjacent blocks. The gap is the area between blocks that does not record user code information

File structure

Logical structure of the file

The logical structure of files can be divided into two forms, streaming files and recording files

Streaming file

Recording document

Is a structured file, which is a record flow file composed of several logical record information

A logical record is a unit of information in a file that is divided according to its logically independent meaning

For example, the salary information of each employee is a logical record; The wage information of whole unit worker formed the record type file of this unit wage information

The physical structure of the file

Sequential file

The sequential structure is formed by storing logically continuous information in a file in sequential adjacent blocks of the storage medium. This kind of file is called sequential file, also known as continuous file

Advantages: Fast sequential access to records

Disadvantages: Before creating a file, you need to determine the file length in advance to allocate storage space; Difficulty modifying, inserting, and adding file records

It’s like an array

Connection file

The file directly

A direct file, also known as a hash file, establishes the corresponding relationship between the physical storage address and the computed record keywords

This transformation is usually done by hashing.

It’s like a hash table

Index file

access

Index files are divided into two areas of file storage: index area and data area

Accessing the index file requires two steps:

1. Find the index table,
2. Get the physical address of the record

Two accesses to secondary storage are required, and if the file index has been pre-called into main storage, one exchange of internal and external memory information is reduced

The characteristics of

File directory

File directory structure

Primary directory structure

A linear table is constructed in the operating system, occupying a directory entry with the related attributes of each file, constituting a level 1 directory structure

Secondary directory mechanism

Tree directory structure

Each level of directory can register the next level of directory, also can register files, thus, the formation of hierarchical file directory structure

The hierarchical directory structure usually adopts the tree directory structure, which is a inverted tree with roots, and the root is the root directory. From the root down, each tree fork is a subdirectory; And leaves are documents

The full name of a file includes all subdirectory paths encountered along the path from the root directory to the file, also known as pathnames

Directory Management

To find the

File search

Directory entry lookup

When searching specific directory items, you can use the sequential search method, scan the directory items in the file directory in turn, compare the name of the directory items with the name of the file to find, you can use some optimization methods to speed up the search directory, such as dichotomy, hash

File directory processing

Active file list

The system can establish an active file table for each user process. Before the user uses a file, the directory information about the file is copied to the specified main storage area through “open” operation, and the relevant information is filled into the active file table to establish the connection between the user process and the file index

When the file is no longer in use, use Close to disconnect the user process from the file. At the same time, if the directory has been modified, update the corresponding file directory in the auxiliary memory

File security and protection

File sharing

Refers to the common use of certain files by different users

Concurrency control

Security measures

File confidentiality means that the file and its contents cannot be stolen by other users without the authorization of the file owner. The measures are as follows:

1. Hidden file directory

2. Set the password

3. Using the key

   Setting a password means that you need to enter a password before opening the file, but the file is stored on disk, so you can directly use the key to encrypt the file itself, so that without the key, the content of the file itself is incomprehensible

File protection

Dynamic multiple copy technology

A file that maintains the same content on multiple media and updates the content simultaneously

Dump, backup, and restore

The file is confidential

Prevents files and contents from being stolen by other users

File access control matrix

Access control table

Since the operating system has many users and many files, the ACCESS control matrix is a sparse matrix, which can be simplified into an access control table

Each line contains: user, file, and access properties

The access control table registers only those parts that have access attributes to a file

File protection based on Access control matrix/table

File attributes

A simplified approach to access control tables is to categorize users and specify file attributes for each class of users

• Categories of users: owner, partner, others

• File properties: Read, write, Execute…

• File attributes can be placed in file directory entries, simplifying management

• When using files, users can check file properties to protect them

  	read	write	perform
  File the main	1	1	0
  partner	1	0	0
  It is the user	1	0	0

File access

Sequential access

Read/write operations in record order

The read operation reads the current record from the read pointer while advancing the read pointer to the next record to be read

Write sets the write pointer, writing a record to the end of the file while pushing the write pointer

Allows n (integer) records to be jumped forward or backward on a read pointer

Direct access

Indexed access

Index access method based on index file

For such files, the address of the information block can be translated by looking for the record key

In practical systems, multilevel indexes are used to speed up the record search process

Use of files

Set up files

Create a file

Required parameters: file name, device class (number), file properties, and access control information

Process: Create a file directory entry on the corresponding device, allocate the first physical block for the file, apply for an entry in the active file table, register the directory information, and return a file handle

Cancel the file

Open the file

Used to establish usage connections between files and user processes

Required parameters: file name, device class (number), and opening mode

Processing flow: apply for an item in the main memory active file table, return a file handle; Follow the file name to find directory files, copy the directory information to the active file table corresponding column; Check access validity according to access control instructions; If you open a shared file, you should handle it accordingly

Close the file

Read/write files

Required Parameters Parameters: file handle, user data area address, number of read and write records or bytes

Processing flow: according to the file handle from the active file table to find the file directory information; Converts related logical records into physical blocks based on the logical and physical organization of the file indicated by the directory entry

Locate the file

Use of auxiliary storage space

Large auxiliary storage space such as disks is shared by the OS and many users. Files are often created and deleted during the running of user processes. The OS should be able to automatically manage and control the auxiliary storage space

As user files are created and destroyed, file storage space can become fragmented. OS’s solution to ‘fragmentation’ is to sort out ‘fragmentation’; In the collation process, files are often reorganized and placed in contiguous storage

allocation

Management of free blocks

Shown in figure

Free block group join method

Hard disks are divided into blocks for management. The blocks are divided into two types: occupied (storing data) blocks, which are called dedicated blocks, and free blocks, which are not occupied. Free blocks form groups and are connected together, as shown in the figure

The top line of each free block group shows the number of free blocks

Each free block group contains a maximum of 100 free blocks, numbered from 0 to 99. Free blocks 0 are used as Pointers, and free blocks 1 to 99 are used as actual free blocks.

Whenever free blocks need to be allocated:

if(this. Number of free blocks =1) {if(thisThe first unit ==0){waiting for free blocks to be allocated; }else{x = the free block group to which a cell points; Allocate free blocks of X; X. Number of free blocks --; }}else if(this. Number of free blocks >1{distributionthis. Free block;this.allocate free block --; }Copy the code

Whenever a free block is returned:

if(this. Number of free blocks <100){return the free block;this. Number of free blocks ++; }else if(this. Number of free blocks ==100){free block group x =newFree block group (); X. Number of free blocks =1; X. First unit =this; Add free blocks to x; X. Number of free blocks ++; }Copy the code

The implementation hierarchy of the file system

Concurrent programming

concept

Sequential programming

Each program executes in strict order on the processor

The general habit of programming is sequential programming: the design of the solution of a specific problem into a program or, if strictly sequential, a sequence of programs, which is called the external sequentiality of program execution

Characteristics of the

Concurrent execution of processes

Multiprogramming allows multiple programs to enter memory at the same time to compete for the processor to run. The OS allows a computer system to have more than one running process at a time, that is, multiple processes to execute concurrently. The OS guarantees that programs written in a sequential programming approach will not be affected by concurrent execution, as if they were monopolizing the computer. These sequential programming processes execute unrelated concurrent processes in the OS.

While (1) {input, process, output} while(1) {input, process, output}

Processor utilization: 52/(78+52+20)≈35%

Instead, design three programs that run independently and let them run concurrently in a multi-program system

1. While (1) {input, send}
2. While (1) {receive, process, send}
3. While (1) {receive, output}

Processor utilization: (52N) /(78N +52+20)≈67%

Concurrent programming

features

• Parallelism: Multiple processes execute concurrently in a multiprogram system or in a multiprocessor system, improving computational efficiency
• Shareability: Multiple processes share software resources
• Interactivity: Constraints exist when multiple processes execute concurrently, which increases the difficulty of programming

Constraints between concurrent processes

Time-related errors

For a group of interacting concurrent processes, the relative speed of execution cannot be mutually controlled. If the program is not designed properly, all kinds of “time-related” errors can occur.

• The result error

  The two processes almost read and write data at the same time, causing data read and write errors

  If the data in x is 1, A and B both read and add 1 to write back, maybe they both read x is 1, when A writes back, B writes back, the final result is that B’s result overwrites A’s result, and if they execute separately, it is +2, and only +1 in the end

• Wait forever

  For example, when process A applies for resources and finds that there are no resources, process A waits. Process B returns the resources later, but Process A does not check whether resources exist

Process mutual exclusion synchronizes with process

A critical region

Critical resources: Resources represented by mutually exclusive shared variables that can only be used by one process at a time

A critical section is a segment of a concurrent process that is associated with mutually exclusive shared variables

When multiple concurrent processes access critical resources, there are competition constraints. If two processes stay in related critical regions at the same time, a time-dependent error occurs.

Description of critical region

Three requirements for critical area management

1. Allow at most one process at a time to remain within the relevant critical region
2. A process cannot remain in a critical region indefinitely
3. A process cannot wait indefinitely to enter a critical section

Nested use of critical sections

Critical area management

Box (test lock, establish lock) two instructions, the execution process can not be interrupted, if interrupted may simultaneously enter the critical area or deadlock.

Test and set up instructions

TS(x) {
    if (x==false) { 
        x=true; return true;
    }else return false;
}
Copy the code

Boolean lock; lock = false; Process Pi {// I = 1,2... ,n Boolean pi; repeat pi = TS(lock) until pi; // loop request lock critical section; The lock = false; / / unlock}Copy the code

Exchange instructions

swap (a,b) { temp=a; a=b; b=temp; }
Copy the code

Boolean lock; lock = false; Process Pi {// I = 1,2... ,n Boolean pi; pi = true; repeat swap(lock, pi) until ! PI; // loop request lock critical section; The lock = false; / / unlock}Copy the code

TS and swap instructions are busy waiting, which is inefficient

interrupt

PV operation

TS or SWAP instruction management critical area, using busy polling, low efficiency

Turn off the interrupt management critical section, which is inconvenient for user programs to use

Reference: The operating system uses request-wait-Interrupt recovery to access hardware resources

Recording semaphore

typedef struct semaphore {
    int value; // Signal value
    struct pcb *list; // The semaphore waits for the process queue pointer
}
Copy the code

PV operation primitive

P Operation primitives (applying for resources)

procedure P(semaphore:s) {s = s --1; // Semaphore minus 1
    if (s < 0) W(s); // If the semaphore is less than 0, the calling process is set to wait for the semaphore s
}
Copy the code

V Operation primitives (free resources)

procedure V(semaphore:s) {
    s = s + 1; // The semaphore increases by 1
    if (s <= 0) R(s); // If the semaphore is less than or equal to 0, release a process waiting for the semaphore s
}
Copy the code

PV operation to solve the process mutually exclusive framework

semaphore s; s = 1; Cobegin process Pi {...... P(s); The critical area; V(s); ... } coend;Copy the code

PV operation solves process synchronization

Concurrent processes coordinate execution priorities based on certain conditions in order to complete a common task

The execution of one process waits for messages from other processes

1 Producer 1 Consumer 1 buffer problem

Int B; // Share the bufferSemaphore sput;// Number of empty buffers that can be used
Semaphore sget; // The number of products that can be used in the buffer
sput = 1; // One item is allowed in the buffer
sget = 0; // There are no products in the buffer

process producer {
	while(1){produce a product; P(sput);//
        B = product；
        V(sget);//
	}
}

process consumer {
    while(1){
        P(sget);//The Product = B; V(sput);//Consume a product; }}Copy the code

1 Producer 1 consumer N Buffer problem

Int B[k]; // Share buffer queueSemaphore sput;// Number of empty buffers that can be used
Semaphore sget; // The number of products that can be used in the buffer
sput = k; // Allow k items in the buffer
sget = 0; // There are no products in the buffer
Int putptr, getptr; // Loop the queue pointer
putptr = 0; getptr = 0;

process producer{
    while(1){produce a product; P(sput);//B [putptr] = product; putptr =(putptr+1) mod k;
        V(sget);//
    }
}

process consumer{
    while(1){
        P(sget);//
        product= B[getptr];
        getptr=(getptr+1) mod k;
        V(sput);//consume a product; }}Copy the code

N producer n consumer n buffer

Int B [k]; Semaphore sput;/* Number of empty buffers available */
Semaphore sget; /* The number of products available in the buffer */
sput = k; /* The buffer allows k items */
sget = 0; /* There are no products in the buffer */
Int putptr, getptr; putptr = 0; getptr = 0;
Semaphore s1,s2; /* Mutually exclusive use putptr,getptr */
s1 = 1; s2 =1;

process producer_i {
    while(1){produce a product; P(sput);//
        P(s1);/ / *B [putptr] = product; putptr =(putptr+1) mod k;
        V(s1);/ / *
        V(sget); //
    }
}

process consumer_j {
    while(1){
        P(sget);//
        P(s2);/ / *The Product = B [getptr]; getptr=(getptr+1) mod k;
        V(s2);/ / *
        V(sput);//Consume a product; }}Copy the code

Apples and oranges

Int plate; Semaphore sp;/* You can put some fruit on the plate */
Semaphore sg1; There are oranges on the plate */
Semaphore sg2; /* There are apples on the plate */
sp = 1; /* One fruit is allowed on the plate */
sg1 = 0; There are no oranges on the plate */
sg2 = 0; There is no apple on the plate

process father {
    while(1){peel an apple; P(sp); Put the apple on the plate; V(sg2); } } process mother {while(1){peel an orange; P(sp); Put the orange on the plate; V(sg1); } } process son {while(1){ P(sg1); Take oranges from the plate; V(sp); Eat oranges; } } process daughter {while(1){ P(sg2); Take the apple from the plate; V(sp); Eat an apple; }}Copy the code

Process of communication

Direct process communication

The process that sends or receives a letter indicates to whom the letter is sent or received from

• Send (P, letter) : Sends a letter to process P
• Receive (Q, letters) : Receives letters from process Q

Process indirect communication

Mailbox for indirect communication

A mailbox is a storage area for letters. Each mailbox can be divided into two parts: a mailbox feature and a letter box

• Mailbox features indicate mailbox capacity, message format, Pointers, and so on
• A letter box is used to store letters. The letter box is divided into sections, each containing a letter

Process of sending letter primitives

If the specified mailbox is not full

Then send the letter to the position indicated by the pointer in the mailbox, and release the waiting person waiting for the letter in the mailbox

If the specified mailbox is full

Process of receiving letter primitives

If there are letters in the specified mailbox

If there is no letter in the specified mailbox

The recipient is placed in a state of waiting for a letter in the mailbox

Advanced process communication mechanism

Stream-based process communication

Multiple processes use a shared message buffer (called pipe, multiplexer, socket)

Some processes write character streams (send/write) to message buffers

Some processes read character streams from message buffers (receive/read)

The information exchange unit is based on a character stream of any length

Rpc-based process communication

A deadlock

When multiple processes are allowed to concurrently execute shared system resources, the system must provide synchronization mechanisms and process communication mechanisms. However, if this mechanism is not used properly, the process can be blocked forever

The factors that cause deadlocks are not only related to the amount of resources the system has, but also related to resource allocation policies, resource usage requirements of processes, and the order in which concurrent processes advance

Deadlocks can be resolved in three ways:

• Deadlock prevention
• Deadlock avoiding
• Deadlock detection and recovery

Deadlock prevention

Static allocation (preallocation)

Static allocation means that a process must request all the resources it wants before it executes and does not start executing until all the resources it wants are satisfied

The total number of resources required by all concurrently executing processes does not exceed the number of resources available to the system

With static allocation, the process does not claim resources during execution, so it does not occupy some resources and wait for others, which breaks the second condition

Level distribution

Deadlock avoidance

While deadlocks cannot be prevented, it is still possible to prevent deadlocks by knowing the resource requests associated with each process in a concurrent process

Simply test the system state before allocating resources to the applicant. If allocating resources to the applicant would cause a deadlock, then refuse to allocate resources. Otherwise, accept the application and allocate resources to it

Banker’s algorithm

Deadlock detection

There is no restriction on the allocation of resources, but the system periodically runs a “deadlock detection” program to determine whether the system has deadlocks, and if deadlocks are detected, try to remove them

One way to detect this: You can set up two tables to record resource usage by a process

• The waiting resource table records the resources that each blocked process is waiting for
• The occupied Resource table records the resources occupied by each process

When a process applies for a resource, check whether the resource is occupied by another process. If the resource is free, the resource will be allocated to the applicant and logged into the occupied resource table; Otherwise, the login process waits for the resource table

detection

To deal with

Restarting process execution can be used, and the recovery effort should involve restarting one or all of the processes and from what point

All involved in deadlock start from scratch, but this cost is quite large, in the process of execution in the periodic set checkpoint, from the checkpoint restart

Aborts a process involved in a deadlock and reexecutes it later