シラバス レッスン 148 中 48 · 借りてきた仕組み
借りてきた仕組み

トリアージを借りる:ジョブのキューの順番

なぜ大切か 「優先度付きキューを使う」は、優先度のあるあらゆるキューへの反射です。それは「誰が最も大事か?」に答えますが、本当の問いはしばしば「誰が最も待てないか?」です。ほかの分野は長い間その問いに答えてきました。

3 つの窓口

病院の救急外来。トリアージの看護師が、到着した人をそれぞれ区分に入れ、それぞれの区分には診察までの目標の時間があります。広く使われるマンチェスターの方式では、即時、10 分以内、60、120、240。医師の手が空いたとき、次の患者はただ部屋で最も重い人ではありません。目標を過ぎそうなふつうの患者が、1 分前に着いてまだ時間のある緊急の患者より先に行けるのです。

空港のチェックイン。プレミアムとエコノミーに別々の列があります。列の中では、着いた順に応じます。でも便がもうすぐ締め切られるとき、係員はエコノミーの列を歩いてその便の人を前へ呼び、後で出る便のプレミアムの乗客より先にします。

図書館の返却の窓口。列はひとつで、厳密に順番に応じます。誰も追い越されず、誰の急ぎも考えられません。

コードの前に比べる

  1. それぞれの窓口で、次に誰が応じられるかを何が決める?
  2. どの窓口が誰かを永久に待たせうる? どれが緊急の場合を待たせすぎうる?
  3. 病院と空港はまったく似て見えない。何を共有している? 病院にも飛行機にも触れない一文で書く。
  4. 空港では、なぜそれぞれの列の先頭を見るだけで十分なのか?

目的の問題

裏方のジョブのシステムが、ジョブごとにちょうど 1 分かかるひとつのワーカーで動きます。ジョブは対話型(優先度 1)、ふつう(2)、バッチ(3)で、それぞれの優先度にはサービスの約束があります。その優先度のジョブが始まるまでに待ってよい最長の時間です。今のスケジューラーはいつも待っているジョブの中で最も優先度の高いものを動かし、バッチのジョブは毎日午後に約束を破ります。

あなたの番

order(jobs, max_wait) を書いてください。jobs は arrive(分の整数)で並べた {"id", "arrive", "priority"} のリストです。max_wait は優先度を、ジョブが待ってよい最大の分数に対応させます。ワーカーが動かす順のジョブの ID を返します。ワーカーは 1 分にひとつのジョブを動かします。ジョブは、到着と前のジョブの終わりの遅いほうに始まり、待ち時間は開始引く到着です。規則:どのジョブも max_wait[priority] より長く待ってはなりません。テストの日はどれも遅れるジョブなしでこなせます。{1: 3, 2: 20, 3: 60} で、1 日に約 1,000 のジョブがあります。

このレッスンに問題を見つけましたか?報告する · このレッスンについて質問する

この演習はまもなく開きます

その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。