Tổng quan luận án

Luận án tiến sĩ "Soft Real-Time Scheduling on Multiprocessors" của tác giả UmaMaheswari C. Devi được bảo vệ năm 2006 tại Khoa Khoa học Máy tính, Đại học North Carolina tại Chapel Hill, dưới sự hướng dẫn của Giáo sư James (Jim) Anderson cùng hội đồng chấm luận án gồm các Giáo sư Sanjoy Baruah, Kevin Jeffay, Daniel Mossé, Ketan Mayer-Patel và Jasleen Kaur.

Tính cấp thiết và khoảng trống nghiên cứu

Theo phân tích của tác giả, thiết kế hệ thống thời gian thực đang chịu tác động trực tiếp từ hai xu hướng công nghệ:

  1. Sự phổ biến của các nền tảng đa bộ xử lý ghép nối chặt chẽ (tightly-coupled multiprocessors), thể hiện qua các hệ thống đa bộ xử lý đối xứng dùng chung bộ nhớ (SMP - Symmetric Shared-Memory Multiprocessors) có giá thành hợp lý và sự xuất hiện của các kiến trúc vi xử lý đa lõi (multicore).
  2. Sự gia tăng của các ứng dụng thời gian thực có khối lượng tính toán lớn vượt quá khả năng xử lý của một vi xử lý đơn lẻ nhưng chỉ yêu cầu các bảo đảm thời gian thực mềm (soft real-time), tiêu biểu như hệ thống theo dõi mục tiêu (tracking), xử lý tín hiệu số (signal processing), hệ thống đa phương tiện (multimedia), thực tế ảo và thị giác máy tính.

Khoảng trống nghiên cứu cốt lõi được tác giả xác định là: Hầu hết các công trình nghiên cứu trước đây về lập lịch đa bộ xử lý chỉ tập trung vào hệ thống thời gian thực cứng (hard real-time) — nơi mọi vi phạm hạn định (deadline miss) đều không được phép xảy ra. Để đáp ứng điều kiện khắt khe này, các thuật toán lập lịch tối ưu trên đa bộ xử lý buộc phải thực hiện thu hồi quyền thực thi (preemption) và di trú tác vụ (migration) với tần suất cao, đồng thời áp đặt các ràng buộc cấu trúc nghiêm ngặt (như chia thời gian thành các quantum đồng bộ và yêu cầu tham số tác vụ nguyên). Hệ quả là chi phí phụ trợ hệ thống (overheads) làm giảm đáng kể năng lực xử lý hữu ích. Ngược lại, các thuật toán không tối ưu nhưng thực tế hơn (như thuật toán phân vùng partitioned-EDF hay thuật toán toàn cục global-EDF) lại đòi hỏi các điều kiện kiểm tra xác thực (validation tests) quá ngặt nghèo, giới hạn tổng tải của hệ thống ở mức xấp xỉ 50% tổng năng lực tính toán $((M+1)/2)$. Đối với các hệ thống thời gian thực mềm chấp nhận được việc trễ hạn ở mức độ hữu hạn (bounded tardiness), các thuật toán và phép kiểm tra này trở nên dư thừa và gây lãng phí tài nguyên phần cứng.

Luận đề nghiên cứu (Thesis Statement)

Luận đề trung tâm của công trình được tác giả phát biểu nguyên văn như sau:

"Processor utilization can be improved on multiprocessors while providing non-trivial soft real-time guarantees for different soft real-time applications, whose preemption and migration overheads can span different ranges and whose tolerances to tardiness are different, by designing new algorithms, simplifying optimal algorithms, and developing new validation tests." (Mức độ tận dụng bộ xử lý trên hệ thống đa bộ xử lý có thể được nâng cao trong khi vẫn cung cấp các bảo đảm thời gian thực mềm có ý nghĩa cho các ứng dụng khác nhau — vốn có chi phí thu hồi và di trú biến thiên trong nhiều khoảng khác nhau và có mức dung sai trễ hạn khác nhau — bằng cách thiết kế các thuật toán mới, đơn giản hóa các thuật toán tối ưu và phát triển các phép kiểm tra xác thực mới.)

Mục tiêu nghiên cứu

Luận án thiết lập 4 mục tiêu nghiên cứu cụ thể:

  1. Xây dựng các phép kiểm tra xác thực đủ điều kiện nhằm bảo đảm trễ hạn hữu hạn cho các thuật toán lập lịch không tối ưu nhưng có tính thực tế cao (bao gồm thuật toán EDF toàn cục có thu hồi và phi thu hồi).
  2. Thiết kế và phân tích lý thuyết một thuật toán lập lịch di trú hạn chế mới (restricted-migration scheduling algorithm) nhằm dung hòa giữa mô hình không di trú và di trú tự do.
  3. Xác định các mức bảo đảm về tính kịp thời khi nới lỏng các ràng buộc cấu trúc của các thuật toán tối ưu đã biết (cụ thể là biến thể EPDF của lớp thuật toán Pfair và hỗ trợ tham số tác vụ không nguyên).
  4. Định lượng hóa các lợi ích và sự đánh đổi của các cơ chế đề xuất thông qua mô phỏng thực nghiệm có tính toán đầy đủ các chi phí phụ trợ hệ thống thực tế.

Giả thuyết và câu hỏi nghiên cứu

  1. Câu hỏi 1: Liệu thuật toán lập lịch sớm nhất đến hạn trước toàn cục (g-EDF) ở cả hai biến thể có thu hồi (preemptive) và phi thu hồi (non-preemptive) có thể bảo đảm trễ hạn hữu hạn cho mọi hệ thống tác vụ tái diễn mà không cần áp đặt bất kỳ ràng buộc nào lên tải công việc, ngoại trừ điều kiện tổng tải không vượt quá dung lượng xử lý sẵn có $(U_{sum} \le M)$ hay không?
  2. Câu hỏi 2: Có thể xây dựng một thuật toán trung gian hạn chế di trú chỉ tại ranh giới công việc (job boundaries) để vừa tránh chi phí mất liên kết bộ nhớ đệm (cache affinity loss) trong khi thực thi công việc, vừa loại bỏ hiện tượng trễ vô hạn của phương pháp phân vùng thuần túy hay không?
  3. Câu hỏi 3: Khi loại bỏ các quy tắc phân giải hòa điểm (tie-breaking rules) phức tạp của thuật toán tối ưu $PD^2$ để thu được thuật toán EPDF đơn giản hơn, hoặc khi cho phép tham số chu kỳ và thời gian thực thi nhận giá trị thực không nguyên, hệ thống có thể duy trì trễ hạn hữu hạn dưới những cận tận dụng nào?

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Hệ thống tác vụ thời gian thực tái diễn (recurrent real-time task systems), bao gồm mô hình tác vụ chu kỳ (periodic), tác vụ rời rạc (sporadic) và các mô hình tổng quát hóa như tác vụ nội rời rạc (intra-sporadic - IS, generalized intra-sporadic - GIS). Các tác vụ được giả định là độc lập (không có ràng buộc đồng bộ hóa tài nguyên hay ràng buộc thứ tự ưu tiên).
  • Phạm vi không gian: Nền tảng đa bộ xử lý đồng nhất (identical multiprocessors) cấu trúc SMP dùng chung bộ nhớ, gồm $M \ge 2$ bộ xử lý giống hệt nhau, có quyền truy cập bộ nhớ đồng nhất và sở hữu các tầng bộ nhớ đệm (cache) phân cấp riêng biệt.
  • Phạm vi thời gian: Mô hình hạn định ngầm định (implicit deadlines, trong đó hạn định tương đối $D_i$ bằng chu kỳ $p_i$). Ràng buộc thời gian thuộc loại thời gian thực mềm, mục tiêu chính là đạt được trễ hạn hữu hạn (bounded tardiness) thay vì bảo đảm không trễ bất kỳ hạn định nào.

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu tiền đề

Luận án điểm lại hệ thống lý thuyết lập lịch thời gian thực từ nền tảng đơn bộ xử lý đến đa bộ xử lý:

  • Lập lịch trên đơn bộ xử lý: Liu và Layland (1973) thiết lập tính tối ưu của thuật toán Rate-Monotonic (RM) cho lớp ưu tiên tĩnh và Earliest-Deadline-First (EDF) cho lớp ưu tiên động. Dertouzos (1974) chứng minh EDF tối ưu toàn diện trên đơn vi xử lý. Mok (1983) đề xuất Least-Laxity-First (LLF) cũng đạt tính tối ưu. Lehoczky, Sha và Ding (1989) đưa ra phân tích chính xác cho RM, chỉ ra mức sử dụng trung bình đạt khoảng 88% so với cận xấu nhất $N(2^{1/N} - 1) \to \ln 2 \approx 0.693$.
  • Hiện tượng kỳ dị trên đa bộ xử lý (Multiprocessor Anomalies): Dhall và Liu (1978) phát hiện hiện tượng mang tên "Dhall’s effect", chỉ ra rằng dưới thuật toán g-EDF hoặc RM toàn cục, một hệ thống tác vụ có tổng mức sử dụng chỉ nhỉnh hơn $1.0$ vẫn có thể trượt hạn định trên hệ thống $M$ bộ xử lý nếu xuất hiện một tác vụ có thời gian thực thi lớn và chu kỳ dài đi kèm các tác vụ nhỏ có chu kỳ ngắn.
  • Phân loại thuật toán đa bộ xử lý: Luận án dựa trên khung phân loại 9 lớp thuật toán của Carpenter, Funk, Holman, Baruah và Anderson (2004), phân chia theo hai chiều: cơ chế ưu tiên (Ưu tiên tĩnh $P_s$, Ưu tiên động cấp tác vụ/cố định cấp công việc $P_{dr}$, Ưu tiên động không hạn chế $P_{du}$) và mức độ di trú (Không di trú/phân vùng $M_p$, Di trú hạn chế $M_r$, Di trú tự do $M_f$).
Mức độ di trú / Mức ưu tiên Ưu tiên tĩnh ($P_s$) Ưu tiên động hạn chế ($P_{dr}$) Ưu tiên động không hạn chế ($P_{du}$)
Di trú tự do ($M_f$) $\frac{M^2}{3M-2} \le U \le \frac{M+1}{2}$ $U = M - \alpha(M-1)$ nếu $\alpha \le \frac{1}{2}$; $U = \frac{M+1}{2}$ trường hợp khác $U = M$ (Thuật toán $PD^2$, Pfair)
Di trú hạn chế ($M_r$) $U \le \frac{M+1}{2}$ $U \ge M - \alpha(M-1)$ nếu $\alpha \le \frac{1}{2}$; $U = \frac{M+1}{2}$ trường hợp khác $U \ge M - \alpha(M-1)$ nếu $\alpha \le \frac{1}{2}$; $U = \frac{M+1}{2}$ trường hợp khác
Phân vùng tĩnh ($M_p$) $U = \frac{M+1}{2}$ $U = \frac{\beta M + 1}{\beta + 1}$ với $\beta = \lfloor \frac{1}{\alpha} \rfloor$ $U = \frac{\beta M + 1}{\beta + 1}$ với $\beta = \lfloor \frac{1}{\alpha} \rfloor$

(Ghi chú: $U$ biểu thị cận mức tận dụng khả lịch xấu nhất; $\alpha = u_{max}$ là mức tận dụng lớn nhất của một tác vụ trong hệ thống).

  • Mô hình lập lịch tỷ lệ công bằng (Pfair): Baruah, Cohen, Plaxton và Varvel (1996) đề xuất khái niệm Pfair và thuật toán PD, chứng minh đây là kỹ thuật tối ưu định kỳ trên đa bộ xử lý với $U = M$. Sau đó, Anderson và Srinivasan tối ưu hóa thành thuật toán $PD^2$. Tuy nhiên, Pfair yêu cầu phân chia thời gian thành các quantum đồng bộ và ép các tham số tác vụ thành số nguyên.
  • Các mô hình thời gian thực mềm trước đó: Luận án khảo sát hai nhóm mô hình:
    • Mô hình xác định: Mô hình tác vụ bỏ qua được (Skippable task model của Koren và Shasha), mô hình Weakly-hard (Bernat et al.), mô hình Window-constrained (West et al.), mô hình tính toán không chính xác (Imprecise computation của Liu et al.), và cơ chế máy chủ Constant-Bandwidth Server (CBS của Lipari và Baruah).
    • Mô hình xác suất và kinh tế: Mô hình bán chu kỳ (Semi-periodic), lập lịch Rate-Monotonic thống kê (SRMS của Atlas và Bestavros), lý thuyết hàng đợi thời gian thực (Real-time queueing theory của Lehoczky), và các hàm giá trị - thời gian (Time-value functions của Jensen).

Khoảng trống luận án lựa chọn giải quyết

Luận án định vị xử lý ba khoảng trống chính:

  1. Thiếu chứng minh hình thức và phương pháp phân tích toán học để xác định xem g-EDF và g-NP-EDF có bảo đảm trễ hạn hữu hạn khi tổng tải đạt mức tối đa $U_{sum} \le M$ mà không cần hy sinh năng lực xử lý hay không.
  2. Chưa có một thuật toán thuộc lớp di trú hạn chế ($M_r$) giải quyết được bài toán cân bằng giữa chi phí mất affinity bộ nhớ đệm và việc bảo đảm trễ hạn hữu hạn mà không bị tắc nghẽn bởi bài toán xếp thùng (bin-packing) của phương pháp phân vùng.
  3. Thiếu các cận phân tích cho các thuật toán Pfair giản lược (như EPDF) và thiếu giải pháp giải quyết triệt để rào cản tham số lượng tử hóa không nguyên (non-integral parameters) trong mô hình Pfair.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung khái niệm và lý thuyết phân tích

  • Mô hình tác vụ: Tập tác vụ $\tau = {\tau_1, \tau_2, \dots, \tau_N}$ gồm $N$ tác vụ sporadic độc lập. Mỗi tác vụ $\tau_i$ có thời gian thực thi trong trường hợp xấu nhất (WCET) là $e_i$, chu kỳ tối thiểu giữa hai lần kích hoạt là $p_i$, và hạn định tương đối $D_i = p_i$. Tỷ lệ tận dụng của tác vụ là $u_i = e_i / p_i$. Tác vụ được phân loại là tác vụ nặng (heavy) nếu $u_i \ge 0.5$ và tác vụ nhẹ (light) nếu $u_i < 0.5$. Tác vụ có mức sử dụng lớn nhất là $u_{max} = \max(u_i)$, và tổng mức sử dụng toàn hệ thống là $U_{sum} = \sum_{i=1}^N u_i \le M$.
  • Độ trễ hạn (Tardiness): Công việc thứ $k$ của tác vụ $\tau_i$, ký hiệu là $\tau_{i,k}$, được kích hoạt tại thời điểm $r_{i,k}$, có hạn định tuyệt đối $d_{i,k} = r_{i,k} + p_i$, và hoàn thành tại thời điểm $c_{i,k}$. Độ trễ hạn của công việc được định nghĩa là $\delta_{i,k} = \max(0, c_{i,k} - d_{i,k})$. Một hệ thống được xem là đạt bảo đảm trễ hạn hữu hạn (bounded tardiness) nếu tồn tại một hằng số $B_i < \infty$ sao cho $\delta_{i,k} \le B_i$ với mọi $k$.
  • Khung phân tích LAG: Tác giả sử dụng kỹ thuật so sánh lịch biểu thực tế $S$ với một lịch biểu lý tưởng chia sẻ bộ xử lý (Processor Sharing - PS), trong đó mỗi tác vụ nhận được tốc độ xử lý liên tục bằng đúng $u_i$. Hàm độ trễ tích lũy (LAG) của tập tác vụ $\tau$ tại thời điểm $t$ được định nghĩa: $$LAG(\tau, t) = A(\tau, 0, t) - S(\tau, 0, t)$$ Trong đó $A(\tau, 0, t)$ là tổng thời gian thực thi phân bổ cho $\tau$ trong lịch biểu lý tưởng trong khoảng $[0, t)$, và $S(\tau, 0, t)$ là thời gian thực thi thực tế mà tập tác vụ nhận được trong lịch biểu $S$. Bằng cách thiết lập quan hệ đệ quy giữa $LAG$ và trễ hạn tối đa của các công việc đang chờ, tác giả dẫn xuất cận trễ trên.

Phương pháp nghiên cứu

Luận án kết hợp chặt chẽ giữa hai phương pháp:

  1. Phương pháp diễn dịch toán học hình thức (Formal deductive proofs): Xây dựng các bổ đề cấu trúc, phân tích trạng thái tới hạn (busy intervals, lag bounds), sử dụng phương pháp phản chứng để thiết lập cận trễ hạn cho g-EDF, g-NP-EDF, EDF-fm và cận tận dụng cho EPDF.
  2. Phương pháp mô phỏng thực nghiệm quy mô lớn: Đánh giá định lượng trên không gian tham số tổng hợp mô phỏng kiến trúc SMP đa lõi với số bộ xử lý $M \in {2, 4, 8}$. Các tham số khảo sát gồm kích thước tập làm việc bộ nhớ đệm (Working Set Size - WSS $\in {4\text{KB}, 64\text{KB}, 128\text{KB}, 256\text{KB}}$), độ dài chu kỳ ($p \in [10\text{ms}, 100\text{ms}]$ và $[100\text{ms}, 500\text{ms}]$), kích thước quantum ($Q \in {1000\mu\text{s}, 5000\mu\text{s}}$), và các phân bố mức sử dụng đồng nhất (uniform) cũng như hai đỉnh (bimodal).

Mô hình hạch toán chi phí phụ trợ (Overhead Accounting)

Luận án không bỏ qua các chi phí thực tế mà tích hợp trực tiếp vào thời gian thực thi thông qua kỹ thuật làm phồng WCET (WCET inflation). Các nguồn chi phí được mô hình hóa chi tiết:

  • Chi phí chuyển đổi ngữ cảnh và lập lịch (scheduling overhead, context switch).
  • Chi phí ngắt đồng hồ hệ thống (tick-scheduling overhead).
  • Chi phí mất liên kết bộ nhớ đệm (cache affinity loss): Đo lường thời gian nạp lại dòng nhớ đệm bị mất khi công việc bị thu hồi hoặc di trú sang bộ xử lý khác, bao gồm chi phí làm mất hiệu lực dòng nhớ (cache line invalidation), nạp lại khối điều khiển tiến trình (PCB - Process Control Block) và cập nhật bảng trang bộ nhớ ảo.

Nội dung chính theo từng chương

Chương 1: Introduction

Chương này đặt nền móng toàn diện cho luận án:

  • Định nghĩa hệ thống thời gian thực, phân biệt rõ ràng giữa tính đúng đắn logic và tính đúng đắn thời gian.
  • Trình bày động lực chuyển dịch sang kiến trúc đa bộ xử lý đối xứng (SMP) và đa lõi, cùng sự gia tăng các ứng dụng thời gian thực mềm có nhu cầu tính toán cao.
  • Trình bày chi tiết mô hình tác vụ định kỳ và rời rạc, mô hình tài nguyên SMP, phương pháp hạch toán chi phí vào WCET.
  • Phân tích sâu sắc sự đánh đổi giữa tính linh hoạt của thuật toán và chi phí phụ trợ hệ thống, giới thiệu phân loại 9 lớp thuật toán lập lịch đa bộ xử lý của Carpenter et al. (Bảng 1.1) và phát biểu luận đề trung tâm.

Chương 2: Soft Real-Time Systems

Chương 2 thực hiện khảo cứu tài liệu chuyên sâu về các mô hình thời gian thực mềm:

  • Các mô hình xác định: Phân tích mô hình tác vụ bỏ qua được (Skippable Task Model), mô hình Weakly-Hard (cho phép tối đa $m$ vi phạm trong bất kỳ $k$ cửa sổ liên tiếp), mô hình Window-Constrained, mô hình Imprecise Computation (chia tác vụ thành phần bắt buộc mandatory và phần tùy chọn optional), và kỹ thuật máy chủ (Server-Based Scheduling).
  • Các mô hình xác suất: Trình bày mô hình bán chu kỳ (Semi-Periodic), lập lịch Statistical Rate-Monotonic (SRMS), Constant-Bandwidth Server (CBS) trên nền tảng xác suất, và lý thuyết hàng đợi thời gian thực (Real-Time Queueing Theory).
  • Hàm giá trị - thời gian (Time-Value Functions): Khảo sát mô hình kinh tế xác định mức độ suy giảm tiện ích khi hoàn thành trễ hạn.
  • Thực trạng lập lịch đa bộ xử lý: Khẳng định các nghiên cứu soft real-time trước đây gần như chỉ bó hẹp trên đơn bộ xử lý, thiết lập tiền đề cho các đóng góp của luận án.

Chương 3: Background on Pfair Scheduling

Chương này cung cấp nền tảng toán học của kỹ thuật lập lịch tỷ lệ công bằng Pfair:

  • Định nghĩa khái niệm quantum, việc phân rã công việc thành các subtask có độ dài một quantum, gán nhãn pseudo-release time ($r$), pseudo-deadline ($d$), cửa sổ thực thi (PF-window, IS-window), và hạn định nhóm (group deadline).
  • Trình bày chi tiết các thuật toán Pfair cơ bản: $PD$, $PD^2$, Earliest Pseudo-Deadline First (EPDF), Weight-Monotonic (WM).
  • Trình bày mô hình siêu tác vụ (supertasks) dùng trong lập lịch phân cấp và phân tích kỹ thuật dời chỗ subtask (subtask displacements) làm công cụ chứng minh.

Chương 4: Tardiness Bounds under Preemptive and Non-Preemptive Global EDF

Đây là một trong những chương đóng góp cốt lõi của luận án:

  • Tác giả đề xuất mô hình thuật toán tổng quát EDF-P-NP (EDF with Preemptive and Non-Preemptive segments), bao hàm cả g-EDF (khi độ dài đoạn phi thu hồi bằng 0) và g-NP-EDF (khi toàn bộ công việc là một đoạn phi thu hồi).
  • Thiết lập chặn trên cho hàm trễ tích lũy $LAG(\Psi, t_d, S) + B(\tau, \Psi, t_d, S)$, từ đó chứng minh bằng quy nạp toán học rằng: Mọi hệ thống tác vụ sporadic có $U_{sum} \le M$ đều đạt được trễ hạn hữu hạn dưới cả g-EDF và g-NP-EDF.
  • Dẫn xuất công thức tính cận trễ hạn khả thi với độ phức tạp tính toán đa thức; tối ưu hóa công thức cho trường hợp hệ thống 2 bộ xử lý ($M=2$) với cận trễ chính xác $e_{max} - 1$.
  • Mở rộng mô hình tác vụ cho phép chi phí thực thi biến đổi theo từng công việc (variable per-job execution costs).
  • Đánh giá thực nghiệm qua mô phỏng: So sánh 3 công thức cận trễ lý thuyết với trễ hạn ghi nhận thực tế, chứng minh khoảng cách trễ thực tế nhỏ hơn rất nhiều so với cận lý thuyết chặn trên.

Chương 5: EDF-fm: A Restricted-Migration Algorithm for Soft Real-Time Systems

Chương này trình bày thuật toán mới EDF-fm thuộc lớp di trú hạn chế ($M_r$):

  • Nguyên lý thiết kế: Tác vụ được phân thành hai nhóm: tác vụ cố định (fixed tasks - chỉ thực thi trên một bộ xử lý duy nhất) và tác vụ di trú (migrating tasks - di trú giữa các bộ xử lý tại ranh giới công việc). Mỗi bộ xử lý được liên kết với tối đa 2 tác vụ di trú, và trên toàn hệ thống có tối đa $M-1$ tác vụ di trú.
  • Thuật toán Assign-Tasks: Phân bổ các tác vụ vào bộ xử lý trong pha tĩnh ngoại tuyến. Sử dụng lịch biểu Pfair bù (complementary Pfair schedule) để phân phối đều đặn các công việc của tác vụ di trú đến các bộ xử lý liên kết trong pha thực thi trực tuyến.
  • Chứng minh cận trễ hạn: Dẫn xuất cận trễ hạn xác định cho cả tác vụ cố định và tác vụ di trú.
  • Kỹ thuật giảm trễ và heuristics: Đề xuất và đánh giá các chiến lược gán tác vụ: HUF (Highest Utilization First), LUF (Lowest Utilization First), LEF (Lowest Execution cost First). Mở rộng thuật toán để xử lý các tác vụ nặng ($u_i \ge 0.5$).
  • Kết quả mô phỏng cho thấy LEF đem lại cận trễ hạn nhỏ nhất, và công thức ước lượng tuyến tính có tốc độ tính toán nhanh trong khi vẫn duy trì độ chính xác cao.

Chương 6: A Schedulable Utilization Bound for EPDF

Chương 6 phân tích thuật toán EPDF — biến thể đơn giản hóa của Pfair khi loại bỏ toàn bộ các quy tắc hòa điểm phức tạp của $PD^2$:

  • Thiết lập động lực: Giảm chi phí tính toán lựa chọn ưu tiên tại mỗi đầu quantum.
  • Dẫn xuất cận mức tận dụng khả lịch (schedulable utilization bound) cho EPDF trên $M$ bộ xử lý: Chứng minh qua Bổ đề 6.1 và Bổ đề 6.2 rằng EPDF bảo đảm không trượt hạn định (zero tardiness) nếu tổng mức sử dụng thỏa mãn một cận hàm phụ thuộc vào trọng số tác vụ lớn nhất $W_{max}$.
  • So sánh định lượng cận này với partitioned-EDF và global fp-EDF, chỉ ra vùng không gian tham số mà EPDF bảo đảm tính khả lịch cứng.

Chương 7: Improved Conditions for Bounded Tardiness under EPDF

Tiếp tục phát triển Chương 6, chương này nghiên cứu EPDF dưới góc độ thời gian thực mềm (cho phép trễ hạn):

  • Phân loại subtask thành Miss Initiator (MI - subtask đầu tiên trượt hạn định) và Successor of Miss Initiator (SMI).
  • Phân nhóm chi tiết các tác vụ hoạt động (active tasks), tính toán độ trễ (task lags) theo từng lớp và phân lớp.
  • Thiết lập phản ví dụ chứng minh trễ hạn dưới EPDF có thể vượt quá 1 quantum và thậm chí vượt quá 3 quantum trên hệ thống nhiều bộ xử lý.
  • Chứng minh điều kiện đủ trên tổng mức tận dụng hệ thống để bảo đảm trễ hạn hữu hạn, mở rộng phạm vi ứng dụng của EPDF lên mức tải cao hơn nhiều so với cận khả lịch cứng ở Chương 6.

Chương 8: Pfair Scheduling with Non-Integral Task Parameters

Chương này tháo gỡ một trong những hạn chế thực tiễn lớn nhất của dòng thuật toán Pfair:

  • Giải quyết bài toán chu kỳ không nguyên (non-integral periods) và thời gian thực thi không nguyên (non-integral execution costs) mà không cần làm tròn lên (round-up) gây lãng phí quantum.
  • Đề xuất kỹ thuật dịch chuyển biên cửa sổ và điều chỉnh trọng số ảo để duy trì các bảo đảm tính công bằng.
  • Mở rộng phân tích sang các thuật toán nền tảng EDF khi thực thi trong môi trường lượng tử hóa thời gian (tick-scheduling).

Chương 9: Performance Evaluation of Scheduling Algorithms

Chương thực nghiệm tổng hợp, so sánh toàn diện các thuật toán dưới điều kiện có chi phí phụ trợ thực tế:

  • Xây dựng mô hình tính toán chi phí chi tiết dựa trên dữ liệu đo lường thực tế từ nền tảng kiểm thử LITMUS$^{RT}$ (LInux Testbed for MUltiprocessor Scheduling in Real-Time Systems).
  • Thực hiện hàng nghìn lượt mô phỏng trên các kịch bản: $M \in {2, 4, 8}$, WSS từ 4KB đến 256KB, chu kỳ ngắn (10-100ms) và dài (100-500ms), quantum $1000\mu\text{s}$ và $5000\mu\text{s}$.
  • Kết quả cho thấy:
    • Khi kích thước tập làm việc nhỏ (WSS = 4KB), g-EDF và g-NP-EDF đạt tỷ lệ khả lịch soft real-time vượt trội do chi phí mất cache affinity không đáng kể.
    • Khi WSS lớn (128KB - 256KB), chi phí di trú tăng vọt làm hiệu năng g-EDF suy giảm; lúc này EDF-fm phát huy ưu thế rõ rệt nhờ việc cô lập việc di trú vào số ít tác vụ.
    • Các thuật toán Pfair/EPDF duy trì trễ hạn rất nhỏ nhưng bị phạt nặng bởi chi phí tick-scheduling tại mỗi quantum, trừ khi chu kỳ tác vụ rất dài hoặc quantum lớn.

Chương 10: Conclusions and Future Work

  • Tổng kết toàn bộ các kết quả lý thuyết và thực nghiệm của luận án.
  • Phân tích đối chiếu với các công trình liên quan xuất hiện cùng thời điểm.
  • Đề xuất các hướng phát triển nghiên cứu tiếp theo về mặt lý thuyết và hiện thực hóa trên hệ điều hành nhân Linux.

Các phụ lục (Appendices A, B, C)

  • Phụ lục A: Cung cấp toàn văn các chứng minh toán học chi tiết của Bổ đề 4.1, 4.2 và kỹ thuật loại bỏ giả định trong Chương 4.
  • Phụ lục B: Dẫn xuất một phép kiểm tra khả lịch mới cho thuật toán Global Preemptive EDF.
  • Phụ lục C: Trình bày chi tiết các chứng minh phụ trợ còn lại của Chương 6 cho thuật toán EPDF.

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận

  1. Phá vỡ rào cản mức tận dụng 50% của Global EDF: Luận án lần đầu tiên chứng minh về mặt toán học rằng cả g-EDF và g-NP-EDF đều bảo đảm trễ hạn hữu hạn cho mọi tập tác vụ sporadic có hạn định ngầm định, miễn là tổng mức tận dụng không vượt quá năng lực xử lý ($U_{sum} \le M$), mà không cần bất kỳ ràng buộc nào lên mức tận dụng của từng tác vụ riêng lẻ ($u_{max}$). Điều này chính thức khẳng định hiện tượng Dhall không gây ra trễ hạn vô hạn trong môi trường thời gian thực mềm.
  2. Khung lý thuyết phân tích trễ hạn bằng hàm LAG: Thiết lập phương pháp luận tổng quát hóa phân tích độ trễ tích lũy ($LAG$) áp dụng cho mô hình EDF-P-NP, tạo tiền đề phân tích trễ hạn cho nhiều lớp thuật toán lập lịch toàn cục khác.
  3. Phát triển thuật toán lập lịch di trú hạn chế EDF-fm: Đề xuất một cấu trúc lập lịch lai hai cấp độc lập, kết hợp tính tối ưu cục bộ của EDF phân vùng với cơ chế phân phối công việc dựa trên lịch biểu Pfair bù, chứng minh được cận trễ hạn xác định cho lớp thuật toán $M_r$.
  4. Mở rộng lý thuyết Pfair cho hệ thống mềm và tham số thực: Thiết lập cận mức tận dụng khả lịch và cận trễ hạn cho biến thể EPDF, đồng thời giải quyết thành công bài toán lập lịch Pfair với các tham số thời gian và chu kỳ không nguyên.

Đóng góp về mặt thực tiễn và kiến nghị

  1. Bộ công cụ kiểm tra xác thực (Validation Tests) hiệu năng cao: Dẫn xuất các công thức tính cận trễ hạn có độ phức tạp tính toán đa thức và tuyến tính $O(N)$, cho phép tích hợp trực tiếp vào các bộ kiểm soát thu nhận trực tuyến (online admission control) của hệ điều hành nhúng đa lõi.
  2. Nguyên tắc lựa chọn thuật toán theo kiến trúc phần cứng:
    • Sử dụng g-EDF cho các ứng dụng có tập làm việc bộ nhớ đệm nhỏ (WSS $\le 16\text{KB}$) hoặc chu kỳ tác vụ tương đối dài, nơi chi phí mất cache affinity không lấn át lợi thế cân bằng tải tự nhiên.
    • Sử dụng EDF-fm khi ứng dụng có dấu chân bộ nhớ đệm trung bình và lớn (WSS $\ge 64\text{KB}$), giúp triệt tiêu chi phí di trú giữa chừng của công việc và hạn chế tối đa số lượng tác vụ phải di chuyển qua lại giữa các lõi.
    • Sử dụng EPDF / Pfair khi ứng dụng đòi hỏi dung sai trễ hạn cực kỳ nhỏ (chỉ vài quantum) và có tỷ lệ hoàn thành đúng hạn rất ngặt nghèo.
  3. Mô hình đánh giá có hạch toán chi phí: Đưa ra phương pháp luận thực nghiệm chuẩn mực cho cộng đồng nghiên cứu hệ thống thời gian thực, buộc các đánh giá thuật toán phải tính toán toàn diện chi phí vô hiệu hóa dòng đệm, tải PCB và phụ trợ lập lịch thay vì chỉ dựa trên các mô hình lý thuyết phi thực tế.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế được văn bản đề cập

  • Giả định tác vụ độc lập: Luận án giới hạn phạm vi nghiên cứu ở các tác vụ hoàn toàn độc lập, chưa xét đến các ràng buộc phụ thuộc dữ liệu (precedence constraints), giao tiếp liên tác vụ, hoặc khóa tài nguyên chia sẻ đồng thời (mutual exclusion locks / semaphores).
  • Mô hình phần cứng đồng nhất: Toàn bộ phân tích lý thuyết và mô phỏng đều dựa trên giả định các bộ xử lý là giống hệt nhau (identical multiprocessors), chưa mở rộng cho các kiến trúc không đồng nhất (uniform hoặc unrelated multiprocessors) hoặc kiến trúc bất đối xứng đa lõi (heterogeneous multicore).
  • Ràng buộc hạn định ngầm định: Các kết quả chứng minh trễ hạn chính yếu được xây dựng trên mô hình hạn định bằng chu kỳ ($D_i = p_i$), chưa bao quát toàn diện cho mô hình hạn định tùy ý ($D_i > p_i$) hoặc hạn định thu hẹp ($D_i < p_i$).

Hướng nghiên cứu tiếp

  • Mở rộng khung phân tích LAG để tính toán cận trễ hạn cho hệ thống có chia sẻ tài nguyên và đồng bộ hóa (resource sharing protocols trên đa bộ xử lý).
  • Thiết lập các cận trễ hạn chặt hơn cho g-EDF trên hệ thống có số lượng vi xử lý lớn ($M > 8$).
  • Hiện thực hóa và kiểm chứng toàn diện thuật toán EDF-fm và các cơ chế kiểm soát thu nhận trực tuyến trực tiếp trên nhân hệ điều hành thời gian thực phân tán (như nền tảng LITMUS$^{RT}$).

Giá trị tham khảo

Luận án là tài liệu học thuật có giá trị tham khảo cao đối với các nhóm đối tượng chuyên môn:

  • Nghiên cứu sinh và nhà nghiên cứu chuyên sâu về Hệ thống thời gian thực và Hệ điều hành: Cung cấp phương pháp luận chuẩn xác về kỹ thuật chứng minh trễ hạn tích lũy bằng hàm LAG ở Chương 4 và cách tiếp cận phân rã công việc Pfair ở Chương 3, 6, 7.
  • Giảng viên và học viên cao học ngành Khoa học máy tính / Kỹ thuật máy tính: Là tài liệu tham khảo mẫu mực về phân loại thuật toán lập lịch đa bộ xử lý (Chương 1) và tổng quan các mô hình thời gian thực mềm (Chương 2).
  • Kỹ sư thiết kế hệ thống nhúng đa lõi và kiến trúc sư hệ điều hành: Cung cấp thuật toán phân vùng lai EDF-fm có tính ứng dụng thực tiễn cao (Chương 5) và phương pháp hạch toán chi phí bộ nhớ đệm vào WCET (Chương 9) để tối ưu hóa hiệu năng hệ thống mà không làm sụp đổ các bảo đảm thời gian thực.

Câu hỏi thường gặp

1. Thuật toán g-EDF và g-NP-EDF có bảo đảm trễ hạn hữu hạn cho mọi tập tác vụ sporadic không?

Có. Luận án đã chứng minh về mặt toán học rằng cả g-EDF (tiền thu hồi) và g-NP-EDF (phi thu hồi) đều bảo đảm trễ hạn hữu hạn (bounded tardiness) cho bất kỳ tập tác vụ sporadic độc lập nào có hạn định ngầm định ($D_i = p_i$), với điều kiện duy nhất là tổng mức sử dụng không vượt quá số lượng bộ xử lý ($U_{sum} \le M$). Không cần áp đặt thêm bất kỳ điều kiện giới hạn nào lên mức tận dụng của từng tác vụ ($u_{max}$).

2. Thuật toán EDF-fm phân loại và lập lịch các tác vụ như thế nào?

EDF-fm phân chia tập tác vụ thành hai nhóm: tác vụ cố định (fixed tasks) và tác vụ di trú (migrating tasks). Tác vụ cố định chỉ thực thi trên một bộ xử lý duy nhất. Tác vụ di trú chỉ di chuyển giữa các bộ xử lý tại ranh giới công việc (không di trú giữa chừng khi đang chạy). Thuật toán quy định mỗi bộ xử lý được liên kết với tối đa 2 tác vụ di trú và toàn hệ thống $M$ bộ xử lý có không quá $M-1$ tác vụ di trú. Việc phân chia các công việc của tác vụ di trú tới các bộ xử lý liên kết được điều phối bằng một lịch biểu Pfair bù (complementary Pfair schedule).

3. Tại sao các thuật toán tối ưu cho hard real-time như Pfair lại bị coi là quá mức cần thiết (overkill) đối với hệ thống soft real-time?

Các thuật toán tối ưu như Pfair chia nhỏ thời gian thực thi thành các quantum đồng bộ và ép việc lập lịch diễn ra tại từng quantum. Điều này dẫn đến tần suất thu hồi và di trú tác vụ cực kỳ dày đặc, gây tổn thất lớn về liên kết bộ nhớ đệm (cache affinity loss), chi phí ngắt đồng hồ (tick-overhead) và chi phí vô hiệu hóa dòng đệm. Đối với hệ thống soft real-time chấp nhận được một mức trễ hạn hữu hạn nhất định, việc chịu các chi phí phụ trợ nặng nề này là không cần thiết và làm giảm đáng kể thông lượng công việc hữu ích.

4. Chi phí bộ nhớ đệm (cache-related overhead) được mô hình hóa và xử lý thế nào trong luận án?

Chi phí bộ nhớ đệm được tích hợp trực tiếp vào thời gian thực thi xấu nhất (WCET) của tác vụ bằng kỹ thuật làm phồng (inflation). Mô hình tính toán chi phí này dựa trên kích thước tập làm việc (Working Set Size - WSS), bao gồm: thời gian tải lại các dòng đệm bị mất khi công việc chuyển bộ xử lý hoặc bị ngắt, chi phí làm mất hiệu lực các dòng đệm bị sửa đổi (dirty lines) trong bộ nhớ đệm ghi sau (write-back cache), chi phí nạp lại khối điều khiển tiến trình (PCB) và chi phí cập nhật bảng trang bộ nhớ ảo.

5. Kết quả thực nghiệm ở Chương 9 đưa ra khuyến nghị gì về việc lựa chọn giữa g-EDF và EDF-fm?

Kết quả mô phỏng cho thấy không có thuật toán nào vượt trội tuyệt đối trong mọi tình huống. g-EDF đạt hiệu năng khả lịch soft real-time tốt nhất khi kích thước tập làm việc của tác vụ nhỏ (WSS = 4KB) hoặc chu kỳ tác vụ dài, vì chi phí mất cache affinity khi di trú tự do là không đáng kể. Ngược lại, khi kích thước tập làm việc lớn (WSS từ 64KB đến 256KB), chi phí di trú tự do của g-EDF tăng vọt làm suy giảm hiệu năng nghiêm trọng; khi đó, EDF-fm trở thành lựa chọn ưu việt hơn nhờ việc cô lập sự di trú vào số ít tác vụ và chỉ di trú tại ranh giới công việc.

Kết luận

Luận án tiến sĩ của UmaMaheswari C. Devi đã mở rộng lý thuyết lập lịch thời gian thực trên các hệ thống đa bộ xử lý đối xứng bằng việc tập trung vào các bảo đảm thời gian thực mềm. Công trình đã giải quyết thành công bài toán dung hòa giữa việc tối đa hóa mức tận dụng tài nguyên bộ xử lý và việc kiểm soát độ trễ hạn trong giới hạn hữu hạn xác định. Các đóng góp lý thuyết then chốt về cận trễ của thuật toán g-EDF/g-NP-EDF, thiết kế giải thuật hạn chế di trú EDF-fm, cùng hệ thống đánh giá thực nghiệm có tính toán chi phí phụ trợ hệ thống đã đặt nền móng quan trọng cho việc thiết kế và triển khai các hệ thống thời gian thực mềm hiệu quả trên các nền tảng tính toán đa lõi hiện đại.