OS LU7

Understanding Operating Systems - Concurrent Processes

• Learning objectives include understanding differences between processes/processors, multiprocessing configurations, critical regions, process synchronization, along with process cooperation and the significance of concurrent programming languages.

Parallel Processing

• Parallel processing involves multiprocessing.
• Two or more processors operate in unison alongside CPUs executing instructions simultaneously.
• The Processor Manager coordinates the activity of each processor and synchronizes the interaction among CPUs.
• Parallel processing development enhances throughput and increases computing power.
• Benefits include increased reliability, and faster processing (two or more instructions at a time).
• Reliability increased because more than one CPU is available, and if one fails, others can take over.
• A challenge for parallel processing is that it is complex to implement.
• Methods involve allocating a CPU to each program/job, working set, or subdividing individual instructions.
• Subdivisions of individual instructions are processed simultaneously through concurrent programing.
• The six-step information retrieval system example highlights orchestrating processor interaction, where synchronization is key.
• An example of the six steps of fast-food lunch process include:
  • Processor 1 (order clerk) handles the query, checks for errors, and passes it to Processor 2 (the bagger).
  • Processor 2 (the bagger) searches for the desired hamburger information.
  • Processor 3 (the cook) retrieves cooking data for the hamburger from database or secondary storage.
  • Once gathered and cooked, the hamburger is placed for Processor 2 (the bagger) retrieve.
  • Processor 2 passes the hamburger to Processor 4 (the cashier).
  • Processor 4 routes the response (order) back to the customer.

Evolution of Multiprocessors

• Multiprocessors were developed for high-end midrange and mainframe computers.
• Each additional CPU is treated as an additional resource.
• Hardware costs have reduced due to Moore's Law.
• Multiprocessor systems are now available on all systems.
• Multiprocessing occurs at job, process, and thread levels, each requiring different synchronization frequencies.
• Job level parallelism assigns each job its own processor, requiring no explicit synchronization.
• Process level parallelism assigns unrelated processes to available processors, needing moderate synchronization.
• Thread level parallelism assigns threads to available processors, this requires a high degree of synchronization.

Multi-Core Processors

• Multi-core processing involves placing several processors on a single chip.
• Problems of multi-core processing include heat and current leakage (tunneling).
• A single chip with multiple processor cores in the same space allows sets of simultaneous calculations.
• Modern multi-core processors can have 80 or more cores on a single chip.
• Each core in a multi-core setup runs more slowly than a single-core chip.

Multiprocessing Configurations

• Multiple processor configurations impact systems, with three main types: master/slave, loosely coupled, and symmetric.

Master/Slave Configuration

• Master/slave configuration is an example of an asymmetric multiprocessing system.
• Single-processor system configurations feature additional slave processors.
• Each processor is managed by a primary master processor
• Master processor responsibilities are to:
  • Manage the entire system.
  • Maintain processor status.
  • Perform storage management activities.
  • Schedule work for other processors.
  • Execute all control programs.
• Advantages of master/slave configurations is simplicity.
• Disadvantages of master/slave configurations include:
  • Reliability no higher than a single processor system.
  • Potentially underutilized resources.
  • Increased number of interrupts.
• In this configuration slave processors can directly access main memory, but must send I/O requests through the master processor.

Loosely Coupled Configuration

• Loosely coupled configuration features several complete computer systems, each with its own resources, and I/O management tables.
• Processors in loosely coupled configurations are independent.
• Independent single-processing differences occurs from each processor communicating and cooperating with others.
• Each process has access to global tables. .
• There are several requirements and policies for job scheduling under this configuration
• A processor failure allows other processors to continue working independently.
• The failure is difficult/slow to detect in this setup.
• Each processor has dedicated resources.

Symmetric Configuration (Tightly Coupled)

• Symmetric configuration (tightly coupled), uses decentralized processor scheduling.
• Each processor is of the same type.
• Advantages over loosely coupled configurations include reliability, effective resource utilization, and load balancing.
• The symmetric configuration can degrade gracefully in a failure situation.
• The symmetric configuration is difficult to implement because it requires synchronized processes and conflict avoidance (races/deadlocks)
• It features single operation system copy with global table listing and decentralized processing.
• Processes access the same resource at the same time, leading to more conflicts, requiring process synchronization.
• Requires algorithms to resolve conflicts between processors.
• Its homogenous processors must be synchronized to avoid deadlocks and starvation.

Process Synchronization Software

• Successful process synchronization requires that used resources are locked and protected from other processes until released.
• Release occurs when the waiting process is allowed to use resource
• Mistakes in synchronization can result in starvation (job waiting indefinitely) or deadlock (key resource being used).
• A critical region is a protected part of a program where it must complete execution (non-interleaved).
• Other processes wait before accessing critical region resources to ensure integrity of operation.
• Synchronization using the lock-and-key arrangement:
  • Process determines key availability, obtains key, puts key in lock, thus making key unavailable.
• Types of locking mechanisms include test-and-set, WAIT and SIGNAL, and semaphores.

Test-and-Set

• Test-and-set is an indivisible machine instruction (TS) which is executed in a single machine cycle.
• If a key is available, test-and-set sets it to unavailable.
• Has an actual key which is a single bit in storage location, that is zero (free) or one (busy).
• Before a process enters the critical region, a condition ode using TS instruction is tested.
  • No other process is in the area.
• If a process proceeds, its condition code changes from zero to one.
• When Pl exits, the code is reset to zero, allowing others to enter with the updated condition code.
• Advantages of test-and-set include simple procedure to implement, and works well for a small number of processes.
• Drawbacks of test-and-set include:
  • Starvation (many processes waiting to enter a critical region).
  • Processes gain access in arbitrary fashion.
  • Busy waiting (processes remain unproductive, resource-consuming wait loops).

Wait and Signal

• Wait and signal act as modifications to the test-and-set method.
• Designed to remove busy waiting, featuring two new mutually exclusive operations (WAIT and SIGNAL).
• Both are part of the process scheduler's operations.
• WAIT is activated when a process encounters a busy condition code.
• SIGNAL is activated when a processor exits critical region, setting condition code to "free.”

Semaphores

• Semaphores are nonnegative integer variable flags.
• Semaphores signals if a resource is free and when the resource can be used by a process.
• Two operations for semaphore:
  • P (proberen means “to test").
  • V (verhogen means “to increment").
• Let s be a semaphore variable.
  • V(s): s: = s +1: Fetch, increment, store sequence
  • P(s): If s > 0, then s: = s -1: Test, fetch, decrement, store sequence
• s = 0 implies busy critical region, and the process calling on P operation must wait until s > 0
• The waiting job of choice is processed next according to the process scheduler algorithm.
• Enforces mutual exclusion concept.
  • P(mutex): if mutex > 0 then mutex: = mutex – 1
  • V(mutex): mutex: = mutex + 1
• Critical regions ensures parallel processes modify shared data only in critical region.
• Parallel computations makes mutual exclusion explicitly stated and maintained.

Process Cooperation

• Process cooperation is when the various processes operate together to complete a task.
• Each case requires mutual exclusion and synchronization.
• If there is an absence of mutual exclusion and synchronization, there can be serious problems.
• Examples of potential cases include producers and consumers problem, and readers and writers problems.
• Each case is implemented using semaphores.

Producers and Consumers

• One process produces data, which a process consumes.
• CPU and line printer buffers are an example of producers and consumers.
• A delay producer example is when the buffer is full.
• A delay consumer example is when the buffer is empty.
• Producers and consumers can be implemented by two semaphores.
• Semaphores include:
  • Number of full positions.
  • Number of empty positions.
  • Mutex
  • A third semaphore ensures mutual exclusion.
• The buffer in a Producer Consumer setup can be in any one of three states:
  • Full
  • Partially Empty
  • Empty

Readers and Writers

• Two process types need access to shared resource such a file or database.
• Airline reservation system is an example of readers/writers setup.
• Readers/writers can be implemented using two semaphores, which ensures mutual exclusion between readers and writers.
• Resources are given to all readers if no writers are processing (W2 = 0).
• Resources are given to a writer if no readers are reading (R2 = 0) and no writers writing (W2 = 0).

Concurrent Programming

• A concurrent processing system allows one job to use several processors.
• Can execute sets of instructions in parallel.
• It requires programming language and supportive computer systems.
• The sequential computation of an operation is performed on the set: A = 3 * B * C + 4 / (D + E) ** (F – G).
  • Step 1: F-G: Store difference in T1
  • Step 2: D+E: Store sum in T2
  • Step 3: T2 ** T1: Store power in T1
  • Step 4: 4/T1: Store quotient in T2
  • Step 5: 3 * B: Store product in T1
  • Step 6: T1 * C: Store product in T1
  • Step 7: T1 + T2: Store sum in A
• Computation performed concurrently on A = 3 * B * C + 4 / (D + E) ** (F – G):
  • Step 1: run in one process which performs 3*B stores the product in T1
  • Step 2: run in a second process which performs D + E, store sum in T2
  • Step 3: run in a third process which performs F-G, stores the difference in T3
  • Step 4: run on process one which performs T1 * C, stores product in T4:
  • Step 5: run on process two which performs T2 ** T3, store power in T5
  • Step 6: run process 3 to perform 4 / T5, store the quotient in T1
  • Step 7: run on process one which performs T4 + T1 which stores the sum in A

Summary of concurrent processes

• Two-or-more CPU systems use a processor manager to synchronize communication/cooperation.
• System configurations include master/slave and symmetric forms.
• Multiprocessing system success relies on synchronization of resources through mutual exclusion to prevent deadlock.
• Mutual process exclusion is maintained with test-and-set, WAIT, SIGNAL, semaphores (P, V), and mutex
• Processes are synchronized using hardware and software mechanisms to avoid waiting customers.
• Threads and multi-core processors are examples of concurrent processing innovations.
• Threads/multi-core processors require modifications to operating systems.

Threads and Concurrent Programming

• Threads are small units within processes that are scheduled and executed, which minimizes overhead.
• Swapping processes occurs between main memory and secondary storage.
• Each active processed thread has processor registers, a program counter, plus stack and status.
• Shares data area and resources allocated to its process.

Thread States

• Thread states include: creation, ready, running, finished, along with variations such as blocked, delayed, and waiting,
• Operating systems support thread states through:
  • Creating new threads.
  • Setting up thread ready to execute.
  • Delaying or putting threads to sleep, by specified amount of time. .
  • Blocks or suspend threads waiting for I/O completion.
  • Setting/terminating threads to WAIT and release its resources.
  • Scheduling/synchronizing thread execution with semaphores, events, or conditional variables.
• Thread Control Block (TCB) contains information about current status and characteristics of thread.
• Thread Control Blocks contain:
  • Thread identification and state.
  • CPU information. The program counter and registers used by the thread
  • Thread priority and pointers including to the process that create it

Concurrent Programming Languages

• Ada was the first language that provided concurrency commands, and developed in the 1970s..
• Java was designed as a universal Internet application software platform.
• Java was developed by Sun Microsystems, and adopted in commercial and educational environments.

Explore the benefits and challenges of parallel processing. Understand master/slave configurations and symmetric multiprocessing. Learn about process synchronization, critical regions, and locking mechanisms like 'test-and-set'.