27 tháng 7, 2019

Go Scheduler

Go Scheduler

Trong bài viết này, chúng ta sẽ cùng tìm hiểu xem Go Scheduler hoạt động như thế nào, thông qua đó ta có thể đưa ra các quyết định về mặt kỹ thuật tốt hơn khi lập trình bằng ngôn ngữ Go.

Khi một chương trình phần mềm được viết bằng ngôn ngữ Go khởi động, nó được cung cấp một Bộ vi xử lý ảo - Logical Processor (P) cho mỗi virtual core trên máy host. Nếu bạn có một bộ vi xử lý với nhiều hardware thread trên mỗi physical core (Hyper-Threading) thì chương trình của bạn sẽ coi mỗi hardware thread như một virtual core.

Ví dụ, giả sử chúng ta có thông số kĩ thuật sau của một máy tính Macbook Pro:

Hình 1:

Hình 1

Như bạn có thể thấy, chúng ta có một bộ vi xử lý đơn với 4 physical core. Theo như những thông số trên thì chúng ta không thấy thông số nào nói đến số lượng hardware thread trên mỗi physical core. Tuy nhiên, bộ vi xử lý Intel Core I7 có tính năng Hyper-Threading, điều này có nghĩa là sẽ có 2 hardware thread cho mỗi physical core. Vậy nên chương trình của bạn sẽ có thể hiểu là có 8 virtual core sẵn sàng để thực thi song song các tác vụ trên các OS Thread.

package main

import (
	"fmt"
	"runtime"
)

func main() {

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

Khi chúng ta thực hiện đoạn code trên với những thông số đã xem qua của máy Macbook Pro thì kết quả NumCPU() sẽ là 8. Mọi chương trình khi chạy sẽ đều được cung cấp 8 P. Mỗi P sẽ được gán cho một OS Thread (M) (M là viết tắt của từ machine). Các Thread này sẽ được quản lý bởi OS và OS vẫn chịu trách nhiệm cho việc đặt Thread lên Core trong quá trình thực thi. Điều này có nghĩa là mỗi khi chúng ta khởi chạy chương trình, chúng ta sẽ có 8 thread sẵn sàng để thực thi công việc, mỗi thread được đính kèm vào một P.

Mọi chương trình Go cũng được cung cấp một Goroutine ban đầu (G), Goroutine giống như OS Thread nhưng mà là ở tầng ứng dụng. Cũng giống như các OS Thread được chuyển đổi ngữ cảnh (context-switch) trên một core, các Goroutine cũng được chuyển đổi ngữ cảnh trên M.

Có 2 run-queue khác nhau trong Go scheduler: Global Run Queue (GRQ)Local Run Queue (LRQ). Mỗi P được cung cấp một LRQ quản lý các Goroutine đã được chỉ định để thực thi bên trong context của P. Những Goroutine này sẽ lần lượt được switch-context on hoặc off trên M mà đã được gán cho P. GRQ dành cho các Goroutine chưa được gán cho một P nào. Ta sẽ thảo luận về tiến trình dịch chuyển các Goroutine từ GRQ sang LRQ trong phần sau.

Hình 2:

Hình 2

Cooperating Scheduler

Như chúng ta biết thì OS scheduler là một Preemptive scheduler. Về cơ bản thì điều này nghĩa là chúng ta sẽ không dự đoán được scheduler sẽ làm gì và vào bất kì lúc nào. Kernel sẽ chịu trách nhiệm đưa ra quyết định và mọi thứ sẽ không thể xác định rõ ràng. Các ứng dụng chạy trên OS không có quyền kiểm soát những gì đang xảy ra bên trong Kernel bằng scheduler trừ khi chúng tận dụng atomic hoặc mutex.

Go scheduler là một phần của Go runtime, và Go runtime được tích hợp vào trong ứng dụng của bạn. Nghĩa là, Go scheduler sẽ chạy trong User space, phía trên Kernel. Hiện tại, cách triển khai Go scheduler không phải là Preemptive scheduler mà là một Cooperating scheduler. Với việc là một Cooperating scheduler nghĩa là scheduler này cần các sự kiện User space được xác định rõ ràng để có thể đưa ra quyết định schedule.

Goroutine States

Cũng giống như Thread, Goroutine cũng có ba trạng thái high-level, chúng chỉ ra vai trò Go scheduler đối với một Goroutine bất kì. Một Goroutine có thể ở một trong ba trạng thái: Waiting, Runable hoặc Executing.

Waiting: Nghĩa là Goroutine bị dừng và đang đợi điều gì đó để tiếp tục. Điều này có thể là vì chờ hệ điều hành phản hồi (system call) hoặc lời gọi đồng bộ (atomic hoặc mutex). Đây là những nguyên nhân gốc rễ dẫn đến hiệu năng kém của một chương trình.

Runnable: Nghĩa là Goroutine đã sẵn sàng để thực thi các chỉ dẫn đã được chỉ định trên M. Nếu chúng ta có nhiều Goroutine cùng trong trạng thái này thì cũng có nghĩa là các Goroutine cũng sẽ phải đợi lâu hơn đến đến lượt thực thi.

Executing: Nghĩa là các Goroutine đã được đặt trên một M và đang thực thi các chỉ dẫn của nó. Công việc liên quan đến ứng dụng đang được thực hiện.

Context Switching

Go Scheduler yêu cầu các sự kiện User-space được xác định rõ xảy ra tại các safe-point trong code để thực hiện context-switch. Các sự kiện và safe-point này được thể hiện bên trong các lời gọi hàm. Các lời gọi hàm rất quan trọng đối với trạng thái của Go Scheduler. Từ Go version 1.11 trở xuống, nếu bạn chạy một vòng lặp đơn giản bất kì mà không thực hiện các lời gọi hàm thì có thể sẽ gây ra độ trễ bên trong Scheduler và Garbage Collection. Các lời gọi hàm phải xảy ra bên trong một khung thời gian hợp lí là cực kì quan trọng.

Có bốn loại sự kiện xảy ra trong các chương trình Go cho phép Scheduler đưa ra các quyết định schedule. Điều này không có nghĩa là nó sẽ luôn luôn xảy ra ở một trong các loại sự kiện này, mà chỉ là Scheduler sẽ có cơ hội để đưa ra quyết định schedule.

Bốn loại sự kiện được nhắc tới là:

  • Sử dụng từ khóa go

  • Garbage collection

  • System call

  • Synchronization và Orchestration

Sử dụng từ khóa go

Từ khóa go giúp bạn tạo mới các Goroutine, khi một Goroutine được tạo mới thì nó sẽ chờ được schedule bởi Go Scheduler.

Garbage collection

GC chạy bằng cách sử dụng chính các Goroutine của riêng nó nên các Goroutine này cần thời gian để thực thi ở trên M. Điều này dẫn đến việc tạo ra nhiều sự hỗn loạn khi schedule. Tuy nhiên, Go Scheduler đủ "thông minh" để đưa ra các quyết định hợp lí. Một trong các quyết định thông minh là thực hiện context-switch cho một Goroutine muốn sử dụng đến Heap trong quá trình GC. Khi đang trong quá trình GC, rất nhiều quyết định schedule sẽ được đưa ra.

System call

Nếu một Goroutine thực hiện một lời gọi system call sẽ khiến Goroutine này bị block trên M, đôi khi scheduler sẽ có thể thực hiện context-switch off Goroutine này trên M và thực hiện context-switch một Goroutine mới ngay trên M này. Tuy nhiên, thỉnh thoảng một M mới sẽ được tạo để tiếp tục thực thi các Goroutine đang trong hàng đợi của P. Chúng ta sẽ tìm hiểu chi tiết về điều này trong phần sau.

Synchronization và Orchestration

Nếu một atomic, mutex hoặc channel được gọi sẽ dẫn đến Goroutine bị block, Go Scheduler có thể thực hiện context-switch một Goroutine mới để tiếp tục thực thi công việc. Một khi Goroutine bị block có thể tiếp tục thực thi tiếp thì nó có thể được cho trở lại vào hàng đợi và đợi đến lượt được context-switch.

Các System-call bất đồng bộ

Khi hệ điều hành của bạn có khả năng xử lý bất đồng bộ một system-call thì network-poller có thể được sử dụng để xử lý system-call này hiệu quả hơn. Điều này có thể thực hiện được là nhờ vào kqueue trên MacOS, epoll trên Linux hoặc iocp trên Windows.

Ngày nay, các system-call dựa trên network có thể được xử lý bất đồng bộ nhờ vào hệ điều hành của bạn. Bằng cách sử dụng network-poller, Go Scheduler có thể ngăn chặn được việc các Goroutine bị block trên M khi các system-call kiểu này được tạo ra. Điều này sẽ giúp cho M tiếp tục được sử dụng để thực thi các Goroutine khác trong LRQ mà không phải tạo ra thêm các M. Nó sẽ giúp giảm thiểu thời gian tải của quá trình schedule trên hệ điều hành.

Hình 3:

Hình 3

Nhìn vào hình 3 chúng ta có thể thấy Goroutine-1 đang thực thi công việc trên M và có 3 Goroutine khác đang đợi đến lượt trong LRQ. Network-poller thì đang nhàn rỗi.

Hình 4:

Hình 4

Trong hình 4, Goroutine-1 muốn thực hiện một network system call, vì vậy Goroutine-1 được chuyển đến cho network-pollernetwork system call sẽ được xử lý bất đồng bộ. Một khi Goroutine-1 được chuyển đến network-poller, thì bây giờ M sẽ thực thi công việc của một Goroutine khác trong LRQ. Như hình 4 thì Goroutine sẽ được context-switch trên M.

Hình 5:

Hình 5

Trong hình 5, network-poller hoàn thành xử lý bất đồng bộ network system call và Goroutine-1 được chuyển lại cho LRQ. Khi Goroutine-1 đến lượt context-switch trở lại, có đoạn code mà nó chịu trách nhiệm xử lý có thể được thực thi lại. Điểm lợi lớn nhất ở đây đó là khi ta thực thi các network system call thì không cần phải tạo thêm M. Network-poller có một OS Thread và nó xử lý event-loop rất hiệu quả.

Synchronous System Call

Vậy điều gì sẽ xảy ra khi một Goroutine muốn thực hiện một system-call không thể được hoàn thành bằng xử lý bất đồng bộ? Trong trường hợp này, network-poller không thể được sử dụng và Goroutine tạo ra system-call sẽ bị block trên M. Chúng ta sẽ không có cách nào để ngăn điều này xảy ra. System-call khi xử lý file là một ví dụ điển hình của một system-call không thể xử lý bất đồng bộ.

Hình 6:

Hình 6

Trong hình 6, Goroutine-1 tạo một synchronous system call dẫn đến nó sẽ bị block trên M1

Hình 7:

Hình 7

Trong hình 7, Go Scheduler có thể xác định được Goroutine-1 gây ra block trên M. Lúc này, Go Scheduler sẽ tách M1 khỏi P kèm theo Goroutine-1 đi với nó. Sau đó, Go Scheduler tạo ra M2 để phục vụ cho P. Lúc này, Goroutine-2 có thể sẽ được lựa chọn từ LRQ và được context-switch trên M2. Nếu một M đã tồn tại từ trước, quá trình chuyển đổi này sẽ diễn ra nhanh hơn so với việc phải tạo mới M2

Hình 8:

Hình 8

Trong hình 8, blocking system call được tạo bởi Goroutine-1 kết thúc. Lúc này, Goroutine-1 được chuyển lại cho LRQ và được xử lý lại bởi P và kịch bản xử lý system call có thể lại tái diễn một lần nữa.

view raw Go Scheduler.md hosted with ❤ by GitHub