Очередь Майкла - Скотт: два конца и помощь соседу

поставить(x):
    узел = новый узел x
    повторять:
        t = хвост;  n = t.следующий
        если хвост != t: заново
        если n пусто:
            # точка линеаризации - этот CAS
            если cas(t.следующий, пусто, узел):
                cas(хвост, t, узел)     # может не пройти - не страшно
                выйти
        иначе:
            cas(хвост, t, n)            # ПОМОЩЬ: хвост отстал

взять():
    повторять:
        h = голова;  t = хвост;  n = h.следующий
        если голова != h: заново
        если h == t:
            если n пусто: вернуть «пусто»
            cas(хвост, t, n)            # ПОМОЩЬ
        иначе:
            # n станет новым фиктивным узлом
            если cas(голова, h, n): вернуть n.значение

# очередь Майкла - Скотт в модели: узел [значение, следующий], узел 0 -
# фиктивный; голова указывает на фиктивный, хвост - на последний или
# отстаёт на один. Шаг потока - одно атомарное действие.

def nachalo(programmy):
    k = len(programmy)
    return {"uzly": [[None, -1]], "golova": 0, "hvost": 0,
            "pc": [0] * k, "op": [0] * k, "h": [-1] * k, "t": [-1] * k,
            "n": [-1] * k, "x": [-1] * k, "vyshlo": []}

def kopiya(s):
    uzly = []
    for u in s["uzly"]:
        uzly.append(u[:])
    s2 = {"uzly": uzly, "golova": s["golova"], "hvost": s["hvost"],
          "vyshlo": s["vyshlo"][:]}
    for pole in ["pc", "op", "h", "t", "n", "x"]:
        s2[pole] = s[pole][:]
    return s2

def gotovo(s, p):
    s["op"][p] = s["op"][p] + 1
    s["pc"][p] = 0

def shag(s, p, programmy, pomoshch):
    op = programmy[p][s["op"][p]]
    pc = s["pc"][p]
    if op != "deq":                              # поставить в очередь op
        if pc <= 1:
            if pc == 0:            # свой узел - приватный шаг, склеен
                s["uzly"].append([op, -1])       # с чтением хвоста
                s["x"][p] = len(s["uzly"]) - 1
            s["t"][p] = s["hvost"]
            s["pc"][p] = 2
        elif pc == 2:
            s["n"][p] = s["uzly"][s["t"][p]][1]
            s["pc"][p] = 3
        elif pc == 3:
            t = s["t"][p]
            s["pc"][p] = 1                       # по умолчанию - заново
            if s["hvost"] != t:
                return
            if s["n"][p] == -1:
                if s["uzly"][t][1] == -1:        # CAS t.next: -1 -> x
                    s["uzly"][t][1] = s["x"][p]
                    s["pc"][p] = 4
            elif pomoshch and s["hvost"] == t:   # хвост отстал: помочь
                s["hvost"] = s["n"][p]
        else:
            if s["hvost"] == s["t"][p]:          # CAS хвоста: t -> x
                s["hvost"] = s["x"][p]
            gotovo(s, p)
    else:                                        # взять из очереди
        if pc == 0:
            s["h"][p] = s["golova"]
            s["pc"][p] = 1
        elif pc == 1:
            s["t"][p] = s["hvost"]
            s["pc"][p] = 2
        elif pc == 2:
            s["n"][p] = s["uzly"][s["h"][p]][1]
            s["pc"][p] = 3
        else:
            h = s["h"][p]
            n = s["n"][p]
            s["pc"][p] = 0
            if s["golova"] != h:
                return
            if h == s["t"][p]:
                if n == -1:
                    s["vyshlo"].append("пусто")
                    gotovo(s, p)
                elif pomoshch and s["hvost"] == h:
                    s["hvost"] = n
            elif s["golova"] == h:               # CAS головы: h -> n
                s["golova"] = n
                s["vyshlo"].append(s["uzly"][n][0])
                gotovo(s, p)

def soderzhimoe(s):
    out = []
    v = s["uzly"][s["golova"]][1]
    while v != -1:
        out.append(s["uzly"][v][0])
        v = s["uzly"][v][1]
    return out

def obojti(s, programmy, vidennye, itogi):
    klyuch = str(s)
    if klyuch in vidennye:
        return
    vidennye[klyuch] = True
    hodit = []
    for p in range(len(programmy)):
        if s["op"][p] < len(programmy[p]):
            hodit.append(p)
    if len(hodit) == 0:
        itog = str(soderzhimoe(s)) + " выдано " + str(s["vyshlo"])
        if itog not in itogi:
            itogi.append(itog)
        return
    for p in hodit:
        s2 = kopiya(s)
        shag(s2, p, programmy, True)
        obojti(s2, programmy, vidennye, itogi)

programmy = [["X"], ["Y"], ["deq"]]
vidennye = {}
itogi = []
obojti(nachalo(programmy), programmy, vidennye, itogi)
itogi.sort()
print("состояний:", len(vidennye), "итоги:")
for i in itogi:
    print("  ", i)

# поток 0 связал узел X и уснул до CAS хвоста; поток 1 работает один
for pomoshch in [False, True]:
    programmy = [["X"], ["Y"]]
    s = nachalo(programmy)
    for i in range(3):
        shag(s, 0, programmy, pomoshch)
    shagov = 0
    while s["op"][1] < 1 and shagov < 100:
        shag(s, 1, programmy, pomoshch)
        shagov = shagov + 1
    print("помощь:", pomoshch, "- поток 1 сделал", shagov,
          "шагов, закончил:", s["op"][1] == 1, "очередь", soderzhimoe(s))

состояний: 1059 итоги:
   ['X', 'Y'] выдано ['пусто']
   ['X'] выдано ['Y']
   ['Y', 'X'] выдано ['пусто']
   ['Y'] выдано ['X']
помощь: False - поток 1 сделал 100 шагов, закончил: False очередь ['X']
помощь: True - поток 1 сделал 7 шагов, закончил: True очередь ['X', 'Y']