En computer består af ...

...en centralenhed, et internt lager og et eksternt lager.

Sådan har der stået i alle de bøger jeg har kunnet finde om programmering og jeg tog mig faktisk tid til at pløje igennem en hel stribe i denne weekend da lejlighed bød sig på KTH i Stockholm.

Der er bare et problem med den beskrivelse: Det passer ikke hvis man er programmør.

Virtual Memory

Virtuel hukommelse blev opfundet i 1959 af Tom Kilburn mens han arbejdede på ATLAS projektet i Manchester.

IBM mainframes adopterede det i en ung alder og fra ca. 1980 og 3BSD distributionen har alle relevante UNIX dialekter brugt "VM".

Microsoft "opfandt" VM i midten af halvfemserne, samtidig med at de lavede verdens "første" editor der kunne bruge en mus.

Kort sagt går VM ud på at operativsystemet flytter data imellem RAM og Disk bag ryggen på programmerne, således at de tror de har hele den teoretisk mulige RAM til rådighed.

På en 32 bit maskine er det typisk omkring 2-3 GB, på en 64 bit maskine er det mere end rigeligt til at give ethvert brintatom i universet sin egen byte.

Hvorfor så den gamle "CPU+RAM+DISK" model ?

Hvorfor bliver vi ved med at fortælle folk der skal lære at programmere at en maskine består af CPU+RAM+DISK når 25 års udvikling i operativsystemer og hardware har gjort den beskrivelse forkert ?

Enhver der skriver et program ud fra C+R+D modellen og derfor selv flytter data imellem ram og disk, risikerer at blive deltager i en farce der er Gøg & Gokke værdig: operativsystem og applikation flytter begge data frem og tilbage uden nogen form for koordination eller samarbejde.

Varnish og Squid

Det sidste halve år har jeg arbejdet på en HTTP accelerator der hedder "Varnish" og den er hen imod 10 gange hurtigere end Squid til den samme opgave.

Forskellen er primært at Squid er skrevet imod den gamle C+R+D model, mens Varnish er skrevet til at udnytte alt det arbejde der er lagt i VM systemer i nyere tid.

Når Varnish har fyldt den fysiske RAM med data og skal bruge mere plads, sørger kernens VM system stille og roligt for at det sker, helt uden at Varnish skal tænke på det.

Når Squid har fyldt den fysiske RAM med data, begynder både Squid og kernens VM system at flytte data frem og tilbage, med det resultat at der ofte foretages op imod 5 til 7 gange mere disktrafik end der er behov for.

Dertil kommer naturligvis al den kode i Squid der slet ikke er brug for til at starte med.

Squid blev skrevet i starten/midten af halvfemserne, så der er ingen undskyldning for at have brugte C+R+D modellen og der er endnu mindre årsag til det idag.

Den nye model

Første trin imod bedre programmer er at lære programmører en bedre model end C+R+D modellen.

Her er mit bedste forsøg indtil videre:

  • Fra en programmørs synspunkt (I modsætning til når man står med skruetrækkeren) består en computer af et antal "kerner" (moderne computere har flere "CPU"'er) og et uendeligt (for den givne arkitektur) virtuelt lager, der transparant representerer data objekter som muligvis har en fysisk manifestation (dvs, ligger på en disk).

Det må kunne gøres mere mundret.

Forslag ?

phk

**

Kommentarer (10)
Carsten Frigaard

Ja, et stykke dårligt skrevet software kan nemt forvandle en gigahertz maskine til en 16.4 Mhz variant når diskswappigen tager fat. Derfor er hørbare 'cue' fra harddisken vigtig for enhver programør og bruger: meget larm og tikken er lig lav hastighed.

Men er det nu ikke lidt at et skråplan at programmere efter hvor ens rigtige hukommelsesblok ligger, på disk eller i rigtig mem? Reelt set vil man blot genudvikle 'smart' virtuel hukommelse for hver applikation, hvor man blot tager specifik hensyn til netop dette programs hukommelsesbrug? Det må kunne gøres bedre!

Et gammelt program jeg arbejdede på (i DOS dagene) havde sin hel egen diskswappning af 64 Kb segmenter og kørte totalt smertefrit ved intelligent at swappe 64 Kb stænger ud og ind fra disk. Smart, men også kodemæssigt vanvittigt.

Mvh
Carsten Frigaard

Karsten Nyblad

Du trænger vist til at få genopfrisket din kemi. Der er flere brintatomer i 1ml vand end 2^64.

Hvad der er mere interessant er, at 2^64 giver mulighed for at addressere hver atom på overfladen af en 12 tomme wafer. Det ville være mere rigtigt at sige, at så længe vi gemmer data på overflader, så er det svært at se, at man kan rende ud af et addresserum på 2^64 på andet end supercomputere.

Anders H

Det virker ikke som om, det er Cpu+Ram+Disk-modellen, du har noget imod. Problemet er vel bare, at mens operativsystemproducenterne har sagt "virtuel hukommelse betyder, at maskinen nu har uendeligt meget hukommelse", så har nogle Karl-kodere tænkt "ej, de lyver for mig" (og det er jo sandt) ", det kan jeg gøre bedre" (og det er -- i langt de fleste tilfælde -- forkert). Og så har du slet ikke nævnt Cpu-caches og branch predictors.

Den nye model kunne måske være: En computer består af Cpu+Hukommlse+Netværk+Disk og ...
... Der er mange cpu'er.
... Cpu'er bliver ikke hurtigere (Moores lov døde i 2004), men der bliver flere af dem.
... Virtuel hukommelse virker (du kan ikke gøre det bedre på en eftermiddag -- specielt ikke når du ikke kan få adgang til hukommelse uden om OS'ets virtuelle hukommelse)
... Hukommelsen er langt hurtigere end disken
... Netværket er hurtigere end disken (og forskellen vokser)

Poul-Henning Kamp Blogger

Efter at have talt med mange udviklere, så tror jeg ikke det er med vilje at de forsøger at omgå VM systemet, jeg tror vitterlig det er uvidenhed.

Hver gange jeg har holdt mit Varnish foredrag har jeg spurgt om nogen har set en programmeringsbog der ikke startede med C+R+D beskrivelsen.

Ingen.

Og hvis alle bøger om programmering siger noget forkert, så skal der ualmindelige selvstændige individer til før folk bruger en anden model.

Poul-Henning

Carsten Frigaard

Som astronomen Sir Arthur Eddington sagde

"I belive there are exactly 157477241362750025776056539611815554680 44717914527116709366231425076185631031296 protons in the universe."

en finurlig tanke egentlig, idet antallet af baryoner i universet ikke er uendeligt og hermed tælbart. Via konserveringen af baryontallet burde tallet også være konstant over tid (men syrede partikelfysik teorier kan sikker modificere dette).

Dette giver så Log2(N) = 263.087, hvorved vi kan enumerer alle baryoner med 264 bits. Dvs at en integer 'long long .. long' er 33 bytes lang.

mvh
Carsten Frigaard

Mogens Nørgaard

Et (for mig ihvertfald) interessant papir jeg har læst for nyligt kan findes ved at skrive "patterson latency", hvor gode gamle Patterson (der bl.a. var med til at skrive det oprindelige RAID-papir) beskriver hvor meget bedre det er gået med CPU'erne end med netværk og diske.

Den fulde titel er "Why latency lags bandwidth, and what it means to computing". Jeg har papiret, hvis I ikke kan finde det (mail til mno@MiracleAS.dk).

Generelt er diske håbløst bagefter. De kan ikke rigtigt komme op over 15K RPM, hvilket reelt betyder 125-150 IO per sekund, og det betyder at en dual-core Opteron kan mætte ihvertfald 50-60 af disse diske.

Når man så skifter sine gamle CPU'er ud med et par nye (og tit billigere) af disse Opteron-monstre, så svarer det til at gøre nedkørslen til motorvejen ved Solrød 16-sporet.

Det kommer man ikke hurtigere til København af. Faktisk tværtimod.

Solid-state diske, RAM-anvendelse (som kan løse mange prolemer) og eksperimentelle diske, der består af vibrerende plader med mange berøringspunkter kan hjælpe på det, men lige om lidt har vi quad-core Opterons...

Én eller anden burde finde ud af at binde en masse iPod nano'er sammen i et solid-state array :).

Jeg har ikke før tænkt på, at Moore's lov var død, men til daglig kan jeg se, at "alle" systemer jeg kigger på (dvs de fleste) er IO-bound, og det er jo ikke lykken :). Mere cache af den traditionelle slags hjælper ikke. Flere spindler (diske) hjælper, men det kan næsten aldrig blive nok, til at systemet bliver CPU-bound, som det burde være.

Derfor er tanken om at kunne komme ud over denne begrænsning besnærende, synes jeg. Desværre er det nok ikke relevant for alle de gamle database-systemer jeg kigger på, men fremtiden kunne jo udmærket tegne lysere for andre typer applikationer.

Jeg synes også det hører med til billedet, at når jeg (i min legacy-verden) ser et system, der vitterligt er CPU-bound, så skyldes det ofte, at der kører noget forfærdeligt møg-kode på det - kode, der typisk kører i uendelige løkker (uløkker, som de populært kaldes) eller bare hele tiden spørger om det samme - hvilket jo er spild.

Mvh.

Mogens

Jens Madsen

Jeg er blevet fortalt (i ganske useriøse vendinger), om tiden, fra før rammen. Da kørte alt software på disk. Fra programmørens side, var der ikke nogen "ram" at kende, og når vi trode vi brugte ram, var det disk.

Jeg husker selv den tid fra gymnasiets basic. Det var et gammelt anlæg, der havde feritkernelager. Men denne, blev alene brugt til basic'ens variable. Der var derfor ikke, fra programmørens side, andet end disk. Ram konceptet var ukendt for programmører. Selv større arrays, gemt med DIM, blev gemt på disk, og jeg fik at vide at peek "kun" læste data fra disken. Et feritkernelager var ganske lille, og kunne ikke bruges til at gemme hverken kode, eller programmets variable.

Men - set fra programmørens side, er RAM'en ganske overflødigt. Ser vi på en traditionel "Microsoft" akitektur, og mange andres, så findes en swap fil, som øger rammens størrelse. Og reelt, er vi dermed faktisk tilbage til et "kun disk" princip.

Vi kan betragte den indbyggede ram, som en cache, til den eksterne (swap) disk. Hvis vi kun bruger en mindre del af denne swap-disk, vil vi arbejde i ram uafbrudt. Og dermed, er den ligeså hurtig, som normal ram.

Det er intet i vejen for, at denne swap fil, kunne øges, til at være hele harddisken - ja endog alle harddiske i hele verden. Derved er alle harddiske i verden memory mapped. Vi kunne forestille os dette, som en 128 bit akitektur. Men, mindre kan gøre det, ved at vi "bestiller" en fil, harddisk, eller lign. til vores CPU, og den så først memorymappes på vores computer ved åbning. Fra øjeblikket filen åbnes, er den derved i CPU'ens addresserum, og vi får en pointer til addressen, uden vi reelt hverken læser eller skriver fra harddisk. Først, hvis data læses fra det tilknyttede hukommelsesområde, læses det fra harddisk, og caches, eller hvis den intelligente styring af cache, finder det mest hensigtsmæssigt fordi intet mere vigtigt findes at cache. Normalt kan computeren "se" igennem programmerne, og gennemskue det som bruges senere.

Softwaremæssigt, er langt nemmere at håndtere en sådan akitektur, fordi der bruges samme metoder, og algorithmer, uanset om data er i ram, på harddisk, eller på internettet.

Når et program opstartes på en sædvanlig computer med "ram", kopieres først programmet til ramlager. Det tager tid. Hele programmet skal kopieres. Ofte, er ikke plads i ram til program - og programmet skal nu gemmes et nyt sted på harddisken (i swap fil). Bruges ikke ram, men udføres programmet direkte på harddisk, så findes ikke dette kopi arbejde. Programmet starter øjeblikkeligt, som hvis den allerede lå i swap filen. Efterhånden som den bruges, vil den "caches" i ram lageret, og derfor bliver den ligeså god, som hvis den lå i ram. Den fysiske kopiering, fra stedet på harddisken hvor programmet ligger, og til swap fil, er undværet, og den originale fil bruges som swap.

Analyseres virkemåden af swap filen, ser vi desuden, at programmet ikke kun swappes ud på harddisken ved åbningen, men at det gentagne gange swappes ud. Der sker løbende skrivninger, og akitekturen fungerer således programmets position på disken uafbrudt ændre plads. Hvis et read-only program aflæses fra dets statiske position, undgås den type flytninger og ikke mindst de skrivninger der bruges, for at flytte position.

Jens Madsen

Desvære er ovenstående ikke korrekt.

Hvis vi "bestiller" filer, til at ligge i et bestemt område (ved hjælp af Virtuel hukommelse konceptet), og hvis vi dermed arbejder med en mindre hukommelse, end den globale store fysiske hukommelse, så arbejdes med to typer lager - det eksterne fysiske lager, vi bestiller hos betragtes som disk, og vores CPU's lager, der caches, vil caches med ram. I princippet behøves ikke nogen cache, og da læses data altid fra den fysiske hukommelse (disk/internet). Derfor mener jeg, at det stadigt er tale om et normalt virtuel hukommelseskoncept, og ikke som et koncept uden hukommelse (selvom det burde fungere uden).

I den nederste del, hvor jeg påstår, programmer kan "sejle" frem og tilbage i swap fil, og derfor kræve skrivning, så er dette forkert. Sådan som swap filer laves, burde dette ikke ske, når programmet har en fast position i ram og derfor ligeledes i swap fil.

Jens Madsen

Jeg mener ikke, at programmører skal kende til "kerner". At programmere, er abstrakt. Og programmører skal ikke kende til "hardwaren".

  1. Programmørens sprog, er high niveau sprog, og disse er uafhængig af hardware. De må ikke afspejle CPU'ens akitektur, eller være låst fast til disse. Hvis en CPU pludselig får 128 bit akitektur, så vil programmørens sprog, være identisk, og softwaren ens. Hvis dens floating point ALU får flere bit må det hellerikke kunne ses eller måles af software. Den kan - på ingen måde - detektere om computeren har 8 bit, eller 128 bit akitektur, eller floating point og antal bits for floating points operationerne. Hardwarens aktitektur er usynlig, for programmøren. Som programmør, har du ikke adgang til oplysninger som antal kerner, antal megabytes, eller CPU'ens type, og indstruktioner. End ikke harddiskens totale størrelse. Når du beder om ram forbrug - så kan du ikke få ledigt hukommelse at vide, men kun at vide, hvor mange meget du har brugt (dette tal er teoretisk, og ikke nødvendigvis 100% identisk med et fysisk forbrug, men er ens uanset computerens hardware og regnes altid ens ud) - og eventuelt hvor meget du har ledigt (hvor meget computeren har fået tildelt, minus ovenfor brugt), således det altid er uafhængigt af computerens akitektur og hardwaren. Computerens totale ledige hukommelse, er ukendt for programmøren. Operativsystemet tildeler programmet en mulig mængde, og kun denne må den vide, og det samme gælder harddisk størrelse. Begge størrelser tildeles udfra brugerens ønske om hvor meget programmet må fylde op.

  2. Et programmeringssprog skal være eksakt. Der må ikke forekomme tilfældigheder, som f.eks. afhænger af opstartstilstand. Disse vil - måske - kunne afsløre noget, om computerens "indre", eller andre programmers data. Det er ulovligt, og operativsystemet skal forhindre en sådan indsigt.
    Tænk, om passwords lå skjult her. Eller ekstrabladet fandt efterretningsvæsenets hemmeligheder.

  3. Et program beskriver sammenhængen mellem input og output. Og intet som helst andet.

  4. I princippet beskriver programmet en algoritme i rækkefølge. Men, dette er kun en abstrakt beskrivelse. Computeren, må gerne abstrahere, og udføre det som den har lyst, såfremt der ikke er forskelle på funktion. Programmøren, må ikke kunne se, hvordan dette fungere fra software side.

  5. Ved at beskrive, om programmets input og output, er afhængige eller uafhængige, specificeres parallelisimen. Er de uafhængige, har computeren ret til, at foretage udregningerne parallelt, og der kan ikke garanteres, at de pågældende outputs er koordineret. Det er muligt, at sætte krav på maksimum forsinkelse mellem et input og output, og computeren kan garantere, at denne forsinkelse ikke overskrides. Det er muligt, at prioritere et output, fremfor et andet. Hvordan parallelismen reelt fungere inden i computeren, beskrives normalt alene af disse krav. Det er computeren, og dets operativsystem, som afgør i hvilken rækkefølge, og hvilke kerner, der bruges, og programmørens eneste indflydelse, er opstilling af krav.

  6. Ofte, er det en fordel, for en programmør, at kunne beskrive et program i parallele dele. Antallet af parallele dele, som programmøren ønsker at anvende til sin beskrivelse, er uafhængig af computer akitektur. Sproget vil normalt give mulighed, for uendeligt antal parallelismer.

  7. Parallelisme defineres ved hjælp af køer. Der fines ikke delte variable. Kun køer, er deterministiske. Delte variable, er kaotiske, og kan afspejle i hvilken rækkefølge parallele dele udføres, og dermed eventuelt muliggøre ulovlig krydstale, mellem software, eller afspejle computerens interne funktion. To processer kan beskrives, og de kan tale sammen, via køer. Det må ikke være muligt, at undersøge om der er data i køen, og hvis der læses fra en kø, der ikke er data i, skal der ventes og udføres noget andet. Hvis to læser fra en kø, læser de samme data. Man kan ikke forestille sig, at det er tilfældigt hvilken kø, som får data. Der findes ikke nogen tilfældighed, og det er ikke tilfældigt, når samme data læses, af et vilkårligt antal parallele processer. Ingen kender rækkefølge af processernes udførsel, og alle får samme data.

  8. Antallet af parallele processer må gerne være en milliard. Computeren vil selv oversætte dette, til ikke parallele processer, og dette gør den fuldt ligeså effektiv, som hvis det beskrives som et event drevet program, eller et program i rækkefølge. Er der dele i parallele programmer, hvor der for en blok, for et input (eventuelt flere input ingange, og med et input på hver), også svarer et output (hvis der er flere udgange, så præcis et output på hver), så kan vises, at disse blokke automatisk typisk indsluses som sekvenetiel kode og udføres i rækkefølge. Her kan de optimeres på forhånd, efter processorens akitektur, og programmøren behøver ikke at vide noget om det.

  9. I forbindelse med paralelle systemer, kan forekomme datafiler, som er fælles for flere processer. Disse har altid indbygget låsemekanisme. Samtidigt, er såvel indhold, som funktion af disse filer, defineret i specifikationen, og de eventuelle tilfældige tilfælde de måtte kunne føre til, er godkendt på top niveauet. En programmør, kan ikke "bare" bruge fælles datafiler mellem sine processer, da brugen fører til ikke determinisme (kaos), og denne opførsel er ulovlig.

Uanset parallelisme, er der ikke noget væsentligt nyt, at lære for programmører. Deres univers er altid konstant. Alt andet, vil føre til problemer.

Jakob I. Pagter

Som jeg lige forstår dit indlæg, så findes der et helt forskningsområde indenfor datalogien som studerer netop dette problem, dvs. hvorledes man laver effektive algoritmer ifbm. virtuel hukommelse.

Grundforskningsfonden bevilget penge til et grundforskningscenter indenfor netop dette område under ledelse af Lars Arge fra Aarhus Universitet.

Mvh. Jakob

Log ind eller Opret konto for at kommentere