Font size
WorksheetsCPU Scheduling Fundamentals: Questions 1-18
Total questions: 107
Worksheet time: 54mins
Định thời CPU (CPU Scheduling) là gì?
Quản lý việc lưu trữ tiến trình trong bộ nhớ
Chọn tiến trình để cấp phát CPU tại một thời điểm
Quản lý các thiết bị ngoại vi
Giám sát hệ thống file
Trong hệ thống đa nhiệm (multitasking), mục đích của định thời CPU là:
Tăng khả năng lưu trữ của bộ nhớ
Tăng hiệu suất sử dụng CPU
Giảm số lượng tiến trình
Giảm dung lượng hệ điều hành
Bộ định thời short-term có nhiệm vụ:
Quyết định tiến trình nào được nạp vào hệ thống
Chọn tiến trình nào trong hàng đợi ready để thực thi tiếp theo
Quyết định chương trình nào được swap ra ngoài
Quản lý việc cấp phát bộ nhớ
Bộ định thời long-term dùng để:
Xác định tiến trình nào được cấp CPU kế tiếp
Quyết định chương trình nào được nạp vào hệ thống để thực thi
Giám sát I/O
Quản lý ngắt phần cứng
Bộ định thời medium-term có chức năng chính là:
Xác định chương trình được swap in/out khỏi bộ nhớ chính
Quản lý hàng đợi ready
Tính toán thời gian đáp ứng
Giám sát CPU burst
Hàng đợi ready (Ready Queue) chứa:
Các tiến trình đang bị block
Các tiến trình đang đợi để được cấp CPU
Các tiến trình đã kết thúc
Các tiến trình chưa được tạo
Khi một tiến trình đang thực thi và bị ngắt do yêu cầu I/O, nó được chuyển sang trạng thái:
Ready
Waiting
Running
New
“Dispatch latency” là:
Thời gian xử lý một tiến trình
Thời gian chuyển đổi CPU từ tiến trình này sang tiến trình khác
Thời gian tiến trình chờ trong hàng đợi
Thời gian CPU rảnh
Mục tiêu của định thời CPU hướng người dùng là:
Tối đa hóa thông lượng
Giảm thời gian đáp ứng và thời gian chờ
Tăng mức độ công bằng
Giảm chi phí hệ thống
“Turnaround time” nghĩa là:
Thời gian từ khi process bắt đầu chạy đến khi kết thúc
Thời gian chờ trong hàng đợi
Thời gian CPU thực sự xử lý process
Thời gian giữa hai lần cấp phát CPU
“Waiting time” là:
Tổng thời gian process chờ trong hàng đợi ready
Thời gian sử dụng CPU
Thời gian chờ nhập xuất I/O
Thời gian xử lý ngắt
“Response time” được hiểu là:
Thời gian từ lúc yêu cầu đến khi có phản hồi đầu tiên
Tổng thời gian hoàn tất process
Thời gian CPU rảnh
Thời gian xử lý trung bình
Một tiêu chuẩn định thời hướng hệ thống là:
Thời gian đáp ứng
Thời gian quay vòng
Tỉ lệ sử dụng CPU
Thời gian chờ
Mục tiêu “throughput” là:
Số lượng tiến trình kết thúc trong một đơn vị thời gian
Thời gian hoàn thành trung bình
Số lần chuyển ngữ cảnh
Tỉ lệ sử dụng bộ nhớ
Trong chế độ non-preemptive, một tiến trình:
Có thể bị ngắt bởi tiến trình khác
Thực thi đến khi kết thúc hoặc bị block
Bị dừng giữa chừng để ưu tiên process khác
Bị loại bỏ nếu thời gian xử lý quá lâu
Trong chế độ preemptive, một tiến trình:
Không thể bị ngắt khi đang chạy
Có thể bị ngắt và chuyển về trạng thái ready
Chạy liên tục đến khi hoàn tất
Luôn có độ ưu tiên thấp
Trong các sự kiện sau, khi nào bộ định thời CPU được kích hoạt?
Khi có ngắt clock
Khi process kết thúc
Khi process chuyển từ waiting sang ready
Tất cả các đáp án trên
Giải thuật FCFS là viết tắt của:
First-Come, First-Scheduled
First-Come, First-Served
First-CPU, First-Service
Fast-Cycle, Fast-Swap
Giải thuật SJF chọn tiến trình nào để cấp CPU?
Tiến trình có độ ưu tiên cao nhất
Tiến trình có thời gian CPU burst ngắn nhất
Tiến trình đến trước
Tiến trình sử dụng I/O nhiều nhất
Giải thuật Priority Scheduling dựa vào yếu tố nào để quyết định lịch?
Thứ tự đến của tiến trình
Thời gian CPU burst
Độ ưu tiên được gán cho mỗi tiến trình
Thời gian thực thi trung bình
Trong định thời non-preemptive, khi nào hàm định thời được gọi?
Khi process chuyển từ waiting sang ready
Khi process chuyển từ running sang waiting hoặc kết thúc
Khi có ngắt clock
Khi CPU rảnh
Trong định thời preemptive, khi nào hàm định thời được gọi?
Khi process chuyển từ running sang ready
Khi process chuyển từ waiting sang ready
Khi process kết thúc
Cả A và B
Ưu điểm chính của định thời preemptive là gì?
Giảm số lần chuyển ngữ cảnh
Cải thiện thời gian đáp ứng trong hệ thống tương tác
Dễ lập trình hơn non-preemptive
Giảm chi phí CPU
Nhược điểm của định thời preemptive là gì?
CPU có thể bị nhàn rỗi
Tăng chi phí chuyển ngữ cảnh
Không công bằng giữa các process
Không tương thích với I/O
Giải thuật FCFS sử dụng cấu trúc dữ liệu nào để quản lý tiến trình?
Stack
Queue FIFO
Tree
Priority Queue
Trong FCFS, tiến trình nào sẽ được cấp CPU trước?
Tiến trình có độ ưu tiên cao nhất
Tiến trình đến sớm nhất
Tiến trình có burst time nhỏ nhất
Tiến trình có PID nhỏ nhất
Giải thuật FCFS thuộc loại định thời nào?
Preemptive
Non-preemptive
Hybrid
Randomized
Một nhược điểm của FCFS là gì?
Gây ra hiện tượng "đói" (starvation)
Tiến trình đến sớm nhưng ngắn có thể bị chờ lâu do tiến trình dài
Cần tính toán độ ưu tiên phức tạp
Khó cài đặt
Giải thuật SJF được xem là tối ưu vì lý do nào sau đây?
Giảm số lần ngắt
Giảm thời gian đợi trung bình
Tăng số lượng tiến trình
Giảm CPU utilization
Điểm yếu chính của SJF là gì?
Cần biết trước thời gian CPU burst của mỗi tiến trình
Không xử lý được tiến trình dài
Không thể thực thi trong hệ điều hành đa nhiệm
Không hỗ trợ ngắt
SJF non-preemptive nghĩa là gì?
Khi tiến trình đang chạy, không bị ngắt giữa chừng
Khi tiến trình mới đến có burst nhỏ hơn, CPU chuyển ngay
CPU luôn chọn tiến trình ưu tiên
CPU không dùng hàng đợi ready
SRTF (Shortest Remaining Time First) là biến thể của giải thuật nào?
FCFS
Round Robin
SJF
Priority Scheduling
SRTF thuộc loại định thời nào?
Preemptive
Non-preemptive
Cả hai
Không thuộc loại nào
Trong SRTF, khi có tiến trình mới đến với thời gian còn lại nhỏ hơn tiến trình đang chạy, điều gì xảy ra?
Tiến trình mới bị chờ
Tiến trình đang chạy bị ngắt và quay lại ready queue
Tiến trình mới bị loại bỏ
Hệ điều hành dừng lại
Nhược điểm của SRTF là gì?
Không hỗ trợ các tiến trình dài
Có thể gây ra tình trạng starvation
Không hỗ trợ hệ thống tương tác
Không công bằng giữa các tiến trình
Giải thuật Priority Scheduling có thể hoạt động theo chế độ nào?
Chỉ preemptive
Chỉ non-preemptive
Cả preemptive và non-preemptive
Không thuộc hai loại trên
Trong Priority Scheduling, nếu có nhiều tiến trình có cùng độ ưu tiên, ta sẽ chọn như thế nào?
Chọn tiến trình đến trước (theo FCFS)
Chọn tiến trình có PID nhỏ nhất
Chọn tiến trình có burst nhỏ nhất
Chọn ngẫu nhiên
Trong Priority Scheduling, hiện tượng "starvation" xảy ra khi nào?
Tiến trình có ưu tiên thấp không bao giờ được cấp CPU
CPU không sử dụng
Quá nhiều tiến trình I/O-bound
Quá nhiều tiến trình CPU-bound
“Aging” trong định thời ưu tiên có nghĩa là gì?
Làm giảm độ ưu tiên theo thời gian
Làm tăng độ ưu tiên của tiến trình chờ lâu
Giữ nguyên độ ưu tiên
Ngắt tiến trình sau thời gian cố định
SJF có thể được xem là một dạng của Priority Scheduling nếu tiêu chí ưu tiên dựa vào đâu?
Mức ưu tiên gán ngẫu nhiên
Thời gian CPU burst dự đoán
Tất cả tiến trình có cùng ưu tiên
PID của tiến trình
Công thức tính waiting time là gì?
Completion Time – Arrival Time
Turnaround Time – Burst Time
Response Time – Arrival Time
Burst Time – Turnaround Time
Công thức tính turnaround time là gì?
Completion Time – Arrival Time
Waiting Time – Burst Time
Response Time + Waiting Time
Arrival Time – Completion Time
Trong FCFS, tiến trình có Arrival Time nhỏ nhất sẽ được xử lý thế nào?
Được chọn sau cùng
Được cấp CPU đầu tiên
Bị loại khỏi hàng đợi
Bị chuyển sang trạng thái waiting
Cho P1 (Burst = 5) và P2 (Burst = 3) đến cùng lúc. Theo FCFS, tiến trình nào chạy trước?
P1
P2
Tiến trình có burst nhỏ hơn
Tiến trình có PID nhỏ hơn
Cho các tiến trình: P1(A=0,B=4), P2(A=1,B=3), P3(A=2,B=1). Theo SJF không chiếm quyền, tiến trình nào chạy đầu tiên?
P1
P2
P3
Không xác định
Với dữ kiện trên, tiến trình chạy thứ hai là tiến trình nào theo SJF không chiếm quyền?
P1
P2
P3
Không xác định
Trong SRTF, khi một tiến trình mới có thời gian còn lại nhỏ hơn tiến trình hiện tại, điều gì xảy ra?
Tiến trình mới bị chờ
CPU lập tức chuyển sang tiến trình mới
Hai tiến trình chạy song song
Hệ điều hành ngắt tiến trình mới
Ưu điểm chính của SRTF so với SJF không chiếm quyền là gì?
Không có ngắt
Giảm waiting time cho tiến trình ngắn mới đến
Không cần biết burst time
Giảm số tiến trình
Cho các tiến trình: P1(A=0,B=8), P2(A=1,B=4), P3(A=2,B=2). Theo SRTF, tại thời điểm t=2 tiến trình nào chạy?
P1
P2
P3
Cả hai
Trong Priority Scheduling, tiêu chí chọn tiến trình đầu tiên là gì?
Có burst nhỏ nhất
Có độ ưu tiên cao nhất
Đến trước
Có PID nhỏ nhất
Trong Priority Scheduling, nếu giá trị số nhỏ hơn thể hiện ưu tiên cao hơn, tiến trình có priority = 1 sẽ:
Được cấp CPU sau cùng
Được cấp CPU trước tiên
Bị loại bỏ
Chờ đến khi CPU rảnh
Ưu điểm chính của Priority Scheduling là:
Linh hoạt khi xử lý tiến trình khẩn
Giảm chi phí CPU
Không cần quản lý hàng đợi
Không bị starvation
Hiện tượng starvation xảy ra khi:
CPU quá tải
Tiến trình có ưu tiên thấp không bao giờ được xử lý
CPU không có tiến trình để chạy
Không đủ bộ nhớ để swap
Giải pháp khắc phục starvation là:
Aging
Dispatch latency
SJF
FCFS
Trong thuật toán Aging, độ ưu tiên của tiến trình:
Giảm dần theo thời gian
Tăng dần theo thời gian chờ
Giữ nguyên
Ngẫu nhiên thay đổi
Giải thuật FCFS phù hợp nhất cho loại hệ thống nào?
Time-sharing
Batch processing (xử lý theo lô)
Real-time
Interactive
Giải thuật SRTF phù hợp với hệ thống:
Time-sharing (chia sẻ thời gian)
Batch
Real-time cứng
Đơn nhiệm
Giải thuật Priority Scheduling preemptive có thể gây ra vấn đề:
Deadlock
Starvation
CPU idle
Aging lỗi
Tiêu chí nào không thuộc nhóm hướng người dùng (user-oriented)?
Response time
Waiting time
Processor utilization
Turnaround time
Tiêu chí Processor Utilization mong muốn đạt giá trị:
Càng nhỏ càng tốt
Càng lớn càng tốt
Luôn bằng 100%
Tùy thuộc vào hệ điều hành
Trong các tiêu chí sau, tiêu chí nào hướng hệ thống?
Fairness (Công bằng)
Waiting time
Response time
Turnaround time
Khi CPU bận liên tục, giá trị throughput sẽ:
Giảm xuống
Không thay đổi
Tăng lên
Bằng 0
Trong FCFS, tiến trình dài chạy trước có thể khiến các tiến trình ngắn phải chờ lâu. Hiện tượng này gọi là:
Starvation
Convoy effect
Aging
Deadlock
Trong SJF, nếu các tiến trình có cùng thời gian CPU burst, thuật toán sẽ hoạt động giống với:
Priority Scheduling
FCFS
SRTF
Round Robin
Để SJF hoạt động, hệ thống cần biết:
Thời điểm tiến trình hoàn thành
Thời gian CPU burst của tiến trình
Số lượng I/O request
PID của tiến trình
Khi không biết CPU burst trong tương lai, có thể ước lượng bằng:
Trung bình cộng
Trung bình hàm mũ (Exponential Averaging)
Trung bình cộng có trọng số
Tích lũy tuyến tính
Trong công thức dự đoán CPU burst bằng Exponential Averaging, trọng số alpha (α) càng gần 1 thì dự đoán sẽ:
Ít nhạy với burst gần nhất
Phụ thuộc nhiều vào lịch sử xa
Phụ thuộc nhiều vào burst gần nhất
Không thay đổi so với α
Trong công thức dự đoán CPU burst: τ(n+1)=α·t(n)+(1−α)·τ(n), khi α càng lớn thì điều gì đúng nhất?
Dữ liệu cũ được coi trọng hơn
Dữ liệu mới được coi trọng hơn
Cả hai bằng nhau
Kết quả không thay đổi
Theo công thức τ(n+1)=α·t(n)+(1−α)·τ(n), nếu α=0.5 thì ý nghĩa là gì?
Dự đoán dựa hoàn toàn vào giá trị trước
Giá trị mới và cũ được coi trọng như nhau
Dữ liệu cũ bị bỏ qua
Sai số bằng 0
Trong Priority Scheduling, độ ưu tiên có thể xác định dựa trên yếu tố nào sau đây?
Burst time
Số lượng file mở
Thời gian I/O
Cả ba yếu tố trên
Khi nhiều tiến trình ưu tiên cao xuất hiện liên tục, tiến trình ưu tiên thấp dễ gặp vấn đề gì?
Chạy bình thường
Bị bỏ qua (starvation)
Được ưu tiên theo FCFS
Chạy xen kẽ
Giải pháp Aging trong lập lịch ưu tiên chủ yếu nhằm mục tiêu nào?
Giảm hiệu năng CPU
Ngăn chặn starvation
Giảm số tiến trình trong hàng đợi
Rút ngắn burst time
Trong hệ thống tương tác, thuật toán định thời được dùng phổ biến nhất là gì?
FCFS
SJF
Round Robin (RR)
Priority không tiền quyền
Đặc điểm chính của Round Robin là gì?
Cấp CPU theo độ ưu tiên
Cấp CPU lần lượt theo lát thời gian (time quantum)
Cấp CPU cho tiến trình dài trước
Không có ngắt thời gian
Khi time quantum của Round Robin quá nhỏ, hệ thống sẽ thế nào?
Giảm overhead
Tăng số lần chuyển ngữ cảnh
Giảm thời gian đáp ứng
Chạy nhanh hơn
Khi time quantum quá lớn, hành vi của Round Robin trở nên giống thuật toán nào?
SJF
FCFS
Priority
SRTF
Trong Round Robin, thời gian đáp ứng trung bình thường như thế nào so với SJF?
Cao hơn SJF
Thấp hơn SJF
Bằng FCFS
Bằng 0
Thuật ngữ dispatch latency đề cập đến điều gì?
Thời gian CPU xử lý tiến trình
Thời gian chuyển đổi CPU giữa các tiến trình
Thời gian CPU nghỉ
Thời gian chờ trung bình
Với cùng dữ liệu trên, theo FCFS, thời gian quay vòng trung bình (turnaround time) là bao nhiêu?
4
5
6
7
Với dữ liệu trên, nếu dùng SJF non-preemptive, tiến trình nào chạy đầu tiên?
P1
P2
P3
Khi P1 kết thúc (t=5), trong hàng đợi có P2 và P3. Theo SJF non-preemptive, tiến trình nào được chọn tiếp?
P2
P3
Với cùng dữ liệu, thời gian chờ trung bình của SJF non-preemptive là bao nhiêu?
2
3
4
1.3
Với dữ kiện SRTF ở câu trên, vì sao thời gian chờ trung bình của SRTF thường nhỏ hơn FCFS?
CPU sử dụng nhiều hơn
Tiến trình ngắn được ưu tiên xử lý trước
Không có chuyển ngữ cảnh
Không có preemptive
Với dữ kiện Priority non-preemptive ở trên, thứ tự chạy là gì?
P1 → P2 → P3
P2 → P1 → P3
P3 → P2 → P1
Cho 3 tiến trình: P1: Burst=10, Priority=3; P2: Burst=1, Priority=1; P3: Burst=2, Priority=2. Với Priority preemptive, tại t=0 P1 bắt đầu; tại t=1 P2 đến. Điều gì xảy ra?
P1 tiếp tục chạy
P1 bị ngắt, P2 chiếm CPU
P3 chạy
Cả 3 cùng chạy
Giải thuật nào có khả năng gây ra starvation nhiều nhất?
FCFS
SJF
Priority
RR
Giải thuật nào ít có khả năng starvation nhất?
FCFS
Priority
SJF
SRTF
Cho Round Robin với quantum = 4 và các burst: P1=24, P2=3, P3=3. Thứ tự thực thi ban đầu là gì?
P1 → P2 → P3
P2 → P3 → P1
P3 → P2 → P1
Với dữ kiện Round Robin ở trên (quantum=4), sau khi hoàn thành vòng đầu tiên, P1 còn lại bao nhiêu thời gian CPU?
4
12
16
20
Ưu điểm chính của Round Robin là gì?
Đơn giản, công bằng giữa các tiến trình
Ưu tiên tiến trình dài
Không có overhead
Giảm số lần context switch
Nhược điểm chính của Round Robin là gì?
Không công bằng
Tăng overhead do nhiều context switch
Chạy tiến trình dài trước
Không có preemption
Khi quantum = 1 ms, hệ thống Round Robin có thể đạt điều gì?
Giảm thời gian đáp ứng nhưng tốn chi phí ngữ cảnh cao
Tăng throughput
Giảm waiting time
Không bị trễ
Khi quantum quá lớn, vì sao Round Robin sẽ giống FCFS?
CPU không chuyển ngữ cảnh thường xuyên
Tất cả tiến trình có cùng độ ưu tiên
Không có tiến trình ngắn
Chạy lần lượt theo PID
Khi chọn time quantum cho Round Robin (RR), cần đảm bảo điều gì để cân bằng phản hồi nhanh và overhead thấp?
Lớn hơn mọi burst time
Vừa đủ để mỗi tiến trình được phản hồi nhanh mà overhead không cao
Càng nhỏ càng tốt
Cố định cho mọi hệ thống
Giải thuật nào có thời gian chờ trung bình tối thiểu (về mặt lý thuyết)?
FCFS
SJF
SRTF
Priority
SRTF là phiên bản mở rộng của giải thuật nào?
SJF
FCFS
RR
Priority
Nếu hệ thống ưu tiên tiến trình I/O-bound hơn CPU-bound, nên chọn giải thuật nào?
FCFS
SJF hoặc SRTF
Round Robin
Priority không ưu tiên gián đoạn (nonpreemptive)
Trong thực tế, SJF không thể triển khai hoàn hảo vì lý do chính nào?
Không biết trước thời gian CPU burst của process
Không có hàng đợi ready
Không thể đo thời gian đáp ứng
CPU không hỗ trợ preemptive
Giải thuật nào phù hợp nhất cho hệ thống chia sẻ thời gian (time-sharing)?
FCFS
SJF
Round Robin
Priority không ưu tiên gián đoạn
Giải thuật nào dễ gây ra hiện tượng Convoy Effect?
SJF
FCFS
RR
Priority
Trong SRTF, nếu hai tiến trình có thời gian còn lại bằng nhau, hệ thống thường chọn tiến trình nào?
Đến sớm hơn
Có PID lớn hơn
Có độ ưu tiên thấp hơn
Ngẫu nhiên
Trong hệ thống có nhiều người dùng, mục tiêu quan trọng nhất của định thời CPU là gì?
Tối thiểu hoá turnaround time
Cân bằng giữa thời gian đáp ứng và công bằng
Giảm CPU utilization
Giảm thời gian I/O
Khi CPU thường xuyên phải ngắt để chuyển ngữ cảnh, điều đó cho thấy điều gì về quantum?
Quantum quá lớn
Quantum quá nhỏ
CPU utilization cao
Không có tiến trình ready
Round Robin cho hiệu quả tốt nhất khi điều kiện nào đúng?
Quantum được chọn hợp lý
Quantum cực nhỏ
Quantum cực lớn
CPU-bound chiếm đa số
Trong định thời Priority non-preemptive, khi một tiến trình ưu tiên cao đến trong lúc CPU đang bận, điều gì xảy ra?
CPU ngắt tiến trình hiện tại
Tiến trình mới phải chờ
CPU chia đều thời gian
Tăng quantum cho tiến trình mới
Trong Priority preemptive, tiến trình đang chạy có thể bị ngắt khi:
CPU rảnh
Có tiến trình khác với độ ưu tiên cao hơn đến
Burst time đã hết
Không có tiến trình trong ready queue
Giải thuật nào có thời gian đáp ứng thấp nhất trong hệ thống tương tác?
FCFS
RR (với quantum nhỏ)
Priority non-preemptive
SJF
