Hệ điều hành

Máy tính có nhiều tài nguyên (thời gian CPU, bộ nhớ, ổ đĩa, I/O) và nhiều chương trình cạnh tranh nhau. OS chia sẻ chúng công bằng và hiệu quả để mỗi tài nguyên được sử dụng tốt và hệ thống luôn phản hồi:

• đa tác vụ — chuyển nhanh CPU giữa các tiến trình để nhiều tiến trình dường như chạy cùng lúc.
• quản lý bộ nhớ — cấp bộ nhớ cần thiết cho mỗi tiến trình; dùng phân trang ổ đĩa khi RAM hết.
• spooling và đệm — nhiệm vụ in xếp hàng trên ổ đĩa để CPU không phải chờ máy in.
• lưu trữ tạm (cache) — giữ dữ liệu ổ đĩa vừa dùng trong cache / RAM.

Giao diện người dùng ẩn đi phần cứng bên dưới các trừu tượng thân thiện: người dùng thấy cửa sổ, menu và thư mục, không phải địa chỉ hay sector. Một lần nhấp vào biểu tượng khiến hệ điều hành tìm chương trình trên đĩa, phân bổ bộ nhớ, tải lên và khởi chạy nó. Một CLI (dòng lệnh) mạnh mẽ và có thể viết script cho chuyên gia; một GUI (đồ họa) dễ học hơn. Hầu hết các hệ thống đều cung cấp cả hai.

"Mô tả hai cách mà độ phức tạp của phần cứng được ẩn khỏi người dùng." (1) Người dùng làm việc với tệp tin và thư mục theo tên, và hệ điều hành chuyển đổi chúng thành các track, sector và block của đĩa; (2) người dùng chạy một chương trình bằng một lần nhấp hoặc một lệnh, và hệ điều hành tải lên, phân bổ bộ nhớ và lập lịch cho nó mà không cần người dùng biết bất kỳ địa chỉ nào; (3) trình điều khiển thiết bị cho phép người dùng in hoặc lưu trữ mà không cần biết máy in hay đĩa được kiểm soát như thế nào; (4) một giao diện đồ họa thay thế các lệnh cấp máy bằng biểu tượng, cửa sổ và menu. Lợi ích đối với học sinh, kèm ví dụ: hệ điều hành giúp phần cứng trở nên sử dụng được mà không cần kiến thức kỹ thuật, chẳng hạn như lưu một tài liệu vào ổ USB bằng cách kéo thả biểu tượng của nó.

"Minh họa cách hệ điều hành tối đa hóa việc sử dụng tài nguyên." Nó lập lịch bộ xử lý để bộ xử lý không bao giờ rảnh khi một tiến trình sẵn sàng; nó quản lý bộ nhớ, phân bổ cho các tiến trình, thu hồi lại và mở rộng thông qua bộ nhớ ảo; nó quản lý đầu vào và đầu ra, sử dụng bộ đệm và spooling để các thiết bị nhanh và chậm chồng chéo công việc của chúng; và nó quản lý lưu trữ, theo dõi dung lượng trống và tệp tin. Mỗi điểm nêu một tài nguyên và những gì hệ điều hành làm với nó.

Một tiến trình là một chương trình đang thực thi — mã nguồn, trạng thái hiện tại, bộ nhớ và các tệp đang mở của nó.

Lập lịch

Bộ lập lịch chọn tiến trình sẵn sàng nào sẽ chạy tiếp theo, và trong bao lâu:

• round robin — mỗi tiến trình nhận được một thời gian slice cố định, sau đó xếp hàng ở cuối hàng đợi.
• first-come-first-served; shortest job first; shortest remaining time (chạy tác vụ còn ít công việc nhất); priority; multilevel feedback queues.

Sự đánh đổi là responsiveness vs throughput vs fairness.

"Mô tả ý nghĩa của multi-tasking và lợi ích của nó đối với quản lý tiến trình." Nhiều tiến trình được giữ trong bộ nhớ cùng lúc và bộ xử lý chuyển đổi giữa chúng rất nhanh đến mức chúng trông giống như đang chạy song song, mỗi tiến trình được giao một phần thời gian bộ xử lý theo lượt. Lợi ích: bộ xử lý không bao giờ bị bỏ rảnh khi một tiến trình đang chờ đầu vào hoặc đầu ra, vì vậy throughput cao hơn và người dùng có thể làm việc với nhiều chương trình cùng lúc. "Giải thích nhu cầu về lập lịch." Có nhiều tiến trình hơn bộ xử lý, vì vậy phải đưa ra quyết định về tiến trình nào sẽ chạy tiếp theo và trong bao lâu; lập lịch đảm bảo mọi tiến trình đều tiến triển, rằng bộ xử lý được sử dụng hoàn toàn, rằng thời gian phản hồi chấp nhận được, và rằng độ ưu tiên có thể được tôn trọng.

Các thủ tục lập lịch, như đề thi muốn mô tả.

Ví dụ đã giải. Ba tiến trình đến cùng lúc với thời gian CPU là 8, 4 và 2 ms. So sánh thời gian chờ trung bình dưới FCFS (theo thứ tự đến A, B, C) và dưới shortest job first.

FCFS: A waits 0, B waits 8, C waits 12; average $(0 + 8 + 12)/3 = 6.7\ \text{ms}$. SJF runs C, B, A: C waits 0, B waits 2, A waits 6; average $2.7\ \text{ms}$. Tổng công việc là như nhau là 14 ms dù theo cách nào; thứ tự quyết định ai phải chờ. Round robin với slice 2 ms sẽ cho A, B và C mỗi người một lượt trong 6 ms đầu tiên, vì vậy C hoàn thành ở ms 6, B ở ms 12 và A ở ms 14: responsive nhất, không phải nhanh nhất về mặt trung bình.

Trạng thái tiến trình

Một tiến trình có thể ở trạng thái mới, sẵn sàng (đang chờ CPU), đang chạy, bị chặn (đang chờ I/O hoặc khóa), hoặc đã kết thúc. Khi thời gian phân bổ của nó hết, nó chuyển từ đang chạy → sẵn sàng; khi nó yêu cầu I/O, nó chuyển từ đang chạy → bị chặn; khi I/O hoàn tất, nó chuyển từ bị chặn → sẵn sàng.

Ba trạng thái và lý do một tiến trình di chuyển. Đang chạy: tiến trình có bộ xử lý. Sẵn sàng: nó có thể chạy nhưng đang chờ bộ xử lý. Bị chặn: nó không thể chạy cho đến khi có sự kiện khác xảy ra. Lý do cho mỗi bước chuyển đổi, mà đề thi thường hỏi từng bước một: đang chạy sang sẵn sàng khi thời gian phân bổ của nó hết, hoặc khi một tiến trình có độ ưu tiên cao hơn trở nên sẵn sàng và chiếm quyền điều khiển (một tín hiệu ngắt); đang chạy sang bị chặn khi nó yêu cầu input hoặc output hoặc đang chờ tài nguyên hoặc một tiến trình khác; bị chặn sang sẵn sàng khi I/O mà nó đang chờ hoàn tất (được báo hiệu bằng tín hiệu ngắt); sẵn sàng sang đang chạy khi bộ lên lịch phân phối nó cho chạy. Một tiến trình bị chặn không bao giờ có thể đi thẳng đến trạng thái đang chạy: nó phải trở thành sẵn sàng trước.

Khối điều khiển tiến trình và chuyển ngữ cảnh

Đối với mỗi tiến trình, hệ điều hành giữ một khối điều khiển tiến trình (PCB) — gồm bộ đếm chương trình, thanh ghi, trạng thái và thông tin bộ nhớ đã được lưu lại.

• một chuyển ngữ cảnh tạm dừng một tiến trình và bắt đầu một tiến trình khác: nó lưu trạng thái vào một PCB và khôi phục từ một PCB khác. Chi phí nhỏ này được trả cho mỗi lần chuyển đổi.
• kernel (lõi của hệ điều hành) đóng vai trò là bộ xử lý ngắt. Khi một thiết bị hoặc bộ hẹn giờ phát ra tín hiệu ngắt, xử lý ngắt sẽ lưu tiến trình đang chạy và thực thi thủ tục phù hợp — đây chính là động lực thúc đẩy việc lên lịch cấp thấp.

"Mô tả cách kernel hoạt động như một bộ xử lý ngắt (hai điểm).**" Khi có tín hiệu ngắt, kernel lưu trạng thái của tiến trình đang chạy (các thanh ghi và bộ đếm chương trình, trong khối điều khiển tiến trình của nó), xác định nguồn và độ ưu tiên của tín hiệu ngắt, thực thi thủ tục dịch vụ ngắt phù hợp, và sau đó khôi phục tiến trình bị gián đoạn (hoặc một tiến trình có độ ưu tiên cao hơn) để việc thực thi tiếp diễn. Đây là cách bộ hẹn giờ kết thúc một thời gian phân bổ và cách một thao tác I/O hoàn tất giải phóng một tiến trình khỏi trạng thái bị chặn.

Giao tiếp liên tiến trình

Các tiến trình được cô lập, vì vậy OS cung cấp giao tiếp liên tiến trình: pipe (đầu ra của chương trình này feeds vào đầu vào của chương trình kia), bộ nhớ chia sẻ (một vùng mà nhiều tiến trình có thể sử dụng), và truyền thông điệp.

Mỗi tiến trình nhận được không gian địa chỉ ảo riêng — một dải địa chỉ liền mạch, sạch sẽ mà OS ánh xạ vào bộ nhớ vật lý. Điều này mang lại cho mỗi tiến trình một không gian đơn giản, bảo vệ các tiến trình khỏi nhau, và cho phép tổng bộ nhớ vượt quá RAM vật lý.

Trong paging, không gian ảo được chia thành các trang (pages) có kích thước cố định và bộ nhớ vật lý thành các khung (frames) có cùng kích thước. Bảng trang ánh xạ mỗi trang đến một khung. Nếu một trang được truy cập không có trong RAM — một lỗi trang (page fault) — OS sẽ đọc nó từ tệp swap vào một khung, loại bỏ một trang khác nếu RAM đã đầy. Lỗi trang thường xuyên gây ra trạng thái đảo lộn (thrashing (đảo lộn đĩa), nơi OS dành phần lớn thời gian để swap trang thay vì làm việc hữu ích.

Trong segmentation, bộ nhớ được chia thành các segment logic có kích thước biến đổi (code, stack, heap), mỗi segment có quyền truy cập riêng. Nhiều hệ thống sử dụng paging bên trong các segment.

"Giải thích ý nghĩa của bộ nhớ ảo (ba điểm).**" Bộ nhớ phụ (đĩa) được sử dụng để mở rộng RAM, sao cho bộ nhớ khả dụng trông lớn hơn bộ nhớ vật lý; không gian địa chỉ của một tiến trình được chia thành trang, và chỉ những trang cần thiết hiện tại được giữ trong RAM trong khi phần còn lại chờ trên đĩa; trang được swap giữa RAM và đĩa theo nhu cầu, và OS dịch mỗi địa chỉ ảo thành một địa chỉ vật lý. Lý do OS cần nó: các chương trình đang chạy có thể cần nhiều bộ nhớ hơn lượng RAM đã cài đặt; nó cho phép nhiều (hoặc lớn hơn) chương trình chạy cùng lúc; một chương trình có thể lớn hơn bộ nhớ vật lý; bộ nhớ được sử dụng hiệu quả vì chỉ các phần hoạt động của chương trình chiếm RAM.

Paging so với segmentation: sự khác biệt mà đề thi muốn. Paging chia bộ nhớ thành các khối có kích thước cố định (trang và khung) do phần cứng chọn, không quan tâm đến cấu trúc của chương trình, và việc ánh xạ là vô hình đối với người lập trình; segmentation chia một chương trình thành các đơn vị logic có kích thước biến đổi (hàm, mảng, stack) mà kích thước và ranh giới của chúng tuân theo chương trình, vì vậy một segment có thể được bảo vệ hoặc chia sẻ như một đơn vị. "Mô tả quy trình segmentation": chương trình được chia thành các segment có kích thước khác nhau, mỗi segment được gán một số segment; một bảng segment ghi lại nơi mỗi segment bắt đầu trong bộ nhớ và độ dài của nó; một địa chỉ logic là số segment cộng với độ lệch, và OS thêm độ lệch vào địa chỉ cơ sở của segment để tìm vị trí vật lý.

"Giải thích ý nghĩa của hiện tượng "thrashing" (lộn xộn bộ nhớ) và khi nào nó xảy ra." Thrashing là trạng thái trong đó các trang được di chuyển vào và ra khỏi RAM quá thường xuyên khiến bộ xử lý dành nhiều thời gian hơn để di chuyển trang thay vì thực thi chỉ thị, làm hệ thống chậm lại gần như đến mức dừng hoạt động. Hiện tượng này xảy ra khi RAM quá nhỏ so với số trang mà các tiến trình đang chạy cần (tập làm việc của chúng): một trang vừa bị đẩy ra sẽ được yêu cầu lại ngay lập tức, nên phải tải lại, điều này đẩy ra một trang khác mà sớm cũng cần, và cứ thế tiếp diễn. Quá nhiều tiến trình hoặc chương trình truy cập bộ nhớ không theo dự đoán sẽ gây ra tình trạng này; cách khắc phục là tăng thêm RAM hoặc giảm số lượng tiến trình.

Một trình biên dịch giải thích dịch và chạy mã nguồn cùng lúc. Với mỗi câu lệnh, nó đọc dòng, thực hiện phân tích từ vựng và ngữ pháp, kiểm tra kiểu dữ liệu, sau đó thực thi hành động, rồi chuyển sang bước tiếp theo. Lỗi được báo cáo ngay lập tức và nó thường dừng lại; không có file thực thi nào được tạo ra. Việc dịch được lặp lại ở mỗi lần chạy (chậm hơn), nhưng nó mang lại phản hồi phát triển nhanh chóng và dễ dàng chuyển đổi giữa các nền tảng.

"Giải thích cách một trình biên dịch giải thích thực thi một chương trình mà không tạo ra phiên bản đã dịch" (ba điểm). Trình biên dịch giải thích lấy một câu lệnh (dòng) một, dịch (phân tích) nó, và thực thi nó ngay lập tức, trước khi chuyển sang câu lệnh tiếp theo; không có phiên bản đã dịch của toàn bộ chương trình nào được tạo ra hoặc lưu trữ, do đó mỗi câu lệnh đều được dịch mọi lần nó được thực thi, bao gồm cả mỗi lần lặp qua vòng lặp; nếu một câu lệnh chứa lỗi, việc thực thi dừng lại tại đó và lỗi được báo cáo. Đây chính là lý do trình biên dịch giải thích rất tốt cho việc phát triển và thử nghiệm (lỗi được tìm thấy ngay khi gặp phải, và sự thay đổi có thể được thử ngay lập tức) nhưng lại chậm hơn đối với việc chạy các chương trình hoàn chỉnh.

Một trình biên dịch biến mã nguồn thành mã máy theo từng giai đoạn:

1. Phân tích từ vựng — trình phân tích từ vựng nhóm các ký tự thành token (từ khóa, danh định, toán tử, hằng số), loại bỏ khoảng trắng và comment.
2. Phân tích cú pháp (parsing) — kiểm tra xem các token có phù hợp với ngữ pháp và xây dựng cây cú pháp trừu tượng. Một dấu ngoặc thiếu sẽ gây ra lỗi cú pháp.
3. Phân tích ngữ nghĩa — kiểm tra xem chương trình có logic hay không (các biến đã được khai báo, các kiểu dữ liệu khớp nhau).
4. Tạo mã — duyệt qua cây và sinh mã đích, lựa chọn thanh ghi và bố trí.
5. Tối ưu hóa mã — loại bỏ công việc thừa, gộp hằng số, sắp xếp lại thứ tự để tối ưu cho pipeline.

Đầu ra là một file thực thi.

Mục đích của từng giai đoạn, dùng đúng thuật ngữ để đạt điểm. Phân tích từ vựng: loại bỏ khoảng trắng và comment; chuyển các ký tự của mã nguồn thành token (từ khóa, danh định, toán tử, hằng số), kiểm tra xem mỗi token có hợp lệ trong ngôn ngữ hay không; đưa các danh định vào bảng ký hiệu. Phân tích cú pháp: kiểm tra xem chuỗi token có tuân thủ ngữ pháp (luật ngữ pháp) của ngôn ngữ hay không; xây dựng cây phân tích (cây cú pháp trừu tượng); báo cáo lỗi cú pháp; việc kiểm tra kiểu và kiểm tra khai báo biến đôi khi được tính vào phần phân tích ngữ nghĩa. Tạo mã: chuyển cây đã được kiểm tra thành mã đối tượng hoặc mã máy (có thể thông qua mã trung gian), cấp phát bộ nhớ và thanh ghi. Tối ưu hóa: làm cho mã chạy nhanh hơn hoặc tiêu thụ ít bộ nhớ hơn, bằng cách loại bỏ các chỉ thị thừa, kết hợp hoặc đơn giản hóa các phép tính, và tổ chức lại các vòng lặp, mà không thay đổi hành vi của chương trình. Câu hỏi ghép nối sẽ ghép mỗi giai đoạn với một trong các mô tả trên.

Một ngữ pháp quy định những chuỗi token nào là chương trình hợp lệ.

Backus-Naur Form - (BNF) là dạng văn bản. Một quy tắc sản sinh có dạng:

<symbol> ::= alternative1 | alternative2 | ...

Mỗi phương án là một chuỗi các ký hiệu cuối cùng (văn bảnROOT) và ký hiệu phi cuối cùng (tên của các quy tắc khác):

<digit>      ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

Quy tắc đệ quy thứ ba biểu diễn "một chữ cái theo sau bởi bất kỳ số lượng chữ cái hoặc digit nào". Một statement IF:

<if-statement> ::= IF <condition> THEN <statement> ENDIF
                 | IF <condition> THEN <statement> ELSE <statement> ENDIF

Một sơ đồ cú pháp (sơ đồ đường ray) hiển thị cùng nội dung dưới dạng đồ họa: các ô vuông cho phi cuối cùng, các ô bo tròn cho cuối cùng, mũi tên cho các đường đi hợp lệ, vòng lặp cho sự lặp lại. Hai ký hiệu này tương đương nhau. Trình phân tích sử dụng ngữ pháp để quyết định xem một chương trình có hợp lệ hay không.

Đọc biểu đồ đề thi. Mỗi biểu đồ xác định một phi kết thúc; hãy đi theo các mũi tên từ điểm đầu vào đến điểm ra, và mọi đường đi bạn có thể traced là một chuỗi hợp lệ. Một lựa chọn các ô bên cạnh nhau là một tập hợp các tùy chọn; một vòng lặp quay lại là "lặp lại bao nhiêu lần tùy thích"; một ô cho một phi kết thúc khác có nghĩa là "chèn bất cứ thứ gì mà quy tắc cho phép". "Giải thích tại sao chuỗi không hợp lệ" yêu cầu quy tắc bị vi phạm, bằng lời: 9K không hợp lệ như một biến vì ký tự đầu tiên phải là chữ cái, không phải chữ số; JJ90 là mã thông báo không hợp lệ nếu quy tắc chỉ cho phép một chữ cái trước các chữ số, hoặc nếu J không nằm trong tập hợp các chữ cái được liệt kê. Luôn kiểm tra chuỗi so với tập hợp các ký hiệu mà biểu đồ thực sự cho phép, không phải so với những gì một ngôn ngữ thực tế sẽ chấp nhận.

Viết BNF từ biểu đồ. Mỗi biểu đồ trở thành một quy tắc <name> ::= ...; các tùy chọn được tách bởi |; một chuỗi được viết một ký hiệu sau ký hiệu khác; và sự lặp lại được viết bằng đệ quy, vì BNF không có ký hiệu vòng lặp: "một hoặc nhiều chữ cái" là <word> ::= <letter> | <letter><word>, và "zero hoặc nhiều chữ số sau một chữ cái" là <variable> ::= <letter> | <letter><digits> với <digits> ::= <digit> | <digit><digits>.

Ví dụ minh họa. Hoàn thiện BNF cho biển số xe bắt đầu bằng hai chữ cái (từ A B C) tiếp theo là một, hai hoặc ba chữ số (từ 0 1 2).

<letter>       ::= A | B | C
<digit>        ::= 0 | 1 | 2
<digits>       ::= <digit> | <digit><digit> | <digit><digit><digit>
<registration> ::= <letter><letter><digits>

AB12 là hợp lệ; A12 không (chỉ một chữ cái); AB1234 không (bốn chữ số); AD1 không (D không phải là chữ cái được liệt kê). Được yêu cầu thêm ràng buộc như "ký tự thứ ba cũng có thể là ký hiệu", hãy thêm tùy chọn bổ sung vào quy tắc cho vị trí đó duy nhất, và định nghĩa <symbol> với quy tắc riêng của nó.

Ví dụ minh họa. Viết BNF cho một biểu thức là một biến, theo sau là một toán tử, tiếp theo là hoặc một biến hoặc một số, trong đó một biến là một chữ cái thường đơn lẻ từ a b c và một toán tử là + hoặc -.

<variable>   ::= a | b | c
<operator>   ::= + | -
<number>     ::= <digit> | <digit><number>
<expression> ::= <variable><operator><variable> | <variable><operator><number>

Quy tắc đệ quy <number> cho phép bất kỳ số lượng chữ số nào; hai tùy chọn của <expression> bao phủ cả hai trường hợp được nêu trong định nghĩa. Giữ nguyên mọi phi kết thúc trong ngoặc nhọn và mọi kết thúc mà không có chúng.

Trong not infix toán tử nằm giữa các toán hạng của nó (3 + 4 * 2), cần ngoặc và quy tắc ưu tiên. Trong Notation Reverse Polish (RPN, postfix) toán tử theo sau các toán hạng của nó (3 4 2 * +), không cần ngoặc.

Chuyển đổi infix sang RPN

Sử dụng một ngăn xếp toán tử. Quét từ trái sang phải: xuất ra một toán hạng; đối với một toán tử, trước hết pop bất kỳ toán tử nào đang được push vào ngăn xếp có ưu tiên cao hơn hoặc bằng vào đầu ra, sau đó push nó; push (; trên ) pop vào đầu ra cho đến khi gặp ( tương ứng. Ở cuối cùng, pop tất cả các toán tử. Ví dụ: (3 + 4) * 2 → 3 4 + 2 *.

Đánh giá RPN

Sử dụng một ngăn xếp các toán hạng. Quét từ trái sang phải; push mỗi toán hạng; trên một toán tử, pop hai phần tử trên cùng, áp dụng toán tử đó, và push kết quả. Đánh giá 3 4 2 * +:

Kết quả: 11. RPN không cần ngoặc ở thời điểm đánh giá và phù hợp với máy ngăn xếp — đó là cách JVM và nhiều trình biên dịch bytecode hoạt động.

"Giải thích tại sao RPN được sử dụng để đánh giá biểu thức (hai điểm)." Trong RPN các toán tử xuất hiện theo thứ tự mà chúng được áp dụng, vì vậy một biểu thức có thể được đánh giá trong một lượt quét trái sang phải duy nhất với không có ngoặc và không có quy tắc ưu tiên; do đó nó đơn giản và nhanh hơn cho trình biên dịch hoặc trình giải mã xử lý. "Xác định, kèm lý do, một cấu trúc dữ liệu phù hợp": một ngăn xếp, vì việc đánh giá cần các toán hạng được push mới nhất trước (vào sau, ra trước): mỗi toán hạng được push, và mỗi toán tử pop hai phần tử trên cùng, áp dụng bản thân nó, và push kết quả. Hiển thị nội dung ngăn xếp sau mỗi token khi được yêu cầu.

Chuyển đổi infix sang RPN bằng tay. (1) Đặt ngoặc đầy đủ cho biểu thức dựa trên các quy tắc ưu tiên; (2) di chuyển mỗi toán tử ngay sau dấu đóng ngoặc của cặp ngoặc của chính nó; (3) loại bỏ các ngoặc. Vì vậy $(a - b) * (a + c) / 7$ trở thành $((a - b) * (a + c)) / 7$, sau đó a b - a c + * 7 /. Lưu ý rằng * và / được áp dụng từ trái sang phải, vì vậy phép chia là toán tử cuối cùng, không phải phép nhân. Nhiều chuyển đổi hơn: $((7 + 3) - (2 * 8)) / 6$ là 7 3 + 2 8 * - 6 /; $(7 - 2 + 8) / (9 - 5)$ là 7 2 - 8 + 9 5 - /; $a * b + b - d + 15$ là a b * b + d - 15 +; $(2 - 6) * (13 + 7) / 5$ là 2 6 - 13 7 + * 5 /.

Chuyển đổi RPN ngược lại thành infix. Làm việc qua RPN với một ngăn xếp biểu thức: push mỗi toán hạng; đối với mỗi toán tử pop hai, viết chúng ở hai bên toán tử trong ngoặc, và push kết quả. Vì vậy a b / 4 * a b + - là $((a / b) * 4) - (a + b)$; 5 2 + 9 3 - / 3 * là $((5 + 2) / (9 - 3)) * 3$; b a c - + d b + * c / là $((b + (a - c)) * (d + b)) / c$; a b - c + c a - * d / là $(((a - b) + c) * (c - a)) / d$. Giữ nguyên các ngoặc: dropping chúng có thể thay đổi ý nghĩa.

Ví dụ minh họa. Đánh giá a b - c d + * e / khi $a = 17$, $b = 5$, $c = 7$, $d = 3$ và $e = 10$, hiển thị ngăn xếp.

Kết quả 12. Thứ tự của các pop quan trọng đối với - và /: giá trị được pop thứ hai là toán hạng bên trái, vì vậy a b - là $a - b$, không phải $b - a$. Hai cái nữa, theo cùng cách: d a b + * c a - / với $a = 6, b = 12, c = 15, d = 5$ cho $5 \times (6 + 12) / (15 - 6) = 90 / 9 = 10$; c a - b d + * b c + / với $a = 4, b = 12, c = 24, d = 6$ cho $(24 - 4) \times (12 + 6) / (12 + 24) = 360 / 36 = 10$.

Ví dụ minh họa. Chuyển $(A + B) \times (C - D)$ sang RPN, sau đó tính $(3 + 4) \times (5 - 2)$. Quét từ trái sang phải sử dụng một ngăn xếp toán tử. Đẩy (; xuất A; đẩy +; xuất B; khi gặp ) thì lấy ra (pop) để khớp với ( tương ứng, tạo thành A B + cho đến thời điểm này. Đẩy ×, và ngoặc thứ hai hoạt động giống nhau, tạo thành C D -. Ở bước cuối cùng, lấy ra (pop) ×. Kết quả: A B + C D - ×. Để tính các giá trị số, sử dụng một ngăn xếp toán hạng: đẩy 3, đẩy 4; + lấy cả hai ra và đẩy 7; đẩy 5, đẩy 2; - lấy cả hai ra và đẩy 3; × lấy 7 và 3 ra và đẩy 21. Hai yếu tố làm cho điều này đáng tin cậy: các toán hạng giữ nguyên thứ tự ban đầu qua quá trình chuyển đổi (chỉ có các toán tử di chuyển), và mỗi toán tử tác động lên hai giá trị ngay bên dưới nó trên ngăn xếp.

Câu hỏi định nghĩa được chấm dựa trên văn phong cố định. Hãy học thuộc những định nghĩa này và chỉ đưa ra một đáp án duy nhất.

• Các câu hỏi về hệ điều hành được chấm dựa trên các cơ chế cụ thể: lập lịch, quản lý bộ nhớ, đệm I/O và spooling, quản lý tập tin; đối với giao diện, tên tập tin chứ không phải địa chỉ, click chứ không phải lệnh, trình điều khiển, giao diện đồ họa GUI.
• Trạng thái tiến trình cùng các chuyển đổi và lý do cho mỗi chuyển đổi; các thủ tục lập lịch dưới dạng hàm cộng lợi ích cộng nhược điểm; kernel lưu trạng thái, xác định ngắt, xử lý ngắt, rồi khôi phục.
• Bộ nhớ ảo: ổ đĩa mở rộng RAM, trang được hoán đổi, chuyển đổi địa chỉ; phân trang là kích thước cố định và vô hình, phân đoạn là kích thước biến đổi và mang tính logic; xé fragment ổ đĩa là việc hoán đổi thay vì làm việc.
• Máy giải thích: từng câu lệnh một, được dịch rồi thực thi, không lưu trữ gì. Các giai đoạn của trình biên dịch: token và bảng ký hiệu, ngữ pháp và cây phân tích, mã, tối ưu hóa.
• BNF: một quy tắc cho mỗi sơ đồ, | cho lựa chọn, đệ quy cho lặp lại, các ký kết thúc hiển thị đơn giản và các ký không kết thúc trong dấu ngoặc nhọn. Nói quy tắc nào mà một chuỗi vi phạm.
• RPN: toán tử nằm sau toán hạng, tính toán bằng ngăn xếp, hiển thị từng bước; chuyển đổi bằng cách đặt ngoặc đầy đủ; khi chuyển đổi ngược lại, giữ nguyên các ngoặc.

Lỗi thường gặp

• Mô tả đa nhiệm là "chạy nhiều chương trình cùng lúc" mà không nói rằng bộ xử lý chuyển đổi giữa chúng.
• Gửi trực tiếp một tiến trình bị chặn sang trạng thái đang chạy, hoặc đưa "hết thời gian slice" làm lý do để chuyển từ đang chạy sang bị chặn.
• Nhầm lẫn shortest job first (không chủ động) với shortest remaining time (chủ động), hoặc round robin với priority.
• Định nghĩa bộ nhớ ảo là "sử dụng ổ cứng như RAM" mà không nhắc đến việc các trang được hoán đổi.
• Nói rằng máy giải thích "chuyển chương trình sang mã máy rồi chạy nó"; đó là đặc điểm của trình biên dịch.
• Đặt kiểm tra cú pháp trong phân tích từ vựng, hoặc tối ưu hóa trước khi sinh mã trong bài tập trắc nghiệm,(matching question).
• Viết lặp lại trong BNF là <letter>* hoặc dùng dấu ba chấm; hãy dùng đệ quy. Bỏ dấu ngoặc nhọn khỏi các ký không kết thúc.
• Đảo ngược thứ tự toán hạng của - hoặc / khi tính RPN, hoặc viết RPN của $a * b + c$ là a b c + *.