Memory & concurrency

paging.py# MODEL: translate virtual pages to physical frames; a miss is a page fault.
class MMU:
    def __init__(self, num_frames):
        self.table = {}                 # virtual page -> frame
        self.free = list(range(num_frames))
        self.faults = 0
    def access(self, page):
        if page in self.table:
            return ("hit", self.table[page])
        self.faults += 1                # page fault: not resident
        if self.free:
            frame = self.free.pop(0)
            self.table[page] = frame
            return ("fault->loaded", frame)
        return ("fault->no-frame", None)  # eviction needed (see Step 2)

mmu = MMU(num_frames=2)
for pg in [1, 1, 2, 3]:
    print(pg, mmu.access(pg))
print("total faults:", mmu.faults)

page_replace.py# MODEL: count page faults for a reference string under three policies.
def simulate(refs, frames, policy):
    mem, faults = [], 0
    for i, page in enumerate(refs):
        if page in mem:
            if policy == "LRU":         # mark as most-recently used
                mem.remove(page); mem.append(page)
            continue
        faults += 1
        if len(mem) < frames:
            mem.append(page); continue
        if policy == "FIFO":
            victim = mem[0]
        elif policy == "LRU":
            victim = mem[0]             # front = least recently used
        else:  # OPTIMAL: page used furthest in the future (or never)
            future = refs[i + 1:]
            victim = max(mem, key=lambda p: future.index(p)
                         if p in future else float("inf"))
        mem.remove(victim); mem.append(page)
    return faults

refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2]
for pol in ("FIFO", "LRU", "OPTIMAL"):
    print(f"{pol:8s} faults={simulate(refs, 3, pol)}")

race.py# REAL threads: this genuinely races. counter += 1 is read-modify-write,
# so concurrent increments lose updates. Output varies per run.
import threading

counter = 0
def bump():
    global counter
    for _ in range(100_000):
        counter += 1            # NOT atomic: read, +1, write

threads = [threading.Thread(target=bump) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print("counter:", counter, "(expected 400000)")

mutex.py# REAL threads: the lock serialises the critical section, so no update is lost.
import threading

counter = 0
lock = threading.Lock()
def bump():
    global counter
    for _ in range(100_000):
        with lock:              # only one thread in here at a time
            counter += 1

threads = [threading.Thread(target=bump) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print("counter:", counter)     # always 400000

bankers.py# MODEL of the banker's algorithm: is the current allocation state SAFE?
# Safe = there exists an order in which all processes can finish.
def is_safe(available, maximum, allocation):
    n = len(maximum)                       # processes
    need = [[maximum[i][j] - allocation[i][j] for j in range(len(available))]
            for i in range(n)]
    work = list(available)
    finish = [False] * n
    order = []
    made_progress = True
    while made_progress:
        made_progress = False
        for i in range(n):
            if not finish[i] and all(need[i][j] <= work[j]
                                     for j in range(len(work))):
                for j in range(len(work)):   # this process can finish; it frees its
                    work[j] += allocation[i][j]  # resources back to the pool
                finish[i] = True
                order.append(i)
                made_progress = True
    return all(finish), order

# 3 resource types, 5 processes (classic textbook state)
available  = [3, 3, 2]
maximum    = [[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]
allocation = [[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]]
safe, order = is_safe(available, maximum, allocation)
print("safe?", safe)
print("safe sequence:", order)

producer_consumer.py# REAL threads: Queue(maxsize=...) blocks the producer when full and the
# consumer when empty, and is internally thread-safe.
import threading, queue

buf = queue.Queue(maxsize=5)
DONE = object()

def producer():
    for i in range(10):
        buf.put(i)              # blocks if buffer is full
    buf.put(DONE)

def consumer(out):
    while True:
        item = buf.get()        # blocks if buffer is empty
        if item is DONE:
            break
        out.append(item)

out = []
p = threading.Thread(target=producer)
c = threading.Thread(target=consumer, args=(out,))
p.start(); c.start(); p.join(); c.join()
print("consumed:", out)