Get best of the week

Perencanaan dalam Go: Bagian II - The Go Scheduler

Halo, Habr! Ini adalah posting kedua dalam seri tiga bagian, yang akan memberikan gambaran tentang mekanika dan semantik karya penjadwal di Go. Posting ini tentang perencana Go.

Pada bagian pertama dari seri ini, saya menjelaskan aspek penjadwal sistem operasi yang, menurut pendapat saya, penting untuk memahami dan mengevaluasi semantik penjadwal Go. Dalam posting ini, saya akan menjelaskan pada tingkat semantik bagaimana penjadwal Go bekerja. Go Scheduler adalah sistem yang kompleks dan detail mekanis kecil tidak penting. Penting untuk memiliki model yang baik tentang bagaimana segala sesuatu bekerja dan berperilaku. Ini akan memungkinkan Anda untuk membuat keputusan teknik terbaik.

Program Anda mulai


Ketika program Go Anda mulai, itu diberikan prosesor logis (P) untuk setiap inti virtual yang ditentukan pada mesin host. Jika Anda memiliki prosesor dengan beberapa utas perangkat keras per inti fisik (Hyper-Threading), setiap utas perangkat keras akan disajikan kepada program Anda sebagai inti virtual. Untuk lebih memahami hal ini, lihat laporan sistem untuk MacBook Pro saya.

gambar

Anda dapat melihat bahwa saya memiliki satu prosesor dengan 4 inti fisik. Laporan ini tidak mengungkapkan jumlah utas perangkat keras per inti fisik. Prosesor Intel Core i7 memiliki teknologi Hyper-Threading, yang berarti bahwa inti fisik memiliki 2 utas perangkat keras. Ini memberitahu Go bahwa 8 core virtual tersedia untuk menjalankan utas OS secara paralel. Untuk memverifikasi ini, pertimbangkan program berikut:

package main

import (
	"fmt"
	"runtime"
)

func main() {

    // NumCPU returns the number of logical
    // CPUs usable by the current process.
    fmt.Println(runtime.NumCPU())
}

Ketika saya menjalankan program ini di komputer saya, hasil memanggil fungsi NumCPU () akan menjadi 8. Program Go mana pun yang saya jalankan di komputer saya akan mendapatkan 8 (P).
Setiap P diberi aliran OS ( M ). Utas ini masih dikelola oleh OS, dan OS masih bertanggung jawab untuk menempatkan utas di kernel untuk dieksekusi. Ini berarti bahwa ketika saya menjalankan Go di komputer saya, saya memiliki 8 utas yang tersedia untuk melakukan pekerjaan saya, masing-masing ditautkan secara individual ke

program P. Each Go juga diberi Goroutine awal ( G) Goroutine pada dasarnya adalah Coroutine, tetapi Go, jadi kami mengganti huruf C dengan G dan mendapatkan kata Goroutine. Anda dapat menganggap Goroutine sebagai utas tingkat aplikasi, dan semuanya mirip dengan utas OS. Sama seperti utas OS dihidupkan dan dimatikan oleh kernel, program konteks dihidupkan dan dimatikan oleh konteks.

Teka-teki terakhir adalah antrian eksekusi. Ada dua antrian eksekusi yang berbeda di penjadwal Go: antrian eksekusi global (GRQ) dan antrian eksekusi lokal (LRQ). Setiap P diberi LRQ yang mengontrol goroutine yang ditugaskan untuk mengeksekusi dalam konteks P. Goroutine ini hidup dan mati dari konteks M yang ditugaskan untuk P. GRQ ini adalah untuk goroutine yang tidak ditugaskan ke P. Ada proses untuk memindahkan goroutine dari GRQ ke LRQ, yang akan kita bahas nanti.

Gambar menunjukkan semua komponen ini bersamaan.

gambar

Perencana koperasi


Seperti yang kami katakan di posting pertama, penjadwal OS adalah penjadwal preemptive. Pada dasarnya, ini berarti bahwa Anda tidak dapat memprediksi apa yang akan dilakukan perencana pada waktu tertentu. Kernel membuat keputusan dan semuanya bersifat non-deterministik. Aplikasi yang berjalan di atas sistem operasi tidak mengontrol apa yang terjadi di dalam kernel dengan penjadwalan kecuali mereka menggunakan primitif sinkronisasi seperti instruksi atom dan panggilan mutex.

Go Scheduler adalah bagian dari Go Runtime, dan Go Runtime ada di dalam aplikasi Anda. Ini berarti bahwa penjadwal Go berfungsi di ruang pengguna di kernel. Implementasi Go scheduler saat ini bukan preemptive, tetapi scheduler interaktif. Menjadi perencana kooperatif berarti perencana itu membutuhkan peristiwa yang didefinisikan dengan baik di ruang pengguna yang terjadi pada titik aman dalam kode untuk membuat keputusan perencanaan.

Apa yang baik tentang perencana kolaboratif Go adalah bahwa ia terlihat dan terasa proaktif. Anda tidak dapat memprediksi apa yang akan dilakukan penjadwal Go. Hal ini disebabkan oleh fakta bahwa pengambilan keputusan untuk penjadwal ini tidak tergantung pada pengembang, tetapi pada waktu eksekusi Go. Penting untuk menganggap penjadwal Go sebagai penjadwal proaktif, dan karena penjadwal adalah non-deterministik, itu tidak terlalu sulit.

Negara Gorutin


Sama seperti aliran, goroutine memiliki tiga tingkat tinggi yang sama. Mereka menentukan peran yang dimainkan perencana Go dengan setiap goroutine. Goroutin dapat di salah satu dari tiga negara: Menunggu, Siap, atau Memenuhi.

Menunggu : Ini berarti bahwa goroutine dihentikan dan menunggu sesuatu untuk melanjutkan. Ini dapat terjadi karena alasan seperti menunggu sistem operasi (panggilan sistem) atau sinkronisasi panggilan (operasi atom dan mutex). Jenis keterlambatan ini adalah penyebab utama buruknya kinerja.

Kesiapan: ini berarti bahwa goroutine ingin waktu untuk mengikuti instruksi yang diberikan. Jika Anda memiliki banyak goroutine yang membutuhkan waktu, maka goroutine harus menunggu lebih lama untuk mendapatkan waktu. Selain itu, jumlah waktu masing-masing yang diterima goroutine berkurang karena semakin banyak goroutine yang bersaing untuk mendapatkan waktu. Jenis penundaan penjadwalan ini juga dapat menyebabkan kinerja yang buruk.

Pemenuhan : ini berarti bahwa goroutine telah ditempatkan di M dan mengikuti instruksinya. Pekerjaan yang terkait dengan aplikasi telah selesai. Ini yang diinginkan semua orang.

Sakelar konteks


Go Scheduler membutuhkan peristiwa ruang pengguna yang terdefinisi dengan baik yang terjadi pada titik aman dalam kode untuk beralih konteks. Peristiwa dan titik aman ini muncul di panggilan fungsi. Panggilan fungsi sangat penting untuk kinerja Penjadwal Go. Jika Anda menjalankan loop sempit apa pun yang tidak membuat panggilan fungsi, Anda akan menyebabkan keterlambatan penjadwalan dan pengumpulan sampah. Sangat penting bahwa pemanggilan fungsi terjadi dalam jumlah waktu yang wajar.

Ada empat kelas peristiwa yang terjadi dalam program Go Anda yang memungkinkan perencana untuk membuat keputusan perencanaan. Ini tidak berarti bahwa ini akan selalu terjadi di salah satu acara ini. Ini berarti bahwa penjadwal mendapat kesempatan.

  • Menggunakan kata kunci go
  • Pengumpul sampah
  • Panggilan sistem
  • Sinkronisasi

Menggunakan
kata kunci go Kata kunci go adalah bagaimana Anda membuat goroutine. Begitu goroutine baru dibuat, itu memberi perencana kesempatan untuk membuat keputusan perencanaan.

Garbage Collector (GC)
Karena GC bekerja dengan set goroutinnya sendiri, gorutin ini membutuhkan waktu untuk menjalankan M. Ini memaksa GC untuk menciptakan banyak kekacauan dalam perencanaan. Namun, perencana sangat pandai dalam apa yang dilakukan goroutine, dan ia akan menggunakannya untuk mengambil keputusan. Salah satu solusi yang masuk akal adalah dengan mengubah konteks ke goroutine, yang ingin mengakses sumber daya sistem, dan tidak ada orang lain kecuali itu selama pengumpulan sampah. Ketika GC bekerja, banyak keputusan perencanaan dibuat.

Panggilan sistem
Jika goroutine membuat panggilan sistem yang akan membuatnya memblokir M, scheduler dapat mengalihkan konteks ke goroutine lain, ke M.

Sinkronisasi yang sama.
Jika panggilan ke operasi atom, sebuah mutex atau saluran menyebabkan goroutine diblokir, penjadwal dapat mengubah konteks untuk memulai goroutine baru. Setelah goroutine dapat berfungsi kembali, ia dapat di-antri dan akhirnya kembali ke M.

Panggilan sistem asinkron


Ketika sistem operasi yang Anda jalankan memiliki kemampuan untuk memproses panggilan sistem secara tidak sinkron, apa yang disebut dengan poller jaringan dapat digunakan untuk memproses panggilan sistem dengan lebih efisien. Ini dicapai dengan menggunakan kqueue (MacOS), epoll (Linux) atau iocp (Windows) di masing-masing OS ini.

Panggilan sistem jaringan dapat ditangani secara tidak sinkron oleh banyak sistem operasi yang kita gunakan saat ini. Di sinilah poller jaringan menunjukkan dirinya, karena tujuan utamanya adalah untuk memproses operasi jaringan. Menggunakan poller jaringan untuk panggilan sistem jaringan, scheduler dapat mencegah goroutine dari memblokir M selama panggilan sistem ini. Ini membantu menjaga M tersedia untuk mengeksekusi goroutine lain di LRQ P tanpa perlu membuat M. baru. Ini membantu mengurangi beban perencanaan dalam OS.

Cara terbaik untuk melihat bagaimana ini bekerja adalah dengan melihat contoh. Gambar tersebut menunjukkan skema perencanaan dasar kami. Gorutin-1 dieksekusi pada M, dan 3 Gorutin lagi sedang menunggu di LRQ untuk mendapatkan waktu mereka di M. Polling jaringan tidak digunakan, dan ia tidak ada hubungannya.

gambar

Pada gambar berikut, Gorutin-1 (G1) ingin membuat panggilan sistem jaringan, sehingga G1 pindah ke poller Jaringan dan diperlakukan sebagai panggilan sistem jaringan asinkron. Setelah G1 dipindahkan ke Network poller, M sekarang tersedia untuk mengeksekusi goroutine lain dari LRQ. Dalam hal ini, Gorutin-2 beralih ke M.

gambar

Pada gambar berikut, panggilan jaringan sistem berakhir dengan panggilan jaringan asinkron, dan G1 bergerak kembali ke LRQ untuk P. Setelah G1 dapat beralih kembali ke M, kode yang terkait dengan Go, untuk kode yang dia menjawab bisa mengeksekusi lagi. Kemenangan besar adalah bahwa tidak ada Ms tambahan yang diperlukan untuk melakukan panggilan sistem jaringan. Poller jaringan memiliki utas OS, dan prosesnya melalui loop peristiwa.

Panggilan sistem sinkron


Apa yang terjadi ketika goroutine ingin membuat panggilan sistem yang tidak dapat dijalankan secara tidak sinkron? Dalam kasus ini, Poller jaringan tidak dapat digunakan, dan goroutine yang membuat panggilan sistem akan memblokir M. Ini buruk, tetapi tidak ada cara untuk mencegah ini. Salah satu contoh panggilan sistem yang tidak dapat dilakukan secara tidak sinkron adalah panggilan sistem berbasis file. Jika Anda menggunakan CGO, mungkin ada situasi lain di mana fungsi C memanggil juga memblokir M.
Sistem operasi Windows dapat membuat panggilan sistem asinkron berbasis file. Secara teknis, ketika bekerja pada Windows, Anda dapat menggunakan poller jaringan.
Mari kita lihat apa yang terjadi dengan panggilan sistem sinkron (misalnya, file I / O) yang akan memblokir M. Angka tersebut menunjukkan diagram perencanaan dasar kami, tetapi kali ini G1 akan membuat panggilan sistem sinkron yang akan memblokir M1.

gambar

Pada gambar berikut, penjadwal dapat menentukan bahwa G1 menyebabkan kunci M. Pada titik ini, penjadwal memutus M1 dari P dengan G1 yang menghalangi masih terpasang. Penjadwal kemudian memperkenalkan M2 baru untuk melayani P. Pada titik ini, G2 dapat dipilih dari LRQ dan termasuk dalam konteks M2. Jika M sudah ada karena pertukaran sebelumnya, transisi ini lebih cepat daripada kebutuhan untuk membuat M. baru

gambar

Langkah selanjutnya melengkapi panggilan sistem kunci yang dibuat oleh G1. Pada titik ini, G1 dapat kembali ke LRQ dan dilayani lagi oleh P. M1 lalu disisihkan untuk penggunaan di masa mendatang jika skenario ini harus diulang.

gambar

Bekerja mencuri


Aspek lain dari penjadwal adalah bahwa ia adalah perencana pencurian goroutine. Ini membantu dalam beberapa bidang untuk mendukung perencanaan yang efektif. Pertama, hal terakhir yang Anda butuhkan adalah agar M pergi ke keadaan siaga, karena begitu ini terjadi, OS akan mengganti M dari kernel menggunakan konteks. Ini berarti bahwa P tidak dapat melakukan pekerjaan apa pun, bahkan jika ada Goroutine dalam keadaan sehat, sampai M beralih kembali ke kernel. Pencurian Gorutin juga membantu menyeimbangkan interval waktu antara semua Ps sehingga pekerjaan lebih baik didistribusikan dan dilakukan lebih efisien.

Pada gambar, kami memiliki program Go multi-threaded dengan dua Ps masing-masing melayani empat Gs dan satu G dalam GRQ. Apa yang terjadi jika salah satu P dengan cepat melayani semua G-nya?

gambar

Selanjutnya, P1 tidak lagi memiliki goroutine untuk dieksekusi. Tetapi ada goroutine dalam kondisi kerja, baik di LRQ untuk P2, dan di GRQ. Ini adalah momen ketika P1 perlu mencuri goroutine.

gambar

Aturan untuk mencuri goroutine adalah sebagai berikut. Semua kode dapat dilihat di sumber runtime.

runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}

Jadi, berdasarkan aturan-aturan ini, P1 harus memeriksa P2 untuk keberadaan goroutine di LRQ-nya dan mengambil setengah dari apa yang ditemukannya.

gambar

Apa yang terjadi jika P2 selesai melayani semua programnya dan P1 tidak memiliki yang tersisa di LRQ?

P2 telah menyelesaikan semua pekerjaannya dan sekarang harus mencuri goroutin. Pertama, dia akan melihat LRQ P1, tetapi tidak akan menemukan Goroutine. Selanjutnya dia akan melihat GRQ. Di sana ia akan menemukan G9.

gambar

P2 mencuri G9 dari GRQ dan mulai melakukan pekerjaan itu. Apa yang baik tentang semua pencurian ini adalah memungkinkan M untuk tetap sibuk dan tidak menjadi tidak aktif.

gambar

Contoh praktis


Dengan mekanika dan semantik, saya ingin menunjukkan kepada Anda bagaimana semua ini bersatu sehingga penjadwal Go dapat melakukan lebih banyak pekerjaan seiring waktu. Bayangkan aplikasi multi-utas yang ditulis dalam C, di mana program mengelola dua utas OS yang saling mengirim pesan. Ada 2 utas dalam gambar yang mengirim pesan bolak-balik. Utas 1 menerima konteks-switched inti 1 dan sekarang berjalan, yang memungkinkan utas 1 untuk mengirim pesannya ke utas 2.

gambar

Selanjutnya, ketika utas 1 selesai mengirim pesan, sekarang ia harus menunggu jawaban. Ini akan menyebabkan utas 1 terputus dari konteks kernel 1 dan dimasukkan ke dalam status menunggu. Segera setelah utas 2 menerima pemberitahuan pesan, ia masuk ke kondisi sehat. Sekarang OS dapat melakukan sakelar konteks dan menjalankan utas 2 pada kernel, yang ternyata adalah kernel 2. Kemudian utas 2 memproses pesan dan mengirim pesan baru kembali ke utas 1.

gambar

Selanjutnya, aliran beralih kembali ke konteks ketika pesan dari aliran 2 diterima oleh aliran 1. Sekarang, aliran 2 beralih dari status run ke status tunggu, dan streaming 1 beralih dari status siaga ke status siap dan akhirnya kembali ke status jalankan, yang memungkinkannya memproses dan mengirim pesan baru kembali. Semua konteks ini beralih dan perubahan status membutuhkan waktu untuk diselesaikan, yang membatasi kecepatan pekerjaan. Karena setiap saklar konteks memerlukan penundaan ~ 1000 nanodetik, dan kami berharap perangkat keras mengeksekusi 12 instruksi per nanodetik, Anda melihat 12.000 instruksi yang kurang lebih tidak dieksekusi selama sakelar konteks ini. Karena aliran ini juga berpotongan antara inti yang berbeda,Kemungkinan tambahan keterlambatan cache-line juga tinggi.

gambar

Dalam gambar ada dua gorutins yang selaras satu sama lain, menyampaikan pesan bolak-balik. G1 mendapatkan saklar konteks M1, yang berjalan pada Core 1, yang memungkinkan G1 untuk melakukan tugasnya.

gambar

Lebih lanjut, ketika G1 selesai mengirim pesan, sekarang dia perlu menunggu jawaban. Ini akan menyebabkan G1 terputus dari konteks M1 dan dimasukkan ke dalam status siaga. Segera setelah G2 diberitahu tentang pesan tersebut, pesan tersebut masuk ke kondisi sehat. Sekarang penjadwal Go dapat melakukan pengalihan konteks dan menjalankan G2 pada M1, yang masih berjalan pada Core 1. Kemudian G2 memproses pesan dan mengirim pesan baru kembali ke G1.

gambar

Pada langkah berikutnya, semuanya beralih lagi ketika pesan yang dikirim oleh G2 diterima oleh G1. Sekarang, konteks G2 beralih dari status eksekusi ke status tunggu, dan konteks G1 beralih dari status tunggu ke status eksekusi dan, akhirnya, kembali ke status eksekusi, yang memungkinkannya memproses dan mengirim pesan baru kembali.

gambar

Hal-hal di permukaan tampaknya tidak berbeda. Semua perubahan konteks yang sama dan perubahan status terjadi terlepas dari apakah Anda menggunakan Streaming atau Goroutine. Namun, ada perbedaan besar antara penggunaan Streams dan Gorutin, yang mungkin tidak jelas pada pandangan pertama.

Jika goroutine digunakan, utas dan kernel OS yang sama digunakan untuk semua pemrosesan. Ini berarti bahwa dari sudut pandang OS, OS Flow tidak pernah masuk ke kondisi menunggu; tidak pernah. Akibatnya, semua instruksi yang kami hilangkan saat mengalihkan konteks saat menggunakan stream tidak hilang saat menggunakan goroutin.

Pada dasarnya, Go mengubah pekerjaan IO / Blocking menjadi pekerjaan yang terikat prosesor di level OS. Karena semua peralihan konteks terjadi pada tingkat aplikasi, kami tidak kehilangan yang sama ~ 12 ribu instruksi (rata-rata) pada peralihan konteks yang kami kehilangan saat menggunakan stream. Di Go, switch konteks yang sama menghabiskan biaya ~ 200 nanodetik atau ~ 2,4 ribu perintah. Penjadwal juga membantu meningkatkan kinerja caching string dan NUMA. Itu sebabnya kami tidak membutuhkan lebih banyak utas daripada kami memiliki inti virtual. Go dapat melakukan lebih banyak pekerjaan seiring waktu, karena penjadwal Go mencoba menggunakan lebih sedikit utas dan melakukan lebih banyak pada setiap utas, yang membantu mengurangi beban pada OS dan perangkat keras.

Kesimpulan


Go Scheduler benar-benar luar biasa dalam hal memperhitungkan kerumitan OS dan perangkat keras. Kemampuan untuk mengubah operasi I / O / mengunci menjadi operasi yang terikat prosesor pada tingkat sistem operasi adalah tempat kami memperoleh keuntungan besar dalam menggunakan lebih banyak daya prosesor dari waktu ke waktu. Inilah sebabnya mengapa Anda tidak membutuhkan lebih banyak utas OS daripada Anda memiliki kernel virtual. Anda dapat dengan wajar berharap bahwa semua pekerjaan Anda akan selesai (dengan penjilidan CPU dan I / O / kunci) dengan satu utas OS per kernel virtual. Ini dimungkinkan untuk aplikasi jaringan dan aplikasi lain yang tidak memerlukan panggilan sistem yang memblokir utas OS.

Sebagai pengembang, Anda harus tetap memahami apa yang aplikasi Anda lakukan dalam hal jenis pekerjaan. Anda tidak dapat membuat goroutine dalam jumlah tak terbatas dan mengharapkan kinerja luar biasa. Less selalu lebih, tetapi dengan pemahaman semantik penjadwal Go ini, Anda dapat membuat keputusan rekayasa yang lebih baik.

More articles:


All Articles