os 기말문제

다음중 프로세스간 동기화를 구현하기 위해 사용되는 동기화 메커니즘이 아닌것은?

(7장 메모리관리) 논리-물리주소 변환과정을 풀이

프로그램을 하드웨어에서 relocation하기 위해서는 base register와 offset 사용

100번지에서 시작한다면 100번지를 base register에 넣고

relative address가 5번지라면

adder가 더해서 105번지

bound register가 경계값을 가지고 있다가 경계를 넘어가면 interrupt발생시켜서 종료

경계보다 작거나 같다면 data에 access하도록

서술형으로 메모리관리 관련해서 fifo, clock등 페이지 폴트 발생 그림 과정 그리기

clock 알고리즘 테이블 그리기

fifo, lru, 최적 테이블 그리는 문제

네트워크 프로토콜에는 syntax, timing , _______ 이 있다

semantics

다음에 해당되는 RAID는 __ level이다 (숫자만 쓰기)

해당하는 유니프로세서 스케줄링은 무엇인가?

____의 주요장점은. 동일한 프로세스 내에서 다른 하나의 스레드에서 컨트롤의 전송을 하는 경우, 커널 모드로의 전환이 필요없다는 것이다.

유저 수준 스레드

다양한 크기의 메모리들로 분할하는 메인 메모리 관리 기술은 _______

세그멘테이션

페이징의 문제점은 _____ 이다

내부파편화

각 프로세스의 페이지 테이블은 _______을 저장합니다.

프레임 번호

OPT vs LRU vs FIFO

OPT (Optimal):가장 나중에 사용될 페이지를 교체.

LRU (Least Recently Used):가장 오래 사용되지 않은 페이지를 교체.

FIFO (First-In, First-Out):가장 먼저 들어온 페이지를 교체.

SPN - SPN은 짧은 프로세스를 우선하여 스케줄링하는 방식

디스크 스케줄링

FCFS (First-Come, First-Served)

SSTF (Shortest Seek Time First)

SCAN (Elevator)

C-SCAN (Circular SCAN)

LOOK

C-LOOK

1. 메모리 관리

a. 동적 파티셔닝에서 사용되는 세 가지 배치 알고리즘을 나열하세요. 이 중 어느 것이 가장 좋은가요?

best-fit - 요구되는 메모리블럭에 가장 근접한 메모리 할당, 내부파편화 최소화

first-fit - 사용할수 있는 첫번째 공간에 할당, 메모리 파편화

next-fit - 마지막 할당한 메모리공간 다음것을 찾아서 할당

b. 간단한 페이징 시스템을 고려하세요. 물리적 메모리 크기 = 2^31 바이트 페이지 크기 = 2^13 바이트 논리 주소에 몇 비트가 있나요? 각 페이지 테이블 항목에 몇 비트가 있나요? 각 페이지 테이블 항목에는 유효/무효 비트가 포함되어 있다고 가정합니다.

페이지수 = 2^31/2^13 = 2^18, 논리주소는 18비트

페이지 프레임 번호는 2^18

페이지프레임번호 표현 18비트 + 유효/무효 비트 1 = 각 페이지 테이블 항목 19비트

2. 가상 메모리

a. 각 프로세스는 자체 페이지 테이블이 필요합니다. 가상 메모리가 2GB이고, 페이지 크기는 1KB입니다. 각 페이지 항목의 크기는 4바이트입니다. 주 메모리에 10개의 프로세스가 활성화되어 있습니다. 페이지 테이블에 의해 주 메모리에 차지되는 최대 페이지 수를 계산하세요.

가상 메모리 크기 = 2^31바이트

페이지크기 = 2^10 바이트

각 페이지 테이블 항목 크기 = 4바이트

페이지수 = 2^31/2^10 = 2^21

각 페이지 테이블 크기 = 2^21 x 4바이트 = 2^23바이트

주 메모리에 활성화된 10개의 프로세스에 의해 차지되는 최대 페이지 수 = 10 x 2^23바이트 = 10 x 8 x 2^20바이트 = 80 MB

최대 페이지 수 = 80 x 2^20바이트 / 1024바이트(1KB) = 80 x 2^10 = 81920

b. 각 프로세스의 가상 메모리 공간과 독립적으로 페이지 테이블의 크기를 사용할 수 있는 대안 접근 방식을 제안하고, 이 접근 방식이 어떻게 작동하는지 설명하세요.

Multi-level page table을 쓸수 있다 - 페이지 테이블을 여러 레벨로 나누어 각 레벨에서 페이지 테이블 항목이 또 다른 페이지 테이블을 가리키게 합니다. 이 접근 방식은 페이지 테이블의 크기를 줄여주며, 가상 메모리 공간의 크기에 상관없이 일정한 크기의 페이지 테이블을 유지할 수 있게 합니다.

3. 프로세서 스케줄링

a. I/O 중심 프로세스는 왜 다단계 피드백 큐 스케줄링에서 일반적으로 선호되는가요?

다단계 피드백 큐 스케줄링은 프로세스의 실행 시간을 기반으로 여러 큐에 프로세스를 분배합니다. I/O 중심 프로세스는 일반적으로 짧은 CPU 시간을 요구하고 빠르게 I/O 작업을 수행합니다. 다단계 피드백 큐는 이러한 짧은 작업을 빠르게 처리하여 I/O 중심 프로세스가 CPU를 신속히 차지하고 곧바로 I/O 작업을 수행할 수 있도록 도와줍니다.

b. 아래 표를 사용하여, 모든 작업이 비율 모놀리틱 스케줄링(RMS) 알고리즘에 의해 성공적으로 스케줄될 것인지 입증하거나 입증하지 못하세요.

비율 모놀리틱 스케줄링은 주기적인 작업의 우선순위를 주기의 역수에 따라 부여하는 고정 우선순위 알고리즘입니다. 각 작업의 실행 시간과 주기를 이용하여 RMS 스케줄링이 가능한지 확인할 수 있습니다.

주어진 작업 정보

• T0: 실행 시간 = 10, 주기 = 100
• T1: 실행 시간 = 20, 주기 = 160
• T2: 실행 시간 = 40, 주기 = 200
• T3: 실행 시간 = 70, 주기 = 350

RMS 스케줄링 가능성 확인

RMS에서 작업이 스케줄될 수 있는지 확인하려면, 각 작업의 CPU 이용률을 계산하고 총 이용률이 한도를 초과하지 않는지 확인해야 합니다.

각 작업의 이용률 $U_i$는 다음과 같이 계산됩니다:

$$U_i = \frac{\text{실행 시간}}{\text{주기}}$$

각 작업의 이용률:

• $U_0 = \frac{10}{100} = 0.1$
• $U_1 = \frac{20}{160} = 0.125$
• $U_2 = \frac{40}{200} = 0.2$
• $U_3 = \frac{70}{350} = 0.2$

총 이용률:

$$U = U_0 + U_1 + U_2 + U_3 = 0.1 + 0.125 + 0.2 + 0.2 = 0.625$$

허용 이용률 한도

주어진 작업이 4개이므로, RMS에서 허용되는 최대 이용률 $U_{max}$는 다음과 같습니다:

$$U_{max} = 4 \left(2^{\frac{1}{4}} - 1\right) \approx 0.756$$

결론

총 이용률 $0.625$가 허용 한도 $0.756$보다 작으므로, 주어진 작업은 비율 모놀리틱 스케줄링(RMS) 알고리즘에 의해 성공적으로 스케줄될 수 있습니다.

4. I/O 관리 및 디스크 스케줄링

a. N-Step-SCAN 정책은 SSTF, SCAN 및 C-SCAN의 "팔 막힘 문제"를 해결하기 위한 접근 방식으로 제안되었습니다. 이 정책이 어떻게 문제를 해결할 수 있는지 설명하세요.

N-Step-SCAN 정책은 디스크 요청을 N개의 고정된 그룹으로 나누고 각 그룹을 별도로 처리합니다. 이를 통해 각 그룹이 독립적으로 스캔되어 "팔 막힘 문제"를 줄일 수 있습니다. 즉, 디스크 팔이 특정 위치에 오래 머무르지 않게 하여 디스크 효율성을 높입니다.

b. N-Step-SCAN 접근 방식이 FIFO 정책의 성능에 접근할 때는 언제인가요?

N-Step-SCAN 정책은 요청이 매우 적거나 각 단계 그룹이 하나의 요청만 포함할 때 FIFO 정책의 성능에 접근할 수 있습니다. 이는 모든 요청이 순서대로 처리되어 추가적인 최적화가 필요 없을 때 발생합니다.

c. N-Step-SCAN 정책이 문제를 완전히 해결하지 못하기 때문에 FSCAN 정책이 대안으로 제안되었습니다. 이 정책이 어떻게 작동하는지 설명하세요.

FSCAN 정책은 N-Step-SCAN의 단점을 해결하기 위해 제안되었습니다. FSCAN은 현재 서비스 중인 요청과 새로운 요청을 별도로 유지하여 두 개의 대기열을 사용합니다. 첫 번째 대기열은 현재 요청을 처리하고, 두 번째 대기열은 새로운 요청을 수집합니다. 이 방식으로 디스크 팔이 멈추는 것을 방지하고 더 효율적으로 디스크 요청을 처리할 수 있습니다.

-------------

1. About Memory Management 

a. 

List three placement algorithms used in dynamic partitioning. Which one is best? 

b. 

Consider simple paging system. 

Size of physical memory = 231 bytes 

Size of page = 213 bytes 

How many bits are in logical address? How many bits are in each table entry? 

Assume each page table entry contain valid/invalid bit. 

2. About Virtual Memory 

a. 

Each process needs own page table. 

We have 2GB virtual memory, 1KB page. Each page entry size is 4 bytes. 

10 process active in main memory. 

Calculate the maximum number of pages in main memory occupied by the page tables. 

b. 

Suggest an alternative approach the use of page tables so the size of table can be independent of 

that Virtual Memory space of each process and explain how this approach works. 

3. About Processor Scheduling 

a. 

I/O bound processes are generally favored by a Multi-Level Feedback Queue scheduling. Why? 

b. 

Using the tables below, prove or disprove that all tasks will be successfully scheduled by rate 

monotonic scheduling (RMS) algorithm.

4. About I/O Management & Disk Scheduling 

a. 

0.756 

0.743 

0.734 

N-Step-SCAN policy has been proposed as and approach to resolve the “arm stickiness problem” 

of SSTF, SCAN and C-SCAN. How does it can resolve it? 

b. 

When may the performance of N-Step-SCAN approach to that of the FIFO policy? 

c. 

Since N-Step-SCAN policy can not resolve the problem completely. FSCAN policy has been proposed 

as and alternative. How?

------------------

시험에 나왔던 문제

객관식은 무난

주관식은 좀 어려운거 몇개 있었다

IO프로그래밍의 목적 두가지?? - 효율성과 일관성?? 이런 느낌의 답이었는데

서술형은 TLB 접근시간 주어지고 상황따라서 접근시간 구하기

그다음은 replacement 알고리즘 표 채우고 몇번 교체되나 쓰기

쉬운문제라고 생각했는데 나랑 답이 갈리는 사람이 있다.... 내가 맞았길 바래야지..