181

J SYSF【,MS SO「 l WAR=
1 り0 ( ) t l l モl 忠1 1 9 8

日tea卜Time Garbage Co‖ ection on GeneralBPurpose
尚lachines

打[其lichi Yuasa
ズで
sで/2 r2ざ′r,rrrrで
αれ｀
′
αr/Jで
,7α
rた
V′Sご′
ビ
″こ
でs, Kノθro υ/1′ソ?As′
プbr,,イ, ヽ, yゃょ77
4ツメθrθ

An a19orithm for real time garbage co‖ection is presented,

datcd appr()priatcly Allcr thc cxccuti()n()i thc ttarbagc

proved correct, and evaluated This algOrithm is intended
forlist processing systems on genera卜 purpose machines,()i thc 11)phCationとpr()gra11l is
ぜollcctorn thc cxcctlti()r、vhich 、u、一
arbと
と
rc、
ulllcd This killd()1 1をど、どC C()11Cct()rゃrを,
inl.1、caHcd a sr̀,βど
frrrttQど̀てきpcnds thc applicati()n pr()と
rο′
こ
っ′
′｀

ie,Von Neumann style serial computers、ハ′
ith a sin91e pro―

cessor On these machines, realtime 9arbage co‖

ect Oninc‐v itably causes some overhead on the overa‖

executionof the list processin9 system, because some ofthe prim
itive list‐
processing operations must check the status ofThc prirnary di、advantagc ()l garhagc c()1lccti()n i、
inl
thC applicati()n progrとthat it pcri()dictiHyusPcnd｀、

9arbage co‖ ection By removing such overhead from fre―

Ⅲどと
irbな
Roughly 、Pcaking. thc tirllc tl)rとどC C()liCCti()n i、quently used prinlit ves such as pointer references(e9 ,Lisp car and cdr)and Stack manipulations, the presented

V i、11lc t()tとi nulllbcr ol｀
cc、、iblc ccH、
ェ
ccll、
ind (Y. 7｀、と

a19orithm reduces the execution overhead to a 9reat ex―
terlt Aithough the algorthm does not suppOrt compacHon

V , W h C r c Д i s t h c r l u n l b c r ( )ぃ′￨ょcstinlatcd as(Y/11β
V C i l l c t (A )、r 、
thc applicati()n pr()tind βa r c 、( ) 1 1 l c Pi(t)iヽ
111()rC ccH、
111l usc、. =arbagc c()llccti()nlkc、
tと k)11=cr
grを

ts partial coln
ofthe whole data space, t efficiently suppo「inl lS suspcndcd in it、
cx―
and thu、thc apphcation progrを

paction such as array relocation

ccution R)ral()ngcr tilllc As rcp()rtcd in Stccic l141,

l lNTRODUCT10N

cconds lt is dillicult ik)r an、
ccond、 to、cvcral tcn、 ()1 、Garbagc collccti()n i、 thc nlost popular illcth()d in list―

intcractivc()r rcal―
tilllc li、t―pr()cc、、ing systc,ll t()pr()vidc
adcquatc scrvicc、 vhcn it suspcnd、 cxccutlon f()r such aR)r typicalをlpplicati()n、,どarbagc collcction takcs、 cvcral

proccssing systc,11、 suCh aヽ 1フisp to rcclairn di、cardcd
list cclis(COns cclls in Li、 p tcrnlinology) Althoughthcrc arc scvcral variations()f garbagc c()llcction, thcy
shilrc csscntia‖y thc sanlc 、 chclllc: Availablc cclis arc

ダなど
om which()nc
collcctcd t()gcthcr t()R)rnla"昭ぅfl・ce‖ is rcmovcd cach tiinc thc application program rc―
quircs a nc、v cctl Whcn thc frcclist is cxhaustcd, thc
application progralll l、tcmporarily suspcndcd and thc
vholc′
でごrθr prOgranl bcgins to run Thc 、
garbαgで ごθ′
thc garbagc collcct()rc()nsists twool｀lllaj()rpr()cess ol｀
cclis
arc in/た力
sでdctcrnlincs、vhich
αβphascs Thc rPPαuSe(Or access,b′ で), by travcrsing list structurcs in usc
Thc swと ep β/rαs2 thcn puts all inacccssiblc cclis into thc
frcclist ln addition‐somc list―proccssing systcms havc
thc conlpacti()n phasc(or rc10Cation phasc)inヽ Vhich all
acccssiblc cc1ls arc nl()vcd into a c()ntiguous nlcnloryar(3a and pointcr rcfcrcnccs to thc rclocatcd cclis arc up―

/4″
どiは こ
っ′cs弾 ″どビ″こでrθT17,た力′ylrr4s″″?″r r2/′
71/b′,Depα r′777α
rrO″α″どCο/Plβ″′?rS(た ″̀でッ?パ′, i蝉 0カ″s力,t/″′ゥ q/五 で力″ο′0, 7bノ0カが力′
イθブα
033″
r7‑C力
, 乃777p2々, イ
即″に, 1 ] l s c v i c r S c i c n c c P u b l i s h i n g〕
rk,NY655 Avcnuc oi thC Aincricas,Ncw
Y〔llX)1()

C ( ) i n clong tilnc F()r cxamplc, if an applicati()n progranl、 vcrc
to control a robot in a product linc of a car fact()ry,
thc rob()t 、v()uld st()p pcriodicaHy 、vhilc thc linc kccps
n10Vin3,thus yiclding faulty carsin()rdcr to av()id thcsc pr()blcms. scvcral algorithmsk)r t̀rcal―
tiinc… 8arbagc collcction havc bccn proposcdll, 2. 5, 6, 9, 10, 13, 141 A real tilllc garbagc collcc―
tor runs in paralicl with thc application progranl so thatthc tilllc for cach iist―
proccssing prinlitivc is boundcd
tiinc alg()―by s()mc small constant Most of thcsc rcal―

rithms arc intcndcd f()r multiproccssor machincs Thc
basic idea is to use()nc pr()cessor k)r garbagc collcction、
vhilc anothcr proccssOr iS rcsponsiblc for thc cxccu―
tion of thc application program Unk)rtunately, manylist―proccssing systcrlls arc runnin3 0n gcncral― purposc
machincs and thus thcsc algorithnls cann()t bc applicd t()
で/2g/r7′々gs rcfcr「
βタィβθsc ″ αご7P′vith a singlc proces―
to Von Nculllann stylc computcrs、
thcsc systcms Hcrc, どsor,such asthc MC68000 and thc VAX Forthcsc ma―
chincs,no supportis expected from thc underlying hard―
warc and frona thc ttrnlwarc メ

ゝlthough thc algorithms
0164‑1212/90/S350

182

J SYSTEMS SOFTヽ VARE
1990111:181‑198

could be simulatcd On gencral― purpose machincs, thc
ovcrali system cfflcicncy would bc reduced to a grcat
extcnt.Nowadays,Lisp machincs are available as cOHl
mercial products,butthcre arc lllany more Lisp systcms(Or liSt―
proccssing systcms in gcncral)in usc On gcneral―purposc machincs. It secms that many othcr Lisp sys―
teins、vill bccOmc avallable on gencral―purpose machincs
in thc futurc.

T Yuasa

4. Thc algorithnl is thcn applicd to more rcalistic list―
processing systcmsi tO a systcm with stack mcchanism
in Scction 5 and to a systenl、vith muitiple kinds of cells
in Section 6.Finally,in ScctiOn 7,、
vc、Vili Sho、v that thc
a180rithnl is casily applicd to thosc systcms、
vith sOmc
sort of compactitting garbagc collcctor
Throughout this papcr,、
ve usc a Pascal―
like languageas thc irnplemcntation languagc of list―
proccssing sys―

On the other hand,Bakcr's real timc algottthm[ll iS tems.Dcviatlons from Pascal arc as 3ollows:
inhercntly scrial and has bccn inlplcmcntcd On singic―
1. Type dcclarations arc onlittcd if thcrc is no Scar ofprocessOr machincs[121,HowcVer,this algorithm puts
ambiguityo We make it a rulc that、 ねriables χ,ノ中そ●an cxtra burden on opcrations of pointer rcferences(le.,and〃arc
pointcr variablcs and variablcs,andブ
arc
car and cdr in Lisp).Implcmcntations Of this algorithm,,″
rqgcr
variablcs.
thcrcftDrc,use special―purpose hard、 vare l101 to achicvc…
2. Wc a‖ o、v undcrscorcs ̀・
in idcntincr、
modcratc performancc. Thc ovcrhcad Of irnplcmcnt―
3
Wc
use
pointcrarithnictic
andp()intcr comparison‐ing them on gcncral― purpOsc machincs is rcgardcd cx―

trcmely high〔31,cvcn With thc suppoR ofthc nrinwarc

similarto thosc in thc c languagc 18卜 Whcn a pointcr

p points to thc Fth clcment of an array, then thc cx̲

[ 1 7 ]
prcsslon β +‑ l rcprescnts a pointcr to thc(, + 1)thThis papcr prcscnts and discusses an a180rithm fOr
clcmcnt
Sinlilarly,comparisons on t、 vO pointcrs arc
real―time garbagc collcction suitabic k)r list―
proccssing
dctlncd
in tcrms Ofthc array indcx,on c()ndition thatsystcms on gcncral―purpose machincs̲ This a130rithm
bothpointcrs
pointto clcmcnts Ofthc samc array For
was dcsigncd with two principlcs kcpt in mind.A rcal―
instancc,、
vhcn
βand?point to thc Fth andブ
th clc―tinlc garbagc collector on gcncral―purposc machincs in―
mcnts, rcspcctivcly,()f an array,thcn r, <￨?holds if
cvitably causcs somc overhcad against thc cxccution cf―
and only tf′<ブ
flcicncy of thc list―
processing systcm The primary rea―son is that somc of thc prirnitivc list―
processing opcr―
ations nlust chcck thc currcnt status of garbagc collcc―
2 THE ALGORITHM
tion. Such a chcck is unncccssary in conventiona1 1lst―
vc 、
cxplain thc basic idca()f our rcal―
proccssin3 systems、vith a stop garbage collector. In or― in this sccti()n,tin3calgorithm
Nt tlrst prcscnt irnplc
a、
list―
dcr to rcducc thc total ovcrhcad duc to thc rcal―
tilne bc―
proccssing
systcnl、vithaconvcntional
stOp
garbagc
cOHcctor. Thishavior ofthc garbage coHcctor,our irst dcsign principlc
is that ovcrhcad on frequently uscd prirnitivcs should be systcm is siinplc in that it supports only a sin81C typcof ccH, ご
θ″ざ 6?′′s, and that it dOcs n()t havc the stacksmall or cvcn noncxistcnt in particular, thc prcscntcd
mcchanism負)r
programexccution
algorithnl、
vas dcsigned so that it docs not put any ovcr―
hcild on thc colllinOnly uscd opcrations of pointcr rcf―
crcnccs, assignments, and stack manipulations, 、v hilc it

A ∽ ″s 解′′,()r

s i mで′p′,liys aaて r c c O r d

OttcCtsisting()f thrcc rlelds: IP22′/‐and cdr
た, 6α

puts an cxtra burdcn on the rarcly uscd destructivc list
type cc‖ =record
opcrations such as,β′α6αandち β′
αcd in Lisp
mark:Boolcant
rThc other dcsign principle is that it should be casy to
car i polntcri

apply the algorithm to convcntional systcms、
vith a stop
garbagc collcctor. Not all list―
p roccssing applications
rcquirc rcal―
tirnc bchavior, but rathcr thc total cxccu―

cdr i pointcri
end′,or eisc it points to cithcr a cc11 0r
tion time may be more important lor many applications.A pointcr rnay be″ ′
an
atom.
Cclls
arc
aHocatcd
in thc hcap〃,、vhich is anThus, 、vc 、
vOuld hkc to havc two vcrslons of thc samc
array
ofブV
tt
l
cclis
list―
proccssing systcm, onc、 vith a stop garbagc collcc―
tor and the other、vith a real―tirne onc, and to have thevarあ ′:array10..ブV10f CCF′
)r cach application.
chancc to sclcct thc bcst of thcm魚In thc ncxt scction, wc prcscnt thc basic idca of our
Thc systcm actually uscs rr[Oi to rr[フ v̲1‖ as thC hCap,
rcal―
tirnc algorithm, flrst by introducing a sinlplc tist一 and thus a maximunl of 7V cclis arc availablc in thcvith a Conventional stop garbagc col― system.Thc last location of〃(灯 [Nl)iS reServcd soproccssing systclll、
lector,and thcn by applying our algorithlll to this systcm that thc cxprcsslon ̀̀β + 1" iS mcaningful 、 vhcncvcr
tiinc systcm The corrcctncss proof of
to makc it a rcal―
p points to a ccn Wc introducc t、 vo conStant pointcrs〃 う″/72 and rrrOp,ヽ
thc algorithnl is givcn in Scction 3, and the dynamic
vhich point to thc rlrst location of thc
bchavior of thc rcal―
t irnc systclll is discusscd in Scction hCap(iC.,〃[0])and the last location()fthc hcap(ic,,Timc Garbagc Collection
Retll―J SYSTEMS SOFTWARE
1990111,181‑198

rriPv̲11),rCSpcctivcly.Atoms are a1located somcwhcrc

vnr frcc̲1lst i Pointcri

not in thc heap To distinguish pointcrs to cells fromprocedure init()ibegim llcc̲list i=ni〕
if o r 〃
: = H b t m l o H t o p d ob e g i n βA r l l a r k i = 1 4 1 s c i/｀
β Car i=frcc listi
lrcc list i=β
endi
f o r ′: = i t o N R d o R I ′卜= n i l″sp̲ 60″spGヮ)thosc to atoms, ve、 use thc prcdicatc cθ
is rrttc if and only if thc pointer p points to a cell
'The systeHl has an array R consistingアofブヽ尺 pointers,
whcrc′Vメそis a smali constant The application program
can access and moditt thC COntcnts of R by primlivc
operationsと gerr and Lscrr と gcrr(′)returns thc rth cl―
cment of tt and Lsで rr(,,p)rcplaccs thcた h clcmcnt ofθr βO'″rc,s only
尺 with〃 Pointers in R arc called ttθ
those cclls rcachable dircctly or indircctly fronl the root
2 0ther cc‖ s arepointcrs are regardcd to be α ccess,b′end{Of init l:procedure Lc()ns(',x,ノ )i
begin if llcc̲list ̲̲ nll thenbegin gc()i1()ragcいif trcc list =nll them crr()r(.=n()、)endi
l CCll allocHttn li
β : = f r c c ̲ l il、ari
f r c c ̲ l i s t Ai =cβinaccessible Thc purpose of garbagc collcction is to ar―rangc inacccssiblc cclis so that thcy may bc rccyclcd
for furthcr usc lt is thc rcsponsibility of thc application
progrann to prcvcnt ali cclis in use from being garbagc―
collccted uncxpcctcdly ln particular, 、 vc assume that
only acccssiblC p()intcr、can bc passcd as argumcnts to
opcratlons̲Thc prirnitivc hst―proccssin3 0pcrations in this sys―
α6α、とrr7Frにど,andと 釘 ,tcrn arcとごθrrs.と協 ′、と胡 r,た ぇβ′cach of、vhich corrcsponds to a Lisp function in thc()bvi―
ous、vay.Untikc Lisp.と ごθ/2s d()CS n()t rcturn a valuc,but
is a proccdure that causcs a sidc cfScct ∽と ″頁′,メ,ノ)r and こどrv ccll 、vith χand ノ in its 6α
a1locatcs a nc、

183

A car:=Iiβ
A cdri=メ
i
β
ズ￨ ′
卜= β

end l()l Lcons}ifunctiom Lcar(I):pt)intcri l″car i=IArと lri
function Lcdr(I):p()intcri Lcdr:=IA cdri
A cari=メ :procedure l´ rPlaCa(メ,ノ)iメ
A cdr:=ッ 1
procedure Lッrplacd(̲r,ノ)iメ
cq:=x
function Lcq(メ ,メ)i B001Cani l″

ッi￨:ニ メiprocedure Lsctr(′ ,I)i庶 ￨′ctr i=ズ ￨′funct'om Lgctr(ア)tpく)intcri LどトP『ocedure gc()i

iclds and,in addition,storcs the ccll pointcr
RI′
ト intobegin
l initializati()n llist consisting ofFor cxamplc, in ordcr to obtain a vnc、

gc、̲init()if o r ′: = l t o N R d o g c 、 p u s h ( R I デ￨)itwo″ ′
な,wc writc

1 11lark phasc l
w h i l e n o t どc S ̲ C t l l p(け)d0begin β :‐gcs̲poP();(PA car)ig c s p uh、A cdr)
gcs̲push(β
endi

′)i
′,″′
とごθ″s(1,″ ′とご0″s(1,/J′′,とgerr(1));

WCCp phょヽcl{ヽ

Thc list is thcn storcd in Rlll

F o r 〃
: = H b t n 1 4 o H t ( ) pi f βA n l a r k t h e nc
β A m a r k : = 偽1 、
A c とl r : = 併c c l it、ieise begin〃llcc list i=β
cnd

Figurc l illustratcs an inlplcmcntation of our sinlplc
list―
proccssing systcnl、vith a convcntional stop garbagc″′
r()which iscollcctor Thc systcm is initializcd by′
invokcd oncc、 vhcn thc systcnl bcgins to run All avail―flclds to forlll thc
ablc cclis arc linkcd throu8h thCir r6αd oend{()1思
C I;

vhosc
freclist、 rlrst clcment is pointcd t()by thcl global
1litivc()pcrttti()ns()n gcs}pri】
なr This inkialization of thc ttcclistis
確C̲′variabicすv a r どc s i a r r a y l l N G C S i o f p O i n t c r irathcr a convcntion to simplitt thc CXplanati()nAvail
VarどCS t()P:intcgcI;
ablc cells could bc a1locatcd dircctly frorll thc hcap until

11
̲t()p ii‐
procedure gc、 init()i gCヽ

thc irst garbagc collcction()ccurs

procedure gc、̲push(メ)i
AF】〕ark)theni f c ( ) n s)pa(nメd(mOtメ?ib e g i n . A I n a r k : = /″ァ:ニgCヽはC S t ( ) p l メi
どC｀ t()pi・どcs̲t()p 1 1
endi
intcrifunct'onど c、
̲p()P:P(〕
bettin gcs t()P:=gC｀̲t()pli
̲t()plgc、̲pop:=EどCsigCヽendi
Function gcs̲clllpりtB()()iCan:
gc、̲cnlpり :=(どCS̲1()p‐ 1)i

Thc garbage collector is invokcd、 vhcn thc freclist is
cxhausted During thc mark phasc, thc garbage collcc―
tor marks‐ ic., turns to r/24C thC r77α′た flclds of, ali
acccssiblc cells by rccursivcly travcrsin3 1iSt Structurcs
by thc usc of thc garbagc collcction stack gcs During
the s、vccp phasc, thc hcap is scanncd scqucntially somarkcd cclis,arethat all inacccssibiC Cclls,ic ,ali non―collccted into thc frcclist Notc thc usc of thc stack op―
crations gcsp17s72 andど csPθ p ThC body ofthc markphase loop siinply repeats thc push and pop opcrations
VhiChs力(χ), ヽand the actual marking is done by gcsP夕「igure l. Thc convcntional systcnl with a slop garbagc coト
lcctor

184

J s Y ヽ 「I J M S ヽ()Fl WARI!
10り()i ll11 1は1(,8T YuasaP『()Cedurcどぜ()!
bettin l illitiと111/titi()n l
さビ｀ lrllt()1, o r i′! l t O
N Rc 、dP oL hどl (ヽ￨ズ, 1 ) icnd
c l s c i r i i c c c ( ) u￨ ヤ
r l̀th二′enbeHin i)htl｀
ぜi n itH( 1)hrt、ぜ!
｀W ぜぜl ) 'ぜt H h i n l ir ′: i t く) N R d o H c 、 F ) u1、
1(☆
￨′
1)
●1 l d l f °P II ｀
1モ
C｀
l ii rl klとwhilc ll()t ビ
ょ、ビ1111〕ty()d()
beHin ′
,i tどで｀P()r)()i

W‖ !Ч
ゆm
デ1 11‖
!(幣
&苫
!'in山
‖

i f i r c c c ( ) u (r)l1t1≧
l e n c H ( H l r1l(())i、
a F)ぜtl l l とi tt i li l( () )i ぜ
] ￨
l は
″: 二十
rcぜ
1 11 、:′l r 1は lt ii 、 ,′・( tとi il r c ( c ( ) u l i t : ぜl(r(ぜ
)uilt
i

(ア
,i cdi)i
どぜ｀ P ( 1hヽ' i ′' ‐ぜt i r′cnd
cndi' C Jとi : 1ヽ′メ・ぐ〔I I : ドt′
,Al】、
a r ( ! ! ( ァ, = 、 、ば P じ「) i′W ぜビI ) P hぜt￨t ｀
l ヽ

!￨‖
■与
,1月
‖
∬
t艦
Ht h岐
粉
cl、
G bettin′,・ズ￨ l′i ,′C : l d l ( i)〕lIlヽ
Lt ぐcと
r t lIぜ
ヽ
ぜ li、
11
1 1ぜ
ぐl i1 、
: / ,

C81d

lttl k()prOccdurせ I】
bt=in′ : li
w h i t c 人, l■ a n d ( 1、c1 (il ,】
p tt ドy (〕) l d 〈l ) c t t i,r:B ′ J ( 、i ) ( ) r ) ( ) i
ヽ1 ,( (′t H ) t
ど( ｀F )1 1に′, ((11)i
F ビ｀ ! ) th:(ヽ″: ′￨ ￨

C n d l ( ) 1 cど l i「i g u r e 2 . A l l l l l t c t l l t l l i v c ( )l rc ll (i )n ￨iごt (i )く々▼()nt()【て、Onty il 、1)()ints t()とpushc、 ゥi il()11‑nlarkcd cせ‖rhi、 nlcchalli、111 111とiy 、cclll ir、
cllicicnt 、11lcc ti p()intcr
nldy bc POpcd i「 ()111々
ごドillllllcdititcly alicr itpu、i、hcd
vcvcr.a、 light chtinぷ
Hl)、ビ、
Vill()vcrc()11lC till、
incilicicllcy
ti、i‖u、tratc(l ill lfi思しlrc 2 ()ur illtcnti()il is t()kccP thcと
tll:orithnl i、
rllplc ind
を Cicと
11

C'1(1

c n d

N o w w c l l l ( ) d i l y t i l C a b、
(y)、vtせ
clll s()that it hcc()Hlc、
a rcal―tilllc、c c Fiどurc 3)
ystclll(、In thc rcal―
t illlc vcr、
1()n, thc とどirbagc c()llccti()n pr()一cccd、 、
vhilc thc applicとiti()n progralll kccps runninど
Sillcc vc、 as、
unlc()1lly 、と、111=lc pr()cc、、()r. thc v()pr()―t、CCヽヽ
CS Cann()t pr()cccd rCally in paralicl ln、
tcad‐thc
var llせc c()u1lt ど
tc「
iritぜ
i

llltlrk pha、
｀
phd、
:
解吊
骨
鮒:十
)hatFlhど ぃwccP ぃ
var、wccpcri pく)intcril ( ) 1 ! 1 1 ( 1 , R

l i

vctlI)1 )(proccd81rc、、
1)Gttin′: ￨〔w h i l ■e 人2
どa nw tぜぜiF 、= H t r ( ) うd ( ))I ぜ
bt4in iふw c ぜp ぐ, 1 1 ■11(thc,1
ヽヽ
Vじ
ぜl)ぜ
〔 1い
を
口k : ￨と11、
せ￨ぐ1、
cir m()t、、ビfで1! c(11
vぜ
1ぜ
〔
1、
ビ i】
】
ぜ thcnb e H i n 、w c ビ! ) iぜ・( ょ1 : l i ゼぜ 1 1l、i｀｀せぜI ) rぐ‐ビ( 1 1 : = にょv ぜ t lぜ】illぜ
ぜ ￨ ￨ t、i 、ぃぜぐ「)ぜ11
1〔ぜビ ぜ( ):にr i t t lぜ
lぜ
( ):に
ご
Iit l lcndi｀
WぜCPぜli ヽ WぜぜPcr 1 1
′t
, 1 1
cnd
Cnd lく)￨ヽ
WCcP Iキ( I , ツ) t
p r o c e d u r e L「ィP l iヱC1と十c a r ) ib e t t i n i f f h a S C m a r ck tp h ei nぶ
cぷ、p u ヽh(メヽ car iメ

cndi
prOcedure init()ibeHin trcc list i=11lli
F o r β: = H b t l l l t o H t ( ) p d ob e g i n r P Ad i n お
k : =tにlc、i
A(ar i=1「cc listiρ
A cdri=icavc rllciノt r c c lti:、=r9
endi
lrcc c()unt t rT7 1、
sc:=‐
idling i
phと｀
WCCPCr:=Ht()p+li
f t ) :r =′i t ( ) 7 V t t
d O
R l r l : = n i l i
gc、̲init()end 1 0f init li
p r o c e d u r e L c o n s ,( I′, ッ) i
begin l garbagC C()Hccti()n disptttchc「￨if phasc
nlark̲pha、 c thenbe■in 11lurk()iぐ｀ C11lPty()them phtl、ぜ:=ヽヽ
VCCp̲phょ 、
cend ifど
elseif phasc 一、、
vCCp̲phtl、c then
脱 tin swccP()i
if、、
vccpcr ,Ht()p then Phasc:=idling・
beJnギ 加よ、
c thcnどc、
h付ttll)iPu、t∬:=ドphよrplttcd(I,ャpr()cedurc lャ
ン)i

endi
「igure 3. I｀アh c rcal―t iri、
c systclll(()pcrati()ns il()t dcscribcd hcrc
arc、amc as in Fiど
urc l)、
vholc pr()ccss Of garbagc collcctiOn is dividcd into
chunks,cach of、 vhich can bc cxccutcd in icss than sOmc
constant tiinc,and is cxccutcd only in ccrtain situatiOns
Thc situation、vc chOsc is、vhcn thc applicati()n pr()gram
rcquircs a nc、v ccH、 ic , whcn と 6072S is callcd Thisidea is creditcd to Bakcr 1ll sincc ccH、 arc rcqucstcd、
vhile garbagc c()llcction i、
in progrcss. 、
vc CannOt、 vait
until the frcelist is cxhaustcd lnstcadn a garbagc col―lcction bcgins、vhcn thc numbcr()f thc frcelist cclis bc―
comes less than a ccrtain numbcr′ ,″̲ 1『( )kccp thc num―

Rcal―
Tinlc Garbagc Collcction

J SYSTEMS S()FTWARE
1 )卜り
()〔
11!181 198

bcr of frcclist ccHsゃ、
vc intr()ducc an ,77re8で
r variablc
電2̲てθ2777r
SヽWith thc rcal― tinlc 、
vcvcrtt thc application
ystcill. hoヽvcCp

pr()grain kccps rcquiring ccils cvcn during thc s、
phttisc rf thc frecli、t is sct clllpty at thc bcginning ol

vccp pha、 c. a、 、
vas in thc 、t〔)p garbagc collcctor、
thc 、、
thcn durins thC ncxt caH()1｀

とこ,ヵざn thC ヽ、てvccping 、tcp、

nlust bc rcpcatcd until ti non‑11舟 arkcd ccll i、 11)und inthc hcap Sincc thcrc i、

no 、111■‖ uppcr b()und k)r thc

tinlc rcquircd t()lind a ll()n‑11larkcd cc‖ . that cと
‖ ()1
ェ
一
1″
̀k少
/7s c()uld takc a l()11ょ
tilllc rrhu、.()ur rcal―tinlc 、y、
tclll sh()uld icavc thc irccli、t al()1lc and c()1lcct()nly th()、cn()n―nlarkcd く,(,lls thと、t ttr(j n()t irl thc lrcclist yct lR)dc―
tt cc‖ i、ill thc trcclist, vc
tcr11linc vhcthcr、、 usc thc(「r/ri｀icld、()1 lrccli、t ccil、
vhich ttrc icit t11lu、
cd ill thc 、t()p、、c()1lcct()r 「″hc ruic()i thtilllb i、thtlt ti ll()11‑111を
irkCd ccil―
i、in thc ircclist il till(1()11ly il (セ
it、
プ
rl‐
icid ha、そ
H di、
til〕
'Pで
Vhich i、 11()t aCcCsscd by thcli｀
hCd p()intcr′て
化
7ツご ′
、ヽ
患し
と
iti()1lpr()とrti111ェpI)licとま′
1、111占ic chunk()￨「hc Pr()cc(lurc′″″r々()11ぃPiClllCnt、とrk、たl cc‖、ctich tinlc it is IllCd.
irk phtと、c it lllと、cを
thc lllと185

progranl arc ncvcr changed during thc lllark phasc,thcn
rcpcatcd calis t(〕′″α/々()CVCntually nlark all accc、、iblc

cc1ls Howcvcr, と rr7′
αこフ and と /r7′
αこど 111()d‖予 thC list
structurcs and thus今vith()ut thc、
c if statcmcnts. thcrc、
is thc po、、ibility that solllCを
iCCCヽ
SibiC cc1ls arc lctt un―
illarkcd Fhis
「 is lllainly bccau、/た()Cannot lllark ac′77″cc‖()ncc thc cc‖
bcconics n()nrcachabic lr()111(pOintcr、on)Fこざ F()r cxanlpic、
uppo、c that thc 11)11()、
ving、tatc―、
incnts arc cxccutcd iinnlcdiatclyと11lcr a gtJrbを
lgc cOlicc―
tion bcgins
た,sで
rr(2,′フごα′(/̲=?r/(1))):
′
ッ
′ρ′
rrご
α(だ
ッ
′)i
H?r′(1),72′
Figurc 4 illustrをltCS thc statti、()i tllc rcicvant ccHふ、
vhcn
rprrrこrン
そ″is lllv()kc(l 、A、 that thc ccll(Y thc
unlc
i、 ()nlyCC‖ thを
it pOintふt()thc cc1l βI「 ′′″(rr sinlPly rcplaccd
″′

thC〔
セ
7 r l i C l d ( ) 1t (h Yc 、n β
w()uld n()t bc rcachiibic ir()nl
iny nl()rc tin(l thu、、
v()tlld i()()、
c thc(fhtincc t()ど ct
r(1ダとillarkcd As thc ic、 ult.β llliょ
ht bc rcttardcd ti、と1どよrbを
1=C、
vhilc it i、、tili ticccSヽ
ibic l｀his 、ituと、ti()1l ctinn()t()cc tir

ど(fcil、
t()!1lark, thと、t i、)nlpty hcik)r(,th、、11【(、bc(!()nlCヽくincc thc p()11ltcr t()βlヽputthcd()111()R(1,ill()ur systcnl 、by tilc 、
tatclllcnt r(1ドr)とit tilC bcど)1
i,1,linょr"イS力(ヽ (イ′くcpcatcd た l tinlc、
b()lly ol｀
thc wh‖ c stを
itCnlcnt i、「n thCllrサ
rprrr(7(ザ▼,̲メ) in()rdCr t()と ichiCVC thc 、cc()nd pr()pcrty

'ア
′
ι
′
/た()rCtu rn、 i11111lcditCly
iを Prcci、cly sPcakingゃ thcrc―lk)rc. ,,7rrr々
rk、 た l ccil、そi、l()ng ti、it i、pos、 ibic()nlとェ

vC tiddcd thc 、tatclllclltとib()vc, 、、vithた l bcill=とCOnstant il thcrc arc ic、s than々 1
1｀11lti‖

Si11lilをirly、thc Pr()ccdurc sw?(4′'()111lf)iClllcnt、と、chunk()￨thC :11を、
Irk l)hと、cとェ
,1(l takC、
ctti C()1 2々cc‖、aふ1()nょa、it iト

‐
・
' ご′
で′
r た : = ( ノ ≧ さl t で
):
′
''″
β ・
rk
i n t ( ) と( o 7 1 s (,′、, メ) I ) u r i n ど c x c c u t i ( ) 1 1 ( ) i t h C liaⅢ
ctivclylllark、と
l11
1lcwlyclll()c.
thi、、
1を
ttCnicnt
cll心pha、、ibic Thc F()r c()ntr(、i vとlrinbic′, u、Cd in thc 、、
vccP
p()、
c lo()p()￨「iどurc l i、rcplを
iCCd by thcど 1()bを
II Vよriabicphil、

vccp phit、c、thi、
inど cxcCutiく)11()i thせヽ、
ctitcd CC‖ヽ DL11‐llふt()s Lll=ep()cとS IIをCp?′ 、()that cとェ
1,l COntillua‖y pr()cc、、

ヤlyょ11()cとitcd cc‖、thtit arc
じ1lCヽ
ヽ
tと
itcnlcnt,1lark、()nly th()、vh()ic hcaP l｀ 1lc ttk)1)と
l vと
riと
thc 、
、
、
と
blc r'77αsで kccp、 trackc(lby swビ ょ
not yct procc、、
p() ()thCr ccH、()i thc currcnt 、tとitc ()￨ ど
arbaょc c()llccti()n、wccp pha、 cn and′ ど′)thCrwi、cル!てくrkcd 、illcc sWご!1)()、in=thC ｀ ｀VCCp phと1、
c llCCd n()t hc lllと
、
()cc、
cヽ
CaCh(icil()1lly()ncc()ic()ursc. thcsc di、cu、一
pl‐
thcとと
b()vc
til予thた
it thc、slonふd()n()t cntircly itl、y、tclll ha、

Thc llloドt inlp()1‐
ttint ttttttirc()1()ur rcal―
ti11lc yヽ、 tCnll、that,during a s、 vccp pha、 c. it co‖cct、tho、c and()11ly

ccti()n
propcrtics rrhc pr()()t is icll t()thc ilcxt 、、CヽNotc that thc rcal― tilllc ystclll
cauヽ n()cxccuti()11th()、c cctis that arc inととcccヽSiblc and ctrc n()tin thc rcclistl｀(ど′、/̲sでr″、どッovcrhcad on thc prilllitivc、 た(″r. 芝フ々?r′.

at thc bcginninど ol thc illark pha、c P、lthough s()lllC CCHヽandと で? A、nlと
ly bcconlcど arbagc durirl=thcと を
irbを
igc c()licction,thcy

can bc cxpandcd inhnc in thc body()fとarc n()t colicctcd until thc ncxt garbaど c coHcction Thi、

bccausc々

1ljを
出turC is rcalizcd by thc lk)ll()、vintェpr()pcrtics()f thc

ccdurcs cをin bC Cxpandcd into straight― linc codc Thus,
vill bc rclativcly、mallthc csscntial()vcrhcad()fと ごθrrs、

it、
valuc i、′
'7rrrたr,/rrrsでdurillぷ111を
rk phasc, s rtlこ,,,77rrsご(lurillどと?′sy、tcnll

A11とicccssiblc ccHs at thc bcgillning()1■ 11lark pha、c2

Nc、 vly a1located cclls during a garbagc coHecti()n arc

arc cvcntually lllarkcd during thc phasc
ncvcr c()llcctcd during thc s、vccp phasc1111()catcd(1【H77αr々()andざ ltlで
?β()11)rと(o″s.caH、 t()′ごθ″s 卜71orcovcr,

1 をindた 2 arc con、tant、.thc l()()pふin thcsc pro―r()ill thc()vcrhcad,but thcsc
αtt Sutttr i｀/̲ィ
βルごα andと rry′
opcrati()ns arc u、 cd ic、s frctlucntly than othcr prillll―
tivcs in actual list―proccssing applicati()ns Thcy nlay
bc uscd intcrnally k)r assignnlcnts to variabic、 in thosc
Lisp systcms that inlplclllcnt variablc bindings by as―

Thc if statcnlcnt

sociati()n lists tll卜Evcn in such Lisp 、 ystcins, local

A.Cα
/2α
if β
s ビ = 7 7 7 α/ た̲ P 7 1 ″s でt h e n g ご
s ̲ p 2 7 s 力( メr)ia rc usually a1locatcd()nvariablcs in compilcd progralll、

in thc dcnnition ofと ,p′
αごα in Figurc 3 and thc sillnilar

algorithm causcs no execution ovcrhcad ()n thc opcra―

if statement ofと ィJ arc addcd to achicvc thc hrst
βrr7t・

tion to rcplace thc contcnts()f thc systcnl stack ln ordcr
tillle systcm, vc、
to estilllatc the ct1lcicncy of our rcal―

pr()peHy lf thc list structures uscd in thc application

vill bc sho、
vn in Scction 5,ourthc systclll stack and,as、

186

J SYSTEMS SOFTヽ VARE
19901 1li 181‑198

T Yuasa

9cs〔 9cs̲top]
R[NR]:

0

RE23:
R[1]:

Figure 4. Thc 、tatus of ccll、 (ThC arro、 vs ̀ → ' rCprcscnt

rcnccs Truth valucs()fァ ″α/々llclds arc rcprcscntcd
p()intcr rctt・
by l(It)r rr″?)and O(k)ryヵ な?))For this purposc, 、VC tlrst postulatc sOmc sysrで777 ″′̲ックァ,α″rs which charactcrizc our rcal―
tinnc systcrll Hcrc,

stili nccd to analyzc ho、
v frcqucntly garbagc coHccti()naSノ S′
rッ?777 /′α′′α″′(or invariants, k)r shOrt)iS a prop―
cltj7()f thc systcnl that holds bct、
vecn calis to prilllitivc

occurs This analysis is lct to Scction 4

opcrations NaturaHy,cach invariant is provcd by induc―

What is as illlp()rtant as cxccution cfllcicncy is thc sizc tion on calis to priinitivc Opcrations Morc prcciscly,
an invariant is provcd first by 、 ho、vins that thc prop―of prirnitivc opcrations, sincc in many list― proccssing
crtyh()lds immcdiatcly attcr thc systcn3 iヽinitiahzcd bysystcms somc prinlitive()pcrati()ns arc cxpandcd inlinc
′
″
′
r(),
and thcn by sho、 ving that cach prirnitivc opcra―in thc compllcd codc of application programs. Usu―
ally,calls toとごθ″s arc not expandcd inlinc bccausc thction prcscrvcs thc propcrty, a、sunling that α′′invariantsb()dy ofと ごθ″s is rclativcly largc Calls toと ィ
α6α andβ′とrp′α3ダ arc rarc in compilcd programs Sincc cach of(inCluding thc invariant t()pr()vc)hold bclk)rc thc prillli―
tive is caHcd. ヽ
Vc alsO assumc that p()intcr argulllcnts tothc othcr prinlltivcs is()f thc sanlc sizc in thc rcal―
tiinc

primitivc()pcrati()ns arc aH acccssiblc sincc thc c()111̲

systcm as in thc c(〕
nvcntional systcm,thc real― tiinc sys―

plctc pr()()f of cach invariant is too l()ng to ntthi、
papcr.
、
vc only givc a rou8h skctCh()fthc pro()f̲ Ho、 vcvcr.thc

tcnl pro■liscs that thc sizc or compilcd codc is kcptsnlallNow 、 vc nCCd t()sh()、v thc mclllory ()verhcad ()f thc
rcal―
tilne systcm̲ First of all,gごs nccds no cxtra spacc
As l〔)r thc sizc of thc hcap, wc nccd to analyzc thc
dynanlic bchavlor ofthc systcm,、 vhich is thc main issucin Scction 4
3 PROOF OF CORRECTNESSOur mttor c()nccrn()fthis scction is tO provc that thc偽1

rcadcr should kccp it in nlind that thc prool｀is csscntia‖
yby induction
The first ik)に
l r invariants arc silllplc propcrtics cOn―
cerncd 、vith gcs and swで qβ?′Invariant 3.1. gtt is clllpty during idling and、 、
vccp
phascs.
Invariant 3.2. gcs cOnsists()nly()f pointcrs to lllarkcd
cclis.

lowing thcorem holds in thc rcal time systcm prcscntcd
in the prcvious scction

lnvariant 3,3. A singic pointcr appcars on gcs atmost oncc

Theorem 3.1. A‖
and only thosc cc‖ S that arc notacccssibic and arc not in thc frcclist at thc bcginning ofa garbagc collccti()n arc put into thc frcclist during thc

IBvariant 3.4. Thc valuc()f thc variablc sw3epで ris a
ccll pointcr Or is cqual to″rθ
β+l lts valuc is PYrOβ+1

VCCp phaSC
Sヽ

during idling phase,and″ br77r during mark phasc,Rea卜 Tilnc Carbagc CoHcction

J SYSTF̲MS SOFTWARE
1り駅)(11モ181 198

P/Oqん Invariant 3 1 holds bccause gtt is augmentcd
only by gcs̲P冴ざ力 、vhich is invokcd Only in mark phascand gcs is cmpty atthc cnd()f nnark phasc lnvariant 3 2
holds bccausc gcs prrs力 lllarks a cell bcftDrc it pushes
thc ccll pointcr()nt()gcs and no markcd ccH is un―
markcd during mark phasc lnvariant 3 3 holds bccauscg6s」θ″sFr pushcs a cc‖pointcr ontO gcs Only、vhen thc
ce1l pointcd to by thc pointcr is not inarkcd yct,、vhercas187

αr'α″rJ̲b‐) An inacccsふ iblc ccll becomcs acccs―(rr7ツ
siblc only 、vhcn it is a1locatcd by と ごθン,s, but とだo/rs
rcplaccs thc 6α r and car ttclds of thc a1locatcd ce11、
vith acccs、iblc cclis. Thc aHOcation Opcration, thcrc―
R)rc,docs not makc Fgα

ソ? 秘 2 aCCCttiblc On thc othcr
hand, ′eaッで 777でmay bc assigned t()thc cdr part of aceli by sw3ep(), but that ccH is inacccssiblC(Invariant
3 10) Thus. teQッで r77?ncvcr beconics acccssiblc

ガα″r J の g t t β 夕s ヵ d ( ) c s n ( ) t m a k c街
′ソで 7 7 7 ご
pointcrs already on gcs point to markcd ceHs(InVariant( / 7 7αツ32)Invariant 3 4 holds bccause sw3eper is sctto Hbrr72reachable fronn gcs bccausc. 、 vhcn it is called fl・omat thc bcginning of mark phasc, incrcmcntcd in vccp
s、
772″
/た(), it pushcs pointcrs p()inting only to alrcady

rop̲十1 atthc cnd ofs、
vccp phasc
phasc. and is rゴ

rcachablc cells, and, whcn calicd from clsc、

vhcrc, it

Lct us introducc somc tcrms uscd in thc ncxt grouppushcs ofpointcrs pointin3 ()nly t()accc、 sibic ccll、but
invariants Whcn sw3epで′points to thcブ
′
gα
ッ
g
777で
iS ncvcr acccssiblc (InVariant 3 5) Rcacha―th CCHプ
γ[ブ1,thC
九h ccll in the hcap(1.c,〃￨′bitity fronlで
cs may be afft・
ctcd by thc dcstructivc opcr―
οッでthc￨)iS Said to bc うα
sw?qβ?r if′
ations ofと ィ
α6α andと ,β′αてで′οw
じr but only accc、siblC Cclis≧ ブ OthCrwisc.thc ccll is said to bcうρ′
thc swでqβでr N()tc that,during thc s、vccp phasc, ̀̀bck)、v'' and .̀abovc thc swで
the sw?マβ?′qρ?r" nlcan ttalrcady
vcpt'' and ̀̀n()t yct s、s、
vcpt,'' rcspcctivcly Also notc
that, by lnvariant 3 4, cvcry ccH is bck)、v thc swとepで″during thc idling phasc. and cvcry ccH is ab()vc thc
sw3epで r during thc mark phasc

bccomc rcachablc by thcsc()pcration、

Tilu、ゃ′
2rJッ
P2で
で′

ncvcr bcconles rcachablc t十 ()mgこ s( 駒 ツαガα″r 『 乃 I n v a r i a n t 3 8 m a k c s s u r c t h a t t h c a l ―location opcration ofと 6θ″s(',メ,ノ)rcll10VCS a CCH frolllthc frcclist By that()pcration, thc こ「ry/ rlcld of thc rc―
movcd ccH is rcplaccd by an acccssiblc ccH that is dis―

Lct u、 call a ccl1 777 777α′女αう′でif it is nOt lllarkcd andtinct fr()lll′
でαッe r77で Invariants 3 5‑3 1()lllakc surc thatthcrc is a path fr()111ど
ごSt()″r travcrsing()nly n()n―,llarkcd

thc frcclist is au8nlcntCd()nty、
vhcn swβ qρ()CncOuntcr、ccHs cxccpt thc ttrst ccH, 、vhich is dircctly pointcd t()

a ccH that i、not in thc frccli、t ln that cvcnt, sw3ep()

from gcs and thcrck)rc is lllarkcd い71orc prcciscly,777 iS

rcplaccs thc cSJr tlcld()fthc ccH 、
vith′2αッで ′″でintirkablc if and ()nty H｀
thcrc is a scqucncc of distinct

rrr'α″′J8) It is CiCar i｀r olll lnvariant 3 7 that thc(/77ツopcration ol｀ sw3ep()tO auど
illcnt thc ttcclist docs not

ccll pointcr、β(),βl,,β ″(″ >())SuCh thatcausc circularity in thc frcclisti β ois on gcs,

α/′α72r」 9) Thc systcnl llcvcr turns,77α ′た ficlds(/77ソ
of cc1ls bclo、
v thc sw2ep?r to rr夕 で:whcncvcr gご ざp1/s/2

A.(ど2 cithcr β ,A.(7′ β メ11()rβ ′r=′■″β′￨ ￨ ( ( ) ≦ ) ,力 な? ( ( 1) ′3 β ′A , 7 / 7 々7= αヽ≦ ″) , a n d
4 β ″p o i n t s t o / 7 2

ls calicd,sw3epで /=rrbr′ ″and thus n()ccll i、bclo、v thc
swをepでr.Whcn s〃

3eper is incrcmcntcd b)′ swとep(),thc

r77α′た ncld 。 ￨｀thc ccH pointcd to by swでマβでr is turncd

Thc intcnti()n is that nlarkablc cclis arc cvcntually

ル なでif it is rrttg bcmrc

lllarkcd during thc lllark phasc

α/'α″r J Fθ) Invariant 3 10 1s pr()vcd in a 、vay(/72ソ
similar tO thc proof of Thcorcm 3 1 bcl()w and is ictt to

Thc f()1lowing invariants are listcd togcthcr bccauscthcy dcpcnd()n cach othcr in that thc pr()()f of cach in―varlant uscs thc othcr invarlants as inductl()n hypOthcscs

thc rcadcr
Now、 vc arC rCady tO provc Thcorcn1 3 1 Figurc S illustratcs thc transtcr of statc during a garbagc co‖ cction
Each arro、v rcprcscnts a ca‖ to a prirnitivc opcration andlnvariant 3.5. ′ βαソ? /77でiS inacccssiblc

cach b()x rcprcscnts a statc Thc garbagc collccti()n is
lnvariant 3.6. ′ gαッe̲777で1ヽnOt rcachabic fr()mど cs

triggcred by a call toと でοヵs in statc Aゃ 、
vhich transScrs
thc statc t()B In statc B,prilllitivc()pcrations arc calicd

lnvariant 3.7. A ccH is a frcclist ccll if and only if
its tどr ttcld is′でαッで ′27で

a ccrtain numbcr()f tillacs, and rinaHy, a cali toとでοヵstransScrs thc statc to C and starts thc s、vccp phasc Sinl一
ilarly, prilllitivc opcrations arc caHcd a ccrtain numbcr

Invariant 3.8. Thc frcclist is loop― frcc

of tinlcs in statc C. FinaHy,a call toと ごθ″s transfcrs thc

lnvariant 3.9. No cc‖

cali thosc cclls that arc cithcr acccssiblc()r in thc frcclist

statc to D and this cnds thc garbagc collcction Lct us

lnvariant 3.10。 Eachbclo、v thc swでマρで/iS markcd
acccssiblc

ccll

swttp?r is cither illarkcd or inarttble
P的 ヴ

abovc

thc

in state A k%プ cclis.and lct us cali thc othcr cclis b′ αcたcelis. What、 vc havc to provc is that all and()nly black
cclis arc addcd to thc frcclist during thc swccp phascT()do this, 、vc postulatc svo loop invariants

188

j SYSTEMS SOFTWARE
1990111, 181‑198

ph

ｅ
ｓ
□ａ

phase
= idling

T Yuasa□phase
i sweep̲phasemark̲phase

Figure 5. Transfcr Of thc statc during garbagc c011cction

p+lase= idling

1 ?O is on gcs,
A.6αr

= ?′ 11 。r ?′ A.てdr( 0 ≦′< ″ ) .
3 ? ′A . ″α/ た― ヵ 位 ( o < ′≦ ″) , a n d
4 ?″ pOints tO初 .
2 cithcr ?′Loop lnvariant B. In statc B, a cell is red if andonly if it is marked, markable, Or in thc freclist.
Loop lnvariant C. In state C, a cell abOvc thc
sッβqper is rcd if and Only if it is marked or in thc
frcclist
By thc deflnitiOn Of swをep(), it adds a cen to the
frcclist if and only if it cncountcrs a cell″
7 that satishcs
the foHO、
ving conditiOns.
1. ″ is abovc thc swβqβビ/
2. ″々is n()t marked.
3 ″ is not in thc frcclist
Loop lnvariant C says that 772 is black,and、
vc cOnclude
that sw3ep()CVentually puts all and Only black cclis tothe frcelist What rcmains to do for thc proOf Of ThcO̲
rcm 3.1,thcrcforc, is to provc thc t、
v01oop invariants
PrOθ /てソ・とθ?β /″ツα″′α″r β Thc pr00f is split intotヽ
vo cases
A― →B:whcnとcθ″s transttrs thc state ttom A to
B,it pushcs root pointcrs()nto gcs ThOsc cclis dircctly
pointcd tO by root pOintcrs are markcd, the othcr ac、
ccssiblc cells bccomc markablc, and no othcr cclls aremarkcd n()r markablc, sincc no ccll、
vas markcd beforc

= ?′

11

Wc 、 vill shO、
v that tt rcmains markablc Or is markcd
aftcr cxccution of thc 100p bodyr花 ゴ 解縫markablc

を経

名

静

″
ょ ゑ舌 点 ∬ 洪

撚

,丹
,ぶ
・
緒者
督
鮮
と
戦1球
撚
7景

cxccutlon of thc 100p body,1̲ ?ヵis On gcs,
2. cithcr ?′A.6α/= ?′ 11 0r ?,A.dr( 力≦ ′< ″) ,3 ?ヵ A.7PrαrAZ=r/夕 で,″ = 力
4 ? ′A . α′た/ 5 C ( 7 2≦ <″)′ , a n d
5 ?″ points tO//7

= ?メ

11

航ns marttЫ
c rた
″
and″
s
gα
盟焦
』猛掛
縄が
C

sα ?

s o m c 力l

J Af ./ 6β= α?

∧? 2ヵ 1lヵ
a n. ヴ/dこ = βa n d2 力( 0 < 力1 ≦ ″, 0 < 力2 ≦ ″) L e t 力=

0rcθ″S thcn rcmOvcs One ccll
(InVariants 3 9 and 3 4). とmaX(力 1,/J2) Thcn thc rlvc propcrtics Of?ヵ, 一 ,?″
from the frcclist and marks it Thus,Loop lnvariant B
givcn in casc 2 hold and thus,aier thc cxccution of thc
holds atter the ccli Ofと6θ/Js.
loop body,cither rP2 rcmains markablc Or rPr is marked
I〕→ B: we nced only to shOw thatと 6θ″s, と ′ちβα6α,
andと ,p′Sincc no cell ls unmarked during the mark phasc andαでガ prcservc Loop lnvariant B, since the otherliSt Structurcs,mark thc loop body Of 777α ′そ()dOes not attcct thc frcclist,
primitive operatiOns do not modiけ
flelds,and gcs Let us bcgin with Lcθ 72S. Considcr thcヽ
VC COnCludc that rP2α
rk prcservcs Loop lnvariant B,and
loop bodythatと cθ″s prcservcs it.
β :=gCSpoβ ();∧g t t p ″s 力υ . 竹/ ) i
gcsコβ夕sヵtpA.胡 r);Silnilarly, tO shoM′that とぇβ′
α6α prcscrves Loop ln―
variant B, it sufrlccs to show that, SOr cach markablc
cellれ , P/J rclllains markable or is markcd atter a call to
乙屯β′α6α. Lct?。 , ?1,… ,?″ (″ >0)bc a scquence ofdistinct ccH pointers as abovc∧s. 密o f t/ tそ/m≠a?r0 k, ?a 1b,l e, ? 打と? 力 街 p r e s c r v c s t h c(α) L。e t ″b c a n a r b i t r a r y c e l i tC ha sa ct F if ヌ
before cxecution of the body, and lct ?。
four propcrties of this pointer sequcnce and therefore初
, ?1,
,?″
(″￨>0)be a sequcncc of distinct cell pointcrs such thatremains markablc.

Rea卜Time Garbagc Collection

J SYSTEMS SOFTWARE
1990i1li 181 198

189

C6ぽ g2r メ A.6α/ = ?O gCSコ β″s力(χA.6α/)doCS nOthing
application program Frolll thc analysis. 、 ve postulate a
O A . r7 た
7 = 7 r α/ で″( I n v a r i asufficicnt
b c c a u s c r Ax . /7A たα/.= 26? α
cOndition on thc system paramctcrsブV.7,″、た1.
n t
3 2 )
andた 2 to avoid srα′ッαr′θ/r. ic ‐thc situation that thc

A.6α/A pOints to rPP,
Cαs? Jf χ A.6α″ = ?″Sincc χA.cα
7A・
Z flcld of r77 ?r/″Thus,
gcsコρtts/J(χ ァ)turns thc 777α
777 getS markcd aierと,pル(フc 岱? ィf メA . ∽/ こ ? ブk ) r s o m e (ブ0 < ブ < ″) A R e r t h c

ca1l of gごs̲β″s力(χA,cαr),
1. ?ブ is on gcs,
2. either ?′ A,6α′ =

?′

11

0r ?′

A.cdr

=

?,11

freelist bccOmcs empty 、 vhilc thc applicatlon programrcquires more cclls We then use this c()ndition tO cs̲
tilnate thc mcnlory ovcrhead of Our rcal― tilnc system
Also in this scctiOn,wc estimatc the numbcr of timcs
the garbagc coHcctor is invokedln ordcr to rncasurc thc coursc of computation,、vc uscthc numbcr of tinles thatとω 72s is invOkcd: at
い tilllc ・r・mcans ttat thc rth cali toとごθ″sい Givcn an applicationσ ≦ ′< 力) ,∧. 7 r7 たルなで( ブ3 ? ′7= α< ′≦ 力) , a n d(r)and Д (r)bC thc numbcr of ttcclist
program,letダ
ce1ls and thc numbcr()f acccssiblc ccns,rcspCctivcly,at

4 ?″timc r Notc that刀points to 777(r)dcpcnds on thc program、on thc systcm paramctcrsブ
V, んイ, た1, andた 2.

hold.

Thus,
7/2
rcmains
niarkablc
aftcr
A 6αr). If ズ
夕ざ力iS
distinctttom
any ?,g(ざ̲β(χσ ≦ ′< ″) , t h c n / 7 2
0 b v i o u s t y" Supposc?ヵ
ter the statcment χA.6α/:=ノ=ズ fOrsomc力 け ≦ 力<″ )If?ヵ A. ヵis distinct侍
Om?ヵ 11,thcn ?ヵ ∧.6α/ = ?乃,1, iC, χA.6″r)偽rO<ブ?ブ=?ヵ 11(―χ

A.car = ?ヵll</7+1<力Thus,,but thisbut not

L c t u s t (r ra )c Cc l戸e a r l( y1 ,) ダ
= N s i n c c c v c r y
is in the frcclist initialy Thcn,during thc idling phase,r e m a i n s

m a r t t b l c

c c l la ←onc ccll is rcmovcd froni thc llcclist cach timc と ごθ/Ps
is caHcd, but no ccH is addcd into thc frcclist Thus,
ダ ( r ) = (ダ r ‑ 1 ) ̲ l

w h c nt h c
n u m b e r
cclis bccomes cqual to ルイ→thc ttrst 8arbagC COHcctiono f t h ebcgins. Suppose this happcns at tirnc r i‐
α Thcncontradicts the assulllption that ?(), ?1,,?″arc dis―A.こtillct Thcrck)rc, ?ヵ
ど/ = ?ヵ ll. ThiS mcans thatダ( a ) = ル″
the abovc propertics of thc scqucncc ?ブ,,?″ h01d
Suppose that,during thc ttrst garbagc collcction,βand thus 777 rcmains markable, cvcn atcr thc statemcnt/2rrS2"is turncd from′ ″αrkrソ ヵαsでtO sw3ep p/7α sでat timc r=
r i=ノχ∧. 6 αThe sirnilar discusslon applies ぇ
toとう and thc garbage collcction cnds at tirnc r T c Durin3
αcdand、 vc cOn―ρ′
thc rnark phasc,gご s̲βop()iS Callcdた l timcs cach tinlc
cludc that thc priinitivc opcrati()ns prcscrvc Loop lnvari―と6θ″s is ca‖cd. Thc only exccption is thc last ca11 0f
ant B

PrOο
77ツ
′
α
′
α77r C The pr00f is also splitと御 ″s/θ〆とοο
β′
into t、
vo cascs
B― →C:Thc discussion in thc proof of Loop lnvariant

w h i c hn l a y β(c a) li lC S gS t ttl h pat θ
m c s
ni た
As discussed in thc prcvious scction, ccll pointcrs thatarc acccssiblc at r = α arc pushcd ()nt()gcs cxactly

B abovc apphcs also to thc llnal call toと cθ77S in State B,

oncc, but p()intcrs to othcr cclls arc ncvcr pushcd Ontoand thus Loop lnvariant B holds、

C Sincc Loop lnvariant B implics Loop lnvariant C,

gtt Thcrcbrc‐g岱 ノ?β()iS Calicd totallyス
during thc mark phasc. Thus,

Loop lnvariant C holds、 vhcn thc state becomcs C
C ―→C: We・ need only to sho、 v thatと oθヵs prcscrvcs

う一α=「刀(α1])/たLoop lnvariant C, sincc the other prilllitivc opcrations,

During thc s、 vccp phasc, thc valuc of sweepで
r is in―cremcnted by た 2 cach timc と ごο/rs is cancd Thc only

vhcn thc statc bccomcs

vhen callcd in statc C, do not afScct the frcclist, mark、(α)times

品elds()f ccHs, and thc valuc of sw3eper during thc

cxccption is thc last ca1l ofと
cθ″s、VhiCh inay incrcmcnt

veep phasc Thc a1location opcration of 乙s、SWでマβ?/by lcss thanた 2. Since sw3epで r is totaHy incrc―

6θ/Ps prc―

serves Loop lnvariant C bccausc it rcmovcs onC CCllfrom the ttechst but nlarks it if it is abovc the swttpで /̲

nlcntcd byブV,

Also,swttp()preserves Loop lnvariant C bccausc nonc

C―う=「N/た2]of thosc cells put into the freellst and nonc of the un―

To simplitt the calculation,let us assume thatmarkcd cclls are above thc sw?qβ

2r aiCr thc call ofswcqβ g/().ThCrcforc,wc concludc thatと6θ″s docs prc―

servc Loop lnvariant C

multiplc ofた2

c ―う= N / た2
Sincc no cell is addcd into thc frcclist during thc mark4̲THE DYNAMiC BEHAViOR
ve analyze the dynanlic behavior of ourIn this section,、real―tilne system. In particular,vc、arc intcrested in thestatus of thc frcclist during thc cxccution of a givcn

phase,ダ( r ) = ダ ( α) 一 ( r ―α) ,f o r ≦α′≦ う

On thc othcr hand, thc valuc of,P(r)during thc s、

vccp

190

j SYS「E卜4S S()FIヽVARE
19り0モ11, 181‑198

T Yuasaphasc dcpcnds on thc distribution ofthc black cclls(iC , thc lowcr boundダ
thosc cclis that arc not acccssiblc nOr in thc frcchst at=0,1, ,N/た 2,lct
r=・の OVCr thc hcap R)r′lb(r)ofダ (r)F ( α) 一 ( r ‑ 2 ) ,』(′)bC thC numbcr〔)f black cclls anl()ng the flrst′*た2cells〃
1 0 1 , …, F r t みた2 ‑ l l i n t h e h c a p(.'ど)givCS thc
number Of black ceHs that arc put int()thc frcclist byダthcib(r)α ≦ ′≦ う 十 ど ￨ ￨ダ ( α) 十 ( ( r ― う 1 ) * た 2 ‑ 刀

flrst,calls Of sll13ep()Thc flrst can to swttp()Occurs
att i m c r =+め
l a n d t h u s , a t t i m c r ( b +′1≦
≦ ご+ 1 ) ,―う‑ 1 ) b l a C k
C e l i s
h a v cb c c n
p u t
3 ( ′

i n t oSincc one ccH is rcl13ovCd fr011l thc frcclist by cach ca‖
ofと こっ″s,wc obtainヤ′わ/ ( r ) ヵ「( b ) 十β( r 一か ̲ 1 ) ̲ (―) ,= ダ( 2 ) 十
』( r

―夕) ,
う‑ 1 ) ̲ ( ′R ) r b + 1 ≦r ≦ご 1 1
Thus, ど (′), tOgcthcr with ダ(2)(=ル の, 7V, た1‐and
た2 , c o n l p l c t c l (y r )d Rc )t ≦
n ≦
c ご
s 戸
rt rα
1 l
A l
'(r)thu、
though thc function 炉
dcllncd nlay pOssibly
havc ncgativc valuc、 、thc systcm causcs thc ・ ｀72οsrO/̲いαgで c rr()r vhcn
、 thc numbcr()fl｀ rcclist ccHs(ic , thC
valuc()f rree 6θ 夕″r)i、 g()ing to bc ncgativc ln()rdcr
負)r thc llrst 8arbagc c()1lccti()n to procccd succcsslヽ
ュlly,
it is ncccssary and sufflcicnt that ダ (r)≧ o R)r ali r( α≦ r ≦ ご + 1 )'Thc distribution function ど(′)can bC an arbitrary
function that satislics thc lk)1lo、
ving cOndition、
1 . β( 0 ) = 0‑ 1 ) ≦』
‑ 1 ) ￨ た
2 』 ( ′
2 ,( )′≦ 』( ′( ″) 一 ダ ( 2 ) )一( r ―α) ,t h c
f r e c l i s t .
b 十 ブ + 2 ≦ r ≦ ご+ 1

Notc thとi t in thc cxtrcnlc casc that all black ccHs arc｀
locatcd at thc highcr part()f thc hcap,(r)is7●idcnticalt ( ) ダl h ( 7 ) T h i ヽm c a n s t h a t rl「h(r)itt thc bcst possiblcl ( ) w c r b o u n d o l戸‐( r ) ダ ￨ 卜( r ) d c c r c a s c 、l n o n ( ) t o n i c a l l y
w h c n ≦αr ≦ わ + 〃 + 1 , b u t i n c r nc la (s )c n、( ) t ( ) n i c a l l y
w h c n b + +び2 ≦ r ≦ ごキ l A s i m p l c c a l c u l a t i ( ) n s
t h a t r h1 b冴+( ゎ1 ) < ダ l h ( ￨ゎど+ 2 ) T h u s , lメh ( r ) t a k c s
thc smaHcst valuc、
vhcn r =わ ￨ 〃+ 1, and a sulllcicnt
c o n d i t i ( () rn ) 0≧i (k α)≧r ′ダ≧ ご+ 1 ) i 、

)(α
ダ( α
1 卜
1 ‑ α) ≧0 ( 4 . 1 )) 一( b + t ( / 1 ( 2 )カ一 ) ) /2た、vhich is cquivalcnt tO
ダ( r r ) (≧刀+1/た
2 ) 1 1 ) / ( 1 ‑ 1 /2女(α)) * ( 1 /1たUsua‖ y, it is difllcult to cstinlatc thc valuc()1｀′4(2)lk)raa cccs、iblc
givcn progralll, but thc illaxinlunl nunlbcr ol｀
cc‖s′4‖1.x is usually rclativcly casy t()cstinlatc.Byingu、/1 nlax, wc obtalll thc l()‖owinど 、u fllcicnt cOnditi()n k)r
F ( r ) o≧んイ≧( / 4 i n a x *1( 11/1たk ) r ' 1 , 2 , , N / た2
/2た
) 1 1 ) / ( 1 ‑ 1 /2 女)3 』( N / た2 ) = N ― Д( 2 ) ダ ( 2 ) ( l n u n l b c rb l oa lc ｀k
Thc abovc di、 cusslon applic、(4.2)■ls()lk)r thc 、cc()nd

cclls l)Sincc

garbagc c()licction il｀ ダ (r) = 7'イ at thc bcginning ol
thc sec()nd garbagc collccti()n This condition is satis―

β( )′= ど( N / た2)

ncd ifダ (r)≧ ブ,ィ ilnmcdiatcly atcr thc fir、
coHcction, ic., ifダ (ご+ 1)≧ んイ, Sincc

2 ) 一』( N / 々
2 1))
(β
(N/た

―(3(′ 1 1) 』(′))

t garbagc・｀一わ) 一( α + 1 )ダ( こ十り = 戸( の ￨ 』( こご｀
= 力( ク) + ( A l ―力( α)ダ (2))一
M ( の/ 女1 ]一N / た2 1≧ N ― ス[ H a 、「スn は/ 々1 ] ‑ 7 V た2 ‑ 1

2 ‑ ′) 米
た2) 一ダ( α≧7 V ―刀( α) 一( N / た= , 米た2 ‑ ス ( α) 一 ダ( α)■7 V ネ2 ) 刀 川d x * ( 1 1 /1た) 2(1 1/たa sufncicnt conditi()n ft)rF(ご +1)≧

フ
ト
イ iS

N 米( 1 ‑ 1 2/ )たДぃ
‑2〃≧ょx * ( 1 1 1 /) たand sincc β(')iS nOnnegativc,

(4.3)

︿
Ｕ

ヽ

＞

σ
β

ｒｌブ

Thc samc discussion hold、 ltDr succcssivc garbagc col―1 ≦′≦ び

ｒ

今と
た

ＩＲ

/ 4 )( 戸α( )α,+冴1 ≦′≦N / 2たlccti()ns Thcrcf()rc,vc、conCludc thc k)1lo、
v inど
Theorem 4.1. Givcn an apphcati()n program, if()ur
rcal―
tinlc systclll satisflcs both(42)and(43), thcn aH

whcrc冴 =[(ス(α2J FIom this,wc obtain garbage colcction prOcccds succcssfully)十ダ(2))/たJ SYSIEMS SOFTヽ VARE
19901111181 198

Thcorem 4 1 is uscfulto nnd appropriatc valucs ofル″アfor a givcn program Practically, 、
and r、
ve can ignorc..+1" in(4.2)and ̀̀‑2" in(43), sinCC′
V, ソ,イ, and/4inax are much larger and, inoreovcr,(42)and (43)are dcrivcd from thc、vorst―
case analysis Thc practicallyvalucs are, thcrcSorensafc・

舟″= 刀n t t

)た/ ( 1 ‑2 1) / た
x1*+(11/2/た

thc scquencc{αh α2,一}偽dCnncd by
1. 夕 ￨=ハ ′十 1
2 . α, 1 1 ‑ ,α= N ― 刀( α) ,′for,=1,2

Again,undcr thc assumption刀(r)=/1ntan.thC numbcr
of garbagc coHecti()ns is cstirnatcd as

T / ( N ―スn l c a n )N = 刀n H x * ( 1 +1 2‑ /1 た
/ 1( *た2た) ) / ( 1 2‑ )1 2/ たthcn ん イ ー「0.105刀 ‖la xln comparisOn, for thc cOnvcn―

For instancc, if kri = た 2 =20命and ブV == 1.216ン 4nlax

ｎン

Rcal Timc Garbage Collectionti()nal systcnl with a stop 8arbagc co‖ cct()r in F18urc l,

This cxprcssi()n supports thc v、idcly bclicvcd rulc that
V is,thc fc、
vcr tilllcs thC garbagc collcctor isthc largcrブ
invokcd.Although this rulc d()cs n()t apply in somc cascs

thc smallcst safc・valuc f()r,V is刀 [ll」
x ln this casc,thcrc―(indCCd,it is n()t difncult to llnd a countcr cxamplc),thisrulc sccms to apply in lllo、
tcたiscs Silllilarlyn thC roughforc, thc rcal=tinlc systcm nccds 21 6ツ

cstinlatc )rf〔thc rcal一
tilllc systcm abovc sugscsts that thc

l morc nlcnloryトイ i、and thc largcr lV i、
Sn3a‖Cr フ, thc ttwcr tinlcs thc

f()r thc hcap
No、v lct us cstiinatc thc nuinbcr()f tilllcs thc garbagc
c o l i c c t o r i s i n v o k c d , a s s u m i n g t h a t N イs
a n daルtistt b()th(42)and(43) SuppOSC that thc,th garbage coliccti()nbcgins at tinle r = 2, and it cnds at r =ごメ As alrcady
shown,

8arbage c()llcct()r is inv()kcd
V and
WVc havc atrcady sccn that thc sal●valucs ft)rブフけイarc, rcspcctivcly, 1 216/4n.lx and 0 105刀
n l.x, in casc
た 2 ‑20 1f wc assumc ttm.x ‑2ス
mc」n.thcn
イ. thc nunlbcr()f garbagck)r thcsc valucs()fブV and ブル

々l

incコ
、R)r thc rcal timc sy、tcm ln contrast, with thc satt valuc()f7V
Дnltlx k)r
collccti()n is about 0 82T/スj′= 「/ 4 (′こ
α1 ] I N / た2 + α′)/たThc numbcr of llcclist cc‖ s altcr thc Fth garbagc co1lcc―

thc convcnti()nal systcm‐thc numbcr of garbagc col―lccti()n is ab()ut T//4tncan Thuヽ .with thc、 c saに valuc、

tlon ls

イ, thc rcal―
cs ress garbagc
ofブV and 7じtilllc ystcnl、
cau、/((111)rV*(1̲1/た2 ) 一 ス( αll l′) 「 ス ( αr)/女Thcn, thc systcnl is in idling phasc until r ′=αll andthus,

hand, it is clcar that,vith、 thc salllc sizc()f hcap‐
thc
rcal―
tinlc systcm cau、cs nlorc =arbagc c()Hccti()n thanthc convcntional systcm F()r in、tancc, with thc hcap
thc
4 nlょ
sizcブV ―‑ 1.216ン
xn thC C()nvcnti()nal systcnl caH、ダ ( r ) = (ダ・ご̲ 1 ) ,こ′+ 1 ) 一( r ̲ ′l b rcollcction than thc convcnti()nal systcn1 0n thc othcr

lcct()r about 0 7T/ス【
ncan timcs Thus.thc
garbagc c(】
イ illorc garbagc coHcction
rcal―
t inlc ystcm、
causcs 17リ
than thc convcntional systclll

C , + r1 ≧≧α′￨ ￨

ン、
Sinccダ (α′1 1 ) = ―アー舟ダ( デご1 1 ) ( α′1 1 ‑ デ
ご 1 ) = ″5 SYSTEM STACK

From this,wc obtain
α′1 1 ‑ α′
) 一〃 ,, T N 一 月( α

偽 r ′= 1 , 2 ,In this sccti()n.
vc 、
cxtCnd Our rcal―
tiinc systcnl s()that
thc application program can handlc thc ノ
ず
srで
″ srα
c々
Thc systcnl stack contains p()intcrs and is typically uscd

for argumcnt passing and variablc a‖()cation Just likct array R,thc systc■
thc ro(〕l stack c()nsists()f root point―
If WC
ers Unlikc R,howcvcr,thc maximum sizc otthc systcmac ( ) n s t a n VSS
n t . n nluch, t h clargcr
nthan thc sizc ol｀
stackブt tist assumcd
R

This formula, togcthcr 、vith thc initial valuc of lαi=N― 〃 +1,dcines thc scqucncc{αl,α2, Ia s s u m ct (h ra )t iスsi d c n t i c a lt oα′= み ( N ―刀m c a nルの― 十刀m aせn + 1

and thus thc systcm callnot takc carc of thc pointcrs on
thc systcm stack all at onccvhen、 a garbagc collcction

and、vc obtain a vcry rough cstilnation of thc numbcr ofv Thc prilllitivc opcr―
bcgins,as、vill bc discusscd bclo、
ations on thc system stack arc Nで r77βは)ゃウ (),N̲β ttS力rノ()rcturns rr夕 ? if thc systcnl
and RttrttTX) SS̲で r7Pβs力(ズ)stack is empけ ,and rCturnsル な?othcrwisc ssp夕ont()thc
systcm
stack
ss̲Pθ
p()
pushcs thc pointcrメ

3arbagc collccti()ns as

T/(N―刀mcan‑7)
whcrc r is thc numbcr()f tinlcsと でθ/rs is caHcd during
thc cxccution ofthc givcn program.Fぐ)r thc convcntlonalsystcnl、vith a stop garbagc collcctor givcn in Figurc l,pops up thc systcm stack and rcturns thc pointcr prcvi―
ously at thc top of thc systcnl stack192

J SYSTEMS SoFTWARE
1990i ll: 181‑19】

T Ytlasa

procedure ss̲push(メ )ibegin SStop:=SStop+ 11
RISStOpJ:=メ
endi

procedure Lconst',X,ノ );beJn l garbagc cdにdbn dAPichcrl
if phasc =:1lark̲phasc thenbegin mark()i
if gcs̲cmp呼 ()theniF SVtOp,ofunction sspOp:pointcri
begin ss̲pop:=尺 iSSt()pli
SSt()p:=SStOp‑ 1endil pttCCSSing ttc savc ttack lthen for,:=SVt()p downto max(SVtOP―
doどcs̲push(SVirl)cise phasc:==、wcCp̲pha、 cfunction ss̲cmpty:B()()icani ss̲cmpty:=(SstOp=NR)￨
Figure 6. Priinitivc opcratiOns On thc systcnl stack

To simplitt thC discusslons on thc system stack,wc
silnply expand tt so that it can cOntain up to NR十ブヽrss

polnters.
var R:array[1.̀(ブ V沢 十 ′VSS)10fβθ′″reri

By this cOnvcntion, とざ?′′(′,メ)and と ggrr(めarc uscd
also to access thc system stack A ncw variable SSr9β
kecps thc index of the top Of thc systcm stack 、vithin
梁. InitiaHy, SSrθV尺 . Thc threc primitivc
β is sct toブ
opcrations on the system stack is deflncd as in Figurc
6.Now,thc pointcrs尺【ll,一 ,ズ iSS′?βl arc the only
root pointers and thosc and only thosc cclls that arc
reachable dircctly or indircctly fronn thcsc r00t pointcrs
arc acccssiblc
For this modcl, thc algorithm prcscntcd in Figure 3
corrcctly wOrks, if、
vc rc、
vritc thc fOr loOp to initializc
vs.
garbagc collection as ftDllo、
f o r ′: = l t O s S r οβ d O g c s P 2 r S 力( ズ[ デ1)
Ho、vevcr,ir SSrop is relativcly largc,thcn thc cxecutionof Lco″s wili takc a 10n3 tiine whcn phase is switchcd
frOEn Jび′′″g to 7/2α
′た̲β力αsで This vlolatcs thc real timc
propeHy of the system. Instcad oF proccssing thc root
pointcrs all at Oncc, Our rcviscd systcnn proccsscs atmost a flxcd numbcr of root pointcrs cach tilncと6θ″s
is called (seC Figurc 7) SincC thc cOntcnts of thc sys―tcnl stack、
vili changc as cOmputatiOn prOcceds,、 vc neCd
to savc the contents of thc systcm of thc stack 、vhen agarbagc collcction begins Or else,、 ve cannot inakc surcthat all acccssiblc cens at thc beginning of 3arbagc cOl―
lection arc cventually marked during thc mark phase
For this purpose,、vc introducc anothcr stack,called theSαツg SrαCた, 、
vhich is implemcnted by an array Sン ′anda global variablc 4′
Sン
op

k3,1)

end
elsetf Phasc ‐ s、
vCCp̲phasc them
begin swccp()￨
if s、
vccpcr ■ Hl()P then phttSc i=:idhng
end
elseif rrcc count ≦ ノ,イthembettin phasc i=mark̲pha、 ci
swccpcr i=Hbtnl,
a V C はj l l l c H s n s y H c m t t a c k )￨ヽcopy̲、ystcm̲stack(SSt()p)iSVt()p:=sst()pendi｀
if frcc cOunt≦O then crrOr(｀
nO st()ragcい)ilocadOn}l CCllぶ
β :=lrCC liSti
l l c c l i s t : =∧βc a r i
frcc cOunt:=frcc cOuntii

A cari=xt
βA.cdr i=ノキ
βA mark:=(βWCCpcr)i
タ
≧、
ズ1 ′
卜= β

end l of Lcons};
Figure 7. とこっ″s Ofthc rcal―
tinic systcnl、vith thc systcnn stacking thc rnark phasc,と6θ77S proccsscs at rnostたJ pointcrs
on the savc stack cach tinlc gcs bccomes cmpty attcr thc
call of″α″た( ) . H e r C , た3 i s a s m a l i c O n s t a n t , lli kacnたd
た2 Thc copying opcration copy̲sysrαη̲̲s確 た(SSrop)can be dircctly irnplemcntcd by thc undcrlying hard―
warc, using thc so― callcd block transScr nlechanism
which alinost all general― purposc machincs support
Sincc thc sizc of thc systcm stack is at
Vズmostブ
VSS
十ブ
and sinceハVSS is bounded by tcns of kilobytes in mostlist―
processin3 systems,wc can assumc that thc copying
opcration takes only a short tillle
Prinlitive opcratlons othcr thanとごοヵs arc thc samc as
those in thc real―tirnc systcHl vithout、
thc systcm stackln particular,the rcvised rcal―
tlinc systcni causcs no ex―

tra burdcn on thc most frcqucntly uscd operationsと6α/
and とcdr As already scen in Scction 3, by expanding″αrk()and sWと ep()inline and by expanding the loops
in these proccdures into straight―
line codc,thc essential
var S/i array[1..ば択 十 NSS)】 Ofpθ,″rgri
ovcrhcad on乙 6θ″s is relativcly smaH In addition,since
た3 is a constant,the for loOp to proccss thc savc stack
varS/′οβ :′″rcgeri
can bc also cxpanded into straight、
linc codc Moreovcr,
When Lcο ″s is callcd in idling phasc,ifthe length ofthc thc reviscd system causes no cxccution ovcrhcad on the
frcelist bccomes too short,thcn all pointcrs in thc system stack opcrations including dircct access to thc stack cn―/by ttpげ
stack arc copied into Sレ
Cた(ssrOp)
titics byとscrr andと g2′/
ジ ざr?r77̲Srα
and the valuc of SSrop is saved into S)/roP Then,dur―
The corrcctncss discussions in Section 3 apply, v、ithTimc Garbagc Collcction
Rcal―

J SYSTEMS SOFTヽ VARE
19901 l1
Ⅲ 181‑198

lllinor changcs, to the reviscd system First of all, 、vc
add an invariant.
Invariant 5.1. Thc savc stack is emptt during idlingand s、vccp phascsl｀hen, 、vc redcinc thc notion of markablc so that, in
addition to gcs、 thc savc stack can bc rc3arded as thc
origin of inarkablc celis That is, a cel1 777 iS 777α/たαb′βif and only if there is a sequcncc of distinct ccll pointcrs?o,?1, 一,?河 (湾>0)Such thatl integcr(Σ)}L/(′)]means thc sum of/(')fOr】
ヤP(′,that satisRcs P(').)Herc,to simplitt the calculation,
wc havc assumcd that(N尺十NSS)/た3 is an integer.
On thc other hand,the timc for thc sweep phasc(1.C,C― う)iS Samc as in Scction 4,and(4 1)is stili Sufttcient' ' i nf O r
F ( or () α≧r C p l a c iαn g ̀ ̀ b ―≧r ≧c + 1 ) B yvith the above uppcr bound,、ve obtain a sufflcient(4 1)、
condition for(4.1).

舟イ≧( ス+ 1 / た2 )m a x * ( 1 /1た

i ?O is either on gcs or on thc savc stack,2. cithcr ?′ A.6α′ = ?￨11 0r ?,A.car = ?,ll
( 0 ≧′< ″) ,女 = ル なc ( 0 < ' ≧″) , a n d
3 . ? ′ハ. ″α′
4. ?河 points to″
Anothcr changc is to rcplacc invariant 3.2 、strongcr condition

3)/(1‑1/た
2)
十ば 尺十NSS)/たF ( C + 1 ) = ダ( α) 十ゼV ― / 4 () α―ダ( 2 ) )一( b 一の 一N / た2 ‑ 1 ≧ N * ( 1 ‑ 1 / た2 )一月m a x * ( 1 +1 1) / た一(N尺十NSS)/た3‑1vith alnvariant 5,2. ′gαソg /77でiS rcachablc neithcr fromphase, gtt bccomcs cmpty(and thus somc pointcrs
on thc savc stack are proccsscd)at r =び
1, … ,び″11y , ヵ< び1 <…< ら < ち + 1( α丁b ) . C l e a r l 一
θ
31
Also
assume
that,
aRcr
r
=
が
SSrοβ /た,(, =「1,2,… ,ヵ),gcsコpοβ()iS Callcdで , tiincs until thc savc
stack is processcd ncxt tiinc Then、 vc have
偽r,=1,2,…

,"たソ カαsc at r = α , gcs
When β んαsc is turncd to ″α″
60tts iS Callcd, thc saveis cmpty. Thus, the ncxt time とstack is ccrtainly proccsscd Thcrcforc,ブ
1=2キ l Lct?′and r,bc,rcspcctivcly,thc quoticnt and thc remaindcr
of 2, divided byた1. Thcn,thc tilne for thc mark phasevs.
is calculatcd as lollo、う一α=(び1 ≦′≦″} [′1‑α) 十Σ{ ′+1冴′びl
= 1 + Σ{ ′1 ≦' ≦″} [ m a Cx ,( /「1た1,1)1= 1 + Σ{ ′r,=0&?,≠
0 } [ ￨? メrF≠0 } ￨ ? , + 1Σ]{十′=?,=0}111r′
十Σ{ ′= 1 + Σ{ ' 1 ≦}[1]' ≦イ[ 9 , 1 +{ Σ' r ,0才= ? ′= 0 } [ 1 ]十Σヤr ′= 1 + Σ{ 1′1 ≦′″′≦ガ[ ( ?十′′) / 1た] 十―Σ{ ' r , = 0 & ? ,0 ≠
}111
3]
θ/た
lJ十「
SSr?β
≦ l十 レ【α)/た≦ 1+レ

無α)/たlJ十 (N沢 十 NSS)/た 3

(5.1)

Sincc

gcs nOr llonl the savc stack
As for the analysis in Scctlon 4, the mark phase
may takc more time than「 Д(2)/た1],Since n()t onlyrた() may invokc
the last but also othcr calis to r77α
gcsPο P()lcSS thanた l timcs Lct SSrθ βθ bc thc valuc
Of ssrθ p at r = αAssunlc that・ during thc mark1],1)+4,が,11=max(「で
,/た

193

t h c

s u f f i c i c n t

ル
c O+ n1 d) i≧t′イii o nSN ネ( 1 ‑ 1 /2た)一
刀m a x * ( 1 + 11 /) た
一ば 尺十NSS)/た3‑1≧ ν

f o r

F ( ご

(5,2)

Theorem 5.1. Givcn an application prograHl for ourh thc systcm stack,if b()th(5.1)andrcal time systcm w■(5.2)hold,thCn al1 8arbagc collcction procccds succcss―
fuHy
Lct us ignorc ‑1''in(5.2)Thcn thC practically safc
valuc ofブV is/ 4‑た1 /1(米たた2 ) ) / ( 12 ‑) 12 / た(H 1l +a 1x1/米

plus thc constant

2‑1))た2‑1)*ぜVR tt NSS)/(た3米(た(2米= た3 = 2 0 , t h tc i mr ec a sl y― s t c mi n
c 1a =s た
c2 たwith thc systcm stack nceds l.216ス nlax+0,102(ゴ V尺 十NSS)Cells in thc hcap ln addition,thc systcm needs
thc spacc for thc savc stack which should contain up
VSS Cells.Thus,the rcal timc systcm nccds
tOブV尺 十 ブ
沢 +7VSS)mOre sPace than the0216刀 max+1.102ばvith the systenl stack
conventional systcnl、
6 MULTIPLE KINDS OF CELLS
So far,、ve havc assumcd that only a singlcけpc of CCliS, COns cclls)arc aVailablc. In this scction,vc、cx―(1.eゃ
t irnc systcln so that it supports other kinds
tcnd our rcal―
vell, such as symbol cclls in Lisp Usually,of cclls as、
cells of a same typc occupy a nxcd size ofrncmory and,thcreliDrc,if frcclists arc used to maintain availablc cclls,
万?で̲′なr.Thc sys―each cell呼 pC α has its own freelist o丁
tem kecps track of the maximum numbcr of a1locatable

194

J SYSTEMS SOFTヽ VARE
,990111: 181 198

T Yuasacelis′
Vα fOr cach ttpc αA pointer can pOints tO a cellof anyけ pc and, 3iVen a pOintcr, the systcm can dctcr―■line the けpC Of the ccll pointed tO by the pOinter lnprocedure Lacons(′,メ1,メど, ,メ"i)￨begin l garbagC c()llccti()n dispatchcr l
if phasc̲=nlark̲Phasc thenbegin mark():
ordcr to simplitt Our discusslon,wc assume that celis
ifどcs̲cnlPty()then phasc!・ i swccp̲̲phaschave ⅢwO cOmlnon t‐
end
lclds rジ
/た:The rノ
pe and 772α
βe fleldciseif PhasC｀｀
VCCp pha、c thenbegin swccP()i
if s、
vccPcrHt()p then phasc:こ idlinど
end
pointers,and thc number of thcse pointcr nclds is ttxcd
d s e i lf T cαc
c ( ノ
)｀
uィ
イ
Y n tt ≦h e n
flDr cachけpC ttr cach typc.lct/1,一α,テ:Ⅲbe thcbe=:m pha、c:=mark̲phtsci、
w c c p c r : 二H b t n l lf()r′i = i t O N R d o g c s p u s h (￨オ′
1)

縄堺鶴協1濫棋艦糸〔
3七
t悟
竹
eお
、
端嵐

陥
VC mC ttbWhg:補認梶燃艦肝塊F猟挙
L tth瑞 d灘:苫七s堺
電 品艦:苫!t)必を祐,iti皆endi
i f ̀ Y l r c c c O u n t ≦( ) t h e m c r r o r ( n tt)く)、r a g c l l ) r t y p c)̀iY …

ll αCCll』10cttiOn
ncld Of thc ccll,and scts the pointcr
to均 tO thCん
ノ :=̀Vtrcc listi

去 i朗 n獣
絲la:苫
L材没
爪
と
品と
:rヽ
ォ∬
抗
縄￨
焦
像
to an αccll and rcturns thc pointcr in thc yi′t h c c c l l i n t o[ズ′￨/tαl l c c l i s t i =A βαt r c c c ( ) u n t i l= Tαc c c o u n tli

A/1:.ャ
11βA / ュ : ニメ2i
β1lcld Ofthc ccll

者狩
点
:J竹
w∝
,★
あ≧、
ドr)

3 Thc updatc proccdurcs と
αrprα
て
1(メ
,ノ),一 ,iメとα?ル qん ィ,ノ),Similar toと rprααィメ,ノ)Each!(メとα卑9ル句 (メ,ノ)rcccivcs a pOintcrメ to an αccll

ズ￨ ' =卜= βCnd l()11ッ
C(〕
n、li

and rcplaccs flCld
thc/ブ of thc hノ
ccll w「igure 8. Thc consing proccdurc k)r typc(YAs in ScctiOn 2, thc systcnl initializati()n proccdurc,″′r()prcparcs ttcclists so that cach ttee̲′なr consists
ol‐7Vα ccHs or typc α、vithout 10ss()f gcncrali呼 , wc
can assumc that ccHs in thc frcctist f()r typc(x arc linkcd

thc typc ncld()1｀ thc cc1l Thc can t()こ っ″tSr2(メ)nlu、 t bc
rCPlaCCd by a can t()thc b()()lcan functi()n that rcturns

through thcirメ
1 品C l d s .

rr″で if and Only if its argulllcnt is a ccH pointcr OthcrF〔)r this inodcl、
vith,1lultiplc cc‖
typcs,Our rcal―
t imc
system in Figurc 3 is cxtcndcd as follo、
vs.Each consing/(′
prirnitivc opcrとitions such asと 貿 ′,I)and とnccd n()t bc changcd

proccdureと α6ο々s(′,メ1, …,χ打【)bCgi1lS with thc samc
ャごθ7Ps in Figurc
garbagc collccti()ndヽ
p atchcr as that inと3,cxccpt that thc dispatchcr inと αごθ″As(′,メ1,一 ,メ″(H)uses an α―
spccinc numbcrフ ト″α (scc Figurc 8)That iS‐
a garbagc colicction starts whcn thc size 昭erなofげ r
becomcs lcss than or cqual to フトイ(Y f〔)r somc typc α

密 (メ,ノ)Thc proof in Sccti()n 3 apphcs also to thi、Thc only changc、

systcmvc havc to inakc is to rcplacc invariant

37、 vith thc f()1lo、
villg:
lRVariant 6.1. Thc frcclist k)r cach ttpc iS 10()p― frcc
ln ordcr to makc surc that cach c()nsing proccdurc bc

The rcst of cach cOnsing procedurc is sirnllar
to succcssfuHyゃthat
cxccutcd
vc havc t()pr()vc、
ofとωヵ
s.Likcと餌ァ
的nctionと,cach rctttcv】
αんは)
Simptt rctumS thC v』
uc of χ.Aん Likcと ?筋 密,invariant 6.2. F()r cach typc α .thc frcclist()1｀
typc(Yeach updatc proccdurcと
α?わり顎メ,ノ)ChCCks thc cur―consists only()1(】 cclls
A.ん withノ if thC sys
rcnt phasc bcbrc rcpLcingメ
But this is obvi()us bccausc s″
3ep()adds a nOn―
tcm is currently in a mark phasc, thcn it cxccutcs

S力
̀A.メ
̲̲r'夕
(ジ
g̀ざ
)
ブ

markcd ccH into thc frcclist()1｀ thc typc ot｀thc ccH
Lct us dctcrminc thc sufficicnt c()nditi()nk)r succcss―
ful garbagc collcctions As in Scction 4, 、vc mcasurcthc coursc of colllputati()n by thc totai numbcr()f tilllc、A.乃
beJR!:ス′″たαざ?men S力
gcsp″
Pん
￨
▼):
:ア
ド
4,;モ

αttqィブprocedureと(X,ノ)ithat thc consing pr()ccdurcs arc callcd Lct′endi

Thc loop body of ″αrた()muSt bc Hlodined so thatit pushcs a1l of the pointcrs in thc pointcr flclds Thc
Vhen it encountcrs a non― marked
proccdure sw?qβ (), ヽα ccli not in the ttcclist, puts the ccll intoギ ree̲′な′Both′竹α′々()and sWθ q,()Check thCけ pe of a ccll by

4(r)bc thc
totai numbcr or acccssiblc cc1ls F()r cach ccll typc α,
lct Dαθ/ 1 s i s c a l l c d ,( r ) b c t h c n u m b c r o f t i l n c s t h αご
atとuntil timc r.Also、
l e t ダてY(r)and刀 Y(r)bC thc nuinbcr
of frcchst cclls and thc numbcr of acccssiblc cclls, rc―
spcctivcly,ofけ pC α attimc r. obviOusly,at any timc

r , o ≦D ( (γr ) r≦ a n d

t h c ちィs( ur m)) 土r o fa 近
l icqual t()′As in Section 4, assumc that a garbage col―t y p c siReal―Tllnc Garbagc Collection

J SYSTEMS SOFTHVARE
199()ill:181‑198

lection bcgins at r =αand cnds at r =c. Also assumc
thatノカαs?is turncd fronl材 α/たP力 αsc tO swgqβP/2αSで
at r =ぅ during thc garbage conection rlγ (47)may bc
larger than ノ
じ″α, since thc garbage collection may betriggercd by thc consing procedurc ofthc cell type otherthan α/ α( α
″α
)≧ 7じ

195

Theorem 6。 1. C}ivcn an application program on Our
real―
tirnc systenl vith、 multiplc kinds of cclis, if bOth
(6 1)and(62)hold f()r eachけ
pe α, thcn all garbagc
coHcction proceeds succcssfully
Extcnslon sinlilar tO thosc in Scction 5 cnablc thc
rcal―
tirnc systc,1、
v ith multiplc kinds of cclls tO support
the systcm stack and 、
vc Obtain the ftDi10、
ving thcOrem
Hcrc, ハFSS andた 3 arc thosc introduccd in Section 5

Thc tlmc for the mark phasc and thc timc fOr thc
s、
vccp
Theorem 6.2. Givcn an application progranl on()ur
rca卜timc systcm with muitiplc kinds Of celis and withthc systcm stack. if bothphase arc the samc as in Scction 4

う一α=「ス(α1])/たご―う= N / た2να≧((Ar̲N付)/た
2+/4付max/た1 +刀 nla 2x/たHerc, Fハis the sum Vαofブ. Asfor ali typc
α in Scc―
tion 4,wc assumc that2 N/たis an intcger ln addition,andwc assumc that N(Y/た2 is also an intcgcr By the samc
calculations as in Sccti()n4,
vc 、
can SCC that during the
garbagc coHcction,rLY(′)takCS thc smaHcst valuc
F

r

Y

(

2

)

一
1

9

ィ

世

(

b

十

び

+

1

)

一

D

(

Y

(

=(N一

F α ( α) ) / た2 1 D て Y ( b 十 び + 1 ) 一

Nα 一N/た2‑/1̀v付
1
ヽaX スina x/た‑(N尺 十NSS)/た3‑1≧ 〃てY

α)atr i b十 ど +1,WhCrcび+ば R tt NSS)/々3)/(l‑1/た2))

hold for cach typc α, thcn aH garbagc c()llcction cnds
N 付 ) / た2 + [ ( / 4 付 ( α) 十succcssfuHy

D ( ャ( α) , W h i C h r c p r c s c n t sUnk)rtunatcly, thc conditiOns of ThcOrcms 6 1 andt h c n u m b c r o f t i m c s t h aαごtとθ7 7 S i S C a n e d b c t w c c n r i = α6 2 arc too strong.According to ThcOrcm 6.1,it is sattc
a n d r = う十ど+ 1 , i s b o u n d c d b y (びb+十1 ) 一α T h u s ,to sctt h c
s u f f i c i c n t
c o n od 偽ri tαi≦o rn ≦ ご
m +r 1 i Y ( r ) ≧lS〃α= ( ( N ‑ 7 V ィ+ スてY ) /2たY m a X1/ たダ(Y(2)一2(b十(N一 Na)/た11l+ [ (てえ】( の一ダr(χの) /2た2+1)/(1‑1/た+ Дm 」
2)x/た)α≧0which is cquivalcnt toよ)r cach typc α,but this valuc ofソ与″Y SCCmS too largc if
刀 αmax is much smallcr than/4聞
ax Thc primary rcason

F α( α2+/4て
1) ≧( ( N ‑ 7 V α)/たY ()α/ たf()r this is that, in thc abovc calculation命vc rcplaccd、∂ a(r)一 D(Y(r′)by r̲r′ Thc diffcrcncc bctwccn thcsctヽ
vo valucs is quitc largc for th()sc ccll typcs that arc+ 1 ) / ( l ‑ 1 / 2た)+ ス( 2 ) /2たBy using刀(ィ
nla x(maximum valuc of刀

scarccly uscd by thc given program in ordcr to obtainてY(r)),and by us̲a nlorc practical cstiination,vc、assumc that thc givcn

uscs ccH ttpcS That is,wc
ing Д max(maXimum valuc of刀
program t̀proportionallyい(r)),wc Obtain thc blassumc that thcrc is a nonncgativc nunlbcr CLi ttjr cachl o w i n g
s u f f i c i c n t ( Yc (o rn0)d(≧iα≦t ir o≦nご十t t r ダ1 ) .

けpC α Such that〃α≧( ( N 一N α) / た
2 + 刀 αm a x /1 たl
D Yて( r ) = ャC 米r
2 4 Y ( r ) = C ( YДネ( r )1 ) / ( 1 ‑ 21 )/ た十Д m a x2 /+ た

(6.1)

Sincc

3. thc sum of Cて 定k)r alitypc α is lUnder this assumption,(6 1)and(62)arc rCSpcctivcly+ 1 ) = ダ ̀ (メ2 ) 十晟 ャ( ご( N ( Y(刀Y ( 一
のダ ィ
ン
( の)

( D α( C + 1 ) ヤ つ て) ) ≧ N α ― スα( 2 )
Y(α

一( ご
―α‑ 1 ) > N α一N / 々2 ‑ ス付n l a X―刀n l a 1x‑/2たthc sufflcicnt condition for ttα(ご+1)≧7'″
α iS

Nα一N/た2‑刀 a nlax―
スrnax/た1‑2≧ 豚α (6.2)

rcplaccd by影α ≧CてY*(口 V一

+/1

N在

)/た 2

Y 2/ )た+ 1 ) / ( 1 ‑ C2 () Y / た
m a x *1 (+ 1C /( たandNα ―Ca*N/た 2‑Д max*(C(Y tt/た
1)
C(文
‑2ネCα

ト
イα
≧フ

196

J SYSTEMS SOFTヽ
1990111:181‑198

T h u s , aVARE

s u t t c i e n t

T Yuasac o na dn id t iN o nf (o ror )n ≧0i N文αlS

N α一N 米( 2 米Cα2‑Ci/た22)/た島
2))21 *‑ C α
≧スn i a x * ( C ( Y/+た/ ( 1た* た‑2*Ci/た2)
十(3*CαLct us ignorc(3米 C(ィ ー 2*Ci/た 2)in thiS incqualky
Thcn,by adding this incquality k)r all typcvcαobtain,、a sufflcicnt conditlon on N

By using block transfcrs the tilne f()r this copying
vill 、
be negligible ln casc that thc application program uscs
many short arrays,it may be more cttcient if/77α′た()itself takcs care of those arrays、
vhosc sizcs arc smallcr
than some sma‖ constant, lmmcdiatcly vhen、
the point―
ers to them are popcd from gござIn many modern Lisps、 arrays arc treatcd as irst―
Ⅲ

class'' data ttpcS・ThCy arc objccts that can bc as―
signcd to variablcs, conSCd into llst structurcs, and soon Thcrcn it is cxpected that the storagc occupied byarrays that arc not uscd any nlorc bc rccyclcd魚)r tbrthcr

N * ( 1 ‑ 2 /2た+ 1 / ( 7 7272*)た)( 7 717**た2た) )≧刀n l a x * ( 11 +‑ 21 // た
whcrc tt is thc numbcr of ccllけ pCS Now a practicallysafc valuc of′V isたN = 刀 n lxょ2))/* ( 1 + 2 / 1た‑ 1 / ( 7 7 71**た))
2 + 1 / ( 7 7 72*2た(1‑2/たusc l」nlikc rlxcd̲sizcd cclls, sinlplc linking〔) f frcc ar―rays nlay causc thc situatl()n that thcrc ls 1lo COnSCcutivc
spacc largc cnough ft)ra nc、 v array, whilc thc total sizcof recycled space is iarge en()ugh f()rthc array T()avoid
such a situation, thc 3arbagc coHcctor should rclocatc
or connpact arrays in usc so that thcy may bc packcd
int()a consccutivc mcmory arealn order to discuss ho、v()ur rcal―tilllc algorithm canvc usc thc fo‖ o、
ving
bc applicd f()r array rclocationゃ 、? = 1, thcn thc safc valuc is idcntical toN()tc that, ifヵ
modcl, 、vhich is bascd ()n Minsky garbagc coliccti()n々incrcascs, this safc valucthat givcn in Scction 4 As″
ll,4,7〕 rcstriCtCd on arrays Each array is rcprcscntedofハF also incrcascs Fbr cxamplc,7V = 1.220ス
nlax inby a rixcd̲sizcd hcadcr and a b()dy Thc hcadcr con―cascた l i=た2 ‑20 and 777 ‑ 3 in this casc, thc rcal― tains uscful inS()rmatlon()n thc array, such as thc lcngth
2 20リイ n10rc spacc as thc hcap than of thc array Thc clements()f thc array are storcd in thc
tinlc systcm nccd、
the conventional systcm

body Sincc thc sizc()1｀array hcadcrs is「lxcdn thc systcrn
can trcat array hcadcr、in thc sitnllar way as othcr ixcd―

7 ARRAYS AND RELOCAT10N

sizcd cclis ln particulartt array hcadcrs arc all()catcd inthc hcap and hcadcr、 of non―uscd arrays may bc linkcd

Our rcal timc systcm can support arrays silllply by rc―
lcngth ce‖s Thc array a1loca―
garding thcm as variablc―

togcthcr to liornl a frcclist()f array hcadcrs Array bod―
ics,on thc othcr hand,arc a‖ ()catcd in a scparatc spacc.

r″ノ(′
r/2α
た2̲α
tion proccdureと,ブ,メ)‐WhiCh a1locates Thc body of an array()ccupics consccutivc locati()ns inand as― that spacc and thc hcadcr of thc array holds thc ttrst
CICmcnts with a1l initial elcmcntsメ
an array ofブlay bc dcttncd sirnilarly
signs(thc pOintcr to)ittO l,■
RI′such iocation Rcfcrcncc to an array is pcrk)rmcd via thc
角to the consing proccdurcs in Scction 6 αとりRX,ブ),
hcadcri no p()intcr can dircctly point to array cicmcnts
d C n l c n t ( ) f ( t h C a r r t t p o i n t c Thc
d tspacc( ) k)r array bodics is dividcd into t、 vo sでr77′
w h たh r c t u r n s tthhe ブ―
th ciC―by)χ, and ttscrは,ブ,ノ), WhiCh rcplaccs thcブ
ment of χ byノ ,may bc denned silnilarly to thc rctricval
functions and the updatc procedurcs, respcctivcly, prc―
scntcd in Section 6̲ In ordcr for thc cxecution tiinc of″αr々()tO be bOundcd by a constant, 、 vc nccd spccial
treatmcnt、vhen thc pointcr poped by
β :=gこざ聟 Gp();
rた()pushCd a1l of thc
points to an ̀̀array ccll " If/77α
elements of thc array at oncc, then the rcal―tinle naturcof thc systcm 、vould be lost, sincc thc numbcr of clc―
ments in an array is not boundcd by a rcasonably small
vc assume that thc clements of an array arc
constant. If、
a1locatcd in consccutive locations, 、vhich is usually thecase,thcn thc usc ofthe savc stack in Scction 5、vi1l over―.That iS,whcn/77αrた()rCCOgnizes
come this difflculけ″αrた()copies the elemcnts intothat p points to an array,ァ
thc save stack so that thcy may later bc takcn carc ofず″ 6?S. During exccution of thc applicati()n proBram,al array bodics are a1locatcd in onc of thc scnlispacc

During thc mark phasc, 、 vhCn thc garbage colicctor isgoing to mark an array hcadcr,thc array body is copied
into thc othcr scnlispacc and, at thc samc tilnc, thc old
location()fthc body storcd in thc hcadcr is updatcd By
copying array bodics into succcssivc locations, bodics
of acccssible arrays arc conlpactcd in thc ̀̀to" scmi,
spacc (rθspαご2)at thC Cnd of thc garbagc collection
Thc contcnts in thc old semispacc m材
ず脚 解 ) a r e t h c n
discarded and bodies of nc、 v arrays arc a1locatcd in thc
tospace Ncxt tirne thc sarbage collcctor is invokcd,thc
rolc of thc nvo scmispaccs is intcrchanged Thc prcvi―
ous tospacc is uscd as the fromspacc and thc prevlous
fromspacc is uscd as thc tospace. Notc that, sincc thc
location of an array body is storcd only in thc headcr,
this systcm necd notleavc thc so―calicd̀̀forwarding ad一
dress"[1,31 in array bodics.

Real―
Time Garbage Collection

Application of Our rcal―
timc algorithlll to this model
is quitc straightttrward The procedurc ″α/た()nOW
copies array bodies into t、
vo placcsi tO thc tospace andto the savc stack. Thc copying proccsscs can be donc ina short timc, by using block transfcr During garbage
collcction, bodics of ne、v arrays arc a1locatcd in thetospacc, not in thc fromspacc. Thus, the tospacc con―sists of copics of accessiblc array bodics and vnc、
array
bodics,swとep()cOllCCts non―marked(ic,,inacccssiblC)
array hcadcrs into a freelist,but docs nothing with arraybodics.
Actually, 777αrた()nCCdS to copy array bOdies only
into the tospace, if thc system takes carc of pointcrs
in thc tospacc as 、vell as pointcrs in thc savc stack Bymaking only onc copy Sor cach acccssiblC array,thc sizc
ofthe savc stack can rcmain smaH,and thus、 vc can savc
mcmory spacc. As alrcady statcd, thc tospacc contains
nc、vly a1locatcd bodics as、vcH,、vhich nccd not bc takcn
carc of. It is not difttcult to distinguish copicd bOdics
fronl nc、
vly aHocatcd bodics Onc mcthod is to add an
cxtra datuHl into thc tospacc, 、vhcn a body is copicd
from thc仲 omspacc or a body is ncwly a1locatcd̲ Each
such datum should contain t、 vo kinds of ink)rnlatloni
whether thc follo、
ving body is copicd()r nc、vly a1locatcd
and ho、v long thc body is ヽ Vith this information, thc
sy、tcm can casily and efficicntly 18norc nc、
vly aHocatcd
bodies in thc tospacc

J SYSTEMS SOFTヽ VARE
1990111: 181‑198

197

ray rclocation which is highly dcsircd in modcrn list―
proccssing systcms
Thc algorithlll presentcd in this papcr are planncd
to bc implcmentcd in a portablc Common Lisp l161
systcm,called Kyoto Common Lisp[181,whiCh iS al
rcady running undcr scveral opcrating systcms on sev―′
eral gcneral一purposc machincs, including theヽAX andthe MC68000 Thc kcrnel ofthis systcm is、
vrittcn in thc
C languagc and、

vith thc usc Of prcproccssOr maCros()fC,ali verslons of thc systclll sharc thc samc sourcc pro―grams. This systcm a1locatcs data celis in thc heap andcsscntially uscs thc sO―called BIBOP(BIg Bag Of Pagcs)
mcthod l151 to lllanagc thcm Variable―

lcn3th data suchas arrays and hash tablcs(in terms Of Common Lisp)
arc a1locatcd in another spacc and arc garbagc―
comcctcd
by copying compacti()n irnplclllcntation of thc rcal―
tinlc
a180rithnl in this systcnl ls strai3htFtjr、
vard and 、vc cx―
pcct that thc samc sourcc pr()grams can bc sharcd also
by thc futurc vcrslons()f thc systclll、 thc rcal―
vith
timc
garbagc c()llcctor.

ACKNOWLEDGMENT
The author wishes to acknowled9e the help of Reui
"ma Na陥WhO
patiently supervised this research This research was motivatedby the implementation discusslons of KyOtO Common Lisp with
Masami Ha9iya The author wishes to thank hirn The author also
thanks Daniel Berry lor his numerous comments on drafts of thispaper

8 CONCLUSiONS AND FUTURE PLANSWtS prcsented an algorithm S()r rcal―
t imc garbagc col―lcction in list―
proccssin3 Systems running on gcncral―purposc machincs This a130rithnl cnablcs thc list―
proccssing systcm t()executc cach list,processing priln―
itivc vithin、a smali constant tiinc and thus not to sus―pend execution of application programs during garbagc
collcction. Althou8h thC Cxccution cfncicncy dCCrcascswith thc rcal―
tiFnC garbagc coHcction, thc ovcrhcad is
kept small bccausc thc a180rithm puts no ovcrhcad on
frcqucntly uscd prilllitives such as pointer rcfcrcnccs,
variablc rcfcrcnccs and assignmcnts, and stack manip―
ulations ln order to see thc mcmory ovcrhcad of thc
vc havc sho、vn sufficicnt conditions on thc
algorithm, 、
size of thc hcap to kccp thc pr()gram running 、vith(〕ut

REFERENCESl H G Bakcr,List Proccssing in Rcal Tinlc on a Scrial
C o n l p u t c r , 7C 7ο7 7″
7 1力C″ M 21(4),280‑294(1978)
Garbagc Colicc―
2 ヽ4 Bcn―arin Algorithms tt)r On lly
thc―tk)n,スCんイTra″s Pttg″ ″ とα″gSレ sr 6(3),333‑344,(1984)
3 R A Brook、,Trading Data Spacc to Rcducc Tilllc and
Codc Spacc in Rca卜 Timc Carbagc Co1lcction on Stock
Hardwarc,ln Cθ 確 ″″確 R ο〃 げ r力?′ 98イ カCM″7P20″ とパPα ″び Frz″
ごr′ο″α′F,Og″ 777777′″g,
Sノ‐辞 S′

tivcly small Application of the algorithln to alrcady cx―
isting list―
processin3 Systcms is casy since it docs not
requirc modincation on thc data rcprcscntation Thc pri―mary disadvantagc of thc algorithnl is that thcy do notvcvcr,
support compaction of thc、vholc data space 1lo、

pp 256‑262. 1984
4 C J Chcncy, A Nonrccursivc List Compacting Algo―
P P力C″ M,13(11),677‑678(1970)
r i t h n l , 7C PθP 7″
lcicnt,Incrcmcn―
5 P L Dcutschand D G Bobr()w,An E廿
1″″刀C M 1 9 ( 9 ) ,t a l , A u t o m a t i c G a r b a gicc cCt((】) r ,″
C7O7′
522‑526(1976)
6 E W Dlkstra,L LampoA,A J Maltin,C S Scholtcn.
cns, On thc―ny CarbagC C()1lcctioni
and E F M StcミA n E x c r c i s c i n C o o p c r a t l o n , C 0″7 7力2 C7 ん
7 イ2
1 ″1 ( H ) ,966‑975(1978)
7 R R FcnichclandJ C Y()chcison,A LISP Carbagc―
Collcctor ibr Virtua卜Mclnory C()illputcr Systcms,Co771‑
r / 1″″ 力C M 1 2 ( 1 1 ) , 6 1 1 ‑ 6 1 2 ( 1 9 6 9 )7Pr̲
8 B W Kcmighan and D M Richic.T/1?CP/og″、
vc havc scen that thc algorithm efficicntly supports ar―

Hall、Inc . New Jerscy, 1978
771′
″gと α″g″段守で, Prcnticc―

exhausting thc frcelist. Thcsc conditions arc too strong
in that the size of thc hcap can bc much smallcr in ac―tual situations Ncvcrthclcss, they have proved that thc
mcmory ovcrhcad of our rcal― tilnc algorithlll is rcla―

198

9

J SYSTEMS SOFTミ ヽRE,990111!181 198
H

T Kung and sw

T YuasasOng, An Efflcient Parallcl

Garbagc C01lcct10n Systcm,in′

8r力力″″″α′【
こここ 助 777‑
βos′″″ ο77乃 ″″が2r,ο″sげ cOr7rp″rでr scFで″cで, PrOvi
dcncc, Rhodc lsiand,pp 120‑131、 1977
10

H Licbcrillan and C Hcwitt,A Rcal―

11

J ヽ 4cCarthy, Rccursivc Functions()「

Timc Carbagc COト
icctor That can RccOvcr TcmpOratt StOragc QuiCkly,

MIT A I Mcmo,No 569,1980
slons and Thcir COmputatiOn by ヽ

Symbolic Exprcs―

4achinc, Part r, Cor72̲

/22″″ ス a'ィ 3(4), 184‑195(1960)

D A MOOn,Carbagc ColicctiOn in a Largc Lisp Systcm‐
in Cο稜 ″″留 Rttο〃 て/77pο
s′
ゾ r力で ′98ィ スcM助
″7/1
0″ と/SP,″ び 炉功″cr′
θ″α′Fケ。g″ 77″″′″g,pp 235‑246,
1984
1 A Ncwman,R P Stallard,and M C ヽ
中b()dward,
A Parallcl COmpactiOn A180rlthm ttjr IultiproccssOr
巾

16

Carbagc Colicction, in P″ 拓″〃?′Cο‐p″ r′″g8J, Nolth―Holland Publishing Conlpany, pp 455‑462, 1983
G L Stcclc,Muitiproccssing Compachtting Garbagc
CollcctiOn,CO″ ″″″ ス cM 18(9),495‑508(1975)
G L Stccic,Data Rcprcscntations in PDP 10障
IacLisp.
in Pttceedi″gsげ r力で ′977 MACSて
MA υ sヶ む Cο″̲
竹々れで,ヽvashington,DC、
215‑224,1977
ゥG L Stccic,ct al,Cθ 777用0″ とヽβf r71でとα″g″αgで,Dig―
ital Prcss, 1984
S Wholcy and S E Fahinlan,Thc Dcsign()f an lnstruc―tlon Sct fOr COinm()n Lisp,in Cο々ンを″″てマR̀(っrr7 q/′
力?
F98イ スCMも りr77β
OSル 7770″ と/SP α″″r力″ご′,ο″″′Pro″?/21′″g,pp 150‑158, 1984
gttα
T Y u a s a a n d M ノ
H Oa rg θlC yθ
a7 ,7 、
′
″
2と
0ヽ
″
r r ,
β R 9 切'「cik()ku lnsatsu Publishing、
KyotO. 1985