Mansoura University

• Second Semester- 2023-2024
• Department of Computer Science
• Faculty of Computers and Information
• [CS211P] Operating System (1)
• Grade : 2
• Week : 6
• Eng. Asmaa Naguib

C# Synchronization and Deadlock

Agenda

• Introduction
• Ticket Reservation Example.
• Thread Synchronization methods.
• Bounded Buffer Producer and Consumer Example.
• Deadlock.
• Dining Philosophers Example.
• 3

Introduction

• Dual Core and Quad Core (Multi-Core):
• Dual Core: PC has two processors.
• Quad Core: PC has four processors.
• Multi Processing:
• One processor contains multi ALU (Arithmetic and Logic Unit).
• Multi Tasking:
• One Processor can switch from one process to another through Context Switch.
• Context Switch is the process of storing the state of one process, so that it can be reloaded and resume execution later.
• i7 vs i5 vs i3:
• 7, 5, 3 don’t mean the number of cores.
• They are related to the performance of processor (including Clock Speed).
• Processor in i7 is faster than in i5 which is faster than in i3.
• 4

Introduction

• Clock Speed:
• It measures the number of cycles your CPU executes per second, measured in GHz.
• Example, CPU with a clock speed 3.2 GHz executes 3.2 billion cycles per second.
• Processor Clock Cycle:
• Sometimes, multiple instructions are completed in a single clock cycle.
• In other cases, one instruction might be handled over multiple clock cycles.
• C# supports parallel execution of code through multithreading.
• Multithreading Problem:
• Threads can share data (they have a common reference to the same object instance).
• Solution:
• Thread synchronization.
• 5

Ticket Reservation Example

• 6
• Shared variable
• Output:
• The same ticket is sold twice

Ticket Reservation Example

• 7
• Shared variable
• Critical Section

Ticket Reservation Example

• 1
• 2
• 3
• 8

Thread 1

• Thread 2
• 1. If (Tickets>0)
• 2a. Register = Tickets
• 2b. Decrement register
• 2c. Tickets = register
• 3. Print “Tickets”
• 1. If (Tickets>0)
• 2a. Register = Tickets
• 2b. Decrement register
• 2c. Tickets = register
• 3. Print “Tickets”
• One Processor
• True
• True
• R = 6
• R = 6
• R = 5
• R = 5
• Tickets = 5
• Tickets = 5
• Print 5
• Print 5
• X
• Ticket is sold twice
• EX: Number of Tickets =6
• 9

Thread Synchronization methods

• Critical section:
• It is a code segment where the shared variable can be accessed.
• An atomic action is required in a critical section (i.e., only one thread can execute the critical section at a time).
• Critical section can be atomic using thread synchronization.
• Thread synchronization methods:
• Lock
• Mutex
• Monitor
• Semaphore
• 10

Thread Synchronization methods

• Lock:
• Exclusive locking ensures that only one thread can enter a critical section at a time.
• Mutex:
• Like lock method, it is exclusive locking.
• It is slower than the lock method.
• It uses WaitOne and ReleaseMutex methods to acquire and release the lock.
• Monitor:
• Like mutex and lock methods (exclusive locking).
• It uses Monitor.Enter and Monitor.Exit methods to acquire and release the lock.
• Semaphore:
• It allows a specified number of threads to enter a critical section.
• A semaphore with a capacity of one thread is called Binary Semaphore and it is similar to a lock, mutex, and monitor.
• A semaphore with a capacity more than one thread is called General Semaphore.
• 11

Thread Synchronization (Lock)

• 12
• Output:

Thread Synchronization (Mutex)

• 13
• Output:

Thread Synchronization (Monitor)

• 14
• Output:

Thread Synchronization (Binary Semaphore)

• 15
• Output:

Thread Synchronization (General Semaphore)

• Bounded Buffer Producer and Consumer Example:
• Buffer is a stack (LIFO).
• Consumer can consume items only when producer produces them.
• When the buffer is completely full, producer cannot produce item.
• Producer and consumer must not access the shared buffer at the same time.
• 16
• D | Z | Y | X | | | | | |
• Producer
• Consumer
• Full = 4
• Empty = 6

Bounded Buffer Producer and Consumer Example

• 17
• Output:

Deadlock

• Deadlock is a situation that occurs when any process enters a waiting state because another waiting process is holding the demanded resource.
• Example: Dining Philosophers Problem
• 18

Dining Philosophers Example

• 19

Dining Philosophers Example

• 20
• Deadlock occurs when each philosopher picks the right fork at the same time

Dining Philosophers Example

• 21
• Deadlock occurs when each philosopher picks the right fork at the same time
• Philosopher 1
• Philosopher 2
• One Processor
• Philosopher 3
• Philosopher 4
• Philosopher 5
• 1. Take fork 1
• 2. Wait fork 5
• 1. Take fork 2
• 2. Wait fork 1
• 1. Take fork 3
• 2. Wait fork 2
• 1. Take fork 4
• 2. Wait fork 3
• 1. Take fork 5
• 2. Wait fork 4
• Waiting
• Waiting
• Waiting
• Waiting
• Waiting
• Deadlock

Dining Philosophers Example

• Some of the ways to avoid deadlock are as follows:
• There should be at most four philosophers on the table.
• An even philosopher should pick the right fork and then the left fork while an odd philosopher should pick the left fork and then the right fork.
• A philosopher should only be allowed to pick their forks if both are available at the same time.
• 22

Dining Philosophers Example (Deadlock Solution)

• 23
• A philosopher picks their forks if both are available at the same time

Any Question ?

• Next ….
• 24