OS_운영체제 카테고리의 PE Series는
2021.10.20 - [학부공부/OS_운영체제] - 00. 운영체제 STUDY 시작
00. 운영체제 STUDY 시작
안녕하세요! 제가 티스토리 페이지를 만든 후 처음으로 작성하는 글입니다... 복학하기 전 개인적인 공부를 정리하자는 취지로 시작하는 글이라 가독성이 떨어지고 부족한 부분이 있을 수 있으
ku320121.tistory.com
포스팅에서 소개한 text book의 연습문제를 풀이한 것을 정리한 것입니다. 해설을 참고하지 않았기 때문에 풀이에 오류가 있을 수 있습니다. 또한 운영체제 교과목 내용을 벗어나는 내용과 사견이 풀이에 포함되어 있을 수 있습니다.
10.2. Assume that you have a page-reference string for a process with m frames (initially all empty). The page-reference string has length p, and n distinct page numbers occur in it. Answer these questions for any page-replacement algorithms:
a. What is a lower bound on the number of page faults?
b. What is an upper bound on the number of page faults?
n. page fault의 하한은 page-reference의 고유한 page 수와 같다. 적어도 m개의 frame이 할당되었다고 가정한다면 HDD에서 memory로의 load는 모든 page에 대해 최초 1번 발생한다.(물론 locality등을 고려한다면 더 줄어들지만 수업시간에 배운 순수 page replacement algorithm(FIFO, Optimal etc)은 page fault 하한 n을 가진다.)
p. page replacement algorithm의 page fault 상한은 page-reference length와 같다. 해당 process에 1개의 frame만 할당되었을 때를 가정하면 된다.
10.4. An operating system supports a paged virtual memory. The central processor has a cycle time of 1 microsecond. It costs an additional 1 microsecond to access a page other than the current one. Pages have 1,000 words, and the paging device is a drum that rotates at 3,000 revolutions per minute and transfers 1 million words per second. The following statistical measurements were obtained from the system:
• One percent of all instructions executed accessed a page other than the current page.
• Of the instructions that accessed another page, 80 percent accessed a page already in memory
• When a new page was required, the replaced page was modified 50 percent of the time.
Calculate the effective instruction time on this system, assuming that the system is running one process only and that the processor is idle during drum transfers
EAT = P(!page fault) memory access + P(page fault) (page fault overhead + swap page out + swap page in)
10.5. Consider the page table for a system with 12-bit virtual and physical addresses and 256-byte pages
The list of free page frames is D, E, F (that is, D is at the head of the list, E is second, and F is last). A dash for a page frame indicates that the page is not in memory.
Convert the following virtual addresses to their equivalent physical addresses in hexadecimal. All numbers are given in hexadecimal.
• 9EF
• 111
• 700
• 0FF
10.8. Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.
How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, six, and seven frames? Remember that all frames are initially empty, so your first unique pages will cost one fault each.
• LRU replacement
• FIFO replacement
• Optimal replacement
위와 같은 reference string이 주어졌을 때 1개의 frame을 사용한다면 어떤 algorithm이든 reference string의 길이만큼 page fault가 발생한다. 반대로 reference string에 주어지는 distinct page수만큼 frame이 주어진다면 page fault는 distinct page 수만큼 발생한다.
| LRU | FIFO | Optimal | |
| 1 | 20 | 20 | 20 |
| 2 | 18 | 18 | 15 |
| 3 | 15 | 16 | 11 |
| 4 | 10 | 14 | 8 |
| 5 | 8 | 10 | 7 |
| 6 | 7 | 10 | 7 |
| 7 | 7 | 7 | 7 |
10.9. Consider the following page reference string: 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0 , 1.
Assuming demand paging with three frames, how many page faults would occur for the following replacement algorithms?
• LRU replacement
• FIFO replacement
• Optimal replacement
18, 17, 13
10.13. Consider a demand-paged computer system where the degree of multiprogramming is currently fixed at four. The system was recently measured to determine utilization of the CPU and the paging disk. Three alternative results are shown below. For each case, what is happening?
Can the degree of multiprogramming be increased to increase the CPU utilization? Is the paging helping?
a. CPU utilization 13 percent; disk utilization 97 percent
b. CPU utilization 87 percent; disk utilization 3 percent
c. CPU utilization 13 percent; disk utilization 3 percent
CPU utilization과 disk utilization은 application의 feature(memory intensive or computation intensive)에 따라 격차가 클 수 있으나 동일한 환경이라고 가정한다면 CPU utilization이 과도하게 낮고 disk utilization이 과도하게 높다면 thrashing이 발생한 것이다. Thrashing은 충분한 page를 process가 보장받지 못해 page fault rate가 높은 상태를 의미한다. 따라서 a의 상황에서 OS는 multiprogramming degree를 낮추는 것은 고려해볼 수 있다. 반대의 경우는 multiprogramming degree를 높여 더 많은 process들이 disk에 access하여 I/O bus의 bandwidth를 충분히 사용하도록 할 수 있다. 따라서 c의 경우 multiprogramming degree를 높이면 되고 b는 CPU utilization을 높이지 않으면서 disk utilization을 높일 수 있는 memory intensive application을 우선적으로 추가 실행하여 multiprogramming degree를 높이는 방향으로 OS가 개입할 수 있다.
11.1. Is disk scheduling, other than FCFS scheduling, useful in a single-user environment? Explain your answer.
FCFS는 request 시점 순서대로 처리하기 때문에 response time을 예측하기 편리하다. 하지만 다른 algorithm은 일정 시점동안의 request를 queue에 넣어두고 sorting하는 방식으로 동작하기 때문에 FCFS보다 response time을 예측하기 어렵다. 따라서 response time 예측 측면과 적은 수의 request 요청을 유지하는 상태라면 FCFS가 유리하다. 다만, 낮은 priority를 가지고 background에서 수행되는 batch program과 다수의 사용자 실행 memory intensive application이 실행될 경우 C-SCAN, LOOK등 다른 scheduling이 유리할 수 있다.
11.2. Explain why SSTF scheduling tends to favor middle cylinders over the innermost and outermost cylinders.
SSTF(Shortest Seek Time First)은 head로부터 가장 가까운 track으로 이동시키는 scheduling 기법이다. 가장 바깥쪽이나 안쪽 cylinder에서 다른 track으로 이동하는 것보다 중간 cylinder에서 다른 track으로 이동하는 것이 더 빠르기 때문이다. 이는 수학적으로도 증명이 가능하다. 단순히 track 사이 거리와 cost(time)가 비례한다고 가정하면 적분을 이용하여 증명할 수 있다.(조금 더 정확한 증명을 위해서 track과 spindle의 거리에 따른 sector의 수도 고려해야 할 것이다.)
11.3. Why is rotational latency usually not considered in disk scheduling? How would you modify SSTF, SCAN, and C-SCAN to include latency optimization?
rotation time에 비해 seek time의 scale이 더 크기 때문이다. 물리적으로 생각해보아도 rotation은 spindle을 중심으로 platter를 회전시키면 되지만 seek time은 arm을 이동시키는 시간으로 seek time이 더 크다. 실제 query processing 과정에서 block transfer time과 seek time을 고려하는 이유가 거기에 있다. 또한 원하는 data가 같은 track의 인접한 sector에 저장되어있다면(실제 되도록이면 연속적으로 저장되도록 한다) rotational latency는 그리 중요한 factor가 아닐 수 있다.
11.8. Could a RAID level 1 organization achieve better performance for read requests than a RAID level 0 organization (with nonredundant striping of data)? If so, how?
향상시킬 수 있다. RAID 0는 non-redundant striping으로 file을 쪼개어 저장한다. RAID 1은 mirrored disk로 Master disk에 먼저 write하고 mirrored disk에 write하는 방식으로 동작한다. 만약, master disk에서 resource contention이 발생할 경우 RAID 1은 mirrored disk에 접근하여 읽어올 수 있다. resource contention이 발생하는 경우가 가장 큰 performance gain을 얻을 수 있고 head의 위치에 따라 RAID 1은 선택할 수 있다는 점 또한 근소한 performance gain을 부여한다.
댓글