[Research on the computer] Operating system D6: concurrent program design

1. Basic concepts of concurrent programs

• Programs Sequentiality
  • Internal sequentiality: CPU executes instructions strictly in order
  • External sequentiality: Programmer design The idea of ​​sequential design is often used in programs
• Sequential program characteristics
  • Sequence of program execution
  • The closedness of the computing environment: the program is executed as if it is an exclusive resource
  • The certainty of the calculation result
  • The reproducibility of the calculation process
• Concurrent processes
  • Unrelated concurrent processes: A group of concurrent processes, running on different sets of variables
  • Concurrent process of communication: A group of concurrent processes, sharing some variables, and mutual influence
• Concurrent process restriction relationship
  • Process mutual exclusion: Compete for a certain resource
  • Process synchronization: Work together to complete a certain task, coordinate the order

  < li>Something went wrong:

  • Errors related to time: wrong result, waiting forever

< li>Critical section:

• Critical resource: A resource that can only be used by one process at a time (mutually exclusive shared variable)
• Critical section: is a program segment, a program segment related to mutually exclusive shared variables in a concurrent process
• Related critical sections: The critical sections of the two processes have the same Critical resources (must be mutually exclusive)
• Problems:
  • There are restrictions on access to critical resources by multiple concurrent processes
  • If two The process is in the relevant critical section at the same time, and time-related errors will occur
• Requirements for critical section management:
  • At most one process is allowed to stay in the relevant critical zone at a time
  • A process cannot stay without restriction in the critical zone
  • A process cannotwait without restriction Enter the critical area
• Critical area nested use
• 

< /li>

2. Concurrent program control and problems

• Critical section management implementation:
  < li>Idea: Judging the lock and Acquiring the lock should be used as atomic operations, otherwise deadlock or time error will occur
  • < strong>Implementation:
    • Atomic instructions: Test and establish lock instructions and swap instructions (busy waiting, low efficiency)
    • < strong>Interrupt control: The switch is interrupted when entering and exiting the critical section, so that the critical section will not be interrupted when the critical section is executed, and atomicity is naturally realized. The solution to this problem
    • It is not recommended for user programs, because there is no guarantee that programmers can design short and concise primitives
  • PV operation: Use semaphore, “application-waiting queue-interrupt recovery”
• Producer consumer issues:
  • 

Inter-process communication < ul>

Semaphore: Low-level communication method

Letter: Process communication mechanism (direct communication, indirect communication)

Stream-based: Multiple processes share a buffer

RPC: Remote procedure call

Deadlock

• Concept: Two processes are waiting for the resources occupied by each other
• The occurrence of deadlock
  • Mutual exclusion: Processes use resources mutually exclusive
  • Own and wait: One process cannot get resources , Just wait and don’t release the existing resources
  • Don’t deprive: A process can’t steal resources from another process
  • Wait in a loop: Each process waits for the resources held by its previous process
• Prevention of deadlock
  • Destruction of the above Either one of the four conditions is sufficient
  • eg. Level allocation: Resources are divided into multiple levels, and one process gets a certain After a resource, only higher-level resources can be obtained
• Avoidance of deadlock: Banker’s Algorithm
• Deadlock detection:
  • 

  • Algorithm: warshall closure