Tìm hiểu về bộ lập lịch linux

Question

Tôi mới sử dụng nhân Linux và lập trình cấp thấp. Tôi muốn biết làm thế nào Linux scheduler được cho là O (1) trong thời gian phức tạp.

Tôi đã xem qua bài viết sau đó là rất nhiều thông tin nhưng tôi có một vấn đề tìm hiểu pargraph tôi đã sao chép dưới đây http://www.ibm.com/developerworks/linux/library/l-scheduler/

Công việc của scheduler rất đơn giản: chọn nhiệm vụ trên ưu tiên cao nhất để thực thi. Để làm cho quy trình này hiệu quả hơn, bitmap được sử dụng để xác định thời điểm tác vụ nằm trong danh sách ưu tiên đã cho. Vì vậy, trên hầu hết các kiến ​​trúc, hướng dẫn tìm bit đầu tiên là được sử dụng để tìm bit ưu tiên cao nhất được đặt theo một trong năm từ 32 bit (đối với 140 ưu tiên). Thời gian cần để tìm một nhiệm vụ để thực hiện không phụ thuộc vào số lượng tác vụ đang hoạt động mà thay vào đó là số lượng ưu tiên . Điều này làm cho quá trình lên lịch 2.6 một quá trình O (1) vì thời gian để lên lịch là cả cố định và xác định bất kể số lượng hoạt động là .

Tại sao 5 từ 32 bit cho 140 hàng đợi? Ai là người chỉ dẫn tìm bit đầu tiên giúp chọn một trong số 140 hàng đợi?

Answer 1

Một trường bit sử dụng một giá trị duy nhất để đại diện cho một số tiểu bang boolean, ví dụ nếu chúng ta đang sử dụng một bit số nguyên 8 thì chúng ta có thể nói rằng:

17 (decimal) = 00010001 (binary) 

đó sẽ chỉ ra rằng thứ 4 và thứ 8 giá trị boolean là đúng, trong đó tất cả các giá trị boolean khác là false. Trong tổng số 8 trạng thái boolean có thể được theo dõi vì có 8 bit.

Vì chúng tôi muốn theo dõi 140 trạng thái (1 cho mỗi hàng đợi, cho biết hàng đợi có chứa tác vụ), cần 140 bit và 140/32 = 4.375, chúng tôi cần ít nhất 5 số nguyên 32 bit để lưu trữ tất cả các trạng thái boolean.

Answer 2

Something như thế này:

int bitmap_idx = priority/BITS_PER_WORD; 
int bitmap_bit = priority%BITS_PER_WORD; 

isSet = (bitmap[bitmap_idx]&(1<<bitmap_bit)); //test 
bitmap[bitmap_idx] |= 1<<bitmap_bit;    //set 

được sử dụng để đạt được quá trình đặc biệt với mảng ưu tiên và đây là cách bitmap được sử dụng trong lịch trình mà lần lượt phụ thuộc vào prio_array Bài viết

struct bạn chỉ ra đã lỗi thời, hãy kiểm tra điều này http://www.informit.com/articles/article.aspx?p=101760&seqNum=2