bộ giáo dục và đào tạo
trờng đại học bách khoa hà nội

luận văn thạc sỹ khoa học Nghiên cứu, thiết kế hệ điều hành trên
bộ vi điều khiển 8 bít

ngành: xử lý thông tin và truyền thông

M số: vũ trung kiên Ngời hớng dẫn khoa học: TS. Nguyễn Linh Giang


Lời nói đầu 9
Chơng 1 - Tổng quan về hệ điều hành 11
1.1. Khái niệm về hệ điều hành (OS-Operating System) 11
1.1.1. Khái niệm 11
1.1.2. Chức năng của hệ điều hành. 11
1.1.3. Các thành phần của hệ điều hành 13
1.2. Quản lý tiến trình 16

1.2.1. Các trạng thái của một tiến trình 16
1.2.2. Khái niệm về tài nguyên găng và đoạn tới hạn 17
1.2.3. Hiện tợng bế tắc 19
1.3. Lập lịch cho CPU 20

1.3.1. Khái niệm giờ CPU 20
1.3.2. Các trạng thái của tiến trình liên quan đến giờ CPU 20
1.3.3. Lập lịch cho CPU 22
1.4. Quản lý bộ nhớ 25

1.4.1. Yêu cầu phải quản lý bộ nhớ 25
1.4.2. Các sơ đồ quản lý bộ nhớ 26
Chơng 2 - Vi điều khiển và ngôn ngữ lập trình
cho vi điều khiển
28
2.1. Vi điều khiển 28
2.1.1. Vi xử lý và vi điều khiển 28
2.1.2. Tổ chức bộ nhớ của vi điều khiển. 30
2.1.3. Các bộ định thời 35
2.1.4. Bộ xử lý ngắt 37
2.2. Ngôn ngữ lập trình cho vi điều khiển 39


-5-

Danh môc c¸c ký hiÖu, c¸c ch÷ viÕt t¾t
STT Ch÷ viÕt t¾t Ch÷ ®Çy ®ñ
1 FCFS First Come First Served
2 FIFO First In First Out
3 LIFO Last In First Out
4 MCS Micro Controller System
5 OS Operating System
6 RTOS Real Time Operating System
7 RR Round Robbin
8 SJF Shortest Job First
9 SRT Shortest Remain Time
10 uC Micro Controller -6-

Danh môc c¸c b¶ng
B¶ng 1.1. Tr¹ng th¸i cña c¸c tiÕn tr×nh 19
B¶ng 1.2. Thêi gian thùc hiÖn cña c¸c tiÕn tr×nh 25
B¶ng 1.3. Thêi gian chê cña c¸c tiÕn tr×nh 25
B¶ng 2.1. Bé nhí d÷ liÖu trªn chÝp cña AT89S52 33
-7-


Hình 4.6. Chuyển giữa các tiến trình bằng sự kiện time out 73
Hình 4.7. Các tiến trình đợc phân bổ thời gian CPU khác nhau 74
Hình 4.8. Ngời sử dụng ra lệnh vào các thời điểm khác nhau 75
Hình 4.9. Chuyển giữa cá tiến trình bằng sự kiện interrupt 76
Hình 4.9. Mô tả trạng thái của các tài nguyên của tiến trình 77
Hình 4.10. Các tài nguyên cần lu khi dừng một tiến trình 78
Hình 4.11. Phân bổ ngăn xếp cho các tiến trình 79
Hình 4.12. Lập lịch cho 8 tiến trình thực hiện quét chữ trên ma trận LED 81
Hình 4.13. Lập lịch cho 4 tiến trình quét các số trên 4 LED 7 đoạn 81
Hình 4.14. Lập lịch cho tiến trình điều khiển LCD 82
Hình 4.15. Lập lịch cho tiến trình thời gian thực 82
Hình 4.16. Tổ chức bộ nhớ ROM của hệ vi điều khiển 83
Hình 4.17. Thay đổi vị trí đặt các chơng trình con phục vụ ngắt 84
Hình 4.18. Phân bổ bộ nhớ ROM 85
Hình 4.19. Phân bổ bộ nhớ RAM 85

-9-

Lời nói đầu
Cùng với sự phát triển của khoa học kỹ thuật, cụm từ tự động hoá đã trở
nên hết sức phổ thông. Từ các máy móc tự động trong các nhà máy xí nghiệp
thay thế cho sức lao động của công nhân, từ các đồ gia dụng tự động trong gia
đình giúp ích cho ngời nội trợ nói chung các thiết bị có khả năng tự động hoá
xuất hiện ở khắp mọi nơi. Một câu hỏi đặt ra với khá nhiều ngời là nhờ đâu mà
các thiết bị có khả năng tự động đợc? Để trả lời câu hỏi này chúng ta cần phải đi
từ khi có cụm từ tự động hoá ra đời.
Trớc kia, khi cha có công nghệ bán dẫn, các phần tử có tiếp điểm nếu
đợc đầu nối với nhau theo một mạch logic nào đó thì vẫn có thể tạo ra một hệ
thống tự động, tuy nhiên khả năng đáp ứng và tính tự động cả hệ thống này

Chơng 1: Giới thiệu tổng quan hệ điều hành.
Chơng 2: Giới thiệu bộ vi điều khiển đợc sử dụng để viết hệ điều hành và
ngôn ngữ lập trình cho vi điều khiển.
Chơng 3. Thiết kế phần cứng hệ vi điều khiển.
Chơng 4. Thiết kế hệ điều hành cho hệ vi điều khiển
Do thời gian và khả năng có hạn nên luận văn này sẽ còn nhiều thiếu sót.
Rất mong đợc sự góp ý và thông cảm của các thầy giáo, cô giáo.
Hà nội, ngày 30 tháng 10 năm 2006
Học viên

Vũ Trung Kiên
-11-

Chơng 1 - Tổng quan về hệ điều hành
1.1. Khái niệm về hệ điều hành (OS-Operating System)
1.1.1. Khái niệm
Khó có một khái niệm hay định nghĩa chính xác về hệ điều hành, vì hệ điều
hành là một bộ phận đợc nhiều đối tợng khai thác nhất, họ có thể là ngời sử
dụng thông thờng, có thể là lập trình viên, có thể là ngời quản lý hệ thống và
tuỳ theo mức độ khai thức hệ điều hành mà họ có thể đa ra những khái niệm
khác nhau.
Khái niệm 1: Hệ điều hành là hệ thống chơng trình với các chức năng giám
sát điều khiển việc thực hiện các chơng trình của ngời sử dụng quản lý và phân
chia tài nguyên cho nhiều chơng trình ngời sử dụng đồng thời sao cho việc
khai thác chức năng của hệ thống máy tính của ngời sử dụng là thuận lợi và hiệu
quả nhất.
Khái niệm 2: Hệ điều hành là một chơng trình đóng vai trò nh giao diện
giữa ngời sử dụng và phần cứng máy tính nó quản lý và điều khiển phần cứng
cũng nh sự thực hiện của tất cả các chơng trình.
Khái niệm thứ hai rất gần với các hệ điều hành đang sử dụng trên các máy

trình mới vào bộ nhớ thì hệ điều hành phải cấp phát không gian nhớ cho chơng
trình, tiến trình đó để chơng trình, tíên trình đó nạp đợc vào bộ nhớ và hoạt
động đợc. Trong môi trờng hệ điều hành đa nhiệm có thể có nhiều chơng
trình, tiến trình đồng thời cần đợc nạp vào bộ nhớ nhng không gian lu trữ củâ
bộ nhớ có giới hạn do đó hệ điều hành phải tổ chức cấp phát bộ nhớ sao cho hợp
lý để đảm bảo tất cả các chơng trình tiến trình khi cần để đợc nạp vào bộ nhớ
để hoạt động. Ngoài ra hệ điều hành còn phải tổ chức bảo vệ các không gian nhớ
đã cấp cho các chơng trình tiến trình để tránh sự truy cập bất hợp lệ và sự tranh
-13-

chấp bộ nhớ giữa các chơng trình, tiến trình, đặc biệt là các tiến trình đồng thời
hoạt động trên hệ thống. Đây là một trong những nhiệm vụ quan trọng của hệ
điều hành.
Trong quá trình hoạt động của hệ thống đặc bệt là các hệ thống đa ngời
dùng đa chơng trình, đa tiến trình. Còn xuất hiện một hiện tợng khác, đó là
nhiều chơng trình, tiến trình đồng thời sử dụng một không gian nhớ hau một tập
tin (dữ liệu, chơng trình) nào đó. Trong trờng hợp này hệ điều hành phải tổ
chức việc chia sẻ và giám sát việc truy xuất đồng thời trên các tài nguyên nói
trên sao cho việc sử dụng tài nguyên có hiệu quả nhng tránh đợc sự mất mát dữ
liệu và làm hỏng các tập tin.
Hai dẫn chứng điển hình giúp chúng ra thấy vai trò của hệ điều hành trong
việc quản lý tài nguyên hệ thống sau này chúng ra sẽ thấy việc cấp phát, chia sẻ,
bảo vệ tài nguyên của hệ điều hành là một trong những công việc khó khăn và
phức tạp nhất. Hệ điều hành đã chi phí nhiều cho công việc nói trên để đát đợc
mục tiêu: Trong mọi trờng hợp tất cả các chơng trình, tiến trình nếu cần đợc
cấp phát tài nguyên để hoạt động thì sớm muộn nó đều đợc cấp phát và đợc
đa vào trạng thái hoạt động.
1.1.3. Các thành phần của hệ điều hành
1.1.3.1. Thành phần quản lý tiến trình.
Hệ điều hành phải có nhiệm vụ tạo lập tiến trình và đa nó vào danh sách

Khi chơng trình, tiến trình có yêu cầu đợc nạp vào bộ nhớ thì hệ điều
hành phải cấp phát không gian nhớ cho nó. Khi chơng trình, tiến trình kết thúc
thì hệ điều hành phải thi hồi lại không gian nhớ đã cấp phát cho chơng trình,
tiến trình trớc đó.
-15-

Trong các hệ thống đa chơng hay đa tiến trình, trong bộ nhớ tồn tại nhiều
chơng trình/ nhiều tiến trình, hệ điều hành phải thực hiện nhiệm vụ bảo vệ các
vùng nhớ đã cấp phát cho các chơng trình/tiến trình, tránh sự vi phạm trên các
vùng nhớ của nhau.
Tóm lại, bộ phận quản lý bộ nhớ chính của hệ điều hành thực hiện những
nhiệm vụ sau:
Cấp phát, thu hồi vùng nhớ.
Chi nhận trạng thái bộ nhớ.
Bảo vệ bộ nhớ.
Quyết định tiến trình nào đợc nạp vào bộ nhớ.
1.1.3.3. Thành phần quản lý vào ra.
Một trong những mục tiêu của hệ điều hành là giúp ngời sử dụng khai thức
hệ thống máy tính dễ dàng và hiệu quả, do đó các thao tác trao đổi thông tin trên
thiết bị xuất / nhập phải trong suốt đối với ngời sử dụng.
Để thực hiện đợc điều này hệ điều hành phải tồn tại một bộ phận điều
khiển thiết bị, bộ phận này phối hợp cùng CPU để quản lý sự hoạt động và trao
đổi thông tin giữa hệ thóng, chơng trình ngời sử dụng và ngời sử dụng với các
thiết bị xuâts/nhập.
Bộ phận điều khiển thiết bị thực hiện những nhiệm vụ sau:
Gởi mã lệnh điều khiển đến thiết bị: Hệ điều hành điều khiển các thiết bị
bằng các mã điều khiển, do đó trớc khi bắt đầu một quá trình trao đổi dữ liệu
với thiết bị thì hệ điều hành phải gởi mã điểu khiển đến thiết bị.
Tiếp nhận yêu cần ngắt (Interrupt) từ các thiết bị khi cần trao đổi với hệ
thống khi nó phát ra một tín hiệu yêu cầu ngắt, hệ điều hành tiếp nhận yêu cầu

Hình 1.1. Các trạng thái của một tiến trình

Hệ điều hành quản lý hoạt động của các tiến trình trong hệ thống thông
qua khối mô tả tiến trình (process control block - PCB). Khối mô tả tiến trình bao
gồm các thành phần:
- Số thứ tự của tiến trình
- Con trỏ trạng thái của tiến trình (cho biết trạng thái hiện tại của tiến
trình).
- Vùng nhớ lu trữ giá trị các thanh ghi mà tiến trình đang sử dụng.
- Thông tin về tài nguyên tiến trình đang sử dụng hoặc đợc phép sử dụng.
1.2.2. Khái niệm về tài nguyên găng và đoạn tới hạn
Chúng ta cùng xem thuật toán sau:
Type
ltem
= ;
Var
Buffer
: array [0 n-1]
of ltem
;

In. Out: 0 n-1
Counter: 0 n


Repeat
While
Counter = 0
do
Skip;
NextC:= Buffer [Out];

Out:= Out + 1
mod
n
;

Lấy thông tin trong chứa trong NextC

Until
false
;
End;
Nhận xét: Vì hai tiến trình P và C song hành nên có thể xảy ra trờng hợp
trong cùng 1 thời điểm, tiến trình P tăng biến Counter lên 1 (Counter:= Counter
+ 1) còn tiến trình C lại giảm biến Counter đi 1 (Counter:= Counter 1) dẫn tới
kết quả sai. Nh vậy biến Counter trong trờng hợp này đợc gọi là tài nguyên
găng. Đoạn trình sử dụng biến Counter gọi là đoạn tới hạn.
Định nghĩa:
- Các tài nguyên logic và vật lý phân bổ cho các tiến trình song hành là tài
nguyên găng.
Các đoạn trình sử dụng tài nguyên găng gọi là đoạn tới hạn (Critical
Section).
-19-


) t
3

t
4
Wait (S
1
)
Nhận xét: Tại vị trí trên, sau thời điểm t
3
, tiến trình P
1
rơi vào trạng thái
chờ tài nguyên r
2
đang đợc P
2
sử dụng; Sau thời điểm t
4
, tiến trình P
2
rơi vào
trạng thái chờ tài nguyên r
1
đang đợc tiến trình P
1
sử dụng và bắt đầu từ đây, cả
hai tiến trình rơi vào trạng thái chờ đợi vô hạn về hệ thống gặp bế tắc.
Nh vậy bế tắc là trạng thái khi hai hoặc nhiều tiến trình cùng chờ đợi một
số sự kiện nào đó và nếu không có tác động đặc biệt từ bên ngoài thì sự chờ đợi
Hình 1.2. Các trạng thái của tiến trình liên quan đến giờ CPU
Read
y
Runin
g
Waitin
g
-21-

- Sẵn sàng (ready): Là trạng thái mà tiến trình đợc phân phối đầy đủ mọi
tài nguyên cần thiết và đang chờ giờ CPU.
- Thực hiện (running): Là trạng thái mà tiến trình đợc phân phối đầy đủ
mọi tài nguyên cần thiết và giờ CPU.
- Đợi (waiting): Là trạng thái tiến trình không thực hiện đợc vì thiếu một
vài điều kiện nào đó (đợi dữ liệu vào/ra, đợi tài nguyên bổ sung ). Khi sự kiện
mà nó chờ đợi xuất hiện, tiến trình sẽ quay trở lại trạng thái sẵn sàng.
Nh vậy, trong suốt thời gian tồn tại của mình, các tiến trình sẽ tuân thủ
theo sơ đồ thực hiện sau:
Hình 1.3. Sơ đồ thực hiện tiến trình

Một tiến trình đang trong trạng thái thực hiện, nó có thể rời khỏi trạng thái
bởi một trong ba lý do:

1.3.3. Lập lịch cho CPU
1.3.3.1. Khái niệm
Để điều khiển tiến trình ở nhiều trạng thái khác, hệ thống thờng tổ chức
các từ trạng thái (thực chất là các khối điều khiển tiến trình) để ghi nhận tình
trạng sử dụng tài nguyên và trạng thái tiến trình. Các từ trạng thái đợc tổ chức
theo kiểu đợi nh sau: Hình 1.4. Sơ đồ tổ chức hàng đợi các tiến trình

Nh vậy, lập lịch cho CPU có nghĩa là tổ chức một hàng đợi các tiến trình
sẵn sàng để phân phối giờ CPU cho chúng dựa trên độ u tiên của các tiến trình
sao cho hiệu suất sử dụng CPU là tối u nhất.
Mỗi tiến trình ở trạng thái sẵn sàng đợc gắn với một thứ tự u tiên. Thứ tự
u tiên này đợc xác định dựa vào các yếu tố nh: Thời điểm hình thành tiến
trình, thời gian thực hiện tiến trình, thời gian kết thúc tiến trình
nhật thông tin về thời gian đã thực hiện tiến trình. Đồng thời chế độ phân bổ lại
giờ CPU cũng phải đợc áp dụng nếu không sẽ làm mất tính u việt của thuật
toán.
4. Round Robin (RR)
Trong thuật toán này, hệ thống quy định một lợng tử thời gian (time
quantum) khoảng từ 10-100 mili giây. Mỗi tiến trình trong hàng đợi lần lợt đợc
phân phối một lợng tử thời gian để thực hiện. Sau khoảng thời gian đó, nếu tiến
trình cha kết thúc hoặc không rơi vào trạng thái đợi thì nó đợc chuyển về cuối
hàng đợi.
Hàng đợi các tiến trình đợc tổ chức theo kiểu vòng tròn và các tiến trình
luôn luôn đảm bảo đợc phục vụ. Khi có tiến trình mới phát sinh, nó sẽ đợc đa
-24-

vào hàng đợi vòng tròn và đợc đặt ở vị trí phục vụ ngay. Các tiến trình dù ngắn
hay dài đều có độ u tiên phục vụ nh nhau.
Trên thực tế, để đảm bảo độ u tiên cho các tiến trình dài, hệ thống sẽ
phân chia các tiến trình thành m lớp. Số lần đợc phục vụ và thời gian một lần
phục vụ tiến trình tại mỗi lớp khác nhau (giả sử ở lớp thứ i, tiến trình đợc phục
vụ k lần và mỗi lần với thời gian q
i
).
Nếu sau khoảng thời gian đã đợc phân phối mà tiến trình cha kết thúc
hoặc không bị ngắt thì nó đợc chuyển sang lớp thứ i+1 (với k
i+1
và q
i+1
lớn hơn).
Lợng từ thời gian sẽ tăng dần cho đến khi tiến trình rơi vào lớp ngoài cùng (lớp
m). ở đó nó sẽ đợc phục vụ với lợng tử q
m

Theo sơ đồ này chúng ta thấy thời chờ đợi của các tiến trình nh bảng 1.2.
Bảng 1.3. Thời gian chờ của các tiến trình

Processes T thực hiện T đợi
P1 24 6
P3 3 1
P1 3 7
Tổng 30 17
Dẫn đến thời gian chờ đợi trung bình của các tiến trình là 17/3 = 5.66
1.4. Quản lý bộ nhớ
1.4.1. Yêu cầu phải quản lý bộ nhớ
Bộ nhớ là thiết bị lu trữ duy nhất mà thông qua đó CPU có thể trao đổi
thông tin với môi trờng bên ngoài. Do vậy, nhu cầu tổ chức, quản lý bộ nhớ là
một trong những nhiệm vụ cơ bản hàng đầu của hệ điều hành. Bộ nhớ đợc tổ
chức nh mảng một chiều các từ nhớ (word), mỗi từ nhớ có một địa chỉ. Việc
trao đổi thông tin với môi trờng bên ngoài đợc thực hiện thông qua các thao tác
đọc/ghi dữ liệu vào một địa chỉ cụ thể nào đó trong bộ nhớ.