Kaj je krožni medpomnilnik (ring buffer) in kdaj bi ga uporabili?

Question

Accepted Answer

**Krožni medpomnilnik** je polje fiksne velikosti, ki se obnaša, kot da sta njegovega konca povezana v prstan. Dva indeksa — **head** (branje) in **tail** (pisanje) — se napredujeta in zavijata s pomočjo modulo aritmetike, kar daje FIFO vrsto s časovno zahtevnostjo O(1) brez **dodeljevanja pomnilnika** po ustvarjanju.

## Kako deluje zavijanje

```text
capacity 5, after writing A,B,C,D and reading A,B:
index:  0   1   2   3   4
      [ . ][ . ][ C ][ D ][ . ]
              head^       tail^   (tail wraps to 0 next write)
```

## Koda

```python
class RingBuffer:
    def __init__(self, n):
        self.buf = [None]*n
        self.head = self.tail = self.size = 0
        self.cap = n
    def enqueue(self, x):                  # O(1)
        if self.size == self.cap: raise Exception("full")
        self.buf[self.tail] = x
        self.tail = (self.tail + 1) % self.cap   # wrap
        self.size += 1
    def dequeue(self):                     # O(1)
        x = self.buf[self.head]
        self.head = (self.head + 1) % self.cap    # wrap
        self.size -= 1
        return x
```

| Operacija | Čas |
|---|---|
| enqueue / dequeue | O(1) |
| prostor | O(n) fiksno |

## Kdaj ga uporabiti

- **Pretakanje / avdio / video medpomnilniki** — omejeni, enakomerni pretok.
- **Proizvajalec–potrošnik** cevovodi s povratnim tlakom.
- **Beleženje zadnjih N dogodkov** (prepisovanje najstarejšega).

## Zakaj je to pomembno

Krožni medpomnilnik zagotavlja napovedljivo, brez dodeljevanja FIFO vedenje, ki je bistveno v sistemih real-time in vgrajenih sistemih, kjer je dinamično dodeljevanje premalo hitro ali tvegano.

Njegova omejena velikost deluje tudi kot naravni povratni tlak, ki preprečuje hitrim proizvajalcem, da izčrpajo pomnilnik.