笔记 OSC_Concurrency1

Concurrency 1

---

Overview

• Examples of concurrency issues (e.g. counter++)
• Root causes of concurrency issues
• Critical sections and mutual exclusion
• Requirements and approaches for mutual exclusion

Concurrency

• Threads and processes execute concurrently or in parallel and can share resources
  • Multiprogramming/multiprocessing improves system utilisation
• A process/thread can be interrupted at any point in time (I/O, timer)
  • The process “state” is saved in the process control block
• The outcome of programs may become unpredictable[不可预知的]
  • Sharing data can lead to inconsistencies[矛盾]
  • I.e., the outcome of execution may depend on the order win which instructions are carried out

Incrementing a counter

• counter++ consists of three separate actions:
  • 1 read the value of counter and store it in a register
  • 2 add one to the value in the register
  • 3 store the value of the register in counter
• The above actions are NOT “atomic”, e.g. they can be interrupted by the timer (⇒ context switch)

Bounded Buffers

• Consider a bounded buffer in which N items can be stored
• A counter is maintained to count the number of items currently in the buffer
  • Incremented when an item is added
  • Decremented when an item is removed
• Similar concurrency problems as with the calculation of sums happen in the bounded buffer (producer/consumer) problem

Race Conditions

• A race condition occurs when multiple threads/processes access shared data and the result is dependent on the order in which the instructions are interleaved

Concurrency within the OS

Data Structures

• Kernels are preemptive these days (⇔ non-preemptive)
  • Multiple processes are running in the kernel
  • I.e. kernel processes can be interrupted at any point
• The kernel maintains data structures, e.g. process tables, memory structures, open file lists, etc.
• These data structures are accessed concurrently/in parallel
• These can be subject to concurrency issues

Resources

• Processes share resources, including memory, files, processor time, printers, I/O devices, etc.
• The operating system must:
  • Allocate and deallocate these resources safely (i.e. avoid interference, deadlocks and starvation)
  • Make sure that interactions within the OS do not result in race conditions
  • The operating system must provide locking mechanisms to implement/support mutual exclusion (and prevent starvation and deadlocks)

Critical Sections[临界段], Mutual Exclusion[互斥]

• A critical section is a set of instructions in which shared variables are changed

• Mutual exclusion must be enforced for critical sections

  • Only one process at a time should be in the critical section (mutual exclusion)
  • Processes have to get “permission” before entering their critical section

    do
    {
    	...
    	// ENTRY to critical section
    	critical section, e.g.counter++;
    	// EXIT critical section
    	remaining code
    	...
    } while (...);

• Any solution to the critical section problem must satisfy the following requirements:

  • Mutual exclusion: only one process can be in its critical section at any one point in time
  • Progress: any process must be able to enter its critical section at some point in time
  • Fairness/bounded waiting: processes cannot be made to wait indefinitely
• These requirements have to be satisfied, independent of the order in which sequences are executed

Enforcing Mutual Exclusion

• Approaches for mutual exclusion can be:
  • Software based: Peterson’s solution
  • Hardware based: test_and_set(), swap_and_compare()
  • Based on:
    • Mutexes
    • Semaphores
    • Monitors (software construct within the programming languages)
• In addition to mutual exclusion, deadlocks have to be prevented (next week’s subject)

Summary

• Examples of concurrency issues (e.g. counter++)
• Root causes of concurrency issues
• Critical sections and mutual exclusion
• Requirements and approaches for mutual exclusion

赏

谢谢投喂 (～o￣3￣)～

支付宝