1

Webページで次のことを達成しようとしています:

  • ユーザーはページの複数のタブ/ウィンドウを開くことができます。
  • 数秒ごとに、コードの特定のセクション (重要な領域) を実行するには、これらのタブ/ウィンドウのいずれかが必要です。
  • どのタブ/ウィンドウがコードを実行するかは気にしません。つまり、ソリューションの公平性や飢餓特性について心配する必要はありません。
  • ユーザーが自分でタブ/ウィンドウを開いたので、ページのさまざまなインスタンスは、相互に認識していないか、直接参照していません (つまり、window.parent などはありません)。
  • Flash、Silverlight、またはその他のプラグインを要求したくありません。すべてをクライアント側で実行する必要があるため、タブ/ウィンドウが通信できる方法は非常に限られています (これまでに見つけたのはLocalStorageだけですが、他の人になる）。
  • タブ/ウィンドウのいずれかがいつでもクラッシュしたり、閉じたり、更新されたりする可能性があり、さらに多くのタブ/ウィンドウをいつでも開くことができます。数秒。
  • これは、モバイル ( caniuse -rating %90 以上)を含む、できるだけ多くのブラウザーで確実に実行する必要があります。

私が最初に試みた解決策は、LocalStorage を共有メモリとして使用する単純な相互排除アルゴリズムを使用することでした。さまざまな理由から、 Burns と Lynch の論文「Mutual Exclusion Using Indivisible Reads and Writes」 (4 ページ (836))から相互排除アルゴリズムを選択しました。

私はjsfiddle (以下のコードを参照)を作成してアイデアを試してみましたが、Firefox で美しく動作します。試してみたい場合は、Firefox の複数 (最大 20) のウィンドウでフィドルへのリンクを開き、そのうちの 1 つだけが毎秒オレンジ色に点滅するのを確認してください。同時に複数のまばたきが見られる場合は、お知らせください。:) (注: フィドルで ID を割り当てる方法は少し安っぽく (0..19 をループするだけ)、すべてのウィンドウに異なる ID が割り当てられている場合にのみ機能します。2 つのウィンドウに同じ ID が表示されている場合は、単純に1 つをリロードします。)

残念ながら、Chrome、特に Internet Explorer では、意図したとおりに動作しません (複数のウィンドウが点滅します)。これは、あるタブ/ウィンドウから別のタブ/ウィンドウへの LocalStorage に書き込むデータの伝播の遅延によるものだと思います (これに関する私の質問はこちらを参照してください)。

したがって、基本的には、遅延データを処理できる別のミューテックス アルゴリズムを見つける必要があります (難しい/不可能に聞こえます)、またはまったく別のアプローチを見つける必要があります。たぶん、StorageEventsが役に立ちますか? それとも、LocalStorage を使用しない別のメカニズムがあるのでしょうか?

完全を期すために、フィドルのコードを次に示します。

// Global constants
var LOCK_TIMEOUT =  300; // Locks time out after 300ms
var INTERVAL     = 1000; // Critical section should run every second



//==================================================================================
// Assign process ID

var myID;
id = window.localStorage.getItem("id");

if (id==null) id = 0;
id = Number(id);
myID = id;
id = (id+1) % 20;
window.localStorage.setItem("id", id);

document.documentElement.innerHTML = "ID: "+myID;



//==================================================================================
// Method to indicate critical section

var lastBlink = 0;
function blink() {
    col = Math.round(Math.min((new Date().getTime() - lastBlink)*2/3, 255));
    document.body.style.backgroundColor = "rgb(255, "+((col >> 1)+128)+", "+col+")";
}



//==================================================================================
// Helper methods to implement expiring flags

function flagUp() {
    window.localStorage.setItem("F"+myID, new Date().getTime());
}

function flagDown() {
    window.localStorage.setItem("F"+myID, 0);
}

// Try to refresh flag timeout and return whether we're sure that it never expired
function refreshFlag() {
    content = window.localStorage.getItem("F"+myID);
    if (content==null) return false;
    content = Number(content);
    if ((content==NaN) || (Math.abs(new Date().getTime() - content)>=timeout))
        return false;
    window.localStorage.setItem("F"+myID, new Date().getTime());
    return Math.abs(new Date().getTime() - content) < timeout;
}    

function setFlag(key) {
    window.localStorage.setItem(key, new Date().getTime());
}

function checkFlag(key, timeout) {
    content = window.localStorage.getItem(key);
    if (content==null) return false;
    content = Number(content);
    if (content==NaN) return false;
    return Math.abs(new Date().getTime() - content) < timeout;
}



//==================================================================================
// Burns-Lynch mutual exclusion algorithm

var atLine7 = false;

function enterCriticalRegion() {

    // Refresh flag timeout and restart algorithm if flag may have expired
    if (atLine7) atLine7 &= refreshFlag();

    // Check if run is due
    if (checkFlag("LastRun", INTERVAL)) return false;

    if (!atLine7) {
        // 3: F[i] down
        flagDown();

        // 4: for j:=1 to i-1 do if F[j] = up goto 3
        for (j=0; j<myID; j++)
            if (checkFlag("F"+j, LOCK_TIMEOUT)) return false;

        // 5: F[i] up
        flagUp();

        // 6: for j:=1 to i-1 do if F[j] = up goto 3
        for (j=0; j<myID; j++)
            if (checkFlag("F"+j, LOCK_TIMEOUT)) return false;

        atLine7 = true;
    }

    // 7: for j:=i+1 to N do if F[j] = up goto 7
    for (j=myID+1; j<20; j++)
        if (checkFlag("F"+j, LOCK_TIMEOUT)) return false;

    // Check again if run is due
    return !checkFlag("LastRun", INTERVAL);
}

function leaveCriticalRegion() {
    // Remember time of last succesful run
    setFlag("LastRun");

    // Release lock on critical region
    atLine7 = false;
    window.localStorage.setItem("F"+myID, 0);
}



//==================================================================================
// Keep trying to enter critical region and blink on success

function run() {
    if (enterCriticalRegion()) {
        lastBlink = new Date().getTime();
        leaveCriticalRegion();
    }
}

// Go!
window.setInterval(run,   10);
window.setInterval(blink, 10);
4

0 に答える 0