1. Xây dựng chương trình mẫu đa tiến trình

Mục tiêu đầu tiên là tạo một ứng dụng người dùng có khả năng sinh ra nhiều tiến trình con hoạt động song song. Mỗi tiến trình con sẽ mô phỏng việc tiêu tốn tài nguyên CPU và I/O trong một khoảng thời gian xác định, thường dưới 30 giây. Tiến trình cha có nhiệm vụ ghi nhận ID của các tiến trình con và chỉ kết thúc khi tất cả tiến trình con đã hoàn thành công việc.

Dưới đây là mã nguồn tham khảo cho tệp worker_sim.c:

#include <stdio.h>
#include <unistd.h>
#include <sys/times.h>
#include <sys/wait.h>

#define CLOCK_FREQ 100
#define TOTAL_WORKERS 10

void simulate_load(int total_duration, int cpu_burst, int io_burst);

int main(int argc, char * argv[])
{
    pid_t worker_ids[TOTAL_WORKERS];
    int idx;

    for(idx = 0; idx < TOTAL_WORKERS; idx++)
    {
        worker_ids[idx] = fork();
        
        if(worker_ids[idx] == 0)
        {
            /* Tiến trình con thực thi tác vụ */
            simulate_load(20, 2 * idx, 20 - 2 * idx);
            return 0;
        }
        else if(worker_ids[idx] < 0)
        {
            printf("Không thể tạo tiến trình con thứ %d!\n", idx + 1);
            return -1;
        }
        /* Tiến trình cha tiếp tục vòng lặp */
    }

    /* In ra PID của các tiến trình con */
    for(idx = 0; idx < TOTAL_WORKERS; idx++)
        printf("Worker PID: %d\n", worker_ids[idx]);

    /* Chờ tất cả tiến trình con kết thúc */
    for(idx = 0; idx < TOTAL_WORKERS; idx++)
        wait(NULL);
        
    return 0;
}

/*
 * Hàm mô phỏng việc chiếm dụng CPU và I/O
 * total_duration: Tổng thời gian thực thi (giây)
 * cpu_burst: Thời gian liên tục占用 CPU (giây)
 * io_burst: Thời gian chờ I/O (giây)
 */
void simulate_load(int total_duration, int cpu_burst, int io_burst)
{
    struct tms start_tick, current_tick;
    clock_t user_ticks, sys_ticks;
    int elapsed_io;

    while (total_duration > 0)
    {
        /* Giai đoạn xử lý CPU */
        times(&start_tick);
        do
        {
            times(&current_tick);
            user_ticks = current_tick.tms_utime - start_tick.tms_utime;
            sys_ticks = current_tick.tms_stime - start_tick.tms_stime;
        } while (((user_ticks + sys_ticks) / CLOCK_FREQ) < cpu_burst);
        
        total_duration -= cpu_burst;
        if (total_duration <= 0) break;

        /* Giai đoạn chờ I/O */
        elapsed_io = 0;
        while (elapsed_io < io_burst)
        {
            sleep(1);
            elapsed_io++;
        }
        total_duration -= elapsed_io;
    }
}

Structure tms được định nghĩa trong nhân để lưu trữ thông tin thời gian CPU:

struct tms {
    __kernel_clock_t tms_utime;       /* Thời gian CPU ở chế độ user */
    __kernel_clock_t tms_stime;       /* Thời gian CPU ở chế độ kernel */
    __kernel_clock_t tms_cutime;      /* Thời gian CPU của con đã chết (user) */
    __kernel_clock_t tms_cstime;      /* Thời gian CPU của con đã chết (kernel) */
};

Biến clock_t là kiểu số nguyên dài. Hằng số CLOCK_FREQ (tương đương HZ) được định nghĩa là 100, nghĩa là một đơn vị thời gian (jiffy) tương ứng với 10ms. Giá trị thời gian thu được là số lượng xung nhịp, cần nhân với 10ms để ra thời gian thực.

2. Implement theo dõi quỹ đạo tiến trình trong nhân

Nhiệm vụ tiếp theo là chỉnh sửa nhân Linux 0.11 để ghi lại lịch sử chuyển trạng thái của mọi tiến trình vào tệp /var/process.log. Quá trình ghi log phải bắt đầu ngay khi hệ thống khởi động.

Các trạng thái chuyển đổi chính cần ghi nhận bao gồm: Mới tạo (New), Sẵn sàng (Ready), Đang chạy (Running), Ngủ/Chờ (Waiting) và Thoát (Exit). Các điểm chèn code thích hợp nằm trong các hàm điều phối như schedule(), các hàm ngủ sleep_on(), interruptible_sleep_on(), các lời gọi hệ thống sys_pause(), sys_waitpid() và hàm đánh thức wake_up().

Khi biên dịch lại nhân, cần đảm bảo môi trường xây dựng đúng phiên bản Linux 0.11. Nếu sử dụng sai cây thư mục nguồn, quá trình biên dịch sẽ thất bại hoặc hành vi không như mong đợi.

Kết quả ghi log sẽ có định dạng gồm 3 cột:

• ID tiến trình.
• Mã trạng thái (N, J, R, W, E).
• Thời điểm xảy ra (tính bằng tick hệ thống).

3. Phân tích thống kê từ log file

Sử dụng script thống kê (ví dụ stat_log.py) để xử lý tệp process.log. Script này cần được cấp quyền thực thi và chạy cùng đường dẫn tới file log.

Các chỉ số cần tính toán bao gồm:

• Turnaround Time: Tổng thời gian từ khi提交 đến khi hoàn thành.
• Waiting Time: Thời gian tiến trình chờ trong hàng đợi.
• CPU/I/O Burst Count: Số lần chuyển đổi giữa trạng thái xử lý và chờ.
• Throughput: Số lượng tiến trình hoàn thành trên một đơn vị thời gian.

Throughput đo lường hiệu suất xử lý của hệ thống trong một khoảng thời gian nhất định.

4. Điều chỉnh thời gian thời片 (Time Slice)

Giá trị khởi tạo của thời片 được định nghĩa trong macro INIT_TASK thuộc tệp include/linux/sched.h. Cấu trúc macro thường có dạng:

#define INIT_TASK \
    { 0, 15, 15, ... }
    /* Tương ứng: state, counter, priority */

Tham số thứ hai hoặc thứ ba (tùy phiên bản cụ thể) đại diện cho độ ưu tiên và thời片初始值. Việc thay đổi giá trị này ảnh hưởng trực tiếp đến hiệu suất hệ thống.

Trường hợp giảm thời片 xuống 5: Khi xem xét file log, tần suất chuyển trạng thái tiến trình tăng lên rõ rệt. Các tiến trình bị chuyển ngữ cảnh liên tục, dẫn đến thời gian chờ và thời gian hoàn thành trung bình tăng lên. Throughput giảm do CPU phải dành nhiều thời gian cho việc chuyển đổi ngữ cảnh thay vì thực thi tác vụ thực tế.

Trường hợp tăng thời片 lên 30: Tần suất chuyển trạng thái giảm. Số lần kích hoạt CPU và I/O ít hơn. Thời gian chờ và hoàn thành trung bình giảm, throughput tăng. Tuy nhiên, nếu thời片 quá lớn, khả năng đáp ứng của hệ thống với các tác vụ tương tác sẽ giảm sút.

Cân nhắc giữa hiệu suất CPU và tính tương tác là yếu tố then chốt khi chọn giá trị thời片. Giá trị quá nhỏ gây lãng phí tài nguyên cho việc chuyển đổi, giá trị quá lớn làm giảm trải nghiệm người dùng trong các hệ thống chia sẻ thời gian.

5. Chuyển đổi ngữ cảnh dựa trên ngăn xếp内核

Linux 0.11 mặc định sử dụng cơ chế TSS (Task State Segment) để chuyển đổi nhiệm vụ thông qua指令 phần cứng. Tuy nhiên, phương pháp này tốn nhiều chu kỳ xung nhịp. Các hệ điều hành hiện đại thường ưu tiên việc chuyển đổi dựa trên ngăn xếp (stack-based switching) để tận dụng pipeline指令 và đơn giản hóa thiết kế CPU.

Để thực hiện điều này trong Linux 0.11, cần viết lại hàm switch_to. Hàm mới sẽ thao tác trực tiếp trên PCB (Process Control Block) và ngăn xếp内核 của tiến trình hiện tại và tiến trình đích. Vì PCB và ngăn xếp内核 nằm chung trên một trang bộ nhớ 4KB, việc truy cập trở nên hiệu quả hơn.

Các bước thực hiện chính bao gồm:

• Xử lý khung ngăn xếp và thanh ghi ebp trong汇编.
• So sánh con trỏ tiến trình hiện tại và đích.
• Thực hiện chuyển đổi PCB, cập nhật con trỏ ngăn xếp trong TSS, chuyển đổi LDT và cập nhật thanh ghi lệnh PC.
• Điều chỉnh hàm fork() để đảm bảo liên kết đúng giữa ngăn xếp người dùng và ngăn xếp内核 mà không phụ thuộc vào TSS cho việc lưu ngữ cảnh.