1.2 Kernel Data Structures.ppt

os

1. Kernel Data Structures
M.AKILA RANI
AP/IT

2. 1.2 Kernel Data Structures
1.2.1 Lists, Stacks and Queues
1.2.2 Trees
1.2.3 Hash Functions and Maps
1.2.4 Bitmaps

3. 1.2.1 Lists, Stacks and Queues
•Anarrayisasimpledatastructureinwhicheachelementcanbeaccesseddirectly.For
example,mainmemoryisconstructedasanarray.Ifthedataitembeingstoredislarger
thanonebyte,thenmultiplebytescanbeallocatedtotheitem,andtheitemisaddressed
as“itemnumber×itemsize.”
•Alistrepresentsacollectionofdatavaluesasasequence.Themostcommonmethodfor
implementingthisstructureisalinkedlist,inwhichitemsarelinkedtooneanother.
Linkedlistsareofseveraltypes:
1.Inasinglylinkedlist,eachitempointstoitssuccessor,asillustratedinFigure1.17.
2.Inadoublylinkedlist,agivenitemcanrefereithertoitspredecessorortoits
successor,asillustratedinFigure1.18.
3.Inacircularlylinkedlist,thelastelementinthelistreferstothefirstelement,rather
thantonull,asillustratedinFigure1.19.

5. •Linkedlistsaccommodateitemsofvaryingsizesandalloweasyinsertionanddeletion
ofitems.Onepotentialdisadvantageofusingalististhatperformanceforretrievinga
specifiediteminalistofsizenislinear—O(n),asitrequirespotentiallytraversingalln
elementsintheworstcase.
•Astackisasequentiallyordereddatastructurethatusesthelastin,firstout(LIFO)
principleforaddingandremovingitems,meaningthatthelastitemplacedontoastack
isthefirstitemremoved.Theoperationsforinsertingandremovingitemsfromastack
areknownaspushandpop,respectively.
•Aqueue,incontrast,isasequentiallyordereddatastructurethatusesthefirstin,first
out(FIFO)principle:itemsareremovedfromaqueueintheorderinwhichtheywere
inserted.
•Therearemanyeverydayexamplesofqueues,includingshopperswaitinginacheckout
lineatastoreandcarswaitinginlineatatrafficsignal.Queuesarealsoquitecommon
inoperatingsystems—jobsthataresenttoaprinteraretypicallyprintedintheorderin
whichtheyweresubmitted,forexample.

6. 1.2.2 Trees
•Atreeisadatastructurethatcanbeusedtorepresentdatahierarchically.Datavaluesin
atreestructurearelinkedthroughparent–childrelationships.
•Inageneraltree,aparentmayhaveanunlimitednumberofchildren.Inabinarytree,a
parentmayhaveatmosttwochildren,whichwetermtheleftchildandtherightchild.
•Abinarysearchtreeadditionallyrequiresanorderingbetweentheparent’stwochildren
inwhichleftchild<=rightchild.Figure1.20providesanexampleofabinarysearch
tree.Whenwesearchforaniteminabinarysearchtree,theworst-caseperformanceis
O(n).
•Toremedythissituation,wecanuseanalgorithmtocreateabalancedbinarysearch
tree.Here,atreecontainingnitemshasatmostlgnlevels,thusensuringworst-case
performanceofO(lgn).

7. 1.2.3 Hash Functions and Maps
•Ahashfunctiontakesdataasitsinput,performsanumericoperationonthedata,
andreturnsanumericvalue.
•Thisnumericvaluecanthenbeusedasanindexintoatable(typicallyanarray)to
quicklyretrievethedata.
•WhereassearchingforadataitemthroughalistofsizencanrequireuptoO(n)
comparisons,usingahashfunctionforretrievingdatafromatablecanbeasgoodas
O(1),dependingonimplementationdetails.Becauseofthisperformance,hash
functionsareusedextensivelyinoperatingsystems.
•Onepotentialdifficultywithhashfunctionsisthattwouniqueinputscanresultinthe
sameoutputvalue—thatis,theycanlinktothesametablelocation.Wecan
accommodatethishashcollisionbyhavingalinkedlistatthetablelocationthat
containsalloftheitemswiththesamehashvalue.

8. •Ofcourse,themorecollisionsthereare,thelessefficientthehashfunctionis.
Oneuseofahashfunctionistoimplementahashmap,whichassociates(or
maps)[key:value]pairsusingahashfunction.
•Oncethemappingisestablished,wecanapplythehashfunctiontothekeyto
obtainthevaluefromthehashmap(Figure1.21).
•Forexample,supposethatausernameismappedtoapassword.Password
authenticationthenproceedsasfollows:auserentersherusernameandpassword.
•Thehashfunctionisappliedtotheusername,whichisthenusedtoretrievethe
password.Theretrievedpasswordisthencomparedwiththepasswordenteredby
theuserforauthentication.

9. 1.2.4 Bitmaps
•Abitmapisastringofnbinarydigitsthatcanbeusedtorepresentthestatusofn
items.
•Forexample,supposewehaveseveralresources,andtheavailabilityofeachresource
isindicatedbythevalueofabinarydigit:0meansthattheresourceisavailable,while
1indicatesthatitisunavailable(orviceversa).
•Thevalueoftheithpositioninthebitmapisassociatedwiththeithresource.Asan
example,considerthebitmapshownbelow:
001011101

10. •Resources2,4,5,6,and8areunavailable;resources0,1,3,and7areavailable.
•Bitmapsarecommonlyusedwhenthereisaneedtorepresenttheavailabilityofa
largenumberofresources.
•Amedium-sizeddiskdrivemightbedividedintoseveralthousandindividualunits,
calleddiskblocks.Abitmapcanbeusedtoindicatetheavailabilityofeachdisk
block.
LINUXKERNELDATASTRUCTURES
•Linuxdatastructuresdefinedinincludefiles<linux/list.h>,<linux/kfifo.h>,
<linux/rbtree.h>