Lịch sử hệ điều hành: từ chạy theo lô tới Linux

Phụ lục trả lời một câu hỏi mà Bài 03 để ngỏ. Vì sao giữa chương trình và phần cứng lại có một lớp trung gian là kernel, và vì sao chương trình đang chạy lại được gói thành một process? Không ai thiết kế những khái niệm đó từ đầu. Mỗi khái niệm là lời giải cho một vấn đề cụ thể, và vấn đề đầu tiên là chuyện tiền.

Trước khi có hệ điều hành: máy chờ người

Máy tính đầu tiên có hệ điều hành không? Không. Những máy tính điện tử thương mại đầu tiên xuất hiện vào thập niên 1950, đắt tới mức chỉ viện nghiên cứu, cơ quan nhà nước và công ty lớn mua nổi, và chúng không có hệ điều hành. Người dùng đăng ký một khung giờ, tự mang chương trình tới, tự nạp vào máy, chạy, lấy kết quả, rồi nhường máy cho người sau.

Chương trình thường được đưa vào máy dưới dạng thẻ đục lỗ (punched card), là những tấm thẻ giấy cứng. Mỗi thẻ thường chứa một dòng lệnh, mã hoá bằng vị trí các lỗ đục.

Cách làm này phí ở đâu? Nó phí đúng thứ đắt nhất. Trong lúc con người thao tác, tức đặt bộ thẻ, lắp cuộn băng, gạt công tắc, đọc kết quả, thì CPU không làm gì cả. Vì vậy vấn đề đầu tiên mà hệ điều hành ra đời để giải quyết là một vấn đề kinh tế. Thời gian của máy đắt hơn thời gian của người, nên phải bỏ con người ra khỏi khoảng trống giữa hai chương trình.

Chạy theo lô và chương trình giám sát

Batch processing xử lý theo lô

Gom công việc (job) của nhiều người thành một lô và cho máy chạy liên tiếp từ job này sang job khác, không cần người can thiệp giữa hai job.

Resident monitor chương trình giám sát thường trú

Một chương trình nằm thường trực trong bộ nhớ, đọc job tiếp theo, nạp và chạy nó, rồi lấy lại quyền điều khiển khi job kết thúc.

Chạy theo lô thì diễn ra thế nào? Người lập trình nộp bộ thẻ cho nhân viên vận hành. Bộ thẻ của nhiều người được xếp nối nhau, và thường được chép trước lên băng từ để máy đọc nhanh hơn. Sau đó chương trình giám sát lần lượt nạp và chạy từng job. Khi một job kết thúc, hoặc chạy quá thời gian cho phép, quyền điều khiển quay về chương trình giám sát, và nó nạp job tiếp theo.

Đây là dạng sơ khai đầu tiên của thứ Bài 03 gọi là kernel, tức một chương trình đứng giữa máy và chương trình của người dùng, quyết định chương trình nào được chạy tiếp theo.

ibm 7090 máy tính lớn

bộ thẻ một chương trình

Giới hạn: CPU vẫn chờ, người vẫn chờ

Chạy theo lô giải quyết được khoảng trống giữa hai job, nhưng để lại hai khoảng trống khác. Khoảng trống thứ nhất là mỗi lúc chỉ có một job trong bộ nhớ, nên khi job đó phải chờ băng từ hay máy in thì CPU lại ngồi không, vì mấy thiết bị cơ khí đó chậm hơn CPU nhiều bậc.

Khoảng trống thứ hai là người lập trình phải chờ. Nộp bộ thẻ xong, thường phải đợi hàng giờ, có khi tới hôm sau, mới nhận được bản in kết quả, và gõ sai một dấu phẩy nghĩa là thêm một vòng chờ nữa. Cảnh chờ ấy về sau thành chuyện để kể, và để nói quá, như ở Ảnh 2.

Đa chương trình: giữ nhiều job trong bộ nhớ cùng lúc

Khoảng trống thứ nhất được lấp bằng gì? Bằng đa chương trình (multiprogramming), tức nạp nhiều job vào bộ nhớ cùng lúc. Khi job đang chạy phải chờ thiết bị thì chương trình giám sát chuyển CPU sang một job khác đang sẵn sàng. Hình 1 so sánh hai cách. CPU vẫn chỉ chạy một job tại một thời điểm, nhưng thời gian chờ của job này được lấp bằng công việc của job khác.

  Một job trong bộ nhớ (chạy theo lô)
    CPU   AAAA........AAAA........AAAA      . = CPU chờ băng từ, máy in

  Ba job trong bộ nhớ (đa chương trình)
    CPU   AAAABBBBCCCCAAAABBBBCCCCAAAA      A phải chờ thì B chạy

Nhiều chương trình nằm chung một bộ nhớ thì có sinh chuyện không? Có, vì một job lỗi có thể ghi đè lên job khác, hoặc lên chính chương trình giám sát, và làm hỏng cả lô. Vì vậy phần cứng của các máy tính thời này dần có thêm hai cơ chế. Cơ chế thứ nhất là bảo vệ bộ nhớ, để mỗi job chỉ ghi được vào vùng của mình. Cơ chế thứ hai là chế độ đặc quyền của CPU, để chỉ chương trình giám sát mới được điều khiển thiết bị và đổi vùng bảo vệ.

Đa chương trình làm máy bận rộn, nhưng người lập trình vẫn chờ hàng giờ. Lời giải cho khoảng trống thứ hai ấy cũng chính là nơi khái niệm process thành hình.

Time-sharing: nhiều người dùng chung một máy, cùng lúc

Time-sharing chia sẻ thời gian

Cách vận hành trong đó thời gian CPU được cắt thành những lượt rất ngắn, luân phiên giữa chương trình của nhiều người dùng, nhanh tới mức mỗi người đều có cảm giác máy chỉ đang phục vụ mình.

Terminal thiết bị đầu cuối

Thiết bị chỉ dùng để gõ lệnh và nhận kết quả, nối với máy tính ở xa. Thời đó thường là một teletype: máy đánh chữ điện, in câu trả lời của máy tính ra giấy cuộn.

Time-sharing khác đa chương trình ở đâu? Khác ở lúc nào CPU được chuyển. Đa chương trình chỉ chuyển khi job đang chạy phải chờ thiết bị, nên một job tính toán dài, không bao giờ chờ, thì giữ CPU tới khi xong. Time-sharing thì chuyển theo đồng hồ. Một bộ đếm giờ phần cứng định kỳ lấy quyền điều khiển khỏi chương trình đang chạy và trả về cho hệ điều hành, nên chương trình hết lượt bị tạm dừng dù chưa xong.

Nhờ vậy không ai giữ được CPU quá lâu, và người ngồi ở terminal gõ một lệnh thì nhận câu trả lời sau vài giây, thay cho vài giờ.

  terminal 1 ──┐
  terminal 2 ──┼──►  một máy tính  ──►  CPU:  1 2 3 1 2 3 1 2 3 ...
  terminal 3 ──┘                         hết lượt thì chuyển, dù chưa xong

Một trong những hệ time-sharing đầu tiên là CTSS (Compatible Time-Sharing System) ở MIT, đầu thập niên 1960. Nó chạy trên một máy IBM 7094 đã được sửa đổi, là đời sau của chiếc 7090 ở Ảnh 1. Từ đó, ý tưởng một máy tính phục vụ nhiều người qua terminal trở thành hướng đi chính của các hệ điều hành.

Từ cắt lượt tới process

Cắt lượt đặt ra một yêu cầu mà chạy theo lô không có. Một chương trình bị dừng giữa chừng thì ở lượt sau phải chạy tiếp được đúng từ chỗ đó, như chưa từng bị dừng. Muốn vậy thì với mỗi chương trình đang chạy, hệ điều hành phải giữ lại một bộ trạng thái:

• lệnh tiếp theo cần chạy;
• các giá trị đang tính dở trong CPU;
• vùng bộ nhớ của nó;
• các file nó đang mở;
• nó thuộc người dùng nào.

Chương trình đang chạy cùng bộ trạng thái đó được gọi là process. Danh sách trên gần như trùng khớp với Hình 6 của Bài 03, các thuộc tính riêng của một process. Vậy các thuộc tính đó tồn tại vì nhiều chương trình phải chia nhau một CPU mà không giẫm lên nhau.

Multics: tham vọng lớn, và Bell Labs rút lui

Giữa thập niên 1960, ba bên cùng làm Multics, gồm MIT, Bell Labs (phòng nghiên cứu của công ty điện thoại AT&T) và hãng General Electric. Multics là một hệ time-sharing rất tham vọng, nhắm tới việc phục vụ rất nhiều người cùng lúc như một tiện ích công cộng, và tham vọng đó kéo theo độ phức tạp.

Multics kết thúc ra sao với Bell Labs? Theo hồi ký của Dennis Ritchie, một người của Bell Labs trong dự án, tới khoảng 1968-1969 Multics vẫn chưa cho ra một hệ thống dùng được như mong đợi, nên Bell Labs dần rút khỏi dự án. Vài lập trình viên của Bell Labs vì thế mất một môi trường làm việc mà họ đã quen.

Process trên server của bạn được sinh ra bằng fork() rồi execve(), và shell chỉ là một process như mọi process khác. Cả hai điều ấy bắt nguồn từ Unix, ở Bell Labs, năm 1969.

Unix (1969): một hệ thống nhỏ, xây quanh process và file

Mất Multics rồi thì họ làm gì? Ken Thompson tìm được một máy tính nhỏ loại PDP-7 ít người dùng, và bắt đầu viết trên đó một hệ thống nhỏ hơn Multics rất nhiều. Dennis Ritchie cùng làm, và Ritchie ghi năm ra đời của Unix là 1969.

Phiên bản đầu được viết bằng hợp ngữ (assembly), ngôn ngữ gần với lệnh máy và gắn chặt với một loại CPU cụ thể. Theo chính Ritchie, những thứ được dựng đầu tiên là hệ thống file và khái niệm process. Tiếp đó là một bộ công cụ nhỏ để chép, in, xoá, sửa file, và một trình thông dịch lệnh đơn giản gọi là shell.

fork() và exec()

Hai bước sinh process đã gặp ở tab Process của Bài 03: nhân bản process hiện tại thành process con, rồi process con thay chương trình của mình bằng chương trình khác. Trên Linux, bước thứ hai là syscall execve().

exit() và wait()

exit(): process tự kết thúc và để lại một mã kết thúc. wait(): process cha dừng lại chờ một process con kết thúc và nhận mã đó.

Shell chỉ là một process bình thường

Ritchie mô tả cách shell của Unix chạy một lệnh thành năm bước, và năm bước đó vẫn là cách bash chạy java -jar app.jar hôm nay. Hình 3 tóm lại theo lời Ritchie.

  1 shell đọc một dòng lệnh từ terminal
  2 shell gọi fork()        →  sinh process con, bản sao của shell
  3 process con gọi exec()  →  nạp chương trình của lệnh từ file
  4 shell gọi wait()        →  chờ process con kết thúc bằng exit()
  5 shell quay lại bước 1

Thiết kế này kéo theo hai điều. Một là shell không nằm trong kernel và không có đặc quyền gì. Nó chạy trong user space và dùng đúng những syscall mà mọi chương trình khác dùng, nên ai cũng có thể viết một shell khác mà không phải sửa kernel, và bash là một trong số đó.

Hai là mọi lệnh đều được sinh ra bằng fork() từ một process có sẵn, nên mọi process trên máy xếp thành một cây có gốc chung. Đó chính là cây ở Hình 5 của Bài 03, nơi java là con của bash.

1973: viết lại kernel bằng C

Viết bằng hợp ngữ thì Unix chỉ chạy được trên một loại máy, vậy sao nó lan ra được? Nhờ ngôn ngữ C mà Ritchie phát triển. C đủ gần phần cứng để viết hệ điều hành, nhưng không gắn với một loại CPU như hợp ngữ, và năm 1973 kernel Unix được viết lại bằng C. Ritchie gọi đó là bước ngoặt quan trọng nhất, vì từ đây hệ thống có hình hài hiện đại, và cũng là lúc Unix có đa chương trình. Về lâu dài, việc này cho tính khả chuyển: đưa Unix sang một loại máy khác chủ yếu là biên dịch lại code C, chỉ phải viết lại phần nhỏ phụ thuộc phần cứng.

Lan rộng rồi thì lại sinh chuyện gì? Unix sang tới các trường đại học và hãng máy tính, và mỗi nơi phát triển một nhánh riêng. Tới thập niên 1980 đã có nhiều bản Unix khác nhau, và một chương trình viết cho bản này chưa chắc chạy được trên bản kia.

Lời giải là một chuẩn chung tên là POSIX, bản đầu tiên công bố năm 1988. POSIX quy định giao diện mà một hệ kiểu Unix phải cung cấp, trong đó có fork(), exec, signal. Các man page ở Bài 03 vẫn ghi rõ mỗi syscall, mỗi signal thuộc phiên bản POSIX nào.

Unix giải quyết bài toán kỹ thuật, nhưng để lại một bài toán khác: ai được dùng và sửa nó. Lời giải cho bài toán ấy chính là kernel đang chạy trên server của bạn.

Vấn đề cuối thập niên 1980: Unix không tự do, máy PC thì rẻ

Unix thuộc về ai? Nó là tài sản của AT&T, và các bản Unix thương mại về sau đều đi kèm giấy phép ràng buộc việc sao chép, sửa và chia sẻ mã nguồn. Trong khi đó, máy tính cá nhân dùng chip Intel 80386 đã đủ mạnh để chạy một hệ thống kiểu Unix, nhưng không có sẵn một hệ như vậy vừa rẻ vừa được tự do sửa.

Người đầu tiên tìm cách lấp chỗ trống đó là Richard Stallman. Từ năm 1983, ông công bố dự án GNU, nhằm viết lại từ đầu một hệ thống kiểu Unix mà ai cũng được dùng, sửa và chia sẻ. Tới đầu thập niên 1990, GNU đã có trình biên dịch, shell hoàn chỉnh.

Linux (1991): mảnh còn thiếu là một kernel

Thứ GNU còn thiếu là kernel, và nó tới từ đâu? Năm 1991, Linus Torvalds, khi đó là sinh viên ở Helsinki, viết một kernel cho máy PC dùng chip 80386 và công bố mã nguồn. Ghép kernel đó với các công cụ của GNU thì được một hệ thống hoàn chỉnh. Hình 4 vẽ lại sự ghép nối đó bằng chính sơ đồ phân tầng của Bài 03.

  user space   bash · trình biên dịch · công cụ dòng lệnh   ← dự án GNU (từ 1983)
               Nginx · java · PostgreSQL                   ← chương trình của bạn
                              │  syscall
  kernel       Linux                                       ← Linus Torvalds (1991)
                              ▼
               CPU    RAM    Disk    Network

Vậy "Linux" chỉ cái gì? Theo nghĩa hẹp, Linux chỉ là kernel, đúng thứ mà Bài 03 gọi là kernel. Thứ người ta cài lên server, như Ubuntu hay Debian, là một bản phân phối (distribution), tức kernel Linux cộng rất nhiều chương trình user space đã chọn sẵn và đóng gói cùng nhau. Linux đi theo các giao diện của POSIX, nên phần lớn chương trình và khái niệm của Unix, như process, fork rồi exec, signal, PID 1, chạy trên Linux gần như nguyên vẹn.

Mỗi bước trên còn để lại dấu vết trên server hôm nay, ngay trong những lệnh bạn đã gõ ở Bài 03.

Những gì còn lại tới hôm nay

Ảnh 5 cho thấy cả hệ thống nhỏ tới mức nào, và cũng cho thấy những cái tên vẫn còn được dùng. Ngoài init và sh, nhiều dấu vết khác vẫn nằm ngay trong những lệnh bạn gõ ở Bài 03:

• Con số 9 trong kill -9 là số hiệu của SIGKILL từ các bản Unix đời đầu, được Linux giữ nguyên.
• Man page vẫn chia theo những phần đánh số của sổ tay Unix. Phần 2 là syscall, nên mới có fork(2), bind(2). Phần 7 là các trang tổng quan, nên có signal(7).
• Chữ tty trong tên thiết bị terminal của Linux nhắc lại chiếc teletype ở Ảnh 3.

Nối về bài chính

Quay lại bài giảng Bài 03.

Nguồn đọc thêm

1. Dennis M. Ritchie, The Evolution of the Unix Time-sharing System. Hồi ký kỹ thuật của chính người làm ra Unix: Multics, PDP-7, năm bước của shell, việc viết lại bằng C.
2. D. M. Ritchie, K. Thompson, The UNIX Time-Sharing System, Communications of the ACM, 1974. Bài báo đầu tiên mô tả Unix.
3. Dennis M. Ritchie, The Development of the C Language. Vì sao C ra đời, và quan hệ của nó với Unix.
4. Thông báo khởi động dự án GNU, năm 1983.
5. The Open Group Base Specifications, bản hiện hành của chuẩn POSIX.
6. fork(2), man page của syscall sinh process trên Linux, có mục ghi chuẩn và lịch sử.

Nguồn ảnh

Ảnh chụp thật đã được chuyển sang hai tông đen trắng và cắt khung cho khớp trang. Ảnh bộ thẻ và teletype được tách khỏi nền cũ. Ảnh chụp màn hình Unix bản 7 được cắt bớt nền trống, phóng to hai lần và vẽ thêm khung đánh dấu. Truyện tranh của xkcd dùng theo giấy phép phi thương mại ghi ở từng dòng, đã phóng to và chuyển sang đen trắng.

1. Ảnh 1Máy IBM 7090, NASA Ames Research Center / Emerson Shaw, Wikimedia Commons, public domain.
2. Ảnh 1Bộ thẻ đục lỗ của một chương trình, ArnoldReinhold, Wikimedia Commons, CC BY-SA 3.0.
3. Ảnh 2Old Days, Randall Munroe, xkcd.com, CC BY-NC 2.5.
4. Ảnh 3Teletype Model 33 ASR (1968), Dennis van Zuijlekom, Wikimedia Commons, CC BY-SA 2.0.
5. Ảnh 4Ken Thompson và Dennis Ritchie, không rõ tác giả, Wikimedia Commons, public domain.
6. Ảnh 5Unix bản 7 trong trình giả lập SIMH, Huihermit, Wikimedia Commons, CC0.