First, we introduce the basic concepts, characteristics, classification, structure and other related basic knowledge of multi-processor systems.
10.1 Basic concepts of multi-processing system MPS
10.1.1 Introduction of multiprocessors
10.1.2 Types of multiprocessor systems
1. The tightness of coupling after interconnection
Tightly coupled MPS: implemented through high-speed bus or high-speed crossbar switch
Loosely coupled MPS: interconnecting multiple computers through channels or communication links
2. Whether the processors used are the same
Symmetric MPS: The processors used are identical in function and structure, most of them are like this
SMP is the most commonly used
Asymmetric MPS: The processors used have different functions and structures. There is only one master processor and multiple slave processors.
10.2 Structure of multiprocessing systems
10.2.1 Structure of Unified Memory Access UMA multiprocessor system
1. SMP structure based on single bus
That is, multiple processors and a shared memory on a bus
Disadvantages: It can easily cause multiple processors to compete for bus resources. As the number of processors increases, the problem will become more serious.
Method: Set up a cache in each CPU
Function: Store commonly used data of the processor in the local cache to reduce the frequency of access to the bus
2. SMP structure using multi-layer bus
That is, multiple processors and a shared memory are on a system bus, and each processor accesses its local private memory through the local bus.
Advantages: Reduces CPU access to shared memory to a considerable extent
3. System structure using single-stage crossbar switch
That is, all processors and shared memories are connected to each other through a crossbar switch array, and each crossbar switch establishes a connection path for two of the nodes.
feature
1. The intersection point is generally an N*N array. Only one point in each column and row is in the open state at the same time.
2. Allow one row to connect multiple crossbar switches at the same time
3. The cross-over cost is large, which limits the application in large-scale systems.
4. System structure using multi-level cross switch
That is, using a multi-level crossbar switch, such as a 2*2 crossbar switch, dual input and dual output
Advantages: Greatly reduces cross-over costs and can disperse traffic well
Disadvantages: Not suitable for large multi-processor systems. As CPUs increase, bus access resources are still a serious problem.
10.2.2 Structure of non-uniform memory access NUMA multiprocessor
Concept: Its access time changes with the location of the storage word. The public storage area allocated in the system and the local memory of all processing together constitute the global space of the system.
Purpose: Suitable for large multi-processing systems
Method: Set up multi-layer memory and try to use local and group memory to ensure that bus resources are sufficient.
1. The structure and characteristics of NUMA
1. NUMA has multiple processor modules, and each processor module has multiple CPUs.
2. In the processor module, each CPU has a local memory, and then the module can access the shared memory in the group through the local bus.
3. In the processor module, each CPU is configured with a high-speed buffer and a directory to record the instructions of each buffer block.
4. All processor modules can access common memory through a common bus
10.3 Characteristics and classification of multiprocessing operating systems
1. Characteristics
Parallelism, distribution, inter-machine communication and synchronization, reconfigurability
2. Different functions from single-processor systems
1. Process management
Process synchronization
Single processor: Each process will only execute alternately, and there will be no problem of two processes accessing the same shared resource at the same time.
Multiprocessor: Due to the concurrency of processes, multiple processes may access a shared resource at the same time
process communication
Uniprocessor: Can communicate directly through "shared memory"
Multiprocessors: extensive use of indirect communication
process scheduling
Single processor: process scheduling knowledge simply selects a process from the ready queue according to a certain algorithm
Multiprocessors: Improving parallelism in program execution
2. Memory management
It is also necessary to enhance the address transformation mechanism, access conflict arbitration mechanism, and data consistency mechanism.
3. File management
Single processor: using a centralized file system
multiprocessor
Centralized, decentralized, distributed
4. System reconstruction: refers to a multi-processor system. If a processor in the system fails, the system needs to automatically remove the faulty resources and replace them with backup resources.
3. Type
independent supervision
Advantages and Disadvantages: Strong autonomy, high reliability, complex implementation, large storage space overhead, unbalanced processor load
Suitable for loosely coupled multi-processing systems
floating supervision
The most complex, efficient and flexible
Suitable for tightly coupled symmetric multiprocessing systems
Describe the process synchronization and process scheduling issues in multi-processor systems
10.4 Process synchronization under multiprocessor systems
10.4.1 Centralized and distributed synchronization methods
Central synchronization entity: refers to the synchronization entity used to implement communication between processes, such as hardware locks and semaphores.
feature
1. Has a unique name that is known to all synchronization processes
2. At any time, there can only be one access to the central synchronization entity
Synchronization algorithm
Centralized synchronization algorithm
feature
1. When multiple processes access shared resources or communicate at the same time, only the central control node determines
2. The judgment information is stored in the central control node
Disadvantages: poor reliability, easy to form bottlenecks
Distributed synchronization algorithm
feature
1. All nodes have the same information and can only make judgments based on local information.
2. When making judgments, all nodes are responsible for the same responsibilities and pay the same workload.
Process synchronization: Synchronize the access of multiple processes to shared resources, that is, control the order of process execution to ensure that the processor works in an orderly manner.
Synchronization mechanism
1. Spin block
Concept: Set a spin lock on the bus. When a process occupies the spin lock, other processes will keep "spin" when trying to access it, that is, loop testing
Applicable to: The protected shared resources need to interrupt context switching or the critical section protected by the calling process is very short, so spin locks should be used.
Category: Ordinary spin lock, read-write spin lock, large reader spin lock
2. Read-copy-modify (RCU) lock
Solve the problem: Spin lock does not allow reading while writing
Concept: The writing process first reads the resource, then copies the resource and writes on the copy. All reading processes on the original copy can read it directly without requesting it.
Advantages: Readers will not be blocked, no need to set up a synchronization mechanism for shared files
Disadvantages: If you are performing a large number of write operations, it is better to use a spin lock
3. Binary exponential compensation algorithm and waiting queue mechanism of CPU to be locked
Binary Exponential Compensation Algorithm
Solve the problem: Every time a shared resource is occupied, the other CPUs will continue to test the lock process, causing bus traffic congestion.
Basic idea: Set an instruction delay execution time for each CPU lock test instruction, and increase each time in a binary exponential manner
Advantages: Significantly reduces bus access
CPU waiting queue mechanism to be locked
Solve the problem: In the binary exponential compensation algorithm, it is possible that there is no CPU to test the lock on the bus for a period of time, but it is in a waiting delay
Basic idea: The CPU occupying the resource has a list of CPUs to be locked. When it releases the resource, it finds the list of CPUs to be locked in the local cache, and sets the private lock variable recorded by the first CPU to allow it to enter the critical state.
4. Sequencing mechanism
Event Count Synchronization Mechanism
10.5 Process Scheduling in Multiprocessor Systems
10.5.1 Several factors to evaluate scheduling performance: task flow time, scheduling flow time, average flow, processor utilization acceleration ratio, throughput
10.5.2 Process allocation method
1. Process allocation under symmetric multi-processing system
1. Static allocation: A process must be allocated to a processor for execution from the beginning to the end of execution. After the process is blocked, it is hung in the ready queue on the processor.
2. Dynamic allocation: A process can be allocated to multiple processors for execution. After the process is blocked, the system's public ready queue is mounted.
2. Process allocation under asymmetric multi-processing systems
Since the master-slave type is generally adopted, process scheduling can be performed by the host.
10.5.3 Process (thread) scheduling method
1. Self-scheduling method
2. Group scheduling method
3. Dedicated processor allocation method
10.5.4 Deadlock
1. Types of deadlocks under multiprocessors: resource deadlock, communication deadlock
2. Detection and release of deadlock
Example: Explain two multiprocessor systems
10.6 Network operating system
10.6.1 Networks and Network Architecture
10.6.2 Network operating system classification
10.6.3 Network operating system functions
See "Principles of Computer Networks"
10.7 Distributed File System DFS
10.7.1 Distributed systems
Characteristics of distributed systems
Transparency: All computers share system resources
Distribution: The system consists of multiple computers, including geographical location, resource distribution, system control, and function distribution.
Identity: Several computers in the system can work together to serve a task
Globality: The system has a global process communication mechanism, and logically all hosts are a whole
Advantages: strong computing power, easy sharing, convenient communication, good scalability, and high reliability
10.7.2 Distributed file system implementation methods and basic requirements
Concept: A distributed file system is a public operating system configured on a distributed system
Implementation method
Shared file system method: data storage on several file servers
Shared disk file: configure a shared disk
Basic requirements: transparency, fault tolerance, security, consistency
10.7.3 Naming and Sharing Semantics
Naming: is to establish a mapping between logical objects and physical objects of data
Sharing semantics: determines the effect of sharing files between multiple clients
10.7.4 Remote file access and caching
Wondershare EdrawMind
