Pyöreä puskuri - Circular buffer
In Computer Science , joka on pyöreä puskuri , pyöreä jono , syklisen puskurin tai rengas puskuri on tietorakenne , joka käyttää yhtä, kiinteän koko puskuri kuin jos se olisi kytketty end-to-end. Tämä rakenne soveltuu helposti puskuroitaviin tietovirtoihin .
Yleiskatsaus
Pyöreä puskuri alkaa ensin tyhjänä ja sillä on asetettu pituus. Alla olevassa kaaviossa on 7-elementtinen puskuri:
Oletetaan, että 1 on kirjoitettu pyöreän puskurin keskelle (tarkka aloituspaikka ei ole tärkeä pyöreässä puskurissa):
Oletetaan sitten, että pyöreään puskuriin lisätään kaksi muuta elementtiä - 2 & 3 - jotka lisätään 1: n jälkeen:
Jos kaksi elementtiä poistetaan, pyöreän puskurin kaksi vanhinta arvoa poistetaan. Pyöreät puskurit käyttävät FIFO ( first in, first out ) -logiikkaa. Esimerkissä 1 ja 2 tulivat ensimmäisenä pyöreään puskuriin, ne poistettiin ensimmäisinä, jättäen 3 puskurin sisään.
Jos puskurissa on 7 elementtiä, se on täysin täynnä:
Pyöreän puskurin ominaisuus on, että kun se on täynnä ja seuraava kirjoitus suoritetaan, se alkaa korvata vanhimmat tiedot. Nykyisessä esimerkissä lisätään kaksi muuta elementtiä - A & B - ja ne korvaavat 3 ja 4:
Vaihtoehtoisesti puskuria hallitsevat rutiinit voivat estää tietojen korvaamisen ja palauttaa virheen tai aiheuttaa poikkeuksen . Päätetäänkö tietojen korvaaminen vai ei, puskurirutiinien semantikasta tai pyöreää puskuria käyttävästä sovelluksesta.
Lopuksi, jos kaksi elementtiä on nyt poistettu, palautettava ei ole 3 & 4 vaan 5 & 6, koska A & B kirjoitti 3 & 4, jolloin puskuri saatiin:
Käyttää
Pyöreän puskurin hyödyllinen ominaisuus on, että sen elementtejä ei tarvitse sekoittaa ympäri, kun niitä kulutetaan. (Jos käytettäisiin ei-pyöreää puskuria, kaikki elementit olisi siirrettävä, kun niitä kulutetaan.) Toisin sanoen pyöreä puskuri sopii hyvin FIFO -puskuriksi ( ensin sisään, ensin ulos ), kun taas vakio, ei-pyöreä puskuri sopii hyvin LIFO -puskuriksi ( viimeinen sisään, ensimmäinen ulos ).
Pyöreä puskurointi on hyvä toteutusstrategia jonolle, jolla on kiinteä enimmäiskoko. Jos jonolle hyväksytään enimmäiskoko, pyöreä puskuri on täysin ihanteellinen toteutus; kaikki jonotoiminnot ovat vakioaikaa. Pyöreän puskurin laajentaminen vaatii kuitenkin muistin siirtämistä, mikä on suhteellisen kallista. Jos haluat laajentaa mielivaltaisesti jonoja, linkitetty luettelomenetelmä voi olla sen sijaan parempi.
Joissakin tilanteissa voidaan käyttää pyöreää puskuria, esimerkiksi multimediassa. Jos puskuria käytetään rajattuna puskurina tuottaja-kuluttaja-ongelmassa, on todennäköisesti toivottavaa, että tuottaja (esim. Äänigeneraattori) korvaa vanhat tiedot, jos kuluttaja (esim. Äänikortti ) ei pysty hetkellisesti pysymään . Myös häviöttömien tietojen pakkausalgoritmien LZ77 -perhe toimii olettamuksella, että äskettäin datavirrassa nähtyt merkkijonot esiintyvät todennäköisemmin pian virrassa. Toteutukset tallentavat uusimmat tiedot pyöreään puskuriin.
Pyöreä puskurimekaniikka
Pyöreä puskuri voidaan toteuttaa käyttämällä neljää osoitinta tai kahta osoitinta ja kahta kokonaislukua:
- puskurin käynnistys muistissa
- puskurin loppu muistissa tai puskurikapasiteetti
- kelvollisten tietojen (indeksi tai osoitin) alku
- kelvollisten tietojen loppu (indeksi tai osoitin) tai puskurissa olevan datan määrä (kokonaisluku)
Tässä kuvassa näkyy osittain täysi puskuri:
Tässä kuvassa näkyy täysi puskuri, joka on korvattu neljällä elementillä (numerot 1-4):
Kun elementti korvataan, aloitusosoitin lisätään seuraavaan elementtiin.
Kun puskurin kapasiteettia käytetään osoitinpohjaisella toteutusstrategialla, puskurin täyttä tai tyhjää tilaa ei voida ratkaista suoraan tarkistamalla alku- ja loppuindeksien sijainnit. Siksi on otettava käyttöön lisämekanismi tämän tarkistamiseksi. Yksi yleinen tapa käsitellä tätä, kun käytetään 2 osoitinta, on sallia puskurin pitää vain (koko - 1) kohteita. Kun molemmat osoittimet ovat yhtä suuret, puskuri on tyhjä, ja kun pääteosoitin on yksi vähemmän kuin aloitusosoitin, puskuri on täynnä.
Kun puskuri on sen sijaan suunniteltu seuraamaan lisättyjen elementtien lukumäärää n , tyhjyyden tarkistaminen tarkoittaa n = 0 tarkistamista ja täyteyden tarkistamista, onko n yhtä suuri kuin kapasiteetti.
Pyöreän puskurin osoitinosoitinten lisääminen ja vähentäminen suoritetaan ohjelmistossa käyttämällä seuraavia moduulikaavoja:
increment_address_one = (address + 1) % Length
decrement_address_one = (address + Length - 1) % Length
In kielillä joiden modulo-operaattori soveltaa katkaistu jako , ylimääräinen pituus lisäksi, että vähennys yhden toiminta on tarpeen, jotta estetään tuloksia ja varmistamaan kaatuessa loppuun osoite pyöreän puskuria.
Optimointi
Pyöreän puskurin toteutus voidaan optimoida kartoittamalla taustalla oleva puskuri kahteen virtuaalimuistin viereiseen alueeseen . (Luonnollisesti taustalla olevan puskurin pituuden on tällöin vastattava jonkin verran järjestelmän sivukoon monikertaa .) Pyöreästä puskurista lukeminen ja kirjoittaminen siihen voidaan suorittaa tehokkaammin suoran muistin avulla; ne käyttöoikeudet, jotka jäävät ensimmäisen virtuaalimuistialueen lopun ulkopuolelle, kiertyvät automaattisesti taustalla olevan puskurin alkuun. Kun lukuero on siirretty toiselle virtuaalimuistialueelle, molemmat siirtymät-luku ja kirjoitus-pienenevät taustalla olevan puskurin pituuden mukaan.
Kiinteäpituinen elementti ja vierekkäinen lohko pyöreä puskuri
Ehkä yleisin pyöreän puskurin versio käyttää 8-bittisiä tavuja elementeinä.
Joissakin toteutuksissa pyöreän puskurin käyttö samanpituisia elementtejä, jotka ovat suurempia kuin 8-bittistä tavua-16-bittisiä kokonaislukuja audio- puskureita, 53-tavun ATM-solut tietoliikenne- puskureita, jne. Jokainen tuote on vierekkäisiä ja on oikea data linjaus , joten ohjelmistojen lukeminen ja kirjoittaminen näihin arvoihin voi olla nopeampaa kuin ohjelmisto, joka käsittelee vierekkäisiä ja kohdistamattomia arvoja.
Ping-pong-puskurointia voidaan pitää hyvin erikoistuneena pyöreänä puskurina, jossa on täsmälleen kaksi suurta kiinteän pituista elementtiä.
The bip buffer (bipartite buffer) is very similar to a circular buffer, except it always returns contiguous blocks which can be variable length. This offers nearly all the efficiency advantages of a circular buffer while maintaining the ability for the buffer to be used in APIs that only accept contiguous blocks.
Kiinteäkokoiset pakatut pyöreät puskurit käyttävät vaihtoehtoista indeksointistrategiaa, joka perustuu peruslukuteoriaan ylläpitääkseen kiinteän kokoisen pakatun esityksen koko datasekvenssistä.