Szymanski算法Szymanski算法是解决多个线程并发访问一个共享资源的互斥问题的一个算法。由Boleslaw Szymanski于1988年提出。[1][2][3]该算法具有很多优良性能，如线性等待，解决了由Leslie Lamport提出的开问题。[4] 算法的类比解释该算法可以用等候室(waiting room)做一个直观地类比。等候室有一个入口门与一个出口门。起初，入口门是打开的。所有想要进入临界区的线程在差不多同一时间由入口进入等候室。最后一个进入的线程负责关闭进口门。然后在等候室的线程根据优先级高低依次进入临界区。最后退出临界区的线程负责打开入口门。 算法的实现每个线程有一个flag变量表示该线程所处的状态。规定其含义为：
可以把这些flag变量表示为一个数组，共有n个元素。每个进程只写属于自己的flag数组元素，只读取其它线程的flag数组元素。这种“单独写”策略有助于提高cache性能。入口门的状态由所有的flag变量共同确定。 算法的伪代码实现: #进入临界区的协议：
flag[self] ← 1 #站在入口门外，申请进入等候室
await_until(all flag[1..N] ∈ {0, 1, 2}) #等待入口门打开。即不存在有进程处于3、4状态，包括正在进门、正在使用临界区
flag[self] ← 3 #站在入口门处，即正在进入。
if any flag[1..N] = 1: #如果还有在入口门外等待进入的线程
flag[self] ← 2 #把自己置为在入口门内，等待所有提出申请的线程都完成进入等候室
await_until(any flag[1..N] = 4) #等待最后进门的线程关闭入口门
flag[self] ← 4 #门处于关闭状态，线程在等候室
await_until(all flag[1..self-1] ∈ {0, 1}) #等待所有具有更高优先级的线程访问完临界区，退出等候室
#这里是临界区
#...
#退出临界区的协议
await_until(all flag[self+1..N] ∈ {0, 1, 4}) #确保所有比自己优先级低的已经通过入口门的线程都进入了等候室
flag[self] ← 0 #离开等候室，如果自己是最后离开的，则入口门被打开
上述伪代码中的"all"与"any"分别表示"所有"与"存在". 该算法容易直观理解其正确性。但是其正确性的形式验证比较难。一些文献给出了形式验证[2][5]. 参考文献
参见 |
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
Portal di Ensiklopedia Dunia
