Starvation و Livelock – دو مشکل رایج در برنامه‌نویسی همروند

مقدمه

تا اینجا با Deadlock آشنا شده‌اید: حالتی که چند ترد یا پردازه برای همیشه منتظر منابعی می‌مانند که هرگز آزاد نمی‌شوند. اما قفل‌شدگی تنها مشکل ممکن در برنامه‌های همروند نیست. دو مشکل دیگر که کمتر شناخته شده‌اند ولی به همان اندازه آزاردهنده‌اند، Starvation (گرسنگی منابع) و Livelock هستند. در این درس با تعریف، علت و نمونه‌ی کد هر کدام آشنا می‌شوید.

Starvation چیست؟

Starvation زمانی رخ می‌دهد که یک ترد هیچ‌وقت قفل یا منبعی را که نیاز دارد به دست نمی‌آورد، چون تردهای دیگر همیشه زودتر از آن منبع را می‌گیرند. برخلاف Deadlock، در اینجا برنامه به طور کلی متوقف نشده و بقیه‌ی تردها به خوبی کار می‌کنند؛ فقط یک یا چند ترد بدشانس هیچ‌وقت نوبتشان نمی‌رسد.

import threading
import time

lock = threading.Lock()
counter = 0

def greedy_worker(worker_id):
    global counter
    for _ in range(5):
        with lock:
            counter += 1
            time.sleep(0.05)
        print(f'greedy-{worker_id}: got the lock, counter={counter}')

def unlucky_worker():
    for _ in range(5):
        acquired = lock.acquire(timeout=0.2)
        if acquired:
            try:
                print('unlucky: finally got the lock')
            finally:
                lock.release()
        else:
            print('unlucky: timed out waiting for the lock')

threads = [threading.Thread(target=greedy_worker, args=(i,)) for i in range(3)]
threads.append(threading.Thread(target=unlucky_worker))
for t in threads:
    t.start()
for t in threads:
    t.join()

import threading
import time

lock = threading.Lock()
counter = 0

def greedy_worker(worker_id):
    global counter
    for _ in range(5):
        with lock:
            counter += 1
            time.sleep(0.05)
        print(f'greedy-{worker_id}: got the lock, counter={counter}')

def unlucky_worker():
    for _ in range(5):
        acquired = lock.acquire(timeout=0.2)
        if acquired:
            try:
                print('unlucky: finally got the lock')
            finally:
                lock.release()
        else:
            print('unlucky: timed out waiting for the lock')

threads = [threading.Thread(target=greedy_worker, args=(i,)) for i in range(3)]
threads.append(threading.Thread(target=unlucky_worker))
for t in threads:
    t.start()
for t in threads:
    t.join()

در این مثال، سه ترد greedy_worker پشت سر هم و با فاصله‌ی کم قفل را می‌گیرند، در حالی که unlucky_worker اغلب با timeout مواجه می‌شود چون هر بار که می‌خواهد قفل را بگیرد، یکی از تردهای دیگر زودتر رسیده است. در برنامه‌های واقعی، این الگو معمولاً ناشی از زمان‌بندی نامناسب، اولویت‌دهی اشتباه بین تردها، یا ترتیب ثابت و قابل پیش‌بینی در گرفتن قفل‌هاست.

Livelock چیست؟

Livelock شبیه Deadlock است با یک تفاوت مهم: تردها مسدود (blocked) نیستند و دائماً در حال کار کردن‌اند، اما این کار هیچ پیشرفتی در نتیجه‌ی نهایی ایجاد نمی‌کند. تصویر کلاسیک آن دو نفر در یک راهرو هستند که هر دو برای رد شدن به یک طرف کنار می‌روند، می‌بینند راه هنوز بسته است، هر دو به طرف دیگر کنار می‌روند، و این رفتار تا ابد تکرار می‌شود.

import threading
import time

lock_a = threading.Lock()
lock_b = threading.Lock()

def polite_worker(first, second, name):
    for _ in range(3):
        while True:
            first.acquire()
            if second.acquire(blocking=False):
                print(f'{name}: acquired both locks')
                second.release()
                first.release()
                break
            else:
                first.release()
                print(f'{name}: backing off to be polite')
                time.sleep(0.01)

t1 = threading.Thread(target=polite_worker, args=(lock_a, lock_b, 'worker-1'))
t2 = threading.Thread(target=polite_worker, args=(lock_b, lock_a, 'worker-2'))
t1.start()
t2.start()
t1.join()
t2.join()

import threading
import time

lock_a = threading.Lock()
lock_b = threading.Lock()

def polite_worker(first, second, name):
    for _ in range(3):
        while True:
            first.acquire()
            if second.acquire(blocking=False):
                print(f'{name}: acquired both locks')
                second.release()
                first.release()
                break
            else:
                first.release()
                print(f'{name}: backing off to be polite')
                time.sleep(0.01)

t1 = threading.Thread(target=polite_worker, args=(lock_a, lock_b, 'worker-1'))
t2 = threading.Thread(target=polite_worker, args=(lock_b, lock_a, 'worker-2'))
t1.start()
t2.start()
t1.join()
t2.join()

هر دو ترد سعی می‌کنند مودبانه رفتار کنند: اگر قفل دوم در دسترس نباشد، قفل اول را آزاد می‌کنند و دوباره تلاش می‌کنند. مشکل این است که چون هر دو ترد دقیقاً همین رفتار را با زمان‌بندی مشابه دارند، ممکن است بارها همزمان قفل اول را بگیرند، ببینند قفل دوم گرفته شده، و هر دو کنار بکشند – دقیقاً مثل آن دو نفر در راهرو. برنامه هیچ‌وقت Exception نمی‌دهد و CPU هم در حال کار کردن است، اما پیشرفت واقعی صفر یا نزدیک به صفر می‌ماند.

تفاوت Livelock با Deadlock

• در Deadlock، تردها متوقف (blocked) می‌مانند و هیچ کاری انجام نمی‌دهند.
• در Livelock، تردها فعال هستند، کد اجرا می‌کنند و حتی منابع CPU مصرف می‌کنند، اما به نتیجه‌ی مفیدی نمی‌رسند.
• تشخیص Deadlock معمولاً ساده‌تر است چون برنامه کاملاً می‌ایستد؛ تشخیص Livelock سخت‌تر است چون برنامه ظاهراً «در حال کار کردن» به نظر می‌رسد.

راه‌حل‌ها

• برای Starvation: استفاده از قفل‌های fair (که نوبت تردها را به ترتیب رسیدن رعایت می‌کنند)، یا تعیین سهمیه و timeout مشخص برای هر ترد.
• برای Livelock: افزودن یک تاخیر تصادفی (random backoff) به جای تاخیر ثابت، تا تردها همگام نمانند و رفتار یکسانی تکرار نکنند.
• در هر دو مورد: ساده نگه داشتن ترتیب گرفتن قفل‌ها (مثلاً همیشه طبق یک ترتیب ثابت سراسری) معمولاً از ریشه مشکل را حل می‌کند.

جمع‌بندی

Deadlock، Starvation و Livelock هر سه از خانواده‌ی مشکلات همگام‌سازی هستند، اما نشانه‌های متفاوتی دارند: یکی برنامه را کاملاً متوقف می‌کند، یکی فقط چند ترد بدشانس را نادیده می‌گیرد، و سومی برنامه را در حالتی نگه می‌دارد که کار می‌کند ولی به جایی نمی‌رسد. شناخت این تفاوت‌ها به شما کمک می‌کند علامت‌های درست را در لاگ‌ها و رفتار برنامه‌ی واقعی تشخیص دهید.