Untitled Quiz

Section 6: Synchronization Tools

• Synchronization problems, such as the Critical-Section Problem, exist
• Synchronization solutions involve:
  • Hardware instructions
  • Mutex locks
  • Binary semaphores
  • Counting semaphores
  • Monitors
• Synchronization tools are used for synchronization examples

Objectives

• Introduces the critical-section problem and its solutions for maintaining shared data consistency
• Explains software and hardware synchronization primitives
• Details different synchronization issues and solution methods using primitives

Background/Motivation

• Cooperating processes/threads access shared data concurrently
• Concurrent access can lead to data inconsistency if not managed properly
• Maintaining data consistency requires mechanisms for orderly execution of cooperating threads

Race Conditions/Critical Sections

• Race conditions occur when multiple threads try to update a shared variable concurrently, leading to unpredictable results
  • Example scenarios and execution sequences illustrating critical sections

The Data Consistency Problem

• Illustrates a program where multiple threads update a shared variable (sum)
• Details how race conditions can lead to incorrect results in concurrent programming

Producer/Consumer Problem

• A producer thread produces data and places it in a buffer
• A consumer thread consumes data from the buffer
• Synchronization is needed to prevent problems like buffer being empty or full at the wrong time
• A solution involves a shared variable (count) and synchronization mechanisms
• Illustrated code snippets of both producer and consumer with critical sections

Race Conditions

• Race conditions occur when multiple threads concurrently access and modify a shared variable
• The solution example demonstrates how the shared variable count can be updated incorrectly due to concurrent access by threads

Critical Section

• A critical section is a segment of code that only one thread can execute at a time to prevent race conditions
• A program needs a mechanism to avoid race conditions from occurring in critical sections
• Illustrations demonstrating synchronization problems using critical sections and possible solutions

Critical-Section Solutions

• Mutual Exclusion: Only one thread can execute in the critical section at a time
• Progress: If no thread is in the critical section and a thread wants to enter, the request cannot be postponed indefinitely
• Bounded Waiting: A bound must exist on the maximum number of times that other threads are allowed to enter the critical section

Hardware Synchronization Primitive: test&set()

• test&set() can be used to implement a critical section.
• Atomically test and set an atomic flag lock to prevent race conditions
• Provides mutual exclusion for access to critical sections.
• Description of the pseudo-code for test&set()

Hardware Instructions

• Computer systems provide hardware instructions for atomic operations on memory locations, such as test&set and compare&swap to prevent race conditions in critical sections.
• Description of pseudo-code for compare&swap

Test&set() Application

• Describes how to implement critical sections using the test&set() instruction
• Demonstrates the test&set() function
• Demonstrates example of code implementation

Test&set() Fails Bound-Waiting Condition

• test&set() does not guarantee bounded waiting, that is the order of which threads are granted entry
• A modified version of test&set() needs to guarantee bounded waiting, such that threads don’t have to wait infinitely
• A new version of test&set() to guarantee a bound on waiting times, along with shared data structures

Bounded-waiting test_and_set()

• An improved test&set() method that guarantees bounded waiting
• Includes a waiting array and illustrative code

Bounded-waiting Mutual Exclusion with TestAndSet()

• Describes how the test&set() method can be modified to solve the bounded waiting problem.
• Ensuring mutual exclusion among threads accessing a shared resource, while guaranteeing that threads won't wait indefinitely.

Hardware Synchronization Primitive: compare&swap()

• Introduces the compare&swap primitive. Illustrates implementation details and the compare&swap method's use case for mutual exclusion in critical sections. Shows an illustrative example of how code uses compare&swap

Compare&swap (cas): Definition

• How the compare&swap operation works and its rationale for mutual exclusion in critical sections.

cas(): Application

• Illustrative implementation of how cas() is used in critical sections
• Shows how to control access to a critical section using the cas() function.

cas() Fails Bound-Waiting Condition

• cas does not inherently guarantee bounded waiting in concurrent access to a critical section.
• Modifying compare&swap to allow for bounded wait

Example: Atomic Adder

• Illustrative implementation of an atomic adder function using cas()

Atomic Adder Explained

• Detailed explanation of the atomic adder function, its functionality and how cas is used in function

Producer/Consumer Problem

• Using AtomicAdd and AtomicSubtract to handle race conditions while updating the count variable, thus guaranteeing correctness when used in the solution to producer/consumer problems

Hardware Synchronizations

• Describes how hardware primitives like test-&-set, compare-&-swap typically are not directly used in high level languages, and how to use assembler to access them
• Discusses the atomic type and its use when updating shared variables correctly even with concurrency

Software Synchronization Primitives: Mutex Locks

• Discusses how operating systems use higher-level software primitives for synchronization using hardware primitives
• Introduces mutex synchronization objects
• Explains a mutex lock's behavior

Mutex Lock

• Discusses a mutex lock's structure.
• Explains how threads using mutex locks should acquire and release the lock when entering and exiting critical sections.
• Explain that Acquire and release should be atomically

POSIX/Linux Mutex Lock

• Describes POSIX mutex locks used in Linux systems
• Shows example of how to initialize and use mutexes
• Explains the use of function calls to acquire and release mutexes. Introduces pthread_mutex_init

Locks and Scheduling

• Describes the scheduling behaviour of different operating systems
• Discusses how concurrent threads accessing critical sections can be managed in relation to scheduling algorithms

Spinning and Blocking Locks

• Distinguishes between "spinning" and "blocking" mutex implementations in software synchronizations
• Discusses the trade-offs between the two approaches, including their strengths, weaknesses, and appropriate situations to use each
• Illustrative examples demonstrating which conditions a 'spinning' or 'blocking' approach is appropriate under

Mutex: Final Words

• Describes the scope of mutexes, whether they are usable for inter-processes synchronization, and why that can be more complicated and semaphores might be more suitable

Semaphores

• Definitions of wait and signal operations in the context of a semaphore, including their associated queues
• Illustrative examples of the use of semaphores for synchronization problems and their behavior

Semaphore Implementation

• Describes an implementation of semaphores using waiting queues
• Details the structure of a semaphore, including its value and associated waiting queue

Semaphore Implementation

• Detailed explanation of the operations for semaphores, including how a semaphore is blocked and woken up, and use cases for their use cases in synchronization issues

Blocking Semaphores

• Negative semaphore values indicate the number of threads waiting on that semaphore
• Semaphore queues can be implemented as FIFO queues

Semaphores in Linux

• Linux uses System V IPC semaphores (named and unnamed) and POSIX semaphores.
• Description of the systema V semaphore

System V Semaphores

• Description of system V semaphores from Unix OSs
• Describes semget and semop operations. Explains the ipcs and ipcrm shell commands for managing system V semaphores and why they are costly and complicated to use

Named Posix Semaphores

• Details the concept of named Posix semaphores as files in the filesystem
• Discusses methods for creating and deleting named semaphores

Unnamed Posix Semaphores

• Describes unnamed Posix semaphores
• Illustrate situations to use unnamed Posix semaphores
• Explains how they are suitable for use in multithreading

Unnamed Posix Semaphores

• Describes how unnamed Posix semaphores are defined and used
• Include examples for initialization and use

Category of Semaphores

• Explains binary and counting semaphores, including the types of values that they can contain
• Discusses how the value range is a significant difference between the two types

Binary and Counting Semaphores

• Illustrative examples of binary and counting semaphore declarations in standard operating systems like Linux, Windows, and Java

Example of Binary Semaphore Usage

• Illustrative example of binary semaphore usage for thread synchronization

Exercise with Bin Semaphores

• Provides a practical exercise using binary semaphores
• Descriptions of the examples

Solution

• Includes detailed explanation and illustrative example of thread synchronization using binary semaphores, provided semaphores

Mutex unlock() versus Semaphore signal()

• Distinction between mutexes and semaphores, particularly how they differ in terms of who can release a lock or signal a condition
• Discusses a scenario using a binary semaphore for thread synchronization

Usage of Counting Semaphores

• Managing resources like shared data, and how counting semaphores can limit the number of threads accessing a resource
• Describes the role in threads and resources, and a hypothetical example of controlling the maximum number of open files a process can have

The Toilet Analogy

• Illustrative analogy of counting semaphores using the concepts of toilets and keys
• Explains scenarios using counting semaphores with related considerations for synchronization.

Two Applications of Semaphores

• Brief descriptions of two applications, bounded buffer problems and reader-writer problems, and how counting semaphores are useful.

Bounded-Buffer Problem

• Description of the bounded buffer problem and how сеmaphores can solve it efficiently
• Illustrative example showing different components of a solution for this problem.

Bounded Buffer Problem (Cont.)

• Detailed code descriptions of both producer and consumer threads for the bounded buffer problem using semaphores

Bounded Buffer Problem (Cont.)

• Illustrative examples of consumer and producer code using semaphores.

Running the Threads

• An example of a complete solution using producer and consumer code

Readers-Writers Problem

• Description of the readers-writers synchronization problem
• Discussion of the requirements for readers and writers to access shared data concurrently without errors

Readers-Writers Problem (Cont.)

• Description of variables and processes used in a solution for the readers-writers problem, such as binary semaphores
• Description of how read_count works for readers and rw_mutex for writer processes accessing shared data

Readers-Writers Problem (Cont.)

• Description of writer and reader code illustrating concurrent access

Semaphores: Potential Problems

• Discusses potential issues of incorrect semaphore usage
• Includes illustrative examples of the problems/errors in coding

Deadlock

• Introduction to the deadlock concept in operating systems
• Discusses conditions in which it occurs, particularly with regard to concurrent processes and semaphores

Deadlock again

• An explanation of a scenario in a program where replacing a mutex signal with wait instruction can still lead to deadlocks
• Demonstrates scenarios where this can happen

Monitors

• Definition of monitors as objects with shared data and methods
• Describes why languages like C/C++ do not contain monitors and how it can be implemented using their primitives

Particularity of Monitors

• A summary of monitors as classes protected by a mutex variable
• Description of how to manage thread execution in critical sections

Definition of a Monitor Class

• Explanation of a monitor's structural components, including instance variables, entry queue, and method implementations
• Description of the basic structure of monitors

Possible Implementation of Account

• A possible implementation of the account class in C++
• Implementation to allow thread safety when multiple threads need to access a shared resource or variable

Condition Variables

• Discussion of how condition variables are used in monitors, allowing threads to block on conditions and resume when those conditions are met
• Explanation of potential problems, such as synchronization error
• Illustrative example for better understanding

Condition Variables

• Detailed description of the wait and signal operations in a condition variable. Emphasizes the purpose of the condition variable queue associated with them.

Monitor with Condition Variables

• Illustrative demonstration of using condition variables to solve the producer-consumer problem in scenarios

signal() on a Condition Variable

• Further elaborates on the 'signal' operation associated with condition variables, emphasizing thread activation and the avoidance of mutual exclusion issues

Implementation of fct wait()

• Detailed implementation of the wait function associated with a condition variable, emphasizing its use in a mutex and related semaphores

Implementation of fct signal()

• Detailed description of the signal function associated with the condition variable, and use case and explanation
• Discussion of next count and the use of the binary semaphore next for thread suspending

Full Implementation of Monitors

• Complete implementation of a monitor including its condition variables, entry queue, methods (add/remove), and the critical sections handling thread access to them

Condition Variables: Example

• Providing a detailed example of how condition.variables can be implemented for scenarios such as the producer and consumer problem

Monitor Class for Producer/Consumer

• Illustrative ProducerConsumer class example that contains the methods add and remove, along with associated condition and mutex variables

Threads for Producer/Consumer

• Describes how threads can call the monitor methods ( add and remove ) from outside the monitor

Posix Condition Variables

• Explanation of POSIX condition variables and their utility in C programming
• Description of how POSIX condition variables can be used in C programming, with detailed wait and signal function descriptions

Simulating Monitors with Posix Conditions

• Illustrative example in C programming to demonstrate how to simulate monitor behavior using POSIX thread and condition variable features to prevent synchronization errors

End of Section 6

Inter-processes Communication: Shared Memory Segments

• Definition of inter-processes communication, shared memory communication, shared memory segments

Examples of IPC Systems - POSIX

• Examples of creating, attaching, and detaching shared memory segments using shmget, shmat, and shmdt functions.

Shared-Memory Server

• Description of the server-side code for establishing shared memory for communication with other processes

Shared-memory Client

• Description of the client-side code for using shared memory for communication with the server process