Algoritma Penjadualan Lif: FCFS, SSTF, SCAN dan LOOK

Memandangkan saya telah bekerja dengan Go untuk sekian lama, saya fikir ia akan menjadi cabaran yang menyeronokkan untuk melaksanakan beberapa penyelesaian reka bentuk peringkat rendah klasik di dalamnya.

Apabila mereka bentuk sistem lif, satu aspek penting ialah cara menentukan tingkat yang akan diservis seterusnya, terutamanya apabila lif mempunyai banyak permintaan. Sintaks dan prestasi mudah Go menjadikannya ideal untuk memodelkan sistem sedemikian, jadi saya mula mencipta pelaksanaan asas FCFS (First Come First Serve), SSTF (Shortest Seek Time First), SCAN dan algoritma LOOK.

1. First Come First Serve (FCFS)

Saya bermula dengan pendekatan paling mudah: permintaan perkhidmatan mengikut urutan yang diterima. Ia mudah untuk dilaksanakan tetapi boleh menjadi tidak cekap jika permintaan tersebar di seluruh tingkat, yang membawa kepada lebih banyak masa perjalanan.

func FCFS(currentFloor int, requests []int) []int {
    path := []int{}
    for _, floor := range requests {
        path = append(path, floor)
    }
    return path
}

Di FCFS, lif hanya bergerak ke setiap tingkat yang diminta mengikut susunan yang diberikan.

2. Masa Carian Terpendek Didahulukan (SSTF)

SSTF cuba meminimumkan perjalanan dengan memilih tingkat yang paling dekat diminta seterusnya. Ini mengurangkan masa perjalanan tetapi boleh menyebabkan "kebuluran" untuk permintaan yang jauh jika permintaan yang lebih dekat terus datang.

func SSTF(currentFloor int, requests []int) []int {
    path := []int{}
    remaining := append([]int{}, requests...)

    for len(remaining) > 0 {
        closestIdx := 0
        minDistance := abs(currentFloor - remaining[0])

        for i, floor := range remaining {
            distance := abs(currentFloor - floor)
            if distance < minDistance {
                closestIdx = i
                minDistance = distance
            }
        }

        currentFloor = remaining[closestIdx]
        path = append(path, currentFloor)
        remaining = append(remaining[:closestIdx], remaining[closestIdx+1:]...)
    }
    return path
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Fungsi ini mencari tingkat yang paling hampir dengan tingkat semasa setiap kali, mengemas kini kedudukan lif selepas setiap pergerakan.

3. SCAN (Algoritma Lif)

Dalam SCAN, lif bergerak ke satu arah, melayani semua permintaan ke arah itu sehingga ia sampai ke penghujung, kemudian berundur. Pendekatan ini lebih adil daripada SSTF kerana ia mengurangkan kebuluran.

func SCAN(currentFloor, maxFloor int, requests []int) []int {
    path := []int{}
    up := []int{}
    down := []int{}

    for _, floor := range requests {
        if floor >= currentFloor {
            up = append(up, floor)
        } else {
            down = append(down, floor)
        }
    }

    sort.Ints(up)
    sort.Sort(sort.Reverse(sort.IntSlice(down)))

    path = append(path, up...)
    path = append(path, down...)
    return path
}

Fungsi ini membahagikan permintaan kepada tingkat di atas dan di bawah kedudukan semasa. Ia berfungsi untuk semua tingkat ke atas, kemudian ke bawah.

4. LIHAT

LOOK ialah sedikit variasi SCAN. Daripada terus ke penghujung, lif berbalik arah pada permintaan terakhir di setiap arah. Ia menjimatkan masa dengan berhenti di tempat permintaan berakhir, bukan pada had fizikal.

func LOOK(currentFloor int, requests []int) []int {
    path := []int{}
    up := []int{}
    down := []int{}

    for _, floor := range requests {
        if floor >= currentFloor {
            up = append(up, floor)
        } else {
            down = append(down, floor)
        }
    }

    sort.Ints(up)
    sort.Sort(sort.Reverse(sort.IntSlice(down)))

    path = append(path, up...)
    path = append(path, down...)
    return path
}

Sama seperti SCAN, pendekatan ini hanya bergerak sejauh permintaan terakhir dalam setiap arah.

Setiap algoritma mempunyai pertukarannya:

• FCFS: Mudah tetapi boleh menjadi tidak cekap.
• SSTF: Mengoptimumkan untuk tingkat yang terdekat tetapi boleh menghilangkan permintaan yang jauh.
• SCAN: Lebih adil dan cekap, meminimumkan perubahan arah.
• LIHAT: Menjimatkan masa tambahan dengan berhenti pada permintaan terakhir.

Pilihan yang tepat bergantung pada keperluan khusus untuk kecekapan, keadilan dan masa tindak balas dalam sistem.

Untuk pelaksanaan penuh menggunakan algoritma LOOK, rujuk repo github saya:

thesaltree / low-level-design-golang

Penyelesaian masalah reka bentuk sistem tahap rendah di Golang

Reka Bentuk Sistem Aras Rendah dalam Go

Selamat datang ke repositori Reka Bentuk Sistem Tahap Rendah dalam Go! Repositori ini mengandungi pelbagai masalah reka bentuk sistem peringkat rendah dan penyelesaiannya dilaksanakan dalam Go. Matlamat utama adalah untuk menunjukkan reka bentuk dan seni bina sistem melalui contoh praktikal.

Jadual Kandungan

• Ikhtisar
• Sistem Tempat Letak Kereta
• Sistem Lif

Ikhtisar

Reka bentuk sistem peringkat rendah melibatkan pemahaman konsep teras seni bina sistem dan mereka bentuk sistem berskala, boleh diselenggara dan cekap. Repositori ini akan cuba merangkumi penyelesaian pelbagai masalah dan senario menggunakan Go.

Sistem Tempat Letak Kereta

Projek pertama dalam repositori ini ialah Sistem Tempat Letak Kereta. Sistem ini menyerupai tempat letak kereta di mana kenderaan boleh diletakkan dan tidak diletakkan. Ia menunjukkan:

• Corak reka bentuk singleton untuk menguruskan contoh tempat letak kereta.
• Mengendalikan pelbagai jenis kenderaan (cth., kereta, trak).
• Pengurusan ruang letak kereta merentas berbilang tingkat.
• Pemprosesan pembayaran untuk kenderaan yang diletakkan.

Ciri

• Tambah dan alih keluar kenderaan daripada…

Lihat di GitHub

Atas ialah kandungan terperinci Algoritma Penjadualan Lif: FCFS, SSTF, SCAN dan LOOK. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!