rse-pmt.ps

Linux下的中文输入法

(language)i(features)g(and)g(especially)g(does)g(not)f(require)h(an)o
(y)f(assembly)h(code)208 1592 y(or)27 b(platform)h(speci\002c)f(tricks)
g(at)h(all.)48 b(The)27 b(most)h(interesting)g(issue)f(is)g(the)h
(technique)h(of)e(creating)h(the)g(machine)g(conte)o(xt)g(for)208
1684 y(threads,)18 b(which)g(this)f(paper)h(e)o(xplains)h(in)e(detail.)
23 b(The)17 b(described)i(approach)g(closely)f(follo)n(ws)g(the)g
(algorithm)g(as)f(implemented)i(by)208 1775 y(the)h(author)h(for)f(the)
g(popular)h(user)o(-space)g(multithreading)g(library)f
Fu(GNU)f(P)-6 b(ortable)21 b(Thr)m(eads)g Fv(\()p Fu(GNU)e(Pth)p
Fv(,)h([25)q(]\))f(which)i(this)f(w)o(ay)208 1866 y(quickly)f(gained)h
(the)f(status)g(of)g(one)g(of)g(the)g(most)g(portable)h(user)o(-space)f
(multithreading)h(libraries.)208 2007 y Ft(K)o(e)o(yw)o(or)o(ds:)e
Fv(portability)-5 b(,)15 b(multithreading,)i(Unix,)e(POSIX,)f(SUSv2,)h
(ANSI-C,)e(user)o(-space,)j(conte)o(xt)g(creation,)g(conte)o(xt)f
(switch-)208 2099 y(ing,)j(signal)i(handler)m(,)f(stack,)g(mak)o
(econte)o(xt,)h(switchconte)o(xt,)g(sigaltstack,)e(setjmp,)h(longjmp.)
208 2240 y Ft(Pub)o(lishing:)g Fv(Early)f(drafts)f(of)h(this)g(paper)g
(were)g(distrib)o(uted)g(with)f(the)h(GNU)g(Pth)f(distrib)o(ution.)22
b(The)c(\002nal)g(release)g(v)o(ersion)g(w)o(as)208 2331
y(published)i(on)f(the)g(USENIX)f(Annual)h(T)-5 b(echnical)20
b(Conference,)f(June)h(18-23,)g(2000,)f(San)g(Die)o(go,)g(California,)f
(USA.)0 2711 y Fs(1)119 b(Intr)n(oduction)0 2895 y FA(1.1)99
b(Multithr)n(eading)0 3052 y Fx(The)25 b(paradigm)d(of)j(programming)c
(with)k(multiple)g(threads)f(of)0 3152 y(e)o(x)o(ecution)c(\(aka)i
Fr(multithr)m(eading)p Fx(\))f(is)i(already)f(a)h(v)o(ery)e(old)h(one)0
3252 y(and)i(dates)g(back)g(to)g(the)h(decades)f(of)g(programming)c
(with)25 b Fr(co-)0 3351 y(r)l(outines)19 b Fx([2,)g(3].)25
b(P)o(aradoxically)-5 b(,)17 b(the)i(use)h(of)f(threads)g(on)g(Unix)0
3451 y(platforms)g(did)h(not)g(become)f(popular)f(until)i(the)g(early)g
(1990s.)0 3602 y FA(Multithr)n(eading)26 b(Adv)o(antages)0
3728 y Fx(Multithreading)31 b(can)i(pro)o(vide)f(man)o(y)g(bene\002ts)h
(for)g(applica-)0 3828 y(tions)26 b(\(good)f(runtime)g(concurrenc)o(y)
-5 b(,)24 b(parallel)i(programming)0 3927 y(techniques)j(can)h(be)g
(implemented)e(more)i(easily)-5 b(,)32 b(the)e(popu-)0
4027 y(lar)22 b(procedural)d(programming)f(style)k(can)f(be)h(combined)
d(with)0 4127 y(multiple)g(threads)f(of)h(e)o(x)o(ecution,)e
Fr(etc.)p Fx(\))24 b(b)n(ut)c(the)f(most)g(interest-)0
4226 y(ing)25 b(ones)g(are)g(usually)g(performance)d(gains)j(and)f
(reduced)g(re-)0 4326 y(source)17 b(consumption.)k(Because)d(in)g
(contrast)f(to)h(multiprocess)0 4425 y(applications,)e(multithreaded)f
(ones)i(usually)f(require)g(less)i(sys-)0 4525 y(tem)25
b(resources)f(\(mainly)g(memory\))e(and)j(their)f(internal)g(com-)0
4625 y(munication)33 b(part)i(can)g(le)n(v)o(erage)f(from)g(the)i
(shared)e(address)0 4724 y(space.)0 4876 y FA(Multithr)n(eading)26
b(and)g(A)n(pplications)0 5001 y Fx(Ne)n(v)o(ertheless)d(there)h(still)
h(e)o(xist)g(just)g(a)f(fe)n(w)h(real)f(applications)0
5101 y(in)35 b(the)f(free)g(softw)o(are)h(w)o(orld)f(that)g(use)h
(multithreading)d(for)0 5201 y(their)20 b(bene\002t,)g(although)f
(their)h(application)f(domains)h(are)g(pre-)0 5300 y(destined)32
b(for)f(multithreading.)59 b(F)o(or)32 b(instance,)j(the)d(popular)0
5400 y(Apache)38 b(webserv)o(er)g(as)i(of)f(v)o(ersion)f(1.3)h(still)h
(uses)g(a)f(pre-)2025 2895 y(forking)32 b(process)h(model)g(for)h
(serving)f(HTTP)h(requests,)i(al-)2025 2995 y(though)14
b(tw)o(o)i(e)o(xperiments)e(with)j(multithreaded)c(Apache)i(v)n(ari-)
2025 3095 y(ants)22 b(in)g(1996)e(\(with)i Fr(r)o(sthr)m(eads)g
Fx([27)n(]\))g(and)f(1998)f(\(with)i Fr(NSPR)2025 3194
y Fx([31)o(]\))37 b(already)f(sho)n(wed)g(great)h(performance)d
(boosts.)76 b(The)2025 3294 y(same)20 b(applies)g(to)h(man)o(y)e
(similar)h(applications.)2150 3401 y(The)h(reason)g(for)g(this)i
(restraint)e(mainly)g(is)i(that)f(for)f(a)h(long)2025
3500 y(time,)c(multithreading)e(f)o(acilities)j(under)d(Unix)i(were)g
(rare.)24 b(The)2025 3600 y(situation)f(became)f(better)h(after)f(some)
h(v)o(endors)f(lik)o(e)h Fr(Sun)f Fx(and)2025 3699 y
Fr(DEC)f Fx(incorporated)15 b(threading)h(f)o(acilities)j(into)f(their)
g(Unix)f(\003a-)2025 3799 y(v)n(ors)36 b(and)g Fr(POSIX)j
Fx(standardized)c(a)i(threading)e Fr(Application)2025
3899 y(Pr)l(o)o(gr)o(amming)18 b(Interface)g Fx(\(API\))h(\(aka)f
Fr(Pthr)m(eads)g Fx([1]\).)24 b(But)c(an)2025 3998 y(API)e(and)f(a)h
(fe)n(w)f(v)o(endor)f(implementations)f(are)j(not)f(enough)e(to)2025
4098 y(ful\002ll)29 b(the)g(portability)e(requirements)g(of)h(modern)f
(free)i(soft-)2025 4198 y(w)o(are)37 b(packages.)74 b(Here)37
b(stand-alone)f(and)g(really)h(portable)2025 4297 y(multithreading)18
b(en)m(vironments)f(are)j(needed.)2150 4404 y(The)49
b(author)g(collected)h(and)f(e)n(v)n(aluated)g(o)o(v)o(er)g(twenty)2025
4503 y(\(mostly)42 b(user)n(-space\))h(a)n(v)n(ailable)f
(multithreading)f(f)o(acilities)2025 4603 y(for)15 b(Unix)g(systems)h
(\(see)g(T)-7 b(able)16 b(1\),)g(b)n(ut)g(only)e(a)i(fe)n(w)g(of)f
(them)h(are)2025 4703 y(freely)27 b(a)n(v)n(ailable)g(and)g(sho)n(wed)g
(to)h(be)g(really)f(portable.)46 b(And)2025 4802 y(e)n(v)o(en)19
b(the)i(mostly)f(portable)f(ones)h(suf)n(fered)f(from)g(the)i(f)o(act)f
(that)2025 4902 y(the)o(y)31 b(partly)g(depend)f(on)h(assembly)g(code)g
(or)h(platform)e(spe-)2025 5001 y(ci\002c)e(tricks)f(usually)g(related)
g(to)h(the)f(creation)g(and)g(dispatch-)2025 5101 y(ing)d(of)h(the)g
(indi)n(vidual)e(threads.)38 b(This)25 b(means)f(that)h(the)g(num-)2025
5201 y(ber)c(of)h(platforms)f(the)o(y)g(support)f(is)j(limited)e(and)h
(applications)2025 5300 y(which)27 b(are)h(based)g(on)g(these)g(f)o
(acilities)h(are)f(only)f(portable)f(to)2025 5400 y(those)c(platforms.)
29 b(This)22 b(situation)f(is)i(not)f(satisf)o(actory)-5
b(,)21 b(so)h(ap-)p Black 1929 5700 a(1)p Black eop
%%Page: 2 2
2 1 bop Black Black 0 83 a Fx(plication)25 b(authors)g(still)j(a)n(v)n
(oid)d(the)i(use)f(of)g(multithreading)d(if)0 183 y(the)o(y)28
b(w)o(ant)g(to)h(\(or)f(ha)n(v)o(e)g(to\))g(achie)n(v)o(e)f(maximum)g
(portability)0 282 y(for)20 b(their)f(application.)125
387 y(A)25 b(pragmatic)e(and)h(mostly)g(portable)f(f)o(allback)h
(technique)0 486 y(for)d(implementing)f(user)n(-space)h(threads)g(can)h
(f)o(acilitate)g(wider)0 586 y(use)e(of)g(multithreading)e(in)i(free)g
(softw)o(are)g(applications.)0 750 y FA(Ingr)n(edients)26
b(of)f(a)g(Thr)n(ead)0 884 y Fx(A)h(Unix)f(process)f(has)i(man)o(y)e
(ingredients,)h(b)n(ut)g(the)g(most)h(im-)0 983 y(portant)k(ones)h(are)
h(its)g(memory)e(mapping)f(table,)34 b(the)e(signal)0
1083 y(dispatching)18 b(table,)h(the)g(signal)g(mask,)g(the)g(set)h(of)
f(\002le)h(descrip-)0 1183 y(tors)30 b(and)f(the)h(machine)e(conte)o
(xt.)52 b(The)29 b(machine)g(conte)o(xt)f(in)0 1282 y(turn)d(consists)i
(of)e(at)i(least)g(the)f(CPU)h(re)o(gisters)e(including)g(the)0
1382 y(program)18 b(counter)h(and)h(the)h(stack)f(pointer)-5
b(.)25 b(In)20 b(addition,)f(there)0 1482 y(can)28 b(be)f(light-weight)
g(processes)g(\(L)-6 b(WP\))28 b(or)f(threads,)i(which)0
1581 y(usually)g(share)g(all)h(attrib)n(utes)f(with)g(the)h(underlying)
c(\(hea)n(vy-)0 1681 y(weight\))19 b(process)h(e)o(xcept)f(for)h(the)g
(machine)f(conte)o(xt.)0 1845 y FA(K)n(er)o(nel-Space)25
b(vs.)31 b(User)l(-Space)0 1979 y Fx(Those)c(L)-6 b(WPs)28
b(or)f(threads,)h(on)e(a)i(Unix)f(platform)e(classically)0
2078 y(can)34 b(be)g(implemented)e(either)i(in)g(k)o(ernel-space)f(or)g
(in)i(user)n(-)0 2178 y(space.)76 b(When)38 b(implemented)d(in)j(k)o
(ernel-space,)h(one)e(usu-)0 2278 y(ally)22 b(calls)h(them)e(L)-6
b(WPs)23 b(or)e(k)o(ernel)g(threads,)h(otherwise)f(\(user)n(-)0
2377 y(space\))d(threads.)24 b(If)19 b(threads)f(are)h(implemented)d
(by)j(the)g(k)o(ernel,)0 2477 y(the)24 b(thread)g(conte)o(xt)f
(switches)h(are)h(performed)c(by)j(the)g(k)o(ernel)0
2576 y(without)17 b(notice)f(by)h(the)g(application,)f(similar)i(to)f
(the)h(dispatch-)0 2676 y(ing)33 b(of)g(processes.)64
b(If)33 b(threads)g(are)g(implemented)e(in)j(user)n(-)0
2776 y(space,)20 b(the)g(thread)f(conte)o(xt)g(switches)i(are)f
(performed)d(usually)0 2875 y(by)31 b(an)g(application)f(library)g
(without)h(notice)f(by)h(the)h(k)o(ernel.)0 2975 y(Additionally)-5
b(,)39 b(there)e(e)o(xist)h(hybrid)d(threading)h(approaches,)0
3075 y(where)28 b(typically)g(a)h(user)n(-space)g(library)e(binds)i
(one)f(or)g(more)0 3174 y(user)n(-space)19 b(threads)h(to)g(one)g(or)g
(more)f(k)o(ernel-space)g(L)-6 b(WPs.)0 3338 y FA(Thr)n(ead)27
b(Models)0 3472 y Fx(The)h(v)o(endor)d(threading)h(f)o(acilities)j
(under)d Fr(Sun)h(Solaris)p Fx(,)i Fr(IBM)0 3572 y(AIX)p
Fx(,)h Fr(DEC)h(T)-5 b(ru64)31 b Fx(\(formerly)d Fr(DIGIT)l(AL)i(UNIX)k
Fx(or)d Fr(OSF/1)p Fx(\))0 3671 y(and)20 b Fr(SGI)h(IRIX)i
Fx(use)e(a)h Fq(M:N)f Fx(mapping)e([21)o(,)i(30)o(],)g
Fr(i.e)o(.)p Fx(,)f Fq(M)i Fx(user)n(-)0 3771 y(space)33
b(threads)g(are)h(mapped)e(onto)g Fq(N)i Fx(k)o(ernel-space)e(L)-6
b(WPs.)0 3871 y(On)20 b(the)h(other)e(hand,)g Fr(LinuxThr)m(eads)g
Fx([29)o(])i(under)e Fr(GNU/Linux)0 3970 y Fx(uses)f(a)f
Fq(1:1)g Fx(mapping)e(and)i(pure)f(user)n(-space)h(implementations)0
4070 y(lik)o(e)k Fr(GNU)g(Pth)p Fx(,)f Fr(FSU)g(pthr)m(eads)f
Fx(or)i Fr(MIT)f(pthr)m(eads)p Fx(,)g Fr(etc.)26 b Fx(use)20
b(a)0 4170 y Fq(M:1)g Fx(mapping)f([25)n(,)i(22)o(,)f(23)o(].)125
4274 y(From)39 b(no)n(w)g(on)h(we)g(focus)g(on)f(such)h
Fq(M:1)g Fx(user)g(space)0 4374 y(threading)d(approaches,)42
b(where)c(one)h(or)f(more)h(user)g(space)0 4473 y(threads)16
b(are)g(implemented)f(inside)i(a)g(single)f(k)o(ernel)g(space)h(pro-)0
4573 y(cess.)24 b(The)15 b(e)o(x)o(ercise)f(is)i(to)g(implement)e(this)
i(by)e(using)h(standard-)0 4672 y(ized)20 b(Unix)g(system)g(and)g
(ANSI-C)g(language)f(f)o(acilities)i Fr(only)p Fx(.)0
4936 y FA(1.2)99 b(The)26 b(Exer)n(cise)0 5101 y Fx(As)d(we)g(ha)n(v)o
(e)f(mentioned,)e(a)j(thread)e(shares)i(its)g(state)g(with)g(the)0
5201 y(underlying)i(process)j(e)o(xcept)f(for)g(the)h(machine)f(conte)o
(xt.)46 b(So)0 5300 y(the)17 b(major)e(task)i(for)f(a)h(user)n(-space)f
(threading)e(system)j(is)g(to)g(cre-)0 5400 y(ate)k(and)e(dispatch)h
(those)g(machine)f(conte)o(xts.)2150 83 y(In)d(practice,)g(the)h
(second)f(major)g(task)h(it)g(has)g(to)g(do)f(is)i(to)f(en-)2025
183 y(sure)k(that)f(no)h(thread)f(by)g(accident)g(blocks)g(the)h(whole)
f(process)2025 282 y(\(and)25 b(thereby)f(all)i(other)f(threads\).)41
b(Instead)25 b(when)g(an)h(opera-)2025 382 y(tion)j(w)o(ould)f(block,)i
(the)f(threading)e(library)h(should)g(suspend)2025 482
y(only)19 b(the)g(e)o(x)o(ecution)e(of)i(the)g(current)g(thread)f(and)h
(in)g(the)h(mean-)2025 581 y(time)g(dispatch)f(the)h(remaining)e
(threads.)24 b(But)d(this)f(task)g(is)h(out-)2025 681
y(side)30 b(the)h(scope)e(of)h(this)h(paper)e(\(see)h([11)o(])h(for)e
(details)i(about)2025 780 y(this)24 b(task\).)33 b(W)-7
b(e)24 b(focus)f(only)f(on)h(the)g(aspect)g(of)g(machine)e(con-)2025
880 y(te)o(xt)f(handling.)2025 1112 y FA(1.3)99 b(The)26
b(Curse)g(of)e(P)n(ortability)2025 1267 y Fx(Our)18 b(goal)g(of)f(real)
i(portability)d(for)i(a)h(threading)d(system)i(causes)2025
1367 y(some)j(non-tri)n(vial)d(problems)i(which)g(ha)n(v)o(e)g(to)h(be)
g(solv)o(ed.)26 b(The)2025 1467 y(most)f(ob)o(vious)e(one)h(is)i(that)f
(dealing)f(with)h(machine)f(conte)o(xts)2025 1566 y(usually)33
b(suf)n(fers)g(from)f(portability)-5 b(,)35 b(because)d(it)j(is)f(a)g
(highly)2025 1666 y(CPU)18 b(dependent)d(task)i(for)f(which)g(not)h(e)n
(v)o(ery)e(Unix)i(\003a)n(v)n(or)g(pro-)2025 1766 y(vides)25
b(a)g(standardized)e(API.)i(Although)e(such)i(an)g(API)g(w)o(ould)2025
1865 y(be)f(not)h(too)f(hard)f(for)h(v)o(endors)f(to)i(pro)o(vide,)e
(because)h(in)h(prin-)2025 1965 y(ciple)d(it)h(is)g(just)g(a)g(matter)e
(of)h(switching)g(a)h(fe)n(w)f(CPU)h(re)o(gisters)2025
2064 y(\(mainly)c(the)h(program)e(counter)h(and)h(the)g(stack)g
(pointer\).)2025 2201 y FA(Assembly)k(Code)i(Consider)n(ed)g(Harmful)
2025 2319 y Fx(Additionally)-5 b(,)21 b(we)j(disallo)n(w)e(the)h(use)h
(of)e(an)o(y)g(assembly)h(solu-)2025 2418 y(tions)c(or)g(platform)e
(speci\002c)j(tricks,)f(because)f(then)h(the)g(thread-)2025
2518 y(ing)e(system)i(again)d(w)o(ould)h(be)h(only)f(semi-portable,)f
Fr(i.e)o(.)p Fx(,)i(it)h(can)2025 2617 y(be)e(ported)f(to)i
Fq(N)f Fx(platforms)f(b)n(ut)i(on)f(the)g Fq(\(N+1\))p
Fx(th)f(platform)g(one)2025 2717 y(has)28 b(to)g(manually)e(adjust)i
(or)f(e)n(v)o(en)g(e)o(xtend)f(it)i(to)g(w)o(ork)f(there,)2025
2817 y(too.)2150 2916 y(This)e(is)h(usually)f(not)g(acceptable,)h(e)n
(v)o(en)e(if)i(it)g(also)g(mak)o(es)2025 3016 y(solving)20
b(the)h(problems)f(harder)-5 b(.)26 b(At)c(least)f(most)g(of)g(the)g
(kno)n(wn)2025 3116 y(free)26 b(softw)o(are)g(user)n(-space)g
(threading)f(systems)i([22)o(,)f(23)o(,)h(24)o(])2025
3215 y(do)15 b(not)g(restrict)h(themself)e(to)i(this)g(and)f(therefore)
e(are)j(just)g(semi-)2025 3315 y(portable.)24 b(But)c(real)g
(portability)f(should)g(be)h(a)h(major)f(goal.)2025 3589
y Fs(2)119 b(Pr)n(oblem)30 b(Analysis)2025 3791 y FA(2.1)99
b(The)26 b(T)-9 b(ask)25 b(in)g(Detail)2025 3947 y Fx(Our)d(task)h(is)g
(simple)f(in)h(principle:)28 b(pro)o(vide)20 b(an)j(API)f(and)g(cor)n
(-)2025 4046 y(responding)f(implementation)f(for)j(creating)f(and)g
(dispatching)2025 4146 y(machine)15 b(conte)o(xts)g(on)h(which)g(user)n
(-space)g(threads)f(can)h(be)h(im-)2025 4246 y(plemented.)2025
4382 y FA(The)26 b(Pr)n(oposed)g(API)2025 4500 y Fx(In)18
b(detail)g(we)g(propose)f(the)h(follo)n(wing)e Fr(Application)g(Pr)l(o)
o(gr)o(am-)2025 4599 y(mer)o(s)21 b(Interface)f Fx(\(API\))g(for)f(the)
h(machine)f(conte)o(xt)g(handling:)p Black 2120 4749
50 50 v Black 2233 4749 a(A)25 b(data)g(structure)f(of)g(type)h
Fp(mctx)p 3266 4749 25 4 v 29 w(t)g Fx(which)f(holds)h(the)2233
4849 y(machine)19 b(conte)o(xt.)p Black 2120 5001 50
50 v Black 2233 5001 a(A)95 b(function)e(\223)p Fq(v)o(oid)h
Fp(mctx)p 3248 5001 25 4 v 29 w(create\(mctx)p 3827 5001
V 28 w(t)2233 5101 y(*)p Fr(mctx)p Fx(,)26 b Fq(v)o(oid)g
Fp(\(*)p Fr(sf)p 2825 5101 V 30 w(addr)r Fp(\)\()p Fq(v)o(oid)e(*)p
Fp(\),)i Fq(v)o(oid)g Fp(*)p Fr(sf)p 3742 5101 V 30 w(ar)m(g)p
Fx(,)2233 5201 y Fq(v)o(oid)c Fp(*)p Fr(sk)p 2531 5201
V 30 w(addr)p Fx(,)g Fq(size)p 2891 5201 V 30 w(t)h Fr(sk)p
3041 5201 V 30 w(size)p Fp(\))p Fx(\224)g(which)g(creates)f(and)2233
5300 y(initializes)17 b(a)h(machine)e(conte)o(xt)f(structure)h(in)i
Fr(mctx)f Fx(with)2233 5400 y(a)25 b(start)g(function)e
Fr(sf)p 2825 5400 V 31 w(addr)p Fx(,)i(a)g(start)h(function)d(ar)o
(gument)p Black 1929 5700 a(2)p Black eop
%%Page: 3 3
3 2 bop Black Black Black 0 3 3864 4 v 0 2441 4 2439
v 68 642 a Fw(P)o(ackage)553 642 y
 gsave currentpoint currentpoint translate 45 neg rotate neg exch neg
exch translate
 553 642 a Fw(Genesis)553
642 y
 currentpoint grestore moveto
 553 642 a 744 642 a
 gsave currentpoint currentpoint translate 45 neg rotate neg exch neg
exch translate
 744 642 a Fw(Latest)19 b(V)-7
b(ersion)744 642 y
 currentpoint grestore moveto