Đã đăng vào thg 1 4, 2023 1:19 CH 8 phút đọc

905

Phần 2: Đi tìm lời giải cho những điều vẫn dang dở

Hello các bác. Ở bài trước em đã trình bày hệ thống ban đầu của em xây dựng. Nhưng nó còn bộc lộ rất nhiều vấn đề chưa giải quyết được.

Nếu các bác chưa đọc có để đọc tại đây

Nhiều vấn đề vẫn còn dang dở

Ở hệ thồng ban đầu các phần chính như giới hạn thời gian, bộ nhớ, tối ưu về thời gian chạy nhiều test case, hay vấn đề về sanbox thôi thúc em phải tìm ra lời giải cho các bài toán này cho bằng được.

Tìm lời giải ở đâu ?

Yeah. Tất nhiên là google rồi, nhưng cái quan trọng search kiểu gì 🤨.

Lúc này em nghĩ ngay đến con open source: Online Judge mà ban đầu CLB em dùng. Các bác có thể xem em nó tại đây.

Lí do em chọn nó là vì nó giữa vô vàn open source là giao diện nó đẹp 😂 tất nhiên rồi cái quan trọng trong source code của nó có câu trả lời cho những câu hỏi của em.

Giới thiệu chung

An onlinejudge system based on Python and Vue.

Đây là 1 open source của các anh pháp sư Trung Hoa.

Hỗ trợ C,C++, Java, Python2, Python.
Hỗ trợ Docker nên việc deploy ez game
Hỗ trợ các cuộc thi như ACM/OI, Real time ranking
Hỗ trợ Markdown & MathJax để trong việc viết đề bài problem.
Vân vân

Cùng đi xem nó có gì nào

Nó có 4 phần:

Frontend được code bằng VueJS.
Backend Django chủ yếu dùng để quản lý contest, problem tương tác với database.
Judge Server thằng này wrapper Judger
Judger là sanbox của Online Judge nó chính là thằng giới hạn các tài nguyên của bài code.

Luồng: Client gửi request kèm data cần thiết -> Backend get thông tin giới hạn tài nguyên và request sang JudgeServer -> JudgeServer gọi Judger ra chạy code -> Chạy thành công hay lỗi thì phản hồi lại Backend -> Backend xử lý rồi gửi lại frontend.

Đáp án thì chỉ có một

Bỏ qua frontend tất nhiên rồi bài này không phải phân tích giao diện.

Bỏ qua tiếp con Django vì nó chỉ chịu phần quản lý và tương tác database, có lẽ tham khảo được cách người ta thiết kế database.

Và đáp án cuối cùng là nó Judger, đây chính là con chịu trách nhiệm chạy code và giới hạn tài nguyên.

Judger sanbox của Online Judge

Con này được viết bằng C. Ký ức con trỏ lại ùa về 😥😥.

Lí do có lẽ là C là ngôn ngữ rất có hiệu quả và được ưa chuộng nhất để viết các phần mềm hệ thống.

Hình dáng nó trông ra sao ?

_judger.run(max_cpu_time=1000,
                  max_real_time=2000,
                  max_memory=128 * 1024 * 1024,
                  max_process_number=200,
                  max_output_size=10000,
                  max_stack=32 * 1024 * 1024,
                  # five args above can be _judger.UNLIMITED
                  exe_path="main",
                  input_path="1.in",
                  output_path="1.out",
                  error_path="1.out",
                  args=[],
                  # can be empty list
                  env=[],
                  log_path="judger.log",
                  # can be None
                  seccomp_rule_name="c_cpp",
                  uid=0,
                  gid=0
           )

Đây là hàm để chạy code do người dùng gửi lên.

Nhận thấy

Đầu vào là 1 file đuôi .in , đầu ra là 1 đuôi .out về cơ bản nó vẫn giống file txt mỗi tội đuôi khác thôi
max_real_time: giới hạn thời gian.
max_memory: giới hạn bộ nhớ.
max_process_number: số lượng process tối đa.
max_output_size: size tối đa của đầu ra.
exe_path: chính là cái tên file sau khi compile.
max_stack: Giới hạn bộ nhớ stack
input_path: Đường dẫn file đầu vào, tương tự output_path, error_path: đường dẫn của file output, và file ghi error.
seccomp_rule_name: chính là ngôn ngữ phải chạy.
và một số cái nữa ...

Một chút nữa

Mở file runner.c ra xem

Đập ngay vào mắt

struct timeval start, end;
gettimeofday(&start, NULL);

Ồ hàm lấy thời gian hiện tại, có vẻ sẽ dùng để tính thời gian chạy.

pid_t child_pid = fork();
if (child_pid < 0) {
    ERROR_EXIT(FORK_FAILED);
}
else if (child_pid == 0) {
   child_process(log_fp, _config);
}

Khởi tạo 1 child process có vẻ như để chạy command line để compile. Nếu khởi tạo thành công gọi hàm child_process()

Hàm child_process()

log_fp: là file log
_config: là đống config thời gian, bộ nhớ ở trên..

Xem hàm child_process() có gì nèo:

// Giới hạn bộ nhớ
if (_config->max_memory != UNLIMITED) {
    struct rlimit max_memory;
    max_memory.rlim_cur = max_memory.rlim_max = (rlim_t) (_config->max_memory) * 2;
    if (setrlimit(RLIMIT_AS, &max_memory) != 0) {
        CHILD_ERROR_EXIT(SETRLIMIT_FAILED);
    }
}

// Giới hạn time
if (_config->max_cpu_time != UNLIMITED) {
    struct rlimit max_cpu_time;
    max_cpu_time.rlim_cur = max_cpu_time.rlim_max = (rlim_t) ((_config->max_cpu_time + 1000) / 1000);
    if (setrlimit(RLIMIT_CPU, &max_cpu_time) != 0) {
        CHILD_ERROR_EXIT(SETRLIMIT_FAILED);
    }
}

// Còn mấy cái giới hạn ở dưới nữa em nghĩ demo đến đây thôi

Ồ thì ra họ dùng hàm setrlimit để giới hạn tài nguyên. Đoạn mã trên giới hạn bộ nhớ của thằng process child mới tạo.

Cho bác nào chưa biết thì setrlimit là một hàm trong hệ điều hành Linux và Unix-like, cho phép người dùng đặt giới hạn trên các tài nguyên hệ thống mà tiến trình hoặc quyền người dùng của họ có thể sử dụng. Ví dụ, người dùng có thể sử dụng hàm này để đặt giới hạn về số lượng file descriptor mà một tiến trình có thể mở, số lượng bộ nhớ mà tiến trình có thể sử dụng, hoặc thời gian tối đa mà tiến trình có thể chạy.

int setrlimit(int resource, const struct rlimit *rlim);

Đối số đầu tiên của hàm setrlimit là resource cần giới hạn các bạn có thể google để xem nó hỗ trợ những thằng resource nào nhé. Ví dụ như đoạn code trên RLIMIT_AS, RLIMIT_CPU là resource bộ nhớ, và thời gian.

Đối số thứ hai là 1 con trỏ kiểu struct rlimit -> nó dùng để giới hạn tài nguyên, các bác google để biết thêm về nó nhé.

Vậy khi mà dùng quá tài nguyên được cho phép thì nó sẽ dừng và phát ra tín hiệu ENOMEM,SIGSEGV đối với RLIMIT_AS và SIGXCPU với RLIMIT_CPU

Quay lại file runner.c

int status;
struct rusage resource_usage;
if (wait4(child_pid, &status, WSTOPPED, &resource_usage) == -1) {
    kill_pid(child_pid);
    ERROR_EXIT(WAIT_FAILED);
}

Ở đây người ta dùng hàm wait4 để chờ đợi process child kết thúc. Điểm quan trọng của hàm này là nó cho phép ta lấy thông tin tài nguyên thằng process child đã sử dụng.

Hàm wait4 là một hàm trong hệ điều hành Linux và Unix-like, cho phép một tiến trình cha đợi một tiến trình con kết thúc. Hàm này có thể được sử dụng để lấy thông tin về tiến trình con khi nó kết thúc.

Con trỏ &resource_usage (kiểu rusage) được truyền vào hàm wait4() -> đây chính là thông số tài nguyên sử dụng.

Công việc còn chỉ là check tài nguyên sử dụng > tài nguyên cho phép thì print ra lỗi tương ứng.

gettimeofday(&end, NULL);
_result->real_time = (int) (end.tv_sec * 1000 + end.tv_usec / 1000 - start.tv_sec * 1000 - start.tv_usec / 1000);

if (_result->signal != 0) {
    _result->result = RUNTIME_ERROR;
}
if (_config->max_memory != UNLIMITED && _result->memory > _config->max_memory) {
    _result->result = MEMORY_LIMIT_EXCEEDED;
}
if (_config->max_real_time != UNLIMITED && _result->real_time > _config->max_real_time) {
    _result->result = REAL_TIME_LIMIT_EXCEEDED;
}
if (_config->max_cpu_time != UNLIMITED && _result->cpu_time > _config->max_cpu_time) {
    _result->result = CPU_TIME_LIMIT_EXCEEDED;
}

Thế server python nó giao tiếp với thằng Judger viết bằng C như thế nào ?

Có vẻ họ build ra và chạy command line với các flag là các config để giao tiếp giữa 2 thằng.

Tổng kết

Mấy anh pháp sư Trung Hoa không làm em thất vọng.
À quên vẫn chưa đọc ra họ xử lý nhiều test case như thế nào có vẻ 1 test case chạy command line 1 lần :v em không chắc.
Họ hỗ trợ hơi ít ngôn ngữ, đặc biệt là JS. Thằng này nó không có hàm nhập từ bàn phím như những thằng khác. Mới đầu em định gợi ý dùng readline nhưng em thấy mấy thằng như leetcode với js nó chả cần hàm nhập nào cả =)) thế mới ảo, nhưng sau em cũng đã giải quyết được.

Kết: Đây vẫn chưa phải đáp án làm em hài lòng, căn bản em không muốn code C và em muốn làm nó đơn giản 1 xíu . Vậy là em lại tiếp tục cuộc hành trình của mình.

Liệu còn cách nào khác không ? Hẹn mọi người ở phần 3 nhé

C online-judge Python