Cấn Trúc Máy Tính
-105-
(a) các thanh ghi nhanh hơn bộ nhớ chính
(b) bởi vì có quá ít thanh ghi nên chỉ cần ít bit để đòa chỉ hóa chúng.
Đáng tiếc là có 8 hoặc 16 thanh ghi cũng làm phức tạp cho việc lập trình do bởi
phải tạo ranhiều quyết đònh như : các toán hạng nào, các kết quả trung gian nào được
giữ trong số thanh ghi giới hạn đó và các toán hạng nào, các kết quả trung gian nào
được giữ trong bộ nhớ chính. W.L.vander Poel (1968) đã nhận xét một cách tinh tế, các
máy tính phải được cung lớp hoặc 0, 1 hoặc một số vô hạn cho mỗi đặc tính (vô hạn có
nghóa là nhiều đủ để người lập trình không cần phải tốn thời gian suy nghó phải làm gì
nếu điều gì đó đã được dùng hết ).
Cả 2 chip Intel và Motorola đều có một lượng lớn các lệnh lấy các toán hạng từ
các thanh ghi và đặt kết quả vào một thanh ghi.
4. Đònh đòa chỉ gián tiếp
Đònh đòa chỉ trực tiếp làsơ đ ừ nhớ nào hoặc thanh ghi
nào c
ồ trong đó đòa chỉ cho biết t
hứa toán hạng. Đònh đòa chỉ gián tiếp là sơ đồ trong đó đòa chỉ cho biệt từ nhớ nào
hoặc thanh ghi nào chứa đòa chỉ của toán hạng. Thí dụ xét một lệnh nâp một thanh ghi
(chúng ta sẽ gọi là thanh ghi R1 ) gián tiếp từ vò trí nhớ 1000, nội dung tại vò trí 1000 là
1510.

Hình 5.8: Đòa chỉ gián tiếp
ào 1 thanh ghi nội của CPU. Nội
dung it na ong R1, ta có
lệnh
a gọi là con trỏ (pointer).
Trước tiên nội dung tại vò trí 1000 được tìm nạp v
16 b øy (1510) không được đặt trong thanh ghi R1. Nếu 1510 có tr
đòa chỉ trực tiếp. Thay vào đó nội dung của vò trí 1510 được tìm nạp và đặt vào
R1. Nội dung ở vò trí 1000 không phải là toán hạng mà trỏ tới toán hạng và vì lý do

5. Đònh chỉ số
Nhiều thuật toán cầøn thực hiện một thao tác nào đó trên một chuỗi cấu trúc dữ
liệu lưu giữ trong những vò trí nhớ liên tiếp. Thí dụ xét một khối n từ máy chiếm các vò
trí
A, A +1, A+2,…,A+n-1
Các từ này phải được chuyển đến các vò trí
B,B+1,B+2,…,B+n-1
Giả thuyết rằng máy có lệnh
MOVE A,B
Chuyển nội dung của vò trí A tới vò trí B, người ta có thể thực thi lệnh này và thay
đổi trên chính lệnh thành
MOVE A+1,B+1
Thực thi lệnh lần nữa, sau và lập lại cho tới khi tất
cả n
quyết bằng đònh đòa chỉ gián tiếp. Một
thanh
đó lại thay đổi lệnh lần nữa
từ được sao chép hết.
Mặc dù các chương trình tự thay đổi được dùng phổ biến trước kia, nhưng nay
được xem như một phương cách lập trình dở. Các chương trình như vậy khó sửa sai và
làm khó khăn cho việc dùng chung một chương trình giữa nhiều người sử dụng trong
hệ thống phân chia thời gian.
Vấn đề sao chép cũng có thể được giải
ghi hoặc một từ nhớ được nạp với đòa chỉ A ; một thanh ghi hoặc một từ nhớ thứ
2 được nạp với đòa chỉ B. lệnh MOVE dùng 2 thanh ghi này làm các con trỏ. Sau mỗi
lần sao chép một từ , các con trỏ được tăng thêm 1. Các con trỏ là một phần của dữ
liệu, không phải là phần của chương trình và những người sử dụng không được dùng
chung đồng thời.
Nguyễn Hữu Lộc Khoa Vật Lý
Cấn Trúc Máy Tính

nhớ. Phần tử đầu tiên được cất vào ngăn xếp. Phần tử gần
nhất được cất vào stack sẽ ở đỉnh ết hợp với một ngăn xếp là một
thanh
Chúng ta đã lưu ý rằng việc tạo ra các lện
Ngăn xếp bao gồm các phần tử dữ liệu ( từ, ký tự, bit, vv…) được cất theo một
trật tự liên tiếp trong bộ
của ngăn xếp. K
ghi hoặc từ nhớ chứa đòa chỉ của đỉnh ngăn xếp, được gọi là con trỏ ngăn xếp
(stack pointer).
Mặt dù đã thảo luận về ngăn xếp ở chương 4, chúng ta cũng sẽ ôn lại ở đây bởi
vì việc sử dụng ngăn xếp cho các phép toán số học hoàn toàn khác với việc sử dụng
ngăn xếp để lưu giữ các biến cục bộ ( dó nhiên có thể dùng kết hợp cả 2). Hình 5.9
minh họa hoạt động của ngăn xếp. Trong hình 5.9(a) đã có 2 phần tử trong ngăn xếp.
Đáy của ngăn xếp ở vò trí nhớ 1000 và đỉnh của ngăn xếp ở vò trí nhớ 1001. Con trỏ
ngăn xếp chứa đòa chỉ của phần tử trên đỉnh ngăn xếp, tức là 1001 ; nghóa là trỏ tới
đỉnh của ngăn xếp. Trong hình 5.9(b), 6 được cất vào ngăn xếp và con trỏ ngăn xếp
chứa 1002 là đỉnh mới của ngăn xếp. Trong hình 5.9(c), 75 được cất lên ngăn xếp, tăng
con trỏ ngăn xếp lên 1003. Trong hình 5.9(d), 75 được lấy ra khỏi ngăn xếp.
Nguyễn Hữu Lộc Khoa Vật Lý
Cấn Trúc Máy Tính
-108-

Hình 5.9: Hoạt động của một ngăn xếp
Các máy tính hướng ngăn xếp (stack-oriented) có lệnh cất ( push) các nội dung
của vò trí nhớ hoặc thanh ghi vào ngăn xếp. Một lệnh như vậy phải thực hiện việc sao
chép phần tử đó và tăng con trỏ ngăn xếp. Tương tự, lệnh lấy (pop) đỉnh của ngăn xếp
đưa vào thanh ghi hoặc vò trí nhớ phải thực hiện một sao chép mới vào nơi thích hợp và
giảm con trỏ ngăn xếp. Một số máy tính có ngăn xếp đảo ngược, với những phần tử
được
III. LUO

Sự quan sát này đã dẫn đường cho Dijkstra (1968) viết một thư gây tranh luận sau
này có tựa đề ‘GO TO Statement Considered Harmfull ‘ (phát biểu GO TO được xem
như có hại), trong đó ông đề nghò nên tránh dùng phát biểu GO TO. Bức thư đó làm
khai sinh ra cuộc cách mạng cho phương pháp lập trình có cấu trúc, một trong những
nguyên lý của phương pháp này là thay thế phát biểu GO TO bằng những dạng có cấu
trúc hơn của luồng điều khiển, như vòng lập WHILE.
Dó nhiên, những chương trình này biên dòch thành những chương trình lớp 2 chứa
nhiều lệnh nhảy, bởi vì hiệbn thực IF, WHILE và những cấu trúc điều khiển lớp cao
khác yêu cầu việc nhảy.
2. Thủ tục
. Từ quan điểm này, lệnh gọi thủ tục được xem như
một lệnh đơn cho dù có thể rất phức tạp. Để hiểu phần mã chứa lệnh gọi thủ tục, điều
cần biết cách thực hiện.
3
Kỹ thuật quan trọng nhất đối với các chương trình có cấu trúc là thủ tục. Lệnh gọi
thủ tục cũng làm thay đổi dòng điều khiển như lệnh nhảy nhưng không giống. Khi thực
hiện song công việc, thủ tục trả điều khiển trở về cho phát biểu hoặc lệnh theo sau
lệnh gọi.
Tuy nhiên, với cách nhìn khác, phần thân của thủ tục có thể được xem như xác
đònh một lệnh mới ở lớp cao hơn
duy nhất cần biết là làm gì, không
. Đồng thủ tục.
Trong chuỗi gọi thông thường, có sự phân biệt rõ giữa thủ tục gọi và thủ tục được
gọi.
Xét thủ tục A gọi thủ tục B. Thủ tục B tính toán trong một khoảng thời gianvà sau
đó trở về thủ tục A. Thoạt nhìn có lẽ ta sẽ nghó rằng tình huống này có tính đối xứng,
bởi vì cả A và B đều không phải là chương trình chính, chúng đều là các thủ tục. Hơn
nữa, điều khiển đầu tiên được chuyển từ A tới B – gọi – và sau đó điều khiển được
chuyển từ B tới A – trở về.
Tính không đối xứng nảy sinh từ thực tế. Khi điều khiển chuyển tứ A tới B , thủ

ương trình phát hiện. Một
phư ả năng điều khiển tràn là dùng một thanh ghi 1 bit được thiết
lập là 1 mỗi khi xảy ra tràn. Người lập trình muốn kiểm tra tràn phải đưa thêm vào một
lệnh
g gian nhớ vừa làm cho tốc độ chậm lại. Bẫy tiết kiệm được thời gian và bộ nhớ
so vơ
ở một lớp có thể ở dưới sự điều khiển của chương trình ở
lớp th
a chỉ lẻ và chia cho zero.
flow) là một thí dụ. Trên nhiều máy tính, nếu kết quả của 1 phép toán số học
vượt quá số lớn nhất có thể biểu diễn, một bẫy xuất hiện, nghóa là luồng điều khiển
được chuyển đến 1 vò trí nhớ nào đó thay vì tiếp tục theo trình tự. Tại vò trí cố đònh đó
có một le
1 động tác thích hợp nào đó, như in 1 thông báo lỗi. Nếu kết quả của phép toán
nằm trong phạm vi cho phép, bẫy không xuất hiện.
Điểm cơ bản của bẫy là bẫy được khởi động bởi 1 điều kiện ngoại lệ nào đó gây
ra bởi chính chương trình và được phần cứng hoặc vi ch
ơng pháp khác có kh
“nhảy nếu bit tràn được thiết lập” sau mỗi lệnh số học. Hiện thực như vậy vừa tốn
khôn
ùi phương pháp kiểm tra điều khiển bởi người lập trình. Bẫy thường được thực hiện
bằng cách có vi chương trình, vi chương trình này đơn giản chỉ thực hiện sự kiểm tra.
Bẫy cũng có thể được thực hiện nhờ vào việc kiểm tra thực hiện bởi trình biên
dòch ở lớp 1. Nếu phát hiện thấy có tràn, đòa chỉ của bẫy được nạp vào bộ đếm chương
trình. Điều này nghóa là bẫy
ấp hơn. Vi chương trình thực hiện việc kiểm tra vẫn tiết kiệm thời gian hơn so với
việc kiểm tra của người lập trình, bởi vì việc này dễ dàng chồng lấp với viêc khác và
cũng tiết kiệm được bộ nhớ, bởi vì việc này chỉ cần xảy ra ở một vài thủ tục của lớp 1,
độc lập với việc có bao nhiêu lệnh số học xuất hiện trong chương trình chính.
Một vài điều kiện thừơng gây ra bẫy là tràn trên dấu chấm động, tràn dưới dấu
Các chương trước đã trình bày cách thức một trình biên dòch chạy trên lớp vi
chương trình (lớp 1) thực thi các chương trình viết cho lớp máy qui ước (lớp 2). Trên
một máy tính được vi lập trì
ơng
trình viết bằng ngôn ngữ máy lớp 2 một trình phiên dòch chạy trên máy lớp 2 có thể
phiên dòch các chương trình viết bằng ngôn ngừ máy lớp 3. Với các lý do có tính lòch
sử, trình phiên dòch chạy trên máy lớp 2 hỗ trợ cho máy lớp 3 được gọi là hệ điều hành
(operating system). Do vậy chúng ta sẽ gọi lớp 3 là lớp máy hệ điều hành do thiếu
thuật ngữ tổng quát chấp nhận được.
Có sự khác biệt quan trọng giữa cách mà lớp máy hệ điều hành được hỗ trợ cách
mà lớp máy qui ước được hỗ trợ. sự khác nhau này thực tế do bởi lớp máy hệ điều
hành được phát triển dần dần ra khỏi lớp máy qui ước. Hầu hết các lệnh của lớp máy
hệ điều hành cũng hiện diện ở lớp máy qui ước. Chúng ta sẽ gọi những lệnh này là các
lệnh lớp 3 "tầm thường" (ordinary) do bởi chúng bao gồm các thao tác bình thường như
các phép toán số học, logic, dòch bit v v… chúng ta cũng sẽ gọi các lệnh khác của máy
lớp 3 (chúng không hiện diện trong máy lớp 2) là các lệnh OSML (Operating System
Machine Language) để nhấn mạnh chúng chỉ hiện diện trong lớp máy hệ điều hành.
Mặc dù ta có thể có hệ điều hành phiên dòch tất cả các lệnh của lớp 3, nhưng
điều này không có hiệu quả cũng như không cần thiết. Các lệnh lớp 3 tầm thường có
thể được dòch trực tiếp bởi vi chương trình. Tình huống này được mô tả cho trương hợp
máy tính chỉ có 1 bộ nhớ để lưu trữ mọi chương trình. Miễn là chỉ có các lệnh tầm
thường đang thực thi, vi chương trình tìm nạp các lệnh trực tiếp từ chương trình người
sử dụng, khảo sát chúng và thực thi chúng.
Tuy nhiên ngay khi gặp một lệnh OSML, tình huống sẽ thay đổi. Vi chương trình
ngừng phiên dòch chương trình của người sử dụng và bắt đầu phiên dòch hệ điều hành.
Hệ điều hành sau đó khảo sát lệnh OSML trong chương trình người sử dụng và thực thi
lệnh này. Khi lệnh OSML đã được thực thi, hệ điều hành thực thi một lệnh nào đó làm
cho vi chương trình tiếp tục tìm nạp và thực thi các lệnh của chương trình người sử

Điều cần đề cập là đa số các hệ điều hành của các máy tính lớn đều là các hệ
thống đa lập trình (multiprogramming system), nghóa là thay vì chỉ hỗ trợ cho máy ảo
lớp 3, hệ điều hành hỗ trợ cho vài máy ảo lớp 3 chạy song song. Nếu mỗi máy ảo được
nối với một thiế bò đầu cuối từ xa, ta có một hệ thống chia sẻ thời gian (time-shared
system). Nếu không có các thiết bò đầu cuối từ xa,
(batch). Với dạng hỗn hợp, một số máy ảo đang được sử dụng trực tuyến (on
line), một số máy khác thì không. Phần chủ yếu của hệ điều hành liên quan đến việc
quản lý tất cả máy ảo hơn là phiên dòch các lệnh OSML.
Chúng ta sẽ tập trung vào 3 vấn đề quan trọng. Trước tiên là bộ nhớ ảo (virtual
memory), một kỹ thuật được cung cấp bởi nhiều hệ điều hành làm cho máy có nhiều
bộ nhớ hơn là máy thật sự có. Thứ 2
cao hơn các lệnh vào/ra mà ta đã nghiên cứu trong chương trứơc. Thứ 3 và cuối
cùng là xử lý song song, cách mà các quá trình (process) có thể thực thi đồng thời ở lớp
3.
Khái niệm quá trình là một khái niệm quan trọng, chúng ta sẽ mô tả chi tiết sau
trong chương này. Một quá trình có thể xem như một chương trình đang chạy với tất cả
các thông tin trạng thái của chương trình (bộ nhớ, các thanh ghi, bộ đếm chương trình,
trạng thái vào/ra…).

I. BỘ NHỚ ẢO
Trong những ngày đầu của máy tính, bộ nhớ có dung lượng nhỏ và rất đắt tiền.
Máy IBM 650, máy tính khoa học hàng đầu lúc này (vào những năm cuối thập niên
1950) chỉ có một bộ nhớ 2000 từ. Một trong những trình biên dòch viết bằng ALGOL 60
đầu tiên được viết cho máy tính chỉ có 1024 từ nhớ. Một hệ thống chia sẻ thời gian
trước đây chạy rất tốt trên PDP-1 với kích thước bộ nhớ tổng cộng chỉ có 4096 từ 18 bit
cho cả hệ điều hành và các chương trình của người sử dụng. Thời đó những người lập
trình phải tốn nhiều thời gian để nén kích thước các chương trình sao cho đặt vừa trong
một bộ nhớ nhỏ. Thông thường họ dùng một giải thuật chạy rất chậm so với giải thuật
khác mà giải thuật tốt hơn thường sẽ rất lớn nghóa là chương trình sử dụng giải thuật
tốt hơn sẽ không đặt vừa trong bộ nhớ của máy tính.

này đều có hệ thống bộ nhớ ảo rất phức tạp.

Phân trang
Nhóm Manchester đã nảy sinh một ý tưởng tách riêng khái niệm về không gian
đòa chỉ và các vò trí ô nhớ (memory location). Thí du ïxét một máy tính có một trường
đòa chỉ 16 bit trong các lệnh của máy này và có 4096 từ nhớ. Một chương trình trên
ma
oá được chỉ tuỳ thuộc vào số bit có trong một đòa chỉ và không có liên quan dù
bằng cách nào với số từ nhớ thực sự sử dụng được. Không gian đòa chỉ (address space)
của máy tính này bao gồm các số 0, 1, 2…, 65535 bởi vì đó là tập các đòa chỉ có thể
có.
T
2 phần đòa chỉ được
dùng bởi vì chúng không tương ứng với các đòa chỉ của bộ nhớ thực). Người ta
không có sự phân biệt nhiều giữa không gian đòa chỉ và các đòa chỉ của bộ nhớ thực bởi
vì phần cứng bắt buộc phải có sự tương ứng một-một giữa chúng với nhau.
Ý tưởng tách riêng không gian đòa chỉ và các đòa chỉ bộ nhớ như sau. Bất cứ lúc
nào, 4096 từ của bộ nhớ đều có thể được truy xuất trực tiếp nhưng chúng không cần
tương ứng với các đòa chỉ từ 0 tới 4096. Thí dụ ta có thể “bảo” máy tính rằng từ bây giờ
trở đi mỗi khi đòa chỉ 4096 được tham chiếu, từ nhớ 0 được sử dụng; mỗi khi đòa chỉ
4097 được tham chiếu, từ nhớ 1 được sử dụng; mỗi khi đòa chỉ 8191 được tham chiếu,
từ nhớ 4095 được sử dụng và v.v … nói cách khác ta đã đònh nghóa một ánh xạ từ
không gian đòa chỉ lên các đòa chỉ bộ nhớ thực, như trì
Nguyễn Hữu Lộc Khoa Vật Lý
Cấn Trúc Máy Tính
-115-

Hình 6.1: Ánh xạ trong đó các đòa chỉ từ 4096 tới 8191 được ánh xạ
lên các đòa chỉ bộ nhớ chính từ 0 tới 4095


thậm chí họ không cần biết đến sự tồn tại của bộ nhớ ảo. Máy tính dường n
Nguyễn Hữu Lộc Khoa Vật Lý
Cấn Trúc Máy Tính
-116-
Điểm này là vấn đề chủ yếu và sẽ được đối chiếu sau này với sự phân đoạn
(segmentation), trong đó người lập trình phải biết đến sự tồn tại ccủa các segment.
Nhấn mạnh lại một lần nữa, sự phân trang cung cấp cho người lập trình ảo tưởng về
một bộ nhớ chính lớn tuyến tính và liên tục có kích thước bằng với kích thước của
không gian đòa chỉ trong khi bộ nhớ chính sử dụng được có thể nhỏ hơn (hoặc lớn hơn)
không gian đòa chỉ. Việc mô phỏng bộ nhớ chính lớn này bằng cách phân trang không
bò chương trình phát hiện (trừ phi bò phát hiện khi đang chạy các chương trình kiểm tra
đònh thì); mỗi khi một đòa chỉ được tham chiếu, lệnh hoặc từ dữ liệu thích hợp sẽ xuất
hiện. Bởi vì ngươ
chế phân tr
Sự phân trang (paging) và sự phân đoạn (segmentation) được so sánh như trong
hình
øi lập trình có thể lập trình như thể sự phân trang không tồn tại, nên cơ
ang được gọi là trong suốt (transparent).
6.2

Sự xem xét Phân trang Phân đoạn
Người lập trình có cần biết kỹ thuật này
đang được sử dụng không ?
Không Có
Có bao nhiêu không gian đòa chỉ tuyến
tính?
1 Nhiều
Không gian chỉ
vượt quá kí thươ
không?

được chia ra
thành nhiều
không gian đòa
chỉ logic độc
lập và để cung
Nguyễn Hữu Lộc Khoa Vật Lý
Cấn Trúc Máy Tính
-117-
bảo vệ
Hình 6.2 So sánh phân trang và phân đoạn

Ýù tưởng mà người lập trình có thể sử dụng một đặc tính nào đó không tồn tại và
không quan tâm đến cách làm việc của đặc tính này không phải là mới đối với chúng
ta. Tập lệnh của máy lớp 2 không tồn tại trong ý nghóa không có lệnh nào hoàn toàn là
lệnh phần cứng, nhưng tất cả chúng thực tế đều được thực hiện bởi phần mền ở lớp 1.
Tương tự, người lập trình ở lớp 3 có thể dùng bộ nhớ ảo mà không phải lo lắng gì về
cách bộ nhớ này làm việc. Chỉ có những người viết hệ điều hành cần phải biết bộ nhớ
ảo làm việc như thế nào.
II. CÁC LỆNH VÀO/RA ẢO
hông thường tập lệnh của lớp 2 hoàn toàn khác với tập lệnh của lớp 1. Các thao
tác mà cả hai có thể được thực hiện và các khuôn dạng của các lệnh của cả hai rất
g nhau tre ùp chỉ là tình cờ.
3 trái lại chứa hầu hết các lệnh của lớp 2 cộng thêm vài
ây tổn hại đ loại bỏ. Vào/ra là một trong
phạm vi trong đó các máy lớp 2 và lớp 3 khác nhau. Lý do của sự khác nhau này
ực thi các lệnh lớp 2 thật sự, có thể đọc các
thiết bò đầu cuối của những người sử dụng
một cách tổng quát có thể tạo ra nỗi phiền toái lớn cho chính họ cũng hư đe
h bình thường và đúng mực không muốn tự
. Tiêu bie ùc thanh ghi thiết bò đối với

Lệnh vào ảo cơ bản đọc bản ghi kế từ 1 tập tin đã được xác đònh và đặt bản ghi
này trong các ô nhớâ liên tiếp trong bộ nhớ chính ở một đòa chỉ đã được xác. Để thực
Một phươ hức vào/ra a
là một chuỗi các bản ghi logic (logical
ng pháp tổ c tưởng äu đư
ord), trong đó một bản gh
người lập trình. Trong trư
n 10x10. Với một ứn
tượng dữ lie ïc hoặc ghi nh
ogic là một đơ
øng hợp đơn giản
øi thay đổi.
Nguyễn Hữu Lộc Khoa Vật Lý