BKSP — Assistant Programmer — Exam: 13.07.2024প্রশ্ন ও সমাধান

A deadlock is a state where two or more processes are each waiting indefinitely for a resource held by another process in the same waiting cycle, so none of them can ever proceed.

graph LR
    P1((Process P1)) -->|holds| R1[Resource R1]
    R1 -->|requested by| P2((Process P2))
    P2 -->|holds| R2[Resource R2]
    R2 -->|requested by| P1

This circular "holds/requests" chain (a Resource Allocation Graph with a cycle) is the classic signature of deadlock: P1 holds R1 and wants R2; P2 holds R2 and wants R1 — neither can proceed.

Deadlock occurs only when all four Coffman conditions hold simultaneously:

Condition	Meaning
Mutual Exclusion	At least one resource must be held in a non-shareable mode
Hold and Wait	A process holds a resource while waiting for another
No Preemption	A resource cannot be forcibly taken away from a process
Circular Wait	A closed chain of processes, each waiting on the next

• Handling strategies: Prevention (break one of the 4 conditions structurally), Avoidance (Banker's Algorithm — grant requests only if the system stays in a safe state), Detection & Recovery (allow deadlocks, detect via cycle-checking, then kill/preempt a process), or simple Ignorance (Ostrich algorithm, used by most general-purpose OSes since deadlocks are rare).

Exam takeaway: deadlock = circular wait for resources satisfying all 4 Coffman conditions; visualise it as a cycle in the Resource Allocation Graph, and remember the 4 conditions are individually necessary but only jointly sufficient.

Quicksort's worst case (O(n²)) happens when pivot selection consistently produces maximally unbalanced partitions — the algorithm degenerates into something as slow as Bubble/Insertion sort.

Why it happens: Quicksort picks a pivot, splits the array into <pivot and >pivot, then recurses on both halves. If the pivot is always the smallest or largest remaining element (e.g. first-element pivot on already-sorted input), one partition has (n−1) elements and the other has 0 — there is no real "divide," so recursion depth becomes n instead of log n.

graph TD
    A["n=5: [1,2,3,4,5], pivot=1"] --> B["Right: [2,3,4,5] (4 elems)"]
    B --> C["pivot=2, Right: [3,4,5] (3 elems)"]
    C --> D["pivot=3, Right: [4,5] (2 elems)"]
    D --> E["pivot=4, Right: [5] (1 elem)"]

Worked example — array [1,2,3,4,5], pivot = first element each pass:

• Pass 1: pivot=1 → right partition of 4 elements
• Pass 2: pivot=2 → right partition of 3 elements
• Pass 3: pivot=3 → right partition of 2 elements
• Pass 4: pivot=4 → right partition of 1 element
• Total comparisons = 4+3+2+1 = 10 = n(n−1)/2 = O(n²)

Recurrence: T(n) = T(n−1) + O(n) → T(n) = O(n²)

• Avoiding it: randomised pivot selection, median-of-three pivot, or switching to Introsort/Heapsort when recursion depth exceeds a threshold — all keep the expected case at O(n log n).

Exam takeaway: Quicksort is O(n²) exactly when every partition is maximally unbalanced (n−1 vs 0) — most likely with a fixed (first/last-element) pivot on sorted or reverse-sorted input; randomised pivot avoids this.