ডেডলক ডিটেকশন ও রিকভারি

# ডেডলক ডিটেকশন -- L23-এর ৫ ফিলোসফার/৫ ফর্ক দৃশ্যকে Allocation/Request ম্যাট্রিক্স হিসেবে মডেল করা

n = 5
allocation = [[0] * n for _ in range(n)]
request = [[0] * n for _ in range(n)]
for i in range(n):
    allocation[i][i] = 1              # Pi ইতিমধ্যে fork i (তার বাম ফর্ক) ধরে আছে
    request[i][(i + 1) % n] = 1       # Pi fork (i+1)%n (তার ডান ফর্ক) চেয়ে অপেক্ষমাণ

total_instances = [1] * n             # প্রতিটি ফর্কের মাত্র ১টি instance
allocated_per_resource = [sum(allocation[i][j] for i in range(n)) for j in range(n)]
available = [total_instances[j] - allocated_per_resource[j] for j in range(n)]

def detect_deadlock(available, allocation, request):
    """L25-এর সেফটি অ্যালগরিদমেরই একটি রূপ -- Need-এর বদলে বর্তমান outstanding Request ব্যবহার করে,
    ইতিমধ্যে ডেডলক ঘটে গেছে কি না তা যাচাই করে। রিটার্ন করে ডেডলকড প্রসেসের index-তালিকা।"""
    n_proc = len(allocation)
    n_res = len(available)
    work = list(available)
    finish = [all(a == 0 for a in allocation[i]) for i in range(n_proc)]  # কোনো allocation নেই = সম্পন্ন ধরা হলো

    progress = True
    while progress:
        progress = False
        for i in range(n_proc):
            if finish[i]:
                continue
            if all(request[i][j] <= work[j] for j in range(n_res)):
                for j in range(n_res):
                    work[j] += allocation[i][j]
                finish[i] = True
                progress = True

    return [i for i in range(n_proc) if not finish[i]]

print("Available:", available)
deadlocked = detect_deadlock(available, allocation, request)
print("ডেডলকড প্রসেস:", [f"P{i}" for i in deadlocked] if deadlocked else "কেউ না")

print("\n--- রিকভারি: P0-কে ভিকটিম হিসেবে বেছে টার্মিনেট করা হলো ---")
victim = 0
rec_available = list(available)
rec_allocation = [row[:] for row in allocation]
rec_request = [row[:] for row in request]

for j in range(n):
    rec_available[j] += rec_allocation[victim][j]   # ভিকটিমের ধরে-রাখা রিসোর্স ফেরত এলো
    rec_allocation[victim][j] = 0
    rec_request[victim][j] = 0                      # ভিকটিমের অনুরোধও বাতিল

print(f"P{victim} টার্মিনেট করার পর Available: {rec_available}")
deadlocked_after = detect_deadlock(rec_available, rec_allocation, rec_request)
if deadlocked_after:
    print("তবুও ডেডলকড প্রসেস:", [f"P{i}" for i in deadlocked_after])
else:
    print("এখন কেউ ডেডলকড নেই -- বাকি সবাই ক্রমান্বয়ে সম্পন্ন হতে পারবে")