Silabus Pelajaran 48 dari 148 · Mesin pinjaman
Mesin pinjaman

Prioritas pinjaman: mengurutkan antrean pekerjaan

Kenapa ini penting "Gunakan priority queue" adalah refleks untuk antrean dengan prioritas. Itu menjawab "siapa yang paling penting?" padahal pertanyaan aslinya seringkali adalah "siapa yang paling tidak bisa menunggu?". Bidang lain sudah lama menjawab pertanyaan itu.

Tiga meja

A unit gawat darurat rumah sakit. Perawat triase memasukkan setiap kedatangan ke dalam kategori, dan setiap kategori punya target waktu untuk diperiksa: dalam sistem Manchester yang umum digunakan, segera, dalam 10 menit, 60, 120 atau 240. Saat dokter luang, pasien berikutnya bukan sekadar yang paling sakit di ruangan: pasien standar yang hampir melewati targetnya bisa didahulukan daripada pasien darurat yang baru datang satu menit lalu dan masih punya waktu.

Check-in bandara. Ada jalur terpisah untuk premium dan ekonomi. Di dalam satu jalur, orang dilayani sesuai urutan kedatangan. Tapi saat penerbangan akan ditutup, staf berjalan di jalur ekonomi memanggil penerbangan itu ke depan, mendahului penumpang premium yang penerbangannya berangkat lebih lambat.

A library mengembalikan desk. Satu baris, dilayani secara ketat sesuai urutan. Tidak ada yang pernah didahului, dan urgensi siapa pun tidak dipertimbangkan.

Bandingkan sebelum kamu coding

  1. Di setiap meja, apa yang menentukan siapa yang dilayani berikutnya?
  2. Meja mana yang bisa membuat seseorang menunggu selamanya? Meja mana yang bisa membuat kasus mendesak menunggu terlalu lama?
  3. Rumah sakit dan bandara sama sekali tidak mirip. Apa kesamaan mereka? Tulis dalam satu kalimat yang tidak menyebutkan rumah sakit maupun pesawat.
  4. Di bandara, kenapa cukup melihat bagian depan setiap jalur saja?

Targetnya

Sistem background job

A berjalan di satu worker yang butuh waktu tepat satu menit per job. Job bersifat interaktif (prioritas 1), standar (2) atau batch (3), dan setiap prioritas punya janji layanan: waktu terlama sebuah job dengan prioritas tersebut boleh menunggu sebelum dimulai. Scheduler saat ini selalu menjalankan job menunggu dengan prioritas tertinggi, dan job batch meleset dari janjinya setiap sore.

Giliranku

Tulis order(jobs, max_wait). jobs adalah daftar {"id", "arrive", "priority"} yang diurutkan berdasarkan arrive (menit penuh); max_wait memetakan prioritas ke menit maksimal sebuah pekerjaan bisa menunggu. Kembalikan id pekerjaan sesuai urutan yang dijalankan worker. Worker menjalankan satu pekerjaan per menit: sebuah pekerjaan dimulai pada waktu yang lebih lambat antara kedatangannya dan selesainya pekerjaan sebelumnya, dan waktu tunggunya adalah mulai dikurangi kedatangan. Aturan: tidak ada pekerjaan yang boleh menunggu lebih lama dari max_wait[priority]. Hari uji coba bisa dilayani tanpa ada pekerjaan yang terlambat; dengan {1: 3, 2: 20, 3: 60} satu hari memiliki sekitar 1.000 pekerjaan.

Ada masalah di pelajaran ini? Laporkan · Tanya tentang pelajaran ini

Latihan ini akan segera dibuka

Selesaikan pelajaran sebelumnya agar pelajaran ini terbuka. Seluruh kursus ini gratis, tidak butuh akun, dan kamu bisa baca pelajaran ini sekarang.