Giới thiệu về Hệ điều hành

Nếu bạn đang học một môn Hệ điều hành ở bậc đại học, hẳn bạn đã có một ý niệm về việc một chương trình máy tính (computer program) làm gì khi nó chạy. Nếu không, cuốn sách này (và cả khóa học tương ứng) sẽ khá khó — vậy nên bạn có lẽ nên tạm ngưng đọc, hoặc chạy ngay ra hiệu sách gần nhất để nhanh chóng đọc qua tài liệu nền tảng cần thiết trước khi tiếp tục (cả cuốn Introduction to Computing Systems của Patt & Patel [PP03] và Computer Systems: A Programmer’s Perspective của Bryant & O’Hallaron [BOH10] đều là những cuốn sách rất hay).

Vậy điều gì xảy ra khi một chương trình chạy?

Thực ra, một chương trình đang chạy làm một việc rất đơn giản: nó excecute các lệnh (instructions). Mỗi giây, bộ xử lý (processor) thực hiện hàng triệu (ngày nay thậm chí là hàng tỷ) lần các thao tác: lấy một lệnh từ bộ nhớ, giải mã (decode) nó (nghĩa là xác định đó là lệnh nào), và excecute (excecute) nó (nghĩa là làm công việc mà lệnh yêu cầu, như cộng hai số, truy cập bộ nhớ, kiểm tra điều kiện, nhảy đến một hàm, v.v.). Khi hoàn tất một lệnh, bộ xử lý chuyển sang lệnh tiếp theo, và cứ thế, cho đến khi chương trình kết thúc ¹.

Như vậy, chúng ta vừa mô tả cơ bản của mô hình Von Neumann (Von Neumann model) trong tính toán ². Nghe có vẻ đơn giản, đúng không? Nhưng trong khóa học này, chúng ta sẽ thấy rằng trong khi một chương trình chạy, có rất nhiều thứ phức tạp khác cũng đang diễn ra, với mục tiêu chính là làm cho hệ thống trở nên dễ sử dụng.

Có một tập hợp phần mềm chịu trách nhiệm cho việc này: giúp chạy chương trình một cách thuận tiện (thậm chí cho phép bạn có vẻ như chạy nhiều chương trình cùng lúc), cho phép các chương trình chia sẻ bộ nhớ, hỗ trợ chúng tương tác với thiết bị, và nhiều thứ thú vị khác. Tập hợp phần mềm đó được gọi là hệ điều hành (Operating System, OS) ³, vì nó chịu trách nhiệm đảm bảo hệ thống hoạt động đúng, hiệu quả, và dễ sử dụng.

Cách chủ yếu mà hệ điều hành làm điều đó là thông qua một kỹ thuật chung gọi là ảo hóa (virtualization). Nói cách khác, OS lấy một tài nguyên vật lý (chẳng hạn như bộ xử lý, bộ nhớ, hay đĩa) và biến nó thành một dạng “ảo” tổng quát hơn, mạnh mẽ hơn và dễ dùng hơn. Chính vì thế, đôi khi chúng ta gọi hệ điều hành là một máy ảo (virtual machine).

Tất nhiên, để cho phép người dùng ra lệnh cho hệ điều hành (và nhờ đó sử dụng các tính năng của máy ảo — như chạy một chương trình, cấp phát bộ nhớ, hay truy cập tệp), OS cung cấp một số interface (API) mà bạn có thể gọi. Một hệ điều hành điển hình thực sự cung cấp vài trăm system call (lời gọi hệ thống) sẵn sàng cho ứng dụng sử dụng. Vì OS cung cấp các call này để chạy chương trình, truy cập bộ nhớ và thiết bị, và các thao tác liên quan khác, nên đôi khi ta cũng nói rằng OS cung cấp một thư viện chuẩn (standard library) cho ứng dụng.

Cuối cùng, vì ảo hóa cho phép nhiều chương trình chạy (chia sẻ CPU), nhiều chương trình đồng thời truy cập lệnh và dữ liệu riêng (chia sẻ bộ nhớ), và nhiều chương trình truy cập thiết bị (chia sẻ đĩa, v.v.), nên OS đôi khi còn được gọi là một bộ quản lý tài nguyên (resource manager). CPU, bộ nhớ, và đĩa đều là tài nguyên của hệ thống; do đó vai trò của OS là quản lý những tài nguyên đó — một cách hiệu quả, công bằng, hay theo nhiều mục tiêu khác nhau. Để hiểu rõ hơn về vai trò của OS, hãy cùng xem qua một vài ví dụ.

Trọng tâm của vấn đề: Làm thế nào để ảo hóa tài nguyên?

Một câu hỏi trung tâm mà chúng ta sẽ trả lời trong cuốn sách này khá đơn giản: Hệ điều hành ảo hóa tài nguyên như thế nào? Đây chính là cốt lõi của vấn đề.

Tại sao OS làm điều này không phải là câu hỏi chính, vì câu trả lời khá hiển nhiên: nó khiến hệ thống dễ sử dụng hơn. Do đó, chúng ta tập trung vào câu hỏi làm thế nào: những cơ chế (mechanisms) và chính sách (policies) nào được OS triển khai để đạt được ảo hóa? OS làm việc này hiệu quả ra sao? Cần hỗ trợ phần cứng gì?

Chúng ta sẽ sử dụng các ô đánh dấu như thế này để chỉ ra những vấn đề cụ thể mà chúng ta cần giải quyết khi xây dựng một hệ điều hành. Vì vậy, trong một ghi chú về một chủ đề nhất định, bạn có thể thấy một hoặc nhiều cruces (dạng số nhiều đúng của “crux”) làm nổi bật vấn đề. Phần nội dung trong chương dĩ nhiên sẽ trình bày lời giải, hoặc ít nhất là các yếu tố cơ bản của một lời giải.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#include "common.h"

int main(int argc, char *argv[]) {
  if (argc != 2) {
    fprintf(stderr, "usage: cpu <string>\n");
    exit(1);
  }
  char *str = argv[1];
  while (1) {
    Spin(1);
    printf("%s\n", str);
  }
  return 0;
}

Figure 2.1: Simple Example: Code That Loops And Prints (cpu.c)

2.1 Ảo hóa CPU (Virtualizing the CPU)

Hình 2.1 mô tả chương trình đầu tiên của chúng ta. Nó không làm được gì nhiều. Thực tế, tất cả những gì nó làm là gọi hàm Spin(), một hàm liên tục kiểm tra thời gian và chỉ trả về sau khi đã chạy đủ một giây. Sau đó, nó in ra chuỗi ký tự mà người dùng truyền vào từ dòng lệnh, rồi lặp lại, mãi mãi.

Giả sử ta lưu tệp này dưới tên cpu.c và quyết định biên dịch rồi chạy nó trên một hệ thống chỉ có một bộ xử lý (processor hay CPU). Khi chạy, chúng ta sẽ thấy như sau:

prompt> gcc -o cpu cpu.c -Wall
prompt> ./cpu "A"
A
A
A
A
ˆC
prompt>

Kết quả chạy không có gì quá thú vị — hệ thống bắt đầu excecute chương trình, chương trình liên tục kiểm tra thời gian cho đến khi một giây trôi qua. Khi một giây đã hết, mã sẽ in ra chuỗi ký tự đầu vào mà người dùng cung cấp (trong ví dụ này là ký tự “A”), rồi tiếp tục. Lưu ý rằng chương trình sẽ chạy mãi mãi; bằng cách nhấn “Control-C” (trên các hệ thống dựa trên UNIX, thao tác này sẽ chấm dứt chương trình đang chạy ở nền trước), ta có thể dừng chương trình.

prompt> ./cpu A & ./cpu B & ./cpu C & ./cpu D &
[1] 7353
[2] 7354
[3] 7355
[4] 7356
A
B
D
C
A
B
D
C
A
...

Hình 2.2: Chạy nhiều chương trình cùng lúc

Bây giờ, hãy làm điều tương tự, nhưng lần này ta sẽ chạy nhiều phiên bản khác nhau của cùng một chương trình. Hình 2.2 cho thấy kết quả của ví dụ phức tạp hơn một chút này.

Lúc này thì thú vị hơn rồi. Dù chỉ có một bộ xử lý, nhưng bằng cách nào đó, cả bốn chương trình này dường như đang chạy cùng lúc! Vậy “phép màu” này diễn ra thế nào?

Hóa ra, hệ điều hành (operating system), với sự hỗ trợ từ phần cứng, chính là bên tạo ra ảo giác này — tức ảo giác rằng hệ thống có một số lượng rất lớn CPU ảo (virtual CPUs). Việc biến một CPU đơn lẻ (hoặc một tập nhỏ CPU) thành một số lượng CPU “vô hạn” để cho phép nhiều chương trình chạy song song chính là cái mà ta gọi là ảo hóa CPU (virtualizing the CPU). Đây là trọng tâm của phần đầu tiên trong cuốn sách này.

Tất nhiên, để chạy chương trình, dừng chương trình, và nói cho hệ điều hành biết chương trình nào cần chạy, ta cần có các interface (APIs) để giao tiếp với hệ điều hành. Chúng ta sẽ bàn về những API này xuyên suốt cuốn sách; thực ra, chúng chính là cách chính yếu mà hầu hết người dùng tương tác với hệ điều hành.

Ngoài ra, khả năng chạy đồng thời nhiều chương trình đặt ra hàng loạt câu hỏi mới. Ví dụ: nếu hai chương trình muốn chạy tại cùng một thời điểm, chương trình nào nên được ưu tiên? Câu hỏi này được trả lời bằng policy (chính sách) của hệ điều hành. Các policy được sử dụng ở nhiều nơi trong hệ điều hành để giải quyết các loại câu hỏi như vậy. Vì thế, ta sẽ nghiên cứu chúng cùng với các cơ chế cơ bản mà hệ điều hành triển khai (như khả năng chạy nhiều chương trình đồng thời). Đây chính là vai trò của hệ điều hành với tư cách là resource manager.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "common.h"

int main(int argc, char* argv[]) {
  int* p = malloc(sizeof(int));
  // a1
  assert(p != NULL);
  printf("(%d) address pointed to by p: %p\n", getpid(), p);
  // a2
  // a3
  *p = 0;
  while (1) {
    Spin(1);
    *p = *p + 1;
    printf("(%d) p: %d\n", getpid(), *p);
    // a4
  }
  return 0;
}

Hình 2.3: Một chương trình sử dụng bộ nhớ (mem.c)

2.2 Ảo hóa bộ nhớ (Virtualizing Memory)

Bây giờ, hãy xét đến bộ nhớ. Mô hình bộ nhớ vật lý (physical memory) mà các máy tính hiện đại cung cấp khá đơn giản. Bộ nhớ chỉ là một mảng các byte; để đọc dữ liệu trong bộ nhớ, ta phải chỉ định một địa chỉ (address) để truy cập dữ liệu đã lưu ở đó; để ghi (hay cập nhật) dữ liệu, ta cũng phải chỉ định dữ liệu cần ghi cùng địa chỉ đích.

Bộ nhớ được truy cập liên tục khi một chương trình đang chạy. Một chương trình lưu giữ tất cả các cấu trúc dữ liệu của nó trong bộ nhớ, và truy cập chúng thông qua nhiều lệnh khác nhau, như load, store, hoặc các lệnh khác có liên quan đến truy cập bộ nhớ. Đừng quên rằng chính các lệnh của chương trình cũng nằm trong bộ nhớ; do đó, bộ nhớ được truy cập ở mỗi lần load lệnh (instruction fetch).

Hãy cùng xem một chương trình (Hình 2.3) cấp phát một vùng bộ nhớ bằng cách gọi malloc(). Kết quả chạy chương trình có thể được thấy như sau:

prompt> ./mem
(2134) address pointed to by p: 0x200000
(2134) p: 1
(2134) p: 2
(2134) p: 3
(2134) p: 4
(2134) p: 5
ˆC
prompt> ./mem & ./mem &
[1] 24113
[2] 24114
(24113) address pointed to by p: 0x200000
(24114) address pointed to by p: 0x200000
(24113) p: 1
(24114) p: 1
(24114) p: 2
(24113) p: 2
(24113) p: 3
(24114) p: 3
(24113) p: 4
(24114) p: 4
...

Figure 2.4: Running The Memory Program Multiple Times

Chương trình thực hiện vài việc. Đầu tiên, nó cấp phát một vùng bộ nhớ (dòng a1). Sau đó, nó in ra địa chỉ của vùng nhớ vừa cấp phát (a2), rồi gán số 0 vào ô nhớ đầu tiên của vùng nhớ đó (a3). Cuối cùng, nó lặp lại: trì hoãn một giây và tăng giá trị được lưu ở địa chỉ con trỏ p. Với mỗi lần in, chương trình cũng in ra process identifier (PID – mã định danh process) của process đang chạy. Mỗi process đang chạy sẽ có một PID duy nhất.

Kết quả đầu tiên này không có gì đặc biệt. Vùng bộ nhớ mới cấp phát có địa chỉ 0x200000. Khi chương trình chạy, nó chậm rãi cập nhật giá trị và in ra kết quả.

Bây giờ, ta lại chạy nhiều phiên bản của cùng một chương trình để xem chuyện gì xảy ra (Hình 2.4). Ta thấy rằng mỗi chương trình chạy đều cấp phát bộ nhớ tại cùng một địa chỉ (0x200000), nhưng mỗi chương trình lại dường như cập nhật giá trị ở 0x200000 một cách độc lập! Như thể mỗi chương trình có một vùng bộ nhớ riêng, thay vì phải chia sẻ cùng bộ nhớ vật lý với các chương trình khác.

Thực tế, đó chính xác là điều đang xảy ra: hệ điều hành đang ảo hóa bộ nhớ (virtualizing memory). Mỗi process truy cập không gian địa chỉ ảo riêng (virtual address space) của nó (còn gọi tắt là address space), và hệ điều hành bằng cách nào đó ánh xạ (map) nó vào bộ nhớ vật lý của máy. Một tham chiếu bộ nhớ trong một chương trình sẽ không ảnh hưởng đến không gian địa chỉ của process khác (hay của chính hệ điều hành). Từ góc nhìn của chương trình đang chạy, nó như thể sở hữu toàn bộ bộ nhớ vật lý. Nhưng thực tế, bộ nhớ vật lý là một tài nguyên dùng chung, được hệ điều hành quản lý.

Chính xác hệ điều hành làm thế nào để thực hiện điều này sẽ là chủ đề của phần đầu cuốn sách, trong phạm trù ảo hóa (virtualization).

2.3 Concurrency (Tính đồng thời)

#include <stdio.h>
#include <stdlib.h>

#include "common.h"
#include "common_threads.h"

volatile int counter = 0;
int loops;

void *worker(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    counter++;
  }
  return NULL;
}

int main(int argc, char *argv[]) {
  if (argc != 2) {
    fprintf(stderr, "usage: threads <value>\n");
    exit(1);
  }
  loops = atoi(argv[1]);
  pthread_t p1, p2;
  printf("Initial value : %d\n", counter);

  Pthread_create(&p1, NULL, worker, NULL);
  Pthread_create(&p2, NULL, worker, NULL);
  Pthread_join(p1, NULL);
  Pthread_join(p2, NULL);
printf("Final value
: %d\n", counter);
return 0;
}

Figure 2.5: A Multi-threaded Program (threads.c)

Một chủ đề chính khác của cuốn sách này là concurrency (tính đồng thời). Chúng tôi dùng thuật ngữ khái niệm này để chỉ một tập hợp các vấn đề phát sinh (và cần phải được giải quyết) khi thực hiện nhiều việc cùng lúc (concurrently) trong cùng một chương trình.

Các vấn đề về concurrency xuất hiện đầu tiên ngay trong bản thân hệ điều hành. Như bạn thấy ở các ví dụ về ảo hóa ở phần trên, hệ điều hành phải “xoay sở” nhiều việc cùng một lúc: chạy một process (process), rồi chuyển sang process khác, và cứ thế tiếp tục. Hóa ra, việc này dẫn đến nhiều vấn đề sâu sắc và thú vị.

Tuy nhiên, các vấn đề về concurrency không còn giới hạn trong hệ điều hành. Thực tế, các chương trình đa luồng (multi-threaded programs) hiện đại cũng gặp chính các vấn đề tương tự. Hãy minh họa bằng một ví dụ về chương trình đa luồng (Hình 2.5).

Mặc dù lúc này bạn có thể chưa hiểu hết ví dụ (chúng ta sẽ học chi tiết hơn trong các chương sau, thuộc phần concurrency của cuốn sách), nhưng ý tưởng cơ bản khá đơn giản. Chương trình chính tạo ra hai thread (luồng) bằng cách gọi Pthread_create() ⁶. Bạn có thể hình dung thread giống như một hàm chạy trong cùng không gian bộ nhớ với các hàm khác, và có thể có nhiều thread hoạt động đồng thời. Trong ví dụ này, mỗi thread bắt đầu excecute trong một thủ tục tên là worker(), trong đó nó chỉ đơn giản tăng giá trị của một biến đếm (counter) trong vòng lặp, lặp đi lặp lại một số lần bằng với giá trị của biến loops.

Dưới đây là bản ghi kết quả khi chạy chương trình với giá trị loops = 1000. Biến loops xác định mỗi thread sẽ tăng biến đếm chung (shared counter) bao nhiêu lần trong vòng lặp. Khi chương trình chạy với loops = 1000, bạn kỳ vọng giá trị cuối cùng của counter sẽ là bao nhiêu?

prompt> gcc -o threads threads.c -Wall -pthread
prompt> ./threads 1000
Initial value : 0
Final value: 2000

Như bạn có thể đoán, khi cả hai thread kết thúc, giá trị cuối cùng của counter là 2000, vì mỗi thread đã tăng counter 1000 lần. Thật vậy, khi giá trị loops = N, ta kỳ vọng kết quả cuối cùng là 2N.

Nhưng thực tế lại không đơn giản như vậy. Hãy thử chạy lại chương trình với giá trị loops lớn hơn để xem chuyện gì xảy ra:

prompt> ./threads 100000
Initial value : 0
Final value  : 143012
prompt> ./threads 100000
Initial value : 0
Final value  : 137298

// huh??
// what the??

Trong lần chạy này, khi ta truyền vào loops = 100000, thay vì nhận được kết quả đúng là 200000, ta lại nhận giá trị 143012. Khi chạy lại, không chỉ giá trị lại sai, mà còn khác với lần trước. Thực tế, nếu chạy chương trình nhiều lần với giá trị loops lớn, đôi khi bạn có thể nhận được kết quả đúng, nhưng hầu hết là sai. Vậy tại sao lại xảy ra hiện tượng này?

Nguyên nhân nằm ở cách lệnh được excecute: từng lệnh một. Đoạn code quan trọng trong chương trình trên — chỗ tăng biến counter chia sẻ — thực ra cần đến ba lệnh:

1. Nạp giá trị counter từ bộ nhớ vào một thanh ghi.
2. Tăng giá trị đó.
3. Ghi kết quả trở lại bộ nhớ.

Vì ba lệnh này không được excecute một cách nguyên tử (atomically, tức tất cả cùng một lúc), nên có thể xảy ra xung đột, dẫn đến kết quả kỳ lạ. Chính vấn đề concurrency này sẽ được chúng ta nghiên cứu chi tiết trong phần thứ hai của cuốn sách.

THE CRUX OF THE PROBLEM: HOW TO BUILD CORRECT CONCURRENT PROGRAMS Khi có nhiều thread excecute đồng thời trong cùng một không gian bộ nhớ, làm thế nào để xây dựng một chương trình hoạt động đúng? Hệ điều hành cần cung cấp những nguyên thủy (primitives) nào? Phần cứng nên hỗ trợ những cơ chế nào? Và chúng ta có thể dùng chúng để giải quyết vấn đề concurrency ra sao?

2.4 Persistence (Tính bền vững của dữ liệu)

Chủ đề lớn thứ ba của môn học này là persistence (tính bền vững của dữ liệu). Trong bộ nhớ hệ thống, dữ liệu có thể dễ dàng bị mất, vì các thiết bị như DRAM lưu trữ dữ liệu theo cách volatile (không bền vững); khi mất điện hoặc hệ thống sập, mọi dữ liệu trong bộ nhớ đều mất. Vì vậy, ta cần cả phần cứng và phần mềm để lưu dữ liệu một cách bền vững; việc lưu trữ này là cực kỳ quan trọng, bởi người dùng luôn quan tâm sâu sắc đến dữ liệu của họ.

Về phần cứng, ta có các thiết bị I/O (input/output); trong các hệ thống hiện đại, ổ cứng (hard drive) là nơi phổ biến để lưu trữ dữ liệu lâu dài, mặc dù ổ đĩa thể rắn (SSD) ngày càng được sử dụng nhiều.

Về phần mềm, bộ phận trong hệ điều hành chịu trách nhiệm quản lý ổ đĩa được gọi là file system (hệ thống tập tin); nó có trách nhiệm lưu trữ tất cả các file mà người dùng tạo ra một cách tin cậy và hiệu quả trên ổ đĩa.

Khác với trừu tượng hóa mà hệ điều hành cung cấp cho CPU và bộ nhớ, hệ điều hành không tạo ra một đĩa riêng ảo (virtualized disk) cho mỗi ứng dụng. Thay vào đó, giả định rằng người dùng thường muốn chia sẻ thông tin trong các file. Ví dụ: khi viết một chương trình C, bạn có thể dùng một trình soạn thảo (như Emacs ⁷) để tạo và chỉnh sửa file C (emacs -nw main.c). Sau đó, bạn dùng trình biên dịch để dịch mã nguồn thành file excecute (gcc -o main main.c). Cuối cùng, bạn chạy file excecute (./main). Như vậy, bạn thấy file được chia sẻ giữa các process khác nhau: trước tiên Emacs tạo file, sau đó compiler dùng nó để tạo file excecute, và cuối cùng chương trình mới được chạy.

#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <fcntl.h>
#include <sys/types.h>

int main(int argc, char *argv[]) {
    int fd = open("/tmp/file",
                  O_WRONLY|O_CREAT|O_TRUNC,
                  S_IRWXU);
    assert(fd > -1);
    int rc = write(fd, "hello world\n", 13);
    assert(rc == 13);
    close(fd);
    return 0;
}

Hình 2.6: Một chương trình thực hiện I/O (io.c)

Để hiểu rõ hơn, hãy xem đoạn code trên. Chương trình này tạo một file (/tmp/file) và ghi vào đó chuỗi "hello world". Để thực hiện, chương trình gọi ba system call (lời gọi hệ thống):

• open() để mở và tạo file.
• write() để ghi dữ liệu vào file.
• close() để đóng file, báo rằng chương trình sẽ không ghi thêm nữa.

Các system call này được chuyển đến file system trong hệ điều hành, nơi tiếp nhận yêu cầu, xử lý, và trả về mã lỗi (nếu có).

Bạn có thể thắc mắc: hệ điều hành thật sự làm gì để ghi dữ liệu xuống đĩa? Câu trả lời khá phức tạp: file system phải xác định dữ liệu mới sẽ nằm ở đâu trên đĩa, và duy trì thông tin này trong các cấu trúc dữ liệu nội bộ. Điều đó đòi hỏi hệ điều hành phải gửi các yêu cầu I/O đến thiết bị lưu trữ bên dưới, để đọc hoặc cập nhật các cấu trúc này. Bất kỳ ai từng viết device driver (trình điều khiển thiết bị) đều biết rằng việc điều khiển một thiết bị là quá trình phức tạp, đòi hỏi hiểu biết sâu sắc về interface cấp thấp và ngữ nghĩa chính xác của nó. May mắn thay, hệ điều hành cung cấp một interface chuẩn và đơn giản thông qua system call. Vì vậy, đôi khi hệ điều hành có thể được xem như một “thư viện chuẩn” để truy cập phần cứng.

Tất nhiên, còn rất nhiều chi tiết khác trong việc truy cập thiết bị và cách file system quản lý dữ liệu bền vững. Vì lý do hiệu năng, hầu hết file system đều trì hoãn việc ghi (delayed writes), nhằm gom nhiều ghi nhỏ thành các ghi lớn. Để xử lý vấn đề hệ thống sập trong lúc ghi, nhiều file system sử dụng các giao thức ghi tinh vi, như journaling hoặc copy-on-write, nhằm đảm bảo nếu có sự cố trong chuỗi ghi, hệ thống vẫn có thể phục hồi về trạng thái hợp lý. Ngoài ra, để tối ưu các thao tác phổ biến, file system áp dụng nhiều cấu trúc dữ liệu khác nhau, từ danh sách đơn giản cho đến B-trees phức tạp.

Nếu lúc này bạn chưa hiểu hết, điều đó hoàn toàn bình thường! Chúng ta sẽ bàn kỹ hơn về tất cả những điều này trong phần ba của cuốn sách về persistence, nơi ta sẽ học về thiết bị, I/O nói chung, rồi đến đĩa, RAID, và file system chi tiết hơn.

THE CRUX OF THE PROBLEM: HOW TO STORE DATA PERSISTENTLY File system là bộ phận trong hệ điều hành chịu trách nhiệm quản lý dữ liệu bền vững. Những kỹ thuật nào cần có để thực hiện đúng? Cơ chế và policy nào cần để đạt hiệu năng cao? Làm sao để đảm bảo độ tin cậy khi phần cứng hoặc phần mềm gặp sự cố?

2.5 Mục tiêu thiết kế

Giờ thì bạn đã có một ý niệm về việc một hệ điều hành thực sự làm gì: nó lấy các tài nguyên vật lý như CPU, bộ nhớ (memory), hoặc đĩa (disk), và “ảo hóa” chúng. Nó xử lý những vấn đề phức tạp và khó khăn liên quan đến đồng thời (concurrency). Và nó lưu trữ tệp (file) một cách bền vững, giúp dữ liệu an toàn lâu dài.

Khi xây dựng một hệ thống như vậy, chúng ta cần có những mục tiêu để định hướng thiết kế và triển khai, đồng thời biết cách cân nhắc giữa các sự đánh đổi (trade-offs); việc tìm ra tập hợp đánh đổi hợp lý chính là chìa khóa để xây dựng hệ thống.

Một trong những mục tiêu cơ bản nhất là xây dựng các trừu tượng (abstraction) nhằm giúp hệ thống thuận tiện và dễ sử dụng. Trừu tượng là nền tảng cho mọi thứ trong khoa học máy tính. Nhờ trừu tượng, ta có thể viết một chương trình lớn bằng cách chia nó thành các phần nhỏ và dễ hiểu; viết chương trình bằng ngôn ngữ bậc cao như C ⁸ mà không cần quan tâm đến assembly; viết code assembly mà không cần nghĩ về cổng logic; và xây dựng một bộ xử lý từ các cổng logic mà không cần bận tâm nhiều đến transistor.

Trừu tượng quan trọng đến mức đôi khi ta quên mất giá trị của nó, nhưng ở đây thì không; trong từng phần, chúng ta sẽ thảo luận về các trừu tượng lớn đã hình thành theo thời gian, từ đó giúp bạn có cách nhìn rõ hơn về từng thành phần của hệ điều hành.

Một mục tiêu khác trong thiết kế và triển khai hệ điều hành là cung cấp hiệu năng cao (high performance); nói cách khác, mục tiêu là giảm thiểu chi phí phụ trội (overheads) do OS gây ra. Việc ảo hóa và làm cho hệ thống dễ sử dụng là xứng đáng, nhưng không thể bằng mọi giá; do đó, ta phải cố gắng cung cấp ảo hóa và các tính năng khác của OS mà không tạo ra chi phí phụ trội quá lớn. Các chi phí này có thể xuất hiện dưới nhiều dạng: thời gian bổ sung (thêm lệnh) hoặc không gian bổ sung (trong bộ nhớ hoặc trên đĩa). Ta sẽ tìm cách tối thiểu hóa một trong hai hoặc cả hai, nếu có thể. Tuy nhiên, sự hoàn hảo không phải lúc nào cũng đạt được – điều này ta sẽ dần học cách nhận ra và (khi phù hợp) chấp nhận.

Một mục tiêu khác nữa là cung cấp cơ chế bảo vệ (protection) giữa các ứng dụng (application), cũng như giữa ứng dụng và hệ điều hành. Bởi vì ta muốn nhiều chương trình chạy cùng lúc, cần đảm bảo rằng hành vi sai trái (dù cố ý hay vô tình) của một chương trình không gây hại cho chương trình khác; đặc biệt là một ứng dụng không được phép làm hỏng hệ điều hành, vì điều đó sẽ ảnh hưởng đến tất cả chương trình đang chạy.

Bảo vệ chính là trung tâm của một nguyên lý cốt lõi trong hệ điều hành: cách ly (isolation). Cách ly các process (process) với nhau là chìa khóa cho bảo vệ, và là nền tảng cho phần lớn những gì OS phải thực hiện.

Hệ điều hành cũng phải hoạt động liên tục; khi nó hỏng, mọi ứng dụng đang chạy cũng ngừng theo. Do sự phụ thuộc này, hệ điều hành thường hướng tới việc cung cấp độ tin cậy cao (high reliability).

Khi hệ điều hành ngày càng phức tạp (đôi khi chứa hàng triệu dòng code), việc xây dựng một OS đáng tin cậy trở thành một thách thức lớn – và thực tế, nhiều nghiên cứu hiện nay (bao gồm cả công trình của chúng tôi [BS+09, SS+10]) tập trung chính vào vấn đề này.

Ngoài ra còn có các mục tiêu khác: hiệu quả năng lượng (energy-efficiency) quan trọng trong một thế giới ngày càng chú trọng “xanh”; bảo mật (security – mở rộng từ bảo vệ) chống lại các ứng dụng độc hại đặc biệt quan trọng trong thời đại kết nối mạng cao; tính di động (mobility) ngày càng cần thiết khi OS được triển khai trên các thiết bị nhỏ hơn và nhỏ hơn nữa. Tùy thuộc vào cách hệ thống được sử dụng, OS sẽ có mục tiêu khác nhau, và do đó thường được triển khai theo những cách khác nhau (dù chỉ khác một chút). Tuy nhiên, như ta sẽ thấy, nhiều nguyên lý xây dựng OS sẽ hữu ích cho nhiều loại thiết bị khác nhau.

2.6 Một chút lịch sử

Trước khi kết thúc phần giới thiệu này, chúng ta hãy điểm qua một chút lịch sử về sự phát triển của hệ điều hành. Giống như bất kỳ hệ thống nào do con người tạo ra, các ý tưởng hay dần dần được tích lũy trong OS theo thời gian, khi kỹ sư học được điều gì quan trọng trong thiết kế. Ở đây, ta sẽ thảo luận một vài bước phát triển lớn. Nếu muốn tìm hiểu sâu hơn, hãy xem cuốn lịch sử xuất sắc của Brinch Hansen về hệ điều hành [BH00].

Hệ điều hành thời kỳ đầu: Chỉ là thư viện

Ban đầu, hệ điều hành không làm được nhiều. Về cơ bản, nó chỉ là một tập thư viện các hàm thường dùng; ví dụ, thay vì để mỗi lập trình viên tự viết mã xử lý I/O cấp thấp, “OS” sẽ cung cấp API này, giúp cuộc sống của lập trình viên dễ dàng hơn.

Thông thường, trên các hệ thống mainframe cũ, chỉ có một chương trình chạy tại một thời điểm, được điều khiển bởi một toán tử (operator) là con người. Nhiều việc mà bạn nghĩ một OS hiện đại phải làm (ví dụ: quyết định thứ tự chạy job) khi đó do người vận hành quyết định. Nếu bạn là lập trình viên khôn khéo, bạn sẽ đối xử tốt với operator để được ưu tiên đưa job của mình lên đầu hàng đợi.

Mô hình tính toán này được gọi là xử lý theo lô (batch processing), khi một loạt job được thiết lập sẵn và chạy theo “lô” bởi operator. Máy tính thời đó chưa dùng theo kiểu tương tác, do chi phí: quá đắt đỏ để cho phép một người ngồi trước máy tính và sử dụng nó, vì phần lớn thời gian máy sẽ rỗi, gây tổn thất hàng trăm nghìn đô la mỗi giờ [BH00].

Vượt khỏi thư viện: Bảo vệ

Khi thoát khỏi vai trò chỉ là thư viện dịch vụ thường dùng, hệ điều hành bắt đầu đảm nhận vai trò trung tâm trong quản lý máy tính. Một khía cạnh quan trọng là nhận thức rằng code chạy thay mặt cho OS là đặc biệt: nó có quyền kiểm soát thiết bị, và vì thế phải được xử lý khác với code ứng dụng thông thường.

Tại sao vậy? Hãy tưởng tượng nếu bất kỳ ứng dụng nào cũng có thể đọc toàn bộ đĩa; khái niệm riêng tư sẽ không còn, vì bất kỳ chương trình nào cũng đọc được mọi file. Do đó, việc triển khai hệ thống file như một thư viện là không hợp lý. Thay vào đó, cần một cơ chế khác.

Vậy nên, khái niệm lời gọi hệ thống (system call) được phát minh, khởi đầu từ hệ thống Atlas [K+61, L78]. Thay vì cung cấp routine của OS như một thư viện (chỉ cần gọi hàm thủ tục), ý tưởng ở đây là thêm một cặp lệnh phần cứng đặc biệt và trạng thái phần cứng để biến việc chuyển vào OS thành một quá trình chính thức và được kiểm soát.

Điểm khác biệt chính giữa system call và procedure call là: system call chuyển quyền điều khiển (jump) vào OS đồng thời nâng mức đặc quyền phần cứng. Ứng dụng người dùng chạy trong cái gọi là chế độ người dùng (user mode), nơi phần cứng hạn chế những gì ứng dụng có thể làm; ví dụ, một ứng dụng trong user mode thường không thể trực tiếp gửi yêu cầu I/O tới đĩa, truy cập bất kỳ trang bộ nhớ vật lý nào, hoặc gửi gói tin mạng.

Khi một system call được khởi tạo (thường qua một lệnh phần cứng đặc biệt gọi là trap), phần cứng sẽ chuyển quyền điều khiển tới một trình xử lý trap (trap handler) đã được OS cài đặt từ trước, đồng thời nâng mức đặc quyền lên chế độ nhân (kernel mode). Trong kernel mode, OS có toàn quyền truy cập phần cứng hệ thống, do đó có thể thực hiện các việc như khởi tạo I/O hoặc cấp thêm bộ nhớ cho chương trình. Khi OS hoàn tất xử lý yêu cầu, nó trả quyền điều khiển về ứng dụng qua một lệnh đặc biệt gọi là return-from-trap, vừa khôi phục về user mode, vừa tiếp tục chương trình tại vị trí nó đã dừng.

Kỷ nguyên đa chương trình (Multiprogramming)

Hệ điều hành thực sự cất cánh trong kỷ nguyên máy tính mini, vượt khỏi mainframe. Những máy kinh điển như dòng PDP của Digital Equipment giúp máy tính trở nên rẻ hơn nhiều; thay vì mỗi tổ chức lớn chỉ có một mainframe, thì một nhóm nhỏ trong tổ chức cũng có thể sở hữu máy tính riêng. Không ngạc nhiên khi chi phí giảm đã dẫn tới sự bùng nổ hoạt động lập trình; nhiều người tài năng được tiếp cận máy tính và tạo ra những hệ thống thú vị và đẹp đẽ hơn.

Đặc biệt, đa chương trình (multiprogramming) trở nên phổ biến nhờ nhu cầu tận dụng tốt hơn tài nguyên máy. Thay vì chỉ chạy một job tại một thời điểm, OS sẽ load nhiều job vào bộ nhớ và chuyển đổi nhanh giữa chúng, giúp tăng hiệu quả sử dụng CPU. Điều này đặc biệt quan trọng vì thiết bị I/O rất chậm; để chương trình ngồi chờ CPU trong lúc I/O xử lý là một lãng phí. Tốt hơn hết là chuyển sang job khác và chạy nó trong khi chờ I/O.

Nhu cầu hỗ trợ multiprogramming và xử lý chồng chéo trong sự hiện diện của I/O và ngắt (interrupt) đã thúc đẩy đổi mới trong thiết kế khái niệm OS theo nhiều hướng. Các vấn đề như bảo vệ bộ nhớ (memory protection) trở nên quan trọng; ta không muốn một chương trình truy cập bộ nhớ của chương trình khác. Hiểu cách xử lý các vấn đề đồng thời (concurrency) do multiprogramming tạo ra cũng rất quan trọng; đảm bảo OS hoạt động đúng bất chấp sự có mặt của ngắt là một thách thức lớn. Những vấn đề này và các chủ đề liên quan sẽ được nghiên cứu kỹ hơn trong các chương sau.

Một trong những tiến bộ thực tiễn lớn của thời kỳ này là sự ra đời của hệ điều hành UNIX, chủ yếu nhờ công của Ken Thompson (và Dennis Ritchie) tại Bell Labs. UNIX đã kế thừa nhiều ý tưởng hay từ các OS khác (đặc biệt là Multics [O72], và một số từ hệ thống như TENEX [B+72] và Berkeley Time-Sharing System [S68]), nhưng làm cho chúng đơn giản và dễ dùng hơn. Chẳng bao lâu, nhóm này đã gửi băng chứa mã nguồn UNIX tới mọi nơi trên thế giới; nhiều người khác tham gia và bổ sung thêm cho hệ thống ⁹.

Thời đại hiện đại

Sau thời kỳ minicomputer (máy tính cỡ trung), một loại máy mới xuất hiện: rẻ hơn, nhanh hơn và dành cho số đông — đó là personal computer (PC, máy tính cá nhân) như chúng ta gọi ngày nay. Dẫn đầu bởi những dòng máy đầu tiên của Apple (ví dụ: Apple II) và IBM PC, thế hệ máy này nhanh chóng trở thành lực lượng thống trị trong ngành tính toán, vì chi phí thấp cho phép mỗi người có một máy tính trên bàn làm việc, thay vì phải chia sẻ một minicomputer cho cả nhóm.

Tuy nhiên, đối với operating system (hệ điều hành), PC lúc đầu lại là một bước lùi lớn, bởi các hệ thống ban đầu đã quên (hoặc chưa từng biết) những bài học trong kỷ nguyên minicomputer. Ví dụ, các hệ điều hành như DOS (Disk Operating System, Hệ điều hành đĩa, của Microsoft) không coi trọng việc bảo vệ bộ nhớ; do đó, một ứng dụng độc hại (hoặc chỉ là lập trình kém) có thể ghi lung tung vào toàn bộ vùng nhớ.

ASIDE: TẦM QUAN TRỌNG CỦA UNIX

Thật khó có thể nói hết tầm quan trọng của UNIX trong lịch sử hệ điều hành. Bị ảnh hưởng từ các hệ thống trước đó (đặc biệt là hệ thống Multics nổi tiếng của MIT), UNIX đã tập hợp nhiều ý tưởng xuất sắc và xây dựng nên một hệ thống vừa đơn giản vừa mạnh mẽ.

Nền tảng của UNIX do “Bell Labs” phát triển dựa trên nguyên tắc thống nhất: xây dựng các chương trình nhỏ nhưng mạnh, có thể kết hợp với nhau thành các luồng công việc (workflow) lớn hơn. Shell — nơi bạn nhập lệnh — cung cấp các công cụ cơ bản như pipes (ống dẫn) để hỗ trợ lập trình ở cấp độ meta. Nhờ vậy, ta có thể dễ dàng ghép các chương trình lại để giải quyết một nhiệm vụ lớn hơn. Ví dụ: để tìm các dòng trong tệp văn bản có chứa từ “foo”, sau đó đếm số dòng đó, bạn chỉ cần gõ:

grep foo file.txt | wc -l

Ở đây, grep dùng để lọc, còn wc (word count) dùng để đếm số dòng.

Môi trường UNIX thân thiện với lập trình viên, đồng thời cung cấp compiler (trình biên dịch) cho ngôn ngữ C mới. Điều này giúp các lập trình viên dễ dàng viết chương trình riêng và chia sẻ, làm cho UNIX trở nên cực kỳ phổ biến. Thêm vào đó, các tác giả còn phát miễn phí bản sao cho bất kỳ ai yêu cầu — một dạng open-source software (phần mềm nguồn mở) sơ khai.

Một điểm then chốt khác là mã nguồn của hệ thống có tính readability (dễ đọc) cao. Kernel (nhân hệ điều hành) nhỏ gọn, đẹp mắt, viết bằng C, khuyến khích cộng đồng tham gia bổ sung tính năng. Ví dụ, một nhóm ở Berkeley do Bill Joy dẫn đầu đã phát triển bản phân phối BSD (Berkeley Systems Distribution) với các hệ thống con tiên tiến về virtual memory (bộ nhớ ảo), file system (hệ thống tệp), và networking (mạng máy tính). Sau này, Bill Joy đồng sáng lập Sun Microsystems.

Đáng tiếc, sự phổ biến của UNIX bị chậm lại do các công ty tìm cách giành quyền sở hữu và lợi nhuận, kết quả thường thấy khi luật sư nhúng tay. Nhiều công ty tung ra biến thể riêng: SunOS (Sun Microsystems), AIX (IBM), HP-UX (HP), IRIX (SGI). Các tranh chấp pháp lý giữa AT&T/Bell Labs và những bên này đã khiến tương lai của UNIX mờ mịt, đặc biệt khi Windows xuất hiện và chiếm lĩnh phần lớn thị trường PC.

ASIDE: RỒI ĐẾN LINUX

May mắn cho UNIX, một hacker trẻ người Phần Lan tên Linus Torvalds quyết định viết phiên bản UNIX riêng, dựa trên các nguyên tắc và ý tưởng ban đầu nhưng không sao chép mã nguồn, từ đó tránh rắc rối pháp lý. Anh kêu gọi sự giúp đỡ từ khắp nơi, tận dụng bộ công cụ GNU sẵn có [G85], và không lâu sau Linux ra đời, kéo theo cả phong trào phần mềm nguồn mở hiện đại.

Khi kỷ nguyên internet bùng nổ, hầu hết các công ty (như Google, Amazon, Facebook,...) đều chọn Linux vì miễn phí và có thể tùy chỉnh. Khó mà tưởng tượng được sự thành công của họ nếu thiếu hệ thống này. Khi smartphone trở thành nền tảng phổ biến, Linux cũng chiếm chỗ đứng (qua Android), vì những lý do tương tự. Steve Jobs cũng mang môi trường NeXTStep dựa trên UNIX đến Apple, khiến UNIX phổ biến cả trên desktop (dù nhiều người dùng Apple không hề hay biết).

Nhờ vậy, UNIX vẫn sống, và ngày nay còn quan trọng hơn bao giờ hết. Nếu tin vào các vị “thần máy tính”, hãy cảm ơn họ vì kết quả tuyệt vời này.

Thế hệ đầu của Mac OS (phiên bản 9 trở về trước) sử dụng cơ chế cooperative scheduling (lập lịch hợp tác); do đó, một thread (luồng) vô tình mắc kẹt trong vòng lặp vô hạn có thể chiếm toàn bộ hệ thống, buộc phải khởi động lại. Danh sách dài những tính năng còn thiếu trong hệ này rất đau đớn, quá dài để bàn hết ở đây.

May mắn thay, sau nhiều năm chịu đựng, các đặc tính từ hệ điều hành minicomputer dần xuất hiện trên desktop. Ví dụ, Mac OS X/macOS có nhân UNIX, bao gồm toàn bộ tính năng của một hệ thống trưởng thành. Windows cũng dần tiếp thu nhiều ý tưởng lớn, bắt đầu từ Windows NT — một bước tiến vượt bậc của Microsoft.

Ngay cả điện thoại ngày nay cũng chạy hệ điều hành (như Linux) gần giống với những gì minicomputer chạy vào thập niên 1970, hơn là PC thập niên 1980 (một điều đáng mừng). Thật tuyệt khi thấy các ý tưởng hay của giai đoạn vàng son trong phát triển hệ điều hành đã được đưa vào thế giới hiện đại. Tốt hơn nữa, các ý tưởng này vẫn tiếp tục phát triển, bổ sung nhiều tính năng và làm cho hệ thống hiện đại ngày càng tốt hơn cho người dùng lẫn ứng dụng.

2.7 Tóm tắt

Chúng ta vừa có cái nhìn tổng quan về hệ điều hành. Ngày nay, hệ điều hành giúp việc sử dụng máy tính trở nên dễ dàng hơn rất nhiều, và hầu hết chúng đều chịu ảnh hưởng từ những phát triển sẽ được bàn trong cuốn sách này.

Tuy nhiên, do hạn chế về thời gian, một số phần sẽ không được đề cập. Ví dụ: hệ điều hành chứa rất nhiều mã mạng (networking code), bạn sẽ học trong môn Mạng máy tính. Tương tự, đồ họa (graphics devices) rất quan trọng, nhưng hãy để dành cho môn Đồ họa máy tính. Một số giáo trình hệ điều hành khác bàn nhiều về bảo mật (security); ở đây, chúng tôi chỉ nói đến khía cạnh hệ điều hành phải bảo vệ giữa các chương trình và cung cấp khả năng bảo vệ tệp cho người dùng, chứ không đi sâu vào an ninh hệ thống như trong môn An toàn thông tin.

Dẫu vậy, có nhiều chủ đề quan trọng sẽ được đề cập, bao gồm cơ bản về virtualization (ảo hóa CPU và bộ nhớ), concurrency (tính đồng thời), và persistence (tính bền vững của dữ liệu) thông qua thiết bị và hệ thống tệp. Đừng lo! Mặc dù còn rất nhiều điều cần học, hầu hết đều rất thú vị, và cuối chặng đường, bạn sẽ có một cách nhìn mới mẻ về cách hệ thống máy tính thật sự vận hành.

Bây giờ thì bắt đầu học thôi!

Tham khảo

[BS+09] “Tolerating File-System Mistakes with EnvyFS”
Lakshmi N. Bairavasundaram, Swaminathan Sundararaman, Andrea C. Arpaci-Dusseau, RemziH. Arpaci-Dusseau
USENIX ’09, San Diego, CA, June 2009
A fun paper about using multiple file systems at once to tolerate a mistake in any one of them.

[BH00] “The Evolution of Operating Systems”
P. Brinch Hansen
In Classic Operating Systems: From Batch Processing to Distributed Systems Springer-Verlag, New York, 2000
This essay provides an intro to a wonderful collection of papers about historically significant systems.

[B+72] “TENEX, A Paged Time Sharing System for the PDP-10”
Daniel G. Bobrow, Jerry D. Burchfiel, Daniel L. Murphy, Raymond S. Tomlinson
CACM, Volume 15, Number 3, March 1972
TENEX has much of the machinery found in modern operating systems; read more about it to see how much innovation was already in place in the early 1970’s.

[B75] “The Mythical Man-Month”
Fred Brooks
Addison-Wesley, 1975
A classic text on software engineering; well worth the read.

[BOH10] “Computer Systems: A Programmer’s Perspective”
Randal E. Bryant and David R. O’Hallaron
Addison-Wesley, 2010
Another great intro to how computer systems work. Has a little bit of overlap with this book — so if you’d like, you can skip the last few chapters of that book, or simply read them to get a different perspective on some of the same material. After all, one good way to build up your own knowledge is to hear as many other perspectives as possible, and then develop your own opinion and thoughts on the matter. You know, by thinking!

[G85] “The GNU Manifesto”
Richard Stallman, 1985
Available: https://www.gnu.org/gnu/manifesto.html
A huge part of Linux’s success was no doubt the presence of an excellent compiler, gcc, and other relevant pieces of open software, all thanks to the GNU effort headed by Richard Stallman. Stallman is quite a visionary when it comes to open source, and this manifesto lays out his thoughts as to why; well worth the read.

[K+61] “One-Level Storage System”
T. Kilburn, D.B.G. Edwards, M.J. Lanigan, F.H. Sumner
IRE Transactions on Electronic Computers, April 1962
The Atlas pioneered much of what you see in modern systems. However, this paper is not the best read. If you were to only read one, you might try the historical perspective below [L78].

[L78] “The Manchester Mark I and Atlas: A Historical Perspective”
S. H. Lavington
Communications of the ACM archive
Volume 21, Issue 1 (January 1978), pages 4-12
A nice piece of history on the early development of computer systems and the pioneering efforts of the Atlas. Of course, one could go back and read the Atlas papers themselves, but this paper provides a great overview and adds some historical perspective.

[O72] “The Multics System: An Examination of its Structure”
Elliott Organick, 1972
A great overview of Multics. So many good ideas, and yet it was an over-designed system, shooting for too much, and thus never really worked as expected. A classic example of what Fred Brooks would call the “second-system effect” [B75].

[PP03] “Introduction to Computing Systems:
From Bits and Gates to C and Beyond”
Yale N. Patt and Sanjay J. Patel
McGraw-Hill, 2003
One of our favorite intro to computing systems books. Starts at transistors and gets you all the way up to C; the early material is particularly great.

[RT74] “The UNIX Time-Sharing System”
Dennis M. Ritchie and Ken Thompson
CACM, Volume 17, Number 7, July 1974, pages 365-375
A great summary of UNIX written as it was taking over the world of computing, by the people who wrote it.

[S68] “SDS 940 Time-Sharing System”
Scientific Data Systems Inc.
TECHNICAL MANUAL, SDS 90 11168 August 1968
Available: http://goo.gl/EN0Zrn
Yes, a technical manual was the best we could find. But it is fascinating to read these old system documents, and see how much was already in place in the late 1960’s. One of the minds behind the Berkeley Time-Sharing System (which eventually became the SDS system) was Butler Lampson, who later won a Turing award for his contributions in systems.

[SS+10] “Membrane: Operating System Support for Restartable File Systems”
Swaminathan Sundararaman, Sriram Subramanian, Abhishek Rajimwale, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, Michael M. Swift
FAST ’10, San Jose, CA, February 2010
The great thing about writing your own class notes: you can advertise your own research. But this paper is actually pretty neat — when a file system hits a bug and crashes, Membrane auto-magically restarts it, all without applications or the rest of the system being affected.