흐이애가 캐리한다

6장부터 11장까지 범위의 용어들을 엑셀 파일로 정리해놓았습니다.

Flashcards Deluxe라는 어플을 이용하여 공부하였습니다.(아는 것은 소거, 모르는 내용만 집중적으로 공부)

3년전에 정말 열심히 공부했었는데, 놀랍게도 지금은 전혀 기억이 안 납니다...

질문 주셔도 잘 모를 것 같습니다.

유용하게 쓰세요! 감사합니다.

운영체제 OS 정리 (기말고사 범위).xlsx

운영체제론                                         제 11장 연습문제                

01 페이징을 구현하는 가상 메모리 시스템에서 다음 각 메모리 관리 전략의 목적을 논의하라.

a.   페치 전략

2차 저장소에 있는 프로그램이나 데이터를 메인 메모리로 옮길 시점을 결정하는 전략이다. 공간적, 시간적 지역성을 이용하여 다음 사용할 페이지를 미리 옮겨놓음으로써 대기 시간 감소 효과를 기대한다.

b.   배치 전략

어느 공간에 페이지를 배치할지 결정하는 전략으로써 메모리 공간을 낭비하지 않으면서 오버헤드 발생을 최소화하여 사용하는 데 목적이 있다.

c.   교체 전략

새로운 페이지를 폴트해야할 때 기존의 어떤 페이지를 교체시켜야 할 지 결정하는 전략이다. 오버헤드와 교체가 최대한 적게 일어나게 함으로써 대기 시간을 감소시키는 데 목적이 있다.

교수님 답

a.페치 전략

2차 저장소에서 메인메모리로 페이지를 가져온다. 페이지가 명확하게 참조하고자 할 때 요구 방식에 의해 페이지를 페치하고, 페이지 대기 시간을 감소하기 위해서는 예측 방식을 사용함

b.배치 전략

페이지를 메인 메모리의 페이지 프레임에 위치시킬 때 사용

c.교체 전략

메인 메모리가 찼다면 대체할 페이지를 선택해야 한다. 예로써 대체할 페이지는 가까운 미래에 필요하지 않을 것 같은 것을 선택하는 방법으로 교체함

03 세그먼테이션과 페이징을 조합한 가상 메모리 컴퓨터 시스템이 멀티프로그래밍 정도 10을 지원한다고 하자. 명령어 페이지(재진입 코드)는 수정 가능한 데이터 페이지와 별도로 유지된다. 시스템을 연구한 후 다음과 같은 사실을 관찰했다. (1) 대부분의 프로시저 세그먼트는 여러 페이지가 들어갈 만큼 크고, (2) 대부분의 데이터 세그먼트는 페이지 중 작은 일부만을 요구한다.

어떤 동료가 메모리 활용도를 높이는 방안으로 여러 사용자의 데이터 세그먼트 몇 개를 한 페이지에 넣자고 제안했다. 다음 이슈들과 관련해 이 제안이 어떠한지 의견을 기술하라.

a.   메모리 사용 메모리 사용 효율이 늘어난다.

b.   실행 효율 한꺼번에 여러 연속된 데이터를 로드하므로 효율적이다.

c.   보호 여러 데이터가 한 페이지에 있으므로 서로 간섭할 수 있다.

d.   공유 같은 페이지 안에 있으므로 자원을 공유하기 편리하다.

교수님 답

a. 메모리 사용

이 제안은 메모리를 더 효율적으로 사용하게 한다. 여러개의 데이터 세그먼트가 하나의 페이지 내에 위치하기 때문에 내부 단편화도 덜 생긴다.

b.           실행 효율

여러개의 데이터 세그먼트에 있는 내용들이 하나의 데이터 세그먼트에 존재하기 때문에 페이지 폴트가 덜 일어난다. 즉 효율이 좋아 진다.

c.           보호

이것은 시스템의 메모리 보호 수준에 따라 다르다. 임의 크기의 세그먼트가 사용될 때 각 프로세스의 데이터 세그먼트는 다른 프로세스로부터 보호될 수 있다. 그러나 크기가 잘 제어되지 않는다면 프로세스들은 서로 영향을 받게 된다. 즉 메모리 보호가 되지 않는다.

d.           공유

역시 이것도 시스템의 메모리 보호 수준에 따라 다르다. 임의 크기의 세그먼트가 사용될 때 각 프로세스의 데이터 세그먼트는 개별적으로 공유될 수 있다. 그러나 크기가 잘 제어 되지 않는다면 프로세스들은 메모리 보호를 유지하면서 데이터 세그먼트를 공유할 수는 없다.

04 오늘날은 예측 페이징과 예측 자원 할당에 대한 관심이 대체로 높다. 다음 각각은 예측 페이징 메커니즘에 어떤 유용한 정보를 줄 수 있는가?

a.   프로그래머

프로그램이 어떻게 작동할 지 알고 있으므로 다음에 사용될 페이지 정보를 줄 수 있다.

b.   컴파일러

c.   운영체제

d.   과거 프로그램 실행 로그

앞으로 어떤 페이지가 사용될 지 과거 기록을 통하여 경험적으로 알 수 있다.

교수님 답

a. 프로그래머

프로그래머는 실행될 프로그램의 다음 영역에 대한 힌트를 제공할 수 있다. 프로그래머가 프로그램이 수행할 경로를 알 필요가 없기 때문에 도전적일 수 있다.

b.컴파일러

컴파일러는 주된 수행 영역을 감지하고 내부 혹은 외부 함수 호출과 같은 천이들을 알려 줄 수 있다(여기서는 천이는 함수호출은 한 영역에서 다른 영역으로 점프하기 때문에 사용함).

c.운영체제

운영체제는 프로그램 동작을 관찰하고 과거의 동작으로부터 추론하여 미래의 동작을 예측 할 수 있다.

d. 과거 프로그램 실행 로그

윈도우 XP는 프로그램의 한 부분으로 그러한 로그를 제공하며, 운영체제는 프로그램이 로드될 때 프로세스가 경험한 페이지 폴트를 감소시키기 위하여 예측 페이징 방법을 수행 하여 미리 페이지를 가져 올 수 있다. 그러나 이러한 방법은 매우 값이 비싸다.

05 일반적인 경우 임의의 프로그램의 실행 경로를 예측하는 것은 불가능하다는 사실이잘 알려져 있다. 만약 예측할 수 있다면 해결할 수 없는 것으로 알려진 정지 문제도 해결할 수 있을 것이다. 예측 자원 할당 메커니즘의 효과에 대한 파생 효과를 설명하라.

 만일 모든 프로그램의 실행 경로를 예측할 수 있다면 프로그램 동작은 지금보다 훨씬 더 빨라질 것이다.

교수님 답

예측 페이징(혹은 예측 자원 할당) 매커니즘은 필요하지 않은 페이지를 메모리에 저장할 수 있게 하는 나쁜 판단을 할 수 있다. 중요한 것은 예측 페이징 매커니즘이 그러한 오버 헤드를 상쇄할 만큼 충분히 좋은 판단을 하느냐 하는 것이다.

10 일반적으로 수정된 페이지보다 수정되지 않은 페이지를 교체하는 것이 더 바람직한 이유는 무엇인가? 어떤 상황에서 수정된 페이지를 교체하는 것이 더 바람직한가?

수정된 페이지는 2차 저장소에 수정된 내용을 작성해야 하는 플러싱 과정을 수행해야 하는데, 이 과정에서 오버헤드와 대기가 발생한다. 그러므로 일반적인 경우 수정되지 않은 페이지를 교체하는 것이 더 바람직하다. 그러나 플러싱이 비동기적으로 발생하여 수정된 페이지가 2차 저장소에 저장이 완료되었고, 해당 페이지가 더 이상 사용되지 않는다고 판단되면 교체하는 것이 바람직하다.

교수님 답

- 수정된 페이지를 교체하기 위해서는 먼저 수정된 페이지를 디스크에 저장해야 한다. 수정 되지 않은 페이지는 단지 해당 페이지에 겹쳐 쓰기만 하면 된다.

- 모든 다른 페이지가 사용될 때 수정된 페이지가 최근에 사용되지 않았다면 그 수정된 페 이지를 교체하는 것은 의미있다

12 최적 MIN 페이지 교체 전략은 실현하기 어렵다. 미래를 예측하는 것이 불가능하기 때문이다. 그러나 MIN을 구현할 수 있는 환경이 있다. 어떤 상황인가?

교수님 답

 즉 미래를 예측 가능한 환경을 만들어야 하는데, 사실 예측 가능한 프로그램을 만드는 것은 힘들다. 그러나 예측가능한 프로그램은 존재하는데 그 프로그램은 순차적 동작들로 이루어진 프로그램이다. 이 경우에 있어서는 다음에 올 페이지들을 예측할 수 있다.

14 페이지화된 시스템에서 시간적, 공간적 지역성을 증명할 수 있는 실험을 설계하라.

교수님 답

 증명하기를 원하는 것은 최근에 사용된 페이지가 가까운 미래에 다시 사용될 수 있 느냐(시간적 지역성) 하는 것과 한 페이지가 사용되면 근처의 페이지가 사용될 것 같느냐 (공간적 지역성)하는 것이다. 증명할 시스템은 페이지 참조 스트링-즉 어떤 시간 구간에 대해 참조되는 페이지들의 리스트-를 만들 수 있다. 그러면 스트링을 분석하여 페이지가 가까운 미래에 참조되는 가를 볼 수 있고 인접 페이지들이 규칙적으로 참조될 수 있다는 것을 알 수 있는지 확인하면 된다.

15 특히 지역성이 두드러지는 프로그램을 작성하는 프로그래머는 실행 효율이 크게 개선되리라 기대할 수 있다. 프로그래머가 지역성을 높일 수 있는 몇 가지 전략을 기술하라. 특히 고급 언어의 어떤 특징이 강조되어야 하는가?

 배열과 같이 메모리가 연속적으로 할당되어 있는 경우 공간적 지역성이 있다고 할 수 있으므로 배열을 사용하면 지역성을 높일 수 있다. 또한 자주 쓰이는 함수, 객체의 인자들 또한 지역성이 있으므로 이를 고려할 수 있다.

교수님 답

강조해야 하는 고급언어의 특징은 배열과 반복문이다. 이러한 특징들에서는 데이터들이 순차적인 가상 주소 순으로 저장되고 접근되기 때문에 공간적 지역성을 증가시킨다. 반복문은 시간적 지역성을 포함한다. 즉 반복문은 주요 부분은 가까운 미래에 계속하여 반복될 수 있기 때문이다.

운영체제론                                         제 10장 연습문제                

01 프로세스의 가상 메모리 공간을 물리 메모리 공간으로부터 분리하면 좋은 이유를 몇 가지 나열하라.

가상 메모리 공간을 이용함으로써 실제 메모리 주소가 연속적이지 않아도 된다는 장점이 있다. 또한 메모리를 원래 있는 것보다 더 많이 존재하는 것처럼 보이게 해서 프로그램이 여유 메모리보다 큰 경우에도 실행할 수 있게 한다. 마찬가지로 멀티프로그래밍 정도를 높인다.

교수님 답

만일 2 공간이 같다면 가상 메모리 공간을 가질 이유가 없다. 분리하면 사용자는 물리 메모리보다 더 많은 공간을 프로그램에게 할당할 수 있다. 중첩과 같은 메모리 관리를 걱정 할 필요도 없고 가상 메모리 시스템의 좋은 특징인 사용자 보호 방법도 제공하기 때문에 분리한다.

03 페이징을 이용해 가상 주소와 물리 주소를 맵핑하는 다양한 기술에 관해 설명하라.

 페이징 시스템에서 가상 주소는 순서 쌍 (p,d)로 표현하며, p는 참조하는 항목이 있는 가상 메모리의 페이지, d는 페이지 p 안에서 참조하는 항목이 위치한 변위를 나타낸다.

 가상 주소 v=(p,d)

페이지 맵 테이블을 통해 페이지 p를 찾고, 페이지 p가 페이지 프레임 p’에 있는지 판단하여 해당 메모리 주소에서 변위 d를 더해 참조되는 주소를 얻어낼 수 있다. 즉 실제 메모리 주소 r은 (p’Xps)+d이다. (ps는 페이지의 고정 크기이다.)

페이지화된 가상 메모리 시스템을 사용함으로써 나타나는 장점 중 하나는 프로세스에 속한 모든 페이지를 동시에 메인 메모리로 로드하지 않아도 됨으로써 메인 메모리에 더 많은 프로세스를 동시에 담을 수 있게 된다는 것이다. 이 때, 페이지 테이블은 대응하는 페이지가 현재 메인 메모리에 있는지 여부를 표시해야 한다. 만약 없다면 페이지 폴트를 발생시킴으로써 2차 저장소에서 메인 메모리로 해당 페이지를 로드하게 된다.

이 외에도 직접 맵핑, 연관 맵핑, 직접/연관 맵핑 등이 있다.

05 세그먼테이션에서 가상 주소와 물리 주소의 맵핑에 관해 설명하라.

세그먼트는 일정한 크기가 없다. 가상 메모리 세그먼테이션 시스템에서는 프로그램이 특정 시간 실행에 필요한 세그먼트만 메인 메모리에 유지해도 된다.

가상 메모리 세그먼테이션의 주소는 순서 쌍 v=(s,d)로 나타내며, s는 참조하는 항목이 존재하는 가상 메모리에서 세그먼트 번호, d는 세그먼트 s에서 참조하는 항목이 있는 곳까지의 변위를 나타낸다.

 가상 주소 v=(s,d)

직접 맵핑 사용 : 시스템은 세그먼트 번호 s를 세그먼트 맵 테이블 시작점 레지스터에 있는 세그먼트 맵 테이블의 기준 주소 값 b에 더한다. 덧셈 결과로 얻은 b+s는 세그먼트의 테이블 맵 엔트리의 위치를 가리킨다. 세그먼트가 현재 메인 메모리에 있을 경우 엔트리는 세그먼트의 메인 메모리 시작 주소 s’를 포함한다. 실제 메모리 주소 r은 s’+d이다.

06 32비트(각각 메모리의 한 바이트를 명시한다) 주소를 사용하는 순수 페이징 시스템이 있다고 가정하자. 메인 메모리의 크기가 128MB고, 페이지 크기가 8KB다.

a.   이 시스템은 페이지 프레임을 몇 개 지니는가?

b.   이 시스템은 변위 d를 유지하는 데 몇 비트를 사용하는가?

c.   이 시스템은 페이지 번호 p를 유지하는 데 몇 비트를 사용하는가?

교수님 답

10 다음 각 유형의 가상 메모리 시스템에서 단편화가 어떻게 나타나는지 논의하라.

a.   세그먼테이션

-       서로 다른 크기의 세그먼트들에 대해 필요시에 메모리에 올리고 필요 없을 경우 내리는 작업을 반복하다 보면 외부 단편화가 생기는 문제점이 있다.

b.   페이징

-       일정 크기의 페이지에 프로세스 할당 시, 프로세스의 크기가 페이지보다 작을 경우 내부 단편화가 발생한다.

c.   세그먼테이션/페이징 조합

교수님 답

a. 세그먼테이션

순수 세그먼테이션의 문제는 9장에서 논의한 가변 파티션 멀티프로그래밍 문제와 유사하다. 세그먼트가 임의 크기이기 때문에 메모리는 다양한 크기의 메모리 홀로 파편화되어 그들 중 일부는 너무 작아서 사용할 수 없다. 압축과 결합 방법이 단편화를 줄이기 위해 사용된다. 테이블 단편화도 일어난다; 즉 세그먼트-매핑 테이블에 의해 취해진 공간이 사용자에게 할당되어 사용할 수 없게 된다.

b. 페이징

프로그램과 데이터 구조가 페이지를 채우지 못하기 때문에 내부적 단편화가 일어난다. 테이블 단편화도 일어난다.

c. 세그먼테이션/페이징 조합

순수 페이징에서 발생하는 단편화 문제와 세그먼트 테이블과 페이지 테이블의 사용 때문에 만들어진 추가적인 테이블 단편화가 발생한다.

12 세그먼테이션/페이징 조합 시스템에서 가상 주소를 물리 주소로 맵핑하는 과정을 설명하라.(10.6.1절 참고)

이 시스템에서는 세그먼트들이 페이지 하나 이상을 차지한다. 이 구조에서 가상 메모리 주소는 세 순서 쌍 v=(s, p, d)로 구현한다. (s : 세그먼트 번호, p : 해당 세그먼트 안에 있는 페이지 번호, d : 원하는 항목이 위치한 페이지 안에서의 변위.)

동적 주소 변환 메커니즘에 의해 연관 검색을 수행하며, TLB가 (s,p)를 포함하면 검색 결과로 페이지 p가 있는 페이지 프레임 p’이 반환된다. 만약 TLB가 (s,p)에 해당하는 엔트리를 포함하지 않으면, 프로세서는 세그먼트 맵 테이블 기준 주소 b를 세그먼트 번호 s에 더해 주소 b+s를 얻는다. 이 주소는 세그먼트 맵 테이블에 있는 세그먼트 엔트리의 물리 메모리 주소에 대응한다. 세그먼트 맵 테이블 엔트리는 세그먼트 s에 해당하는 페이지 테이블(메인 메모리에 존재)의 기준 주소 s’을 나타낸다. 프로세서는 페이지 번호 p를 기준 주소 s’에 더해 세그먼트 s의 페이지 p에 해당하는 페이지 테이블 엔트리의 주소를 얻는다.

14 실제 메모리 시스템보다 가상 메모리 시스템에서 코드와 데이터 공유가 훨씬 자연스러운 이유는 무엇인가?

가상 메모리에서 공유를 할 경우 시스템이 각 프로세스에 공통인 페이지들을 공유함으로써 메모리 낭비를 줄일 수 있다. 세그먼테이션에서는 직접 맵핑의 순수 페이징 시스템보다 오버헤드를 적게 발생한다.

교수님 답

주소 변환 방법과 연관된 테이블 구조가 테이블들을 공유하게 함으로써 모든 페이지와 세그먼트를 유지시켜 주기 때문이다.

15 페이징과 세그먼테이션의 유사점과 차이점을 기술하라.

두 가지 모두 블록 맵핑의 방법들이다. 가장 큰 차이점은 페이징은 블록이 고정 크기인 것이고 세그먼테이션은 블록이 가변 크기라는 것이다. 페이징은 맵핑 시 고정 크기이므로 실제 메로리 주소를 참조할 때 r=(p’Xps)+d로 참조하는 위치가 정해져있지만, 세그먼테이션은 가변 크기이므로 여러 가정이 성립되는 상황에서만 공식이 적용되며 더 복잡한 참조방식을 갖고 있다.

교수님 답

2 방법 모두 가상 메모리를 구현하기 위해 많이 사용되는 구조이다. 2 방법 모두 가상 주소 공간을 분리된 공간(블록, 페이지 혹은 세그먼트)으로 나누게 하고 불연속 메모리 할당을 한다. 페이징은 물리적 공간을 처리하고 세그먼테이션은 논리적 공간을 처리한다. 페이징은 블록의 크기가 일정하여 메모리 배치 결정을 단순하게 하지만 세그먼테이션은 블록의 크기가 가변적이어서 가변 파티션 멀티프로그래밍의 방법과 같이 복잡한 메모리 배치 결정을 한다.

운영체제론                                         제 9장 연습문제                  

01 계층적 메모리 시스템에서 프로그램과 데이터를 다양한 계층 간에 옮기는 데 일정량의 오버헤드가 든다. 이러한 시스템에서 오버헤드에도 불구하고 얻을 수 있는 이점은 무엇인가?

계층적 메모리 시스템은 사용할 가능성이 있는 메모리 수준(예, 캐쉬, 메인 메모리, 2차 저장장치 등)에 가능한 정보(프로그램과/혹은 데이터)를 읽고 쓸 수 있도록 설계되었다. 동작중인 프로세스에 당분간 필요하지 않을 것 같은 정보는 2차 저장장치에 유지해야 한다. 동작중인 프로세스, 특히 현재 실행중 혹은 준비상태인  프로세스에 의해  필요할 것 같은 정보는 1차(메인) 메모리에 저장되어 있어야 한다. 현재 실행중인 프로세스에 의해 많이 참조되는 정보는, 고속 캐쉬 메모리가 있다면, 고속 캐쉬 메모리에 유지되어야 한다. 고속 캐쉬와 같은 메모리들의 상대적으로 비싼 비용때문에 모든 프로그램과 데이터를 가장 빠른 메모리에 저장하지 못한다. 그래서 정보들을 최적 메모리 수준에 저장하도록 해야 한다. 즉, 관리 비용(오버헤드)이 최적 메모리 수준에서 정보를 유지하는 비용보다 매우 싸기 때문이다.

02 요구 페치가 전통적인 방식으로 오래 지속된 이유는 무엇인가? 예측 페치 전략이 지난 수십 년 동안 보다 오늘날 훨씬 많은 관심을 받는 이유는 무엇인가?

요구 페치가 단순하여 구현하기가 쉽다는 것이고 바로 필요할 프로그램 혹은 데이터 조각만 메인 메모리로 가져오기 때문에 메모리의 낭비가 없다는 것이다. 예측 페치 방법은 상당한 수준의 오버헤드를 요구하고 있다: 어떤 조각들이 메인 메모리에 이동할 것이냐를 결정하는 것은 상당한 시간을 소비하고 메인 메모리 자원을 소비할 뿐만 아니라 잘못된 예측을 할 수 있다. 과거에는 이러한 오버헤드 때문에 예측 페치 방법을 사용하지 못하였다. 오늘날 프로세서 속도가 디스크 속도보다 훨씬 빨라졌기 때문에, 어떤 조각을 디스크로부터 메인 메모리로 가져올 것인가에 대한 결정은 오버헤드 비용을 감소시킨다. 또한 메인 메모리도 비용도 많이 저렴해졌기 때문에 메모리의 부담도 많이 덜게 되었다.

05 멀티프로그래밍이 생겨난 동기에 대해 논의하라. 프로그램과 시스템의 어떤 특징 때문에 멀티프로그래밍이 바람직한가? 어떤 상황에서 멀티프로그래밍이 바람직하지 못한가?

입출력 중심 작업은 프로세서 시간을 덜 사용하기 때문에 멀티프로그래밍은 유용한 프로세서 시간을 사용하여 더 많은 작업을 하도록 도와준다. 시스템은 다양한 입출력 장치들을 가질 수 있고 어떤 작업은 이러한 장치들의 일부들을 사용할 수 있다. 멀티프로그래밍은 장치 이용률을 높이면서 더 많은 작업을 할 수 있도록 하여 주기 때문에 사용하게 되었다.

이상적인 특징은 다음과 같다.

실행중인 작업들의 많은 부분이 입출력 중심이고, 그 작업들은 공유가능한 장치 혹은 서로 다른 전용 장치를 사용하고, 프로세서는 멀티프로그래밍 운영체제에서 내재되는 오버헤드(예: 문맥교환시간 등)를 지원할 만큼 충분히 빠르고, 멀티프로그래밍이 효율적이 되도록 동작중인 작업들을 유지할 만큼 메인 메모리가 충분히 존재하여야 하고 시스템은 작업 들의 요구들을 지원하도록 충분한 장치들을 가지고 있어야 한다.

앞에서 설명한 조건들 중 하나라도 만족하지 못하면, 적절하지 못하다. 작업들이 멀티프로그래밍 운영체제에서 수행될 때보다 전용 프로세서에서 한 번에 하나씩 수행될 때 긴 프로세서-중심 작업들을 처리하는 시스템은 더 좋은 처리량을 보여준다. 이는 멀티프로그래밍 시스템에서는 문맥 교환등에 소요되는 오버헤드가  처리량을  감소시키기  때문이다. 물론  문맥  교환과  같은  오버헤드는  입출력-중심  시스템에  존재하지만  그  시스템에서는 입출력 장치와 프로세서가 병렬로 처리하기 때문에 그 오버헤드는 보상이 된다.

08 멀티프로그래밍 환경에서 프로그램을 재배치하는 간단한 방법은 단일 재배치 레지스터를 사용하는 것과 관련 있다. 모든 프로그램은 0에서 시작해 변환되지만, 프로그램이 실행될 때 변환되었던 각 주소는 프로세서의 재배치 레지스터의 내용이 더해지면서 수정된다. 가변 파티션 멀티프로그래밍에서 재배치 레지스터를 사용하고 제어하는 것에 관해 논의하라. 보호 메커니즘을 위해 재배치 레지스터가 어떻게 사용될 수 있는가?

연속적인 메모리 할당을 가정하면, 재배치 레지스터에는 문맥교환시 파티션내에 있는 프로그램의 기저 주소(base address)가 저장(load)된다. 재배치 레지스터는 낮은 메모리 경계 레지스터로써 동작한다. 또한 다른 레지스터가 필요로 하는데, 이 레지스터는 높은 메모리 경계 레지스터 혹은 그 파티션의 길이를 포함하여 한다. 이 2개의 레지스터를 사용하여 메모리를 보호한다.

11 불연속 메모리 할당의 장단점을 설명하라.

장점 : 메모리의 요구가 유용한 가장 큰 메모리 영역의 크기를 초과하더라도 작업이 동작할 수 있다는 것.

단점 : 하드웨어와 운영체제의 복잡성과 비용이 증가하는 것

13 운영체제의 발전은 혁명보다는 진화의 양상을 띠었다. 다음 각 발전에 대해 운영체제 설계자들이 구형에서 신형 시스템으로 발전시킨 주요 동기를 설명하라.

a.   단일 사용자 전용 시스템에서 멀티프로그래밍 시스템으로의 변화

b.   절대 변환과 로딩을 하는 고정 파티션 멀티프로그래밍 시스템에서 재배치 가능한 변환과 로딩 방식의 고정 파티션 멀티프로그래밍 시스템으로의 변화

c.   고정 파티션 멀티프로그래밍에서 가변 파티션 멀티프로그래밍으로의 변화

d.   연속 메모리 할당 시스템에서 불연속 메모리 할당 시스템으로의 변화

e.   수동으로 작업 간 전환을 하는 단일 사용자 전용 시스템에서 단일 스트림 배치 처리를 하는 단일 사용자 전용 시스템으로의 변화

a. 많은 입출력-중심 작업들을 처리하는 시스템에서 프로세서와 장치들의 이용율을 높이기 위하여.

b. 작업을 적재할 수 있을 정도로 충분히 큰 파티션이 유용하더라도 현재 사용중인 파티션으로 컴파일된 작업은 사용하지 못하기 때문에 이를 피하기 위하여.

c. 모든 파티션이 파티션보다 작은 작업들로 차지하게 될 때 사용하지 못하는 공간이 많이 생기게 되는 것을 피하기 위하여.

d. 어떤 작업에서 요구하는 전체 메모리 양이 현재 유용한 가장 큰 여유 메모리 공간보다 많지만 모든 유용한 여유 공간의 전체 합보단 적은 경우에 그 작업을 수행할 수 있도록 하기 위하여.

e. 하나의 작업에서 다른 작업으로 전환하는 과정을 자동화함으로써 처리량을 증가하기 위하여.

22 가변 파티션 멀티프로그래밍 시스템은 여유 메모리를 추적하기 위해 ‘여유 메모리 리스트’를 사용한다. 리스트에는 현재 150KB, 360KB, 400KB, 625KB, 200KB가 있다. 시스템은 215KB, 171KB, 86KB, 481KB과 같은 순서로 요청을 받았다. 시스템이 다음 각 메모리 배치 전략을 사용할 때, 최종적인 리스트의 내용을 기술하라.

a.  최적합

모든 프로그램이 메모리에 동시에 존재할 수 있다. 여유 메모리 리스트는 다음의 값을 가진다 : 150KB, 59KB, 400KB, 144KB, 29KB.

150 KB

360 KB -> 145 KB (215 KB 할당) -> 59 KB (86 KB 할당)

400 KB

625 KB -> 144 KB (481 KB 할당)

200 KB -> 29 KB (171 KB 할당)

b.  최초 적합

모든 프로그램이 메모리에 동시에 존재할 수 있다. 여유 메모리 리스트는 다음의 값을 가진다. :   64KB, 145KB, 229KB, 144KB, 200KB.

150 KB -> 64 KB (86 KB 할당)

360 KB -> 145 KB (215 KB 할당)

400 KB -> 229 KB (171 KB 할당)

625 KB -> 144 KB (481 KB 할당)

200 KB

c.  최악 적합

모든 프로그램이 메모리에 동시에 존재할 수 없다. 여유 메모리 리스트는 다음의 값을 가진다 : 150KB, 360KB, 314KB, 239KB, 200KB. (481 KB 프로그램은 다른 프로그램들이 완료될 때까지 할당될 수 없다.)

150 KB

360 KB

400 KB   -> 314 KB (86 KB 할당)

625 KB   -> 410 KB (215 KB 할당)   -> 239 KB (171 KB 할당)

200 KB

d.  차선 적합

모든 프로그램이 메모리에 동시에 존재할 수 있다. 여유 메모리 리스트는 다음의 값을 가진다 :   150KB, 145KB, 143KB, 144KB, 200KB.

150 KB

360 KB   -> 145 KB (215 KB 할당)

400 KB   -> 229 KB (171 KB 할당)   -> 143 KB (86 KB 할당)

625 KB   -> 144 KB (481 KB 할당)

200 KB

[OS]운영체제론 중간고사 - 문제 및 해설

1.   (12점)

A.      운영체제란 무엇인가?(6점)

운영체제란 하드웨어와 소프트웨어가 서로 잘 동작하도록 도와주는 소프트웨어이다. 또한 운영체제는 자원을 관리하고, 인터페이스를 제공하며, 응용 프로그램들을 동작하도록 돕는다.(내 답)

B.       멀티프로그래밍과 멀티프로세싱을 구분하시오.(6점)

멀티프로그래밍 시스템은 하나의 프로세서에 하나이상의 프로그램은 동시에 수행시킨다. 멀티프로그래밍 시스템은 여러 개의 프로그램을 메인 메모리에 저장해 놓고 프로세서를 여러개의 프로그램들 사이로 빠르게 스위치하여 프로그램을 동작시킨다. 멀티프로세싱시스템은 둘 이상의 프로세서를 가진 컴퓨터 시스템이다.

ᅟ멀티프로그래밍은 프로세서와 I/O 자원 이용률을 증진하기 위해 개발되었다. 멀티프로세싱은 실제로 프로그램을 병렬 수행하게 함으로써 처리 속도를 증가시키기 위한 노력으로 개발되었다.(교수님 답)

멀티프로그래밍은 CPU연산과 입출력 연산을 동시에 할 수 있다. 연산을 병행하여 수행하므로, 사용자가 느끼기에 연속적으로 처리하는 것처럼 보인다.

멀티프로세싱은 여러 개의 프로세스가 협력하여 하나 혹은 여러 프로그램을 동시에 수행한다. 따라서 아주 효율적인 시스템이라 할 수 있다.(내 답)

2.   (16점)

A.      사용자 모드, 커널모드와 특권 명령어를 최소권한원칙을 가지고 설명하시오.(8점)

만일 운영체제를 사용하는 모든 사용자가 운영체제의 모든 권한을 갖는다면, 고의적이거나 악의적인 명령어에 의해 시스템에 문제가 생길 수도 있다. 이를 방지하기 위해서 사용자 모드와 커널모드를 만들었다. 사용자 모드에서는 메모리 접근과 기타 주요한 데이터로의 접근을 금지한다. 이를 최소권한원칙이라 한다.

커널모드에서는 모든 명령어 사용과 메모리 접근이 가능하다.

특권 명령어란 커널모드에서만 접근할 수 있는 명령어를 뜻한다.(내 답)

B.       고급언어를 작성된 프로그램이 수행을 위해 어떤 과정을 거치는지 간략하게 설명하시오. 또한 절대 로더와 재배치가능한 로더를 비교하시오.(8점)

컴파일러에 의해 컴파일된다. 오브젝트에 의해 기계어로 번역된다. 다양한 모듈이 사용된다. 링커에 의해 모듈과 라이브러리들이 링크된다. 로더에 의해 상대적인 메모리 주소가 할당되고, 메모리 위에 적재되고 수행된다.

절대 로더는 프로그램과 데이터를 직접 링커 혹은 프로그래머가 지정한 메모리 주소에 위치하여 저장한다. 재배치가능한 로더는 적재(load)할 모듈의 상대적 주소를 메모리 블록내의 주소의 offset에 의해 결정된 절대적 주소로 변환한다. 절대 로더는 재배치가능한 로더보다 단순하고 빠르게 수행한다. 재배치가능한 로더는 보다 유연하기 때문에 메모리의 허비를 최소화한다. 재배치가능한 로딩은 절대 로딩보다 시스템 상에 더 많은 프로그램들을 허락한다.

절대 로딩은 중첩되는 주소들을 가진 2개의 프로그램은 동시에 수행될 수 없지만 재배치가능한 로딩은 그러한 문제는 없다. 재배치가능한 로딩은 메모리내의 프로그램에 어디에 위치할 것인지에 대해 프로그래머가 알 필요가 없다. 즉 프로그래밍을 좀 더 쉽게 만든다.(교수님 답)

3.   (10점)스레드와 프로세스의 정의를 하고 이들을 비교하여 설명하시오.

프로세스는 실행중인 프로그램이고, 스레드는 프로세스 안에서 나누어지는 작업 단위이다. 프로세스는 스레드에 비해 함수 호출 시 작업 속도가 빠르지만 Data 교환이 느리다. 프로세스는 메모리를 공유하지 않지만 스레드는 메모리를 공유하므로 이에 접근하여 발생할 수 있는 문제에 대해 잘 대비하여야 한다.(내 답)

4.   (프로세스)(24점)

A.      신호와 메시지 교환 방법을 사용하여 프로세스간 통신(IPC)을 비교하시오.(8점)

신호는 이벤트가 발생하였다는 것을 다른 프로세스에게 알려주는 단순하고 효율적인 방법이다. 그러나 신호는 데이터를 보낼 수 없기 때문에 신호가 다른 프로세스에게 보낼 수 있는 정보의 양에 따라 프로세스에서 신호 사용이 제한된다. 또한 신호는 한 운영체제 내의 IPC에 제한된다.

메시지 교환은 하나의 프로세스가 많은 데이터를 다른 프로세스에게 전달하게 한다. 그러나 이 방법은 신호와 비교하면 상당한 오버헤드를 가진다. 즉 메시지를 위하여 메모리를 할당하고 송신자와 수신자의 이름과 위치를 알아야 하는 등의 오버헤드가 존재한다.(교수님 답)

B.       퀀텀의 크기를 정하는 일은 효율적인 운영체제를 만드는데 매우 중요하다. 매우 긴 시간을 사용할 경우에도 문제이고 매우 짧은 시간을 사용하는 경우에도 문제이다. 이러한 2 경우에 왜 문제가 생기는 지를 설명하시오. (8점)

퀀텀이 매우 길다면, 한 프로그램이 퀀텀동안 시스템을 독점하여 다른 프로세스들에게 빠른 응답을 하지 못하게 된다.

반대로 퀀텀이 매우 짧다면, 운영체제가 매우 많은 수의 문맥 교환을 하기 때문에 실제 프로그램 실행은 매우 더디게 된다. 즉, 한 퀀텀의 사용 시간을 비교하면 문맥 교환의 시간이 실제 프로그램 수행 시간보다 길 수 있기 때문에 효율적이지 못하고 실제 프로그램 수행 완료까지 오래 걸린다.(교수님 답)

C.       사용자 수준 스레드와 커널 수준 스레드와 그들의 조합 방법에 대해 설명하시오. (8점)

사용자 수준 스레드는 사용자 영역에서 스레드 연산을 수행한다. 특권 명령을 실행할 수 없거나 커널 프리미티브에 직접 접근할 수 없는 런타임 라이브러리가 스레드를 생성한다. 다대일 스레드 맵핑이로고도 한다. 멀티 스레드 프로세스 하나에 있는 모든 스레드에 실행 문맥 하나를 맵핑한다.

커널 수준 스레드는 각 스레드마다 고유한 실행 문맥을 맵핑하는 방법으로 사용자 수준 스레드의 한계를 해결했다. 일대일 스레드 맵핑이라고도 한다. 상호작용성이 증가하는 장점이 있다.

사용자 수준 스레드와 커널 수준 스레드의 조합을 수행하면 다대다 스레드 맵핑이 된다. 이 방식은 많은 사용자 수준 스레드를 한 그룹의 커널 스레드에 맵핑한다. 스레드 풀링을 통해 오버헤드 문제를 해결한다.(책 참고)

5.   (10점) 몇 가지 독립적인 계산을 동시에 수행하는 알고리즘에 대해 스레드를 사용하는 경우와 사용하지 않는 경우 어느 쪽이 더 효율적인가? 이 질문에 답하기 어려운 이유는 무엇인가?

이 문제의 답은 스레드의 구현 방식과 시스템이 하나의 프로세스 혹은 다중 프로세스를 사용하느냐에 따라 다를 수 있다. 시스템이 다중프로세스 시스템이면 각 스레드가 각 독립적인 프로세서에서 수행된다면 스레드를 사용하는 함수는 매우 효율적일 수 있다. 그러나 시스템이 하나의 프로세서로 운영된다면 스레드를 생성하고 스레드간 문맥을 교환(Context switching)하는데 걸리는 추가적인 오버헤드 때문에 스레드를 사용하는 함수는 비효율적일 수 있다.(교수님 답)

만일 단일 프로세서를 이용하는 경우, 스레드를 사용해도 프로세서는 1개만 존재하므로 스레드를 사용하지 않는 경우보다 잦은 문맥교환이 일어나므로 비효율적이다. 그러나 멀티프로세서 환경인 경우, 스레드가 사용되면 시스템을 효율적으로 사용할 수 있다. 예를 들어 여러 서버에 대한 접속을 시도한 후 대기해야 하는 상황에서 스레드가 존재한다면 한 서버에 접속을 시도한 후 대기하는 동안 다른 스레드에게 CPU를 할당할 수 있다. 해당 질문에 대한 답변은 상황에 따라 달라질 수 있으므로 답하기가 어렵다.(내 답)

6.   (24점) (비동기식 병렬 수행)

A.      운영체제 커널에서 바이너리 세마포어와 바이너리 세마포어 연산을 구현하는 방법을 자세히 설명하시오. (8점)

커널은 세마포어의 값을 표현하도록 한 비트를 할당할 뿐만 아니라 세마포어에 블록된 스레드를 대기하도록 큐를 할당한다. 이러한 큐는 PCB들의 영결 리스트(linked list) 데이터 구조를 사용하여 구현될 수 있다.

스레드가 P 동작을 호출할 때 커널은 인터럽트를 비활성화시킨다. 세마포어 값이 0이면 스레드는 블록 큐의 끝에 추가된다.이 때 사용되는 블로 큐가 연결 리스트(linked list)구조를 사용한다. 그 후 인터럽트가 재활성화된다. 세마포어 값이 1이면 스레드는 새마포어 값을 0 로 설정하고 인터럽트를 재활성화한다. 다시 말하면 세마포어 값이 1이면 자원이 있는 상태이고 0이면 자원이 없는 상태이다.

스레드가 V 동작을 호출할 때 커널은 P 동작과 같이 먼저 인터럽트를 비활성화한다. 그리고 커널은 블록 큐가 비어 있는지를 확인한다. 만일 큐가 비어있다면(즉, 대기하고 있는 스레드가 없다면) 세마포어의 갑슬 1로 설정하고 인터럽트를 활성화시킨다. 만일 세마포어를 기다리고 있는 스레드가 있다면(즉, 큐에 스레드가 있다면) 커널은 블록 큐로부터 스레드를 꺼내어 (deque 시키고) 그 스레드를 준비 큐에 넣는다. 그리고 인터럽트를 재활성화 시킨다.(교수님 답)

B.       단일 프로세서 시스템에서 상호배제 프리미티브를 구현할 때, 인터럽트를 활성화하고 비활성화하는 이유를 설명하시오. (8점)

실제로 상호배제 기능을 구현하는 것은 매우 직선적이다. 스레드가 enterMutualExclusion()을 수행할 때 모든 인터럽트는 비활성화된다. 그리고 스레드는 중요 영역을 인터럽트가 안 들어오는 상태에서 수행된다. 쓰레드가 exitMutualExclusion()를 수행할 때 인터럽트는 재활성화된다. 인터럽트를 비활성화시키지 않은 상태에서 중요 영역에 들어가는 경우, 인터럽트들에 의해 다른 스레드들이 수행되기 때문에 중요 영역을 수행하는 스레드의 수행 시간이 길어지기 때문에 다른 스레드들이 해당 중요 영역을 사용하기를 원할 때 많은 시간이 지연되는 문제가 있다.(교수님 답)

하나의 스레드가 임계 영역을 수행중일 때, 다른 스레드가 해당 영역을 접근하면 상호 배제가 이루어지지 않는다. 인터럽트에 의해 CPU 권한을 빼앗기지 않음으로써 상호 배제를 이룰 수 있다.(내 답)

C.       상호배제 프리미티브는 바쁜 대기나 블록킹을 사용하여 구현할 수 있다. 각 접근법의 적용 가능성과 상대적인 장점을 논의하시오. (8점)

이러한 2가지 방법은 장단점이 있기 때문에 응용에 맞게 사용되어야 한다. 바쁜 대기 방법으로써 스레드가 계속하여 작업을 수행할 수 있을 때까지(즉, 어떤 플래그가 설정될 때까지) 프로세서는 플래그를 계속 검사한다. 플래그가 설정될 때 만일 해당 프로세스가 실행 상태에 있다면 계속하여 수행한다. 그렇지 않다면(즉, 준비 상태이 있다면) 스레드는 실행상태가 되었을 때 동작을 계속한다. 이 방법의 문제는 해당 스레드가 계속하여 수행되기 전에 많은 시간을 지연된다면 프로세서는 시간을 허비하게 된다는 것이다. 블록 방법에서는 어떠한 프로세서 시간도 허비하지 않는다는 것이다. 스레드는 플래그를 검사하여 설정이 되어 있지 않았다면 프로세서 사용을 포기하고 즉시 블록 상태로 들어간다. 스레드가 계속하여 수행될 때(즉, 다른 스레드가 자원을 다 사용하고 반납할 때) 스레드 먼저 블록 상태를 준비 상태로 상태 전이를 하고 준비 큐의 앞에 그 스레드를 삽입하여 바로 바로 수행하게 한다. 실시간 응용에서는 스레드들이 바로 반응할 필요가 있다. 즉 자원이 반납되는 플래그가 설정되면 바로 즉시 해당 스레드가 동작되어야 한다. 스레드를 블록 상태에서 준비상태로 만들고 준비 큐에 넣는 것은 오버헤드 시간을 요구한다. 이는 실시간 응용에서는 알맞지 않을 수 있기 때문에 바쁜 대기 방법이 좋을 수 있다.(교수님 답)

바쁜 대기의 경우 플래그를 설정하여 해당 플래그를 지속적으로 검사한다. 그러나 이는 오직 해당 플래그를 확인하는 일에만 CPU를 사용하므로 비효율적이다. 블록킹의 경우 플래그를 검사하여 스레드가 사용할 자원이 없다고 판단되면 블록 상태로 만들어 블록 큐에 삽입한다. 사용할 자원이 생기면 준비상태로 스레드를 적재시킨 후 실행한다. 실시간 시스템의 경우 블록킹을 사용하면 스레드가 블록->준비->실행상태를 거치므로 시간이 걸린다. 그러므로 실시간 시스템의 경우 바쁜대기의 방법이 더 적절하다.(내 답)

7.   (5점)운영체제를 배우면 프로그래밍에 어떤 도움이 되는가?

운영체제를 공부함으로써 컴퓨터 구조를 파악할 수 있으므로 프로그래밍을 할 때 스레드와 프로세스를 더욱 효율적이고 정확하게 구성할 수 있다.(내 답)

8.   (20점)분산 시스템에서 여러 개의 컴퓨터에서 한 컴퓨터의 자원(예:데이터베이스, 프린터)을 사용하고자 하고 있다. 이러한 목표를 얻기 위해서는 어떠한 방법이 있는지 아는 범위내에서 설명하시오. 기본적으로 네트워크를 활용한다고 가정하고, 네트워크 프로그램은 주어진다고 생각하시오.(보너스 점수)

프로세서의 속도에 차이가 있을 경우 버퍼나 스풀링을 이용하여 속도 문제를 해결할 수 있다.(내 답, 5점 받음)

[OS]운영체제론 연습문제 8장 - 문제 및 해설

02 다음 각 문제를 어떤 수준의 스케줄러에서 결정해야 하는가?

a.   프로세서를 사용할 수 있을 때, 준비 상태 프로세스 중 어떤 프로세스에 프로세서를 할당할 것인가?

   -저수준 스케줄링

b.  디스크에 스풀되어 대기하는 일련의 배치 프로세스 중 어떤 것을 시작할 것인가?

-저수준 스케줄링

c.   프로세서에 대한 단기적인 부하를 줄이려면 어떤 프로세스를 일시 정지할 것인 것인가?

-중간 수준 스케줄링

d.  멀티프로그래밍의 균형을 유지하려면 입출력 중심이라고 알려진 일시 정지 프로세스 중 어떤 것을 활성화할 것인가?

-고수준 스케줄링

교수님 답

a. 디스패처(혹은 저수준 스케쥴러)

b. 고수준 스케쥴러

c. 중간수준 스케쥴러

d. 중간수준 스케쥴러

03 스케줄링 정책과 스케줄링 메커니즘의 차이를 설명하라.

스케줄링 정책은 시스템이 프로세스를 선택할 때, 어떤 기준-처리량을 최대화할 지, 자원 활용도를 최대화할 지, 공정성, 응답 시간, 우선순위 등-에 따라 선택을 할지를 결정하는 것이다. 스케줄링 정책에는 선점/비선점 스케줄링, 정적/동적 우선순위 스케줄링 등이 있다.

스케줄링 메커니즘은 스케줄링 정책들이 어떠한 메커니즘을 쓸 것인지-문맥 전환, 퀀텀 등-를 결정하는 것이다.

교수님 답

정책은 스케쥴러의 특정 수준에 의해 사용되어지는 규칙 혹은 전략의 집합이다. 매커니즘은 정책을 구현하는 실제 시스템 SW이다.

04 다음은 일반적인 스케줄링의 목표다. P391

a.   공평성 : 스케줄링 규칙이 유사한 프로세스들을 모두 동일하게 대우하고, 어떤 프로세스도 스케줄링 때문에 무기한 연기에 빠지지 않는다면 공평한 원칙이라고 할 수 있다. P393

b.  처리량 극대화 : 스케줄링 규칙은 단위 시간당 가능하면 많은 프로세스가 서비스를 받을 수 있도록 해야 한다.

c.   적정 시간 안에 반응을 얻는 대화식 사용자 수 극대화

d.  예측 가능성 : 유사한 시스템 부하 시에는 주어진 프로세스가 항상 비슷한 시간 동안 실행해야 한다.

e.  오버헤드 최소화

f.   자원 활용도의 균형 유지 : 스케줄링 메커니즘은 시스템 자원을 부지런히 사용하게 해야 한다.

g.  반응성과 자원 활용도 사이의 균형 유지

h.  무기한 연기 방지

i.   우선순위 준수

j.   핵심 자원을 보유한 프로세스에 우선권 부여

k.  오버헤드가 많은 프로세스에 낮은 수준의 서비스 제공

l.   시스템 부하가 커질 때도 점진적인 성능 저하 : 규모 확장성

위에서 열거한 목표 중 다음 각 사항에 직접 적용되는 것을 선택하라.

i.       특정 사용자가 특히 오랜 시간 동안 대기했다면, 해당 사용자에게 우선권을 준다.

-h. 무기한 연기 방지

ii.       직원 1,000명이 근무하는 회사에서 급여 계산을 수행하는 사용자가 있다. 이 사용자는 급여 계산 작업을 매주 일정한 시간 안에 수행하려고 한다.

-b. 처리량 극대화

iii.      시스템은 대부분의 장치를 바쁘게 활용할 수 있는 방향으로 프로세스를 적절하게 배분해야 한다.

-f. 자원 활용도의 균형 유지

iv.      시스템은 중요한 프로세스를 선호해야 한다.

-j. 핵심 자원을 보유한 프로세스에 우선권 부여.

v.       중요한 프로세스가 도착하더라도, 요구하는 자원을 중요하지 않은 다른 프로세스가 보유하고 있다고 해서 해당 프로세스를 앞지를 수는 없다.

-i. 우선순위 준수

vi.      시스템이 가장 바쁠 때 많은 프로세스를 관리하는 오버헤드 때문에 시스템이 다운되면 안 된다.

-k. 오버헤드가 많은 프로세스에 낮은 수준의 서비스 제공

vii.      시스템은 입출력 중심 프로세스를 선호해야 한다.

-i. 우선순위 준수

viii.     문맥 전환은 가능하면 빨리 수행해야 한다.

-e. 오버헤드 최소화

교수님 답

i. 무기한 연기 방지를 위해서는 h), 공평성을 위해서는 a), 예측 가능성을 위해서는 d)

ii. d)

iii. 자원활용도의 균형유지를 위해서는 f), 반응성과 자원활용도간 균형유지를 하기 위해서는 g)

iv. i)

v. j)

vi. l)

vii. c)

viii. e)

06 다음 사항이 올바른지 판단하고 답에 대한 이유를 설명하라.

a.   프로세서를 프로세스로부터 강제로 제거할 수 없다면, 해당 프로세스 스케줄링 규칙은 선점형이다.

올바르지 않다. 프로세스로부터 프로세서를 강제로 제거할 수 없는 스케줄링 규칙은 비선점형 스케줄링이다. 비선점형 스케줄링은 프로세스 수행이 완료될 때까지 대기하며 처리 시간을 예측할 수 있다는 장점이 있다.

b.  실시간 시스템은 대체로 선점형 프로세서 스케줄링을 사용한다.

올바르다. 선점형 프로세서 스케줄링은 우선순위가 높은 프로세스에 빨리 응답해야 하는 시스템에서 유용하다. 만일 실시간 시스템에서 인터럽트에 대해 제시간에 응답하지 않으면 큰 재앙을 초래할 수도 있다.

c.   시분할 시스템은 대체로 비선점형 프로세서 스케줄링을 사용한다.

올바르지 않다. 대화식 시분할 시스템에서는 선점형 스케줄링을 통해 각 사용자가 수용할 만한 반응 시간을 보장할 수 있다.

d.  처리 시간 예측은 비선점형 시스템보다는 선점형 시스템에서 더 용이하다.

올바르지 않다. 비선점형 스케줄링은 프로세스가 완료될 때까지 대기하므로 처리 시간을 예측할 수 있다.

e.  우선순위 구조의 한 가지 약점은 해당 시스템이 우선순위를 충실하게 지키지만 우선순위 자체가 무의미할 수도 있다는 점이다.

교수님 답

a. 거짓. 선점형은 프로세서가 강제적으로 프로세스로부터 제거할 수 있다는 것을 의미한다.

b. 참. 실시간 시스템의 성공의 요건은 프로세스의 데드라인을 만족시키는 능력이다. 이 능력은 서비스에 대해 응답을 재빨리 하는 것이다.

c. 거짓, 새로운 요구에 대하 빠른 응답을 보장하기 위해서는 선점형 스케쥴링을 사용한다. 

d. 거짓. 비선점형 시스템에서 프로세스가 프로세서를 획득하면 완료할 때까지 동작한다. 즉,

다른 프로세스들에 의해 반복적으로 선점되는 가능성때문에 발생하는 예측의 불확실성도 없다.

e. 참. 시스템에서 우선순위 설정은 중요한 작업이다. 그러나 우선 순위를 지키는 시스템에 서는 우선 순위가 낮은 프로세스가 한 자원을 사용하고 있을 때, 높은 우선순위의 프로세스가 그 자원을 사용하기 위해 요구하는 경우를 생각해보자. 이 경우에는 우선순위가 거의 무의미해진다.

09 데드라인 스케줄링이 복잡한 이유를 설명하라. P409

사용자들은 정확한 자원 요구량을 미리 제시해 해당 프로세스가 데드라인까지 완료할 수 있게 보장해야 한다. 이러한 정보는 얻기 어렵다.

시스템은 데드라인에 맞춰 프로세스를 실행하되 다른 사용자들에 대한 서비스에 심각한 악영향을 미치면 안 된다.

시스템은 데드라인이 될 때까지 자원 요구량을 철저하게 계획해야 한다. 새로운 프로세스들이 도착해 예상치 못한 자원들을 요청할 수도 있으므로 매우 어려운 일이다.

여러 데드라인 프로세스들이 한꺼번에 활성화되는 경우 스케줄링이 아주 복잡해진다.

데드라인 스케줄링이 요구하는 강도 높은 자원 관리는 상당한 오버헤드를 가져올 수도 있다.

교수님 답

다음의 내용들을 모르기 때문에 데드라인 스케쥴링 계획을 설정하는데 있어서 불확실성 이 존재한다.

- 프로세스의 수행시간

- 필요한 자원의 종류와 수

또한 실제 동작하면서는 시스템내에서 동작하는 시스템 부하가 예측할 수 없이 변할 수 있다는 것이다.

이러한 원인들 때문에 데드라인 스케쥴링이 힘들다. 역으로 이러한 것들을 관리할 수 있다면 데드라인 스케쥴링이 가능하다.

10 대화식 사용자들에게 FIFO가 부적절한 프로세서 스케줄링이라는 점을 예를 들어 설명하라.

FIFO방식은 실행 시간이 긴 프로세스들 때문에 짧은 프로세스들이 오래 대기해야 하는 경우가 있다. 또한 중요하지 않은 프로세스 때문에 중요한 프로세스들이 오래 대기할 수 있다. 따라서 FIFO 방식은 사용자 입력에 대해 짧은 시간 안에 반응함을 보장할 수 없다. 그러므로 대화식 사용자들에게 FIFO는 부적절한 프로세서 스케줄링이다.

교수님 답

FIFO의 동작으로 한 프로세스가 시작하면 그 프로세스의 완료시까지 동작한다고 가정 한다. 즉, 비선점형 구조로써 동작한다. 이러한 구조는 시스템이 의미있는 대화식 응답시간을 보장하지 못하게 한다. 예로써 큰(혹은 수행시간이 긴) 프로세스가 하나의 프로세서를 가진 시스템에 들어간다고 가정하자. 그 프로세스가 수행되면 다른 프로세스들은 수행할 수가 없다. 웹 페이지를 보거나 SNS 메시지를 보내고자하는 사용자는 그 수행 시간이 긴 프로세스가 완료할 때까지 이러한 사용자 요구들에 대해 반응할 수 없다.

11 [연습문제 8-10]의 답을 바탕으로, 라운드로빈 방식이 대화식 사용자들에게 더 나은스케줄링인 이유를 설명하라.

라운드로빈 방식은 FIFO 순서대로 디스패치하지만 퀀텀 시간 안에서만 수행한다. 이 방식은 적절한 반응 시간을 보장해야 하는 대화식 환경에서 효과적이다. 시스템은 효율적인 문맥 전환 메커니즘을 사용하고, 대기 프로세스를 메인 메모리에 유지해 선점 때문에 발생하는 오버헤드를 최소화해야 한다.

교수님 답

라운드로빈 방식은 클럭에 의해 인터럽트되는 선점형 구조이다. 수행시간이 긴 프로세스들을 보다 짧은 프로세스들을 지연시킬 수 없다. 이는 짧은 프로세스들도 주기적으로 프로세서의 권리를 얻기 때문이다. 대화식 사용자들은 좋은 응답시간을 유지할 만큼 빈번 하게 프로세스들을 할당받는다.

14 다음 각 항목에서 잘못된 점을 지적하라.

a.   SPF는 SRT보다 처리량을 늘릴 수 없다.

경우에 따라 SRT는 SPF보다 더 많은 오버헤드를 발생시킬 수 있다. 그러므로 SPF는 SRT보다 더 많은 양의 처리를 할 수 있다.

b.  SPF는 공평하다.

공평하다는 것은 스케줄링 규칙이 유사한 프로세스들을 모두 동일하게 대우하고, 어떤 프로세스도 스케줄링 때문에 무기한 연기에 빠지지 않는다는 것을 의미한다. SPF방식은 완료 시까지 실행 시간이 가장 짧을 것으로 예상하는 프로세스를 선택한다. 만일 실행 시간이 상대적으로 짧은 프로세스가 계속하여 도착한다면 상대적으로 긴 프로세스는 무기한 연기에 빠질 수 있다. 따라서 공평하다고 할 수 없다.

c.   프로세스가 짧을수록, 시스템은 더 나은 서비스를 제공해야 한다.

우선순위가 낮은 프로세스가 우선순위가 높은 프로세스에 할당해야 할 핵심 자원을 보유하고 있어서 해당 프로세스를 빨리 반납할 수 있게 하기 위하여 우선순위가 낮은 프로세스에 평소보다 더 긴 실행 시간을 허용하는 ‘우선순위 역전’ 기술을 쓰는 경우가 아닌 한, 시스템은 짧은 프로세스에 굳이 더 나은 서비스를 제공해야 할 이유는 없다. 스케줄링 방법에 따라 짧은 프로세스가 더 높은 우선순위를 가질 수도 있지만, 그렇지 않은 경우도 있으므로 반드시 짧은 프로세스에게 더 나은 서비스를 제공해야 하는 것은 아니다.

d.  SPF는 짧은 프로세스를 선호하므로 시분할 시스템에서 유용하다.

SPF는 프로세스의 예상 종료 시간을 예측할 수 없다. 적절한 반응 시간을 보장해야 하는 환경에서는 부적합하다.

교수님 답

a. SRT는 선점에 드는 오버헤드시간이 존재하기 때문에 프로세스들의 수행시간이 짧을수록 SPF가 처리량이 더 많을 수 있다.

b. 프로세스들이 동작 순서대로 서비스되지 않는다. 수행 시간이 긴 프로세스들은 짧은 프 로세스가 먼저 서비스되기 떄문에 기다려야 한다.

c. 이 정책은 대화식 시분할 시스템에서는 빠른 응답 시간을 보장하기 위해서는 효과적인다. 그러나 프로세스의 상대적인 중요성(우선 순위)와 같은 다른 사항들을 무시한 것이다. 동 작하는 대부분의 프로세스들은 높은 우선순위를 요구하지 않지만 어떤 프로세스들은 특병 하게 긴급하게 서비스될 수 있다. 한 예가 데드라인 스케쥴링인데, 여기에서는 데드라인에 가까이 다가왔지만 만족할 만한 진행을 하지 못한 프로세스는 더 높은 우선순위를 할당받 아 수행시간을 더 많이 소비해야 한다.

d. SPF는 비선점형 스켸쥴링 정책이므로 대화식 사용자가 단순한 요구를 할 때 긴 시간을 수행할 수 있다. 이는 SPF가 완료시까지 수행을 계속하게 만들기 때문이다.

22 스케줄링 정책의 두 가지 공통적인 목적은 반응 시간을 최소화하고 자원 활용도를 극대화하는 것이다.

a.   이 두 가지 목적이 어떻게 상충하는지 설명하라. P392

반응 시간을 최소화하려면 언제든지 사용할 수 있는 충분한 자원을 보유하면 된다. 그러나 이 전략을 사용하면 자원 활용도가 떨어진다.

b.  이 장에서 제시한 스케줄링 정책을 이 두 가지 관점에서 분석하라. 사용자의 반응 시간에 편중된 정책은 어떤 것인가? 자원 활용도를 극대화하는 방향으로 편중된 정책은 어떤 것인가?

사용자의 반응 시간을 최소화하기 위해선 선점형이어야 한다. 따라서 반응 시간에 편중된 정책은 라운드로빈 방식이다.

자원 활용도를 극대화하기 위해선 프로세서가 노는 시간 없이 동작하는 것을 말한다. 자원 활용도 극대화에 편중된 정책은 SPF이다.

c.   두 가지 상충하는 목적을 균형 있게 이룰 수 있는 시스템이 되도록 새로운 스케줄링 정책을 개발하라.

자원을 적절히 활용하면서도 사용자의 반응 시간을 최소화하려면 다중 큐를 이용한 이기적 라운드로빈 방식을 들 수 있다.

교수님 답

a. 수행시간이 짧은 프로세스가 주요 장치들을 사용하지 않는다면, 그 프로세스들이 빠른 응답시간을 제공하더라도 자원 활용도는 매우 낮을 것이다.

b. 선점형 구조는 빠른 반응시간을 보장하는데 더 좋고 I/O 프로세스들의 혼합시 좋은 자원 활용도를 제공한다. 짧은 서비스 시간을 요구하는 프로세스들이 모든 장치들에 대해 항상 공평하게 사용되지 않기 때문에 어떤 장치들은 매우 활용도가 낮을 수 있다.

공평 공유 스케줄러는 보다 나은 장치 활용률을 제공한다. 이는 프로세서 시간이 우선순위 혹은 프로세스의 수행시간 뿐만 아니라 다양한 장치들을 공유하는 공평 공유 그룹내에 멤버쉽에 기반하여 설정되기 때문이다.

c. 자원 활용도를 균형있게 하기 위해서 저활용되는 자원들을 사용하는 프로세서들에게 우선순위를 높여준다. 그러면 우선 순위 그룹내에서 짧은 요구를 원하는 프로세스에게 우선 순위를 주게 함으로써 먼저 수행하도록 한다.

27 EDF와 SPF를 비교, 대조하라.

EDF는 최단 데드라인 우선 스케줄링 정책으로써 데드라인이 가장 임박한 프로세스를 디스패치하는 선점형 스케줄링이다.

SPF는 최단 프로세스 우선 스케줄링 정책으로써 비선점형이다. 실행 시간이 가장 짧을 것으로 예상하는 프로세스를 선택하여 실행한다. FIFO보다는 평균 대기 시간이 감소하지만 종료 시간을 예측하기가 어렵다.

EDF는 선점형인데 반하여 SPF는 비선점형이다. EDF는 데드라인이 가장 이른 프로세스를 먼저 스케줄링하고, SPF는 실행 시간이 가장 짧을 것으로 예상되는 프로세스를 먼저 스케줄링한다. 두 정책 모두 프로세스 완료 시간을 예측하기가 어렵다는 공통점이 있다.

교수님 답

   EDF와 SPF 모두 평균 대기 시간을 최소화하고 처리률을 최대화하도록 하는 선점형 스케쥴링 알고리즘이다. EDF에서는 처리율의 정의가 단위 시간당 데드라인을 만족하는 프로세스들의 수이고 SPF에서는 처리율의 정의는 단위시간당 완료되는 프로세스들의 수이다.

28 정적 실시간 스케줄링 알고리즘이 동적 실시간 스케줄링 알고리즘보다 적절한 때는 언제인가?

하드 실시간 시스템은 프로세스가 데드라인을 철저히 지키도록 보장해야 한다. 정적 스케줄링 알고리즘은 특정 시스템에 이러한 속성을 부여함은 물론 구현 오버헤드를 줄여준다.

교수님 답

정적 실시간 스케쥴링 알고리즘은 선점형 하드웨어를 제공하지 않는 시스템에 더 알맞다. 즉, 시스템이 그것의 모든 데드라인을 만족함을 증명해야 할 때 더 적절하다는 것을 의미한다. 즉, 자원을 공유하지 않고 새로운 프로세스가 만들어지지 않는 경우에 적절하다. 새로운 프로세스가 만들어지지 않는다는 의미는 실시간 스케쥴링을 수행할 시 실제 수행 시작시 알고 있었던 프로세스들을 제외하고 새로운 프로세스가 만들어져 수행하지 않는다는 것이다.

참고로 동적 실시간 스케쥴링 알고리즘은 시간에 따라 프로세스의 우선순위가 변할 때 더 적절하다.

29 썬에서 현재의 솔라리스 운영체제를 구현하기 전에 주로 워크스테이션으로 사용한썬 유닉스 시스템 70은 기본 우선순위를 할당하고, 우선순위를 조절함으로써 프로세스들을 스케줄링했다. 기본 우선순위는 최대 -20에서 최소 +20이었고, 중간 값은 0이었다. 우선순위 값은 시스템의 조건이 변함에 따라 조절되었다. 이 값들을 기본 우선순위 값에 더해 현재 우선순위 값을 계산했다. 그리고 현재 우선순위 값이 가장 높은 프로세스를 먼저 디스패치했다.

        우선순위 조절은 최근 프로세서 시간을 비교적 적게 사용한 프로세스들을 선호하는 경향이 강했다. 스케줄링 알고리즘은 동작 방식이 변하는 프로세스들이 이점을 얻도록 프로세서 사용 형태를 재빨리 ‘잊는다’. 알고리즘은 최근 5Xn초 동안의 프로세서 사용 현황을 90% 잊는다. n은 마지막 1분 동안의 실행 가능 프로세스 수의 평균이다. 이러한 프로세스 스케줄링 알고리즘과 관련해 다음 각 질문에 답하라.

a.   시스템 부하가 클 때와 작을 때 중 언제 프로세서 중심 프로세스를 선호하는가?

시스템 부하가 클 때 프로세서 중심 프로세스를 선호한다.

b.  입출력 중심 프로세스는 입출력 완료 후에 어떻게 즉시 실행할 수 있는가?

입출력 중심 프로세스는 프로세서를 잠시 사용하고 반납한다. 따라서 프로세서 시간을 비교적 적게 사용하므로 우선순위가 높아진다.

c.   프로세서 중심 프로세스가 무기한 연기될 위험이 있는가?

우선순위가 낮은 프로세스는 프로세서 시간을 비교적 적게 사용했으므로 우선순위가 점점 높아진다. 따라서 무기한 연기될 위험이 크지 않다.

d.  시스템의 부하가 증가할 때 프로세서 중심 프로세스는 상호 작용 반응 시간에 어떤 영향을 미치는가?

부하가 증가하면 프로세서 중심 프로세스는 이따금씩 지연이 생길 수도 있다.

e.  이 알고리즘은 프로세스가 프로세서 중심에서 입출력 중심으로, 혹은 그 반대로 변할 때 어떻게 반응하는가?

교수님 답

a. 시스템 부하가 작을때

b. 최근의 프로세서 사용 부하가 작게 될 수 있다. 그래서 프로세서를 바로 사용할 수 있다.

c. 프로세스가 수행할 수 있을 만큼 높은 우선순위를 얻을 때까지 알고리즘은 최근의 프로세서 사용한 것을 기억하지 못하기 때문에 무기한 연기될 가능성은 없음.

d. 프로세서 중심 프로세스들은 대화식 프로세스들보다 낮은 우선순위를 가진다. 그래서 대 화식 프로세스들이 좋은 응답시간을 가지게 된다. 프로세서 중심 프로세스들은 가끔씩 사용시간인 퀀텀을 받아서 수행한다. 프로세서 중심 프로세스가 많을수록 더 많은 퀀텀이 사용된다. 이것은 대화식 사용자들에게는 응답시간이 길어지게 하는 원인이 된다. 물론 프로세서 중심 프로세스의 수가 커지면 포화 지점이 있게 된다. 즉 더 이상 프로세스 중심 프로세스를 더 받지 않게 된다. 받더라도 대화식 사용자의 응답시간을 지연시키지 않는다. 그러나 선 알고리즘에서는 합리적인 프로세서 중심 부하가 시스템상에서 동작할 때 대화식 사용자에게 좋은 응답시간을 주도록 동작하게 하였다.

e. 알고리즘은 “기억 상실” 떄문에 조정된다. 프로세서 중심에서 입출력 중심으로 변환은 시스템이 어떤 시간동안 프로세스 중심으로 고려하여야 하기때문에 약간 동작이 느리다. 입출력 중심에서 프로세서 중심으로 변환은 첫 몇 퀀텀동안 실제로 프로세스들에게 프로세서를 많이 할당하게 해준다.

[OS]운영체제론 연습문제 7장 - 문제 및 해설

01 교착 상태가 무엇인지 정의하라.

교착 상태란 둘 이상의 프로세스가 각자가 가지고 있던 자원을 보유한 채로 외부적 조치가 없는 한 영원히 그 상태에서 기다리고 있는 상황을 말한다.

교수님 답

교착상태(데드락, deadlock)는 하나 이상의 프로세스들이 결코 일어날 수 없는 이벤트 를 기다리는 상황을 의미한다. 즉, 교착상태는 프로세스 A가 사용하고 있는 자원을 기다리는 다른 프로세스 B에 의해 사용되는 자원을 기다리는 프로세스 A 상황에서 발생한다.

04 무기한 연기는 무엇인가? 교착 상태와 어떻게 다른가? 무기한 연기와 교착 상태의 유사점은 무엇인가?

무기한 연기란 운영체제가 많은 프로세스들의 다양한 요청을 처리해 주다가 몇몇 프로세스가 매우 오랜 시간 동안 서비스를 받지 못하는 경우가 발생하는 상황을 말한다.

무기한 연기 상태인 사용자는 오랜 기간 서비스를 할당 받지 못한다. 이들의 사용자들은 마치 자신들이 교착 상태에 빠진 것과 유사한 기분을 느끼게 될 것이다. 그러나 실제로 교착 상태와는 달리 오랜 시간 후에라도 무한 대기로부터 벗어나 서비스를 받을 수 있다.

교수님 답

무기한 연기 : 이벤트의 어떤 특정 시간과 순서가 프로세스(혹은 스레드)의 수행을 하지 못 하게 만드는 경우 발생하는 상태이다. 무기한 연기의 주된 이유는 선입선출 방식보다 우선 순위대로 요구들을 서비스하는데 있다. 우선 순위 구조는 보다 높은 우선 순위의 프로세스 혹은 스레드가 보다 낮은 프로세스(혹은 스레드)를 반복적으로 중지시키게 됨으로써 낮은 프로세스(혹은 스레드)에서는 무기한 연기가 생기게 된다.

교착상태와의 차이점 : 무기한 연기되고 있는 프로세스는 결국 수행을 하게 되지만 프로세스들이 교착상태가 되면 해당 프로세스들은 결코 수행을 재개할 수 없다.(최소한 시스템 내의 한 부분을 희생하지 않고서는 수행 재개 불가능함)

교착상태와 유사점 : 수행을 더 이상 하지 않는다는 것이 유사함. 지연 시간이 길어질수록 사용자, 오퍼레이터 등은 프로세스가 교착상태 혹은 무기한 연기 상태에 있는지를 구분하지 못한다.

08 프로세스 n개가 있는 시스템에서 이 프로세스들의 부분 집합인 m이 현재 무기한 연기 상태에 빠져있다. 시스템에서 어떤 프로세스가 무기한 연기되고 있는지 파악할 수 있는가?

프로세스들은 무기한 연기 상태일 수도 있지만 아닐 수도 있다. 프로세스들은 곧 발생할 이벤트를 대기하고 있을 수도 있고, 무한 루프에 빠진 것일 수도 있고, 곧 끝날 복잡한 계산을 하고 있을 수도 있다. 그저 ‘기능이 멈춘’ 것처럼 보일 수도 있다는 것이다. 따라서 시스템에서는 어떤 프로세스가 무기한 연기되고 있는지 장담할 수 없다.

교수님 답

일반적인 경우에 있어서는 파악할 수 없다. 이는 프로그램의 수행 경로를 예측할 수 없 기 때문이다. 즉 어떤 프로세스들의 경우에는 무기한 연기를 방금 시작하여 성능적인 측 면에서는 아직 프로그램에서 지연을 시키는지 시스템에서 무기한 연기를 시키는지를 판단 할 수 없기 때문이다.

09 철학자들의 만찬 문제 : 모니터를 사용해 철학자들의 행동을 시뮬레이션하는 병행 프로그램을 작성하라. 프로그램은 교착 상태나 무기한 연기의 위험이 없어야 한다. 상호 배제를 보장해야 한다.

(a)  

pickUpLeftFork();             //모든 철학자가 동시에 왼쪽 포크를 집어들면 다음 줄로 넘어갈 수 없기 때문에 이 줄에서 교착상태가 일어나게 된다.

pickUpRightFork();    

eat();

putDownLeftFork();

putDownRightFork();

(b)  

pickUpBothForksAtOnce();   //특정 철학자만 계속하여 포크를 집을 기회를 획득하여, 기회를 획득하지 못하는 철학자가 발생할 수 있다.

eat();

pickDownBothForksAtOnce();

(c)  

while(notHoldingBothForks)

{

        pickUpLeftFork();

        if(rightForkNotAvailable)     putDownLeftFork();   //모든 철학자가 동시에 왼쪽 포크를 들고 다시 내려놓기만을 반복하는 livelock상태가 발생할 수 있다.

        else pickUpRightFork();

}

eat();

putDownLeftFork();

putDownRightFork();

(d)  

if(philosopherID%2==0){     //짝수 번째 철학자들은 왼쪽 포크부터 집어든다.

        pickUpLeftFork();     

pickUpRightFork();    

eat();

putDownLeftFork();

putDownRightFork();

} else {               //홀수 번째 철학자들은 오른쪽 포크부터 집어든다.

pickUpRightFork();    

pickUpLeftFork();      

eat();

putDownRightFork();

putDownLeftFork();

        }

이와 같은 경우, 먼저 포크를 집은 사람이 식사를 하고 있을 때, 그 양 옆의 사람 중 한 명은 포크 하나를 든 상태로 대기하다가 식사를 하던 옆 사람이 포크를 내려놓으면 바로 그 포크를 집어들 수 있다. 따라서 비슷한 횟수로 식사에 성공하게 되므로 위의 문제들을 모두 해결한 알고리즘이라고 할 수 있다.

교수님 답

 (철학자의 만찬)

a. 이 내용은 철학자들이 알맞게 먹는 것을 허용하지만 교착상태에 들어간다. 예로써, 모든 철학자들이 그들의 왼쪽 포크들을 먼저 집는다고 가정하자. 철학자들이 그들의 오른쪽 포크를 집고자 할 때 사용가능한 오른쪽 포크는 없게 된다. 즉 교착상태이다.

b. 이 내용은 “줄다리기” 해결책의 하나이다.  2명의 철학자가 그들의 포크를 집고 먹고 내려놓고 하는 동작을 무한정 반복한다. 이 방법은 다른 철학자들을 굶게 한다. 즉, 다른 철학자들 관점에서 보면 무기한 연기를 하게 만든다.

c. 이 내용은 혹 가다가 동작하지만 너무 자주 무기한 연기(즉, 철학자들을 굶게 만드는 원인임)를 발생한다. 5명의 철학자들이 동기화되어 왼쪽 포크를 집어 들고 오른쪽 포크가 없다는 것을 보면 그들의 왼쪽 포크를 내려놓는다고 가정한다. 이러한 순서는 무한정 갈 수 있다.

d. 이 내용은 순환 대기가 결코 발생하지 않기 때문에 교착상태를 방지할 수 있다. 철학자들이 원탁에 앉아 있기 때문에 순환대기는 모든 철학자가 교착상태에 들어가면 발생한다. 그러나 짝수 번호의 철학자들이 왼쪽 포크를 먼저 집어 들고 홀수 번호의 철학자들은 오른 쪽 포크를 먼저 집어들기 때문에 먼저 같은 포크를 집어 들고자 하는 한 쌍의 철학자들만 있다. 이러한 철학자들 중 어떠한 사람도 다른 사람을 기다리는 동안 포크를 가지고 있는 사람이 없기 때문에 이러한 좌석 구성에서는 순환대기는 결코 발생하지 않고 그래서 교착 상태는 발생하지 않는다. 그러나 특정 철학자가 포크를 항상 가지고 있다면 무한 연기가 발생할 가능성도 있다.

11 교착 상태가 발생하기 위한 네 가지 필요 조건을 기술하라. 각 조건이 왜 필요한지 직관적으로 생각나는 이유들에 대해 논하라.

상호 배제 조건 : 두 개 이상의 프로세스가 동시에 임계영역에 접근하는 경우 공유자원의 혼란이 올 수 있기 때문이다.

대기 조건 또는 보유 후 대기 조건 : 프로세스들이 서로 자신의 자원은 내놓지 않고 동시에 서로의 자원을 획득하기 위해 대기하는 경우 어느 프로세스도 결코 원하는 자원을 얻을 수 없기 때문이다.

비선점 조건 : 프로세스는 자원을 무한정 사용하거나 기아상태의 프로세스가 발생할 수 있기 때문이다.

순환 대기 조건 : 순환 고리형이 아니라면 이 프로세스들은 언젠간 자원을 획득하게 될 수도 있다. 고리형이어야 프로세스들이 원하는 자원을 획득할 수 없는 교착 상태가 된다.

교수님 답

4가지 필요 조건 : 상호배제조건, 대기 조건, 비선점 조건, 순환대기 조건    상호배제조건 : 자원은 한 번에 단 하나의 프로세스에 의해 배타적으로 사용된다. 이 때문에 다른 프로세스를 강제적으로 대기시키게 하는 방식이 만들어짐.

대기 조건 : 배타적으로 자원을 획득한 프로세스가 해당자원을 보유한 채 다른 자원을 얻으려고 대기할 수 있다.

비선점 조건 : 일단 프로세스가 자원을 확보하면 해당 프로세스가 자원을 모두 사용할 때까지 시스템이 프로세스의 제어를 빼앗을 수 없다.

순환대기 조건: 2개 이상 프로세스가 순환고리를 형성하고 있는 경우에 해당된다. 즉 프로세스들이 순환고리 안에 있는 다음 프로세스가 점유하고 있는 자원을 대기한다.

19 교착 상태 회피가 교착 상태 방지보다 직관적으로 호소력이 있는 이유는 무엇인가?

교착 상태 방지를 사용하면 자원 활용도가 떨어지는 결과를 초래한다. 그러나 교착 상태 회피는 교착 상태의 가능성이 어느 정도 있을 수 있지만 교착 상태가 발생하려는 조짐이 보일 때마다 조심스럽게 비켜서는 전략을 취한다. 따라서 교착 상태도 피하고 자원 활용도도 높일 수 있는 것이다.

교수님 답

교착상태 회피는 자원 사용을 더 효율적으로 하는 것으로 보인다. 역시 교착상태회피가 더 많은 동시 사용자를 허용한다.

24 자원을 그룹으로 할당하면 은행원 알고리즘이 여전히 제대로 동작할 수 있는가? 답을 상세히 설명하라.

자원을 그룹으로 할당해도 가용 자원 수가 현재 요청 수 보다 많고, 그로 인하여 프로세스가 정상적으로 수행되며, 반납된 자원을 이용하여 다른 프로세스들을 모두 수행할 수 있다면 제대로 동작할 수 있을 것이다.

교수님 답

가능하다. 이것은 시스템의 상태에 의존적이다. 목표가 단순히 모든 시간내내 시스템의 상태를 안전하게 유지하는 것이다. 충분한 자원들이 요구를 들어주고 시스템의 안전상태 를 유지할 만큼 충분하면 은행원 알고리즘은 잘 동작한다.

25 은행원 알고리즘을 사용해 교착 상태 회피 방법을 사용하는 시스템이 다섯 개 프로세스(1, 2, 3, 4, 5 프로세스)와 네 가지 유형(A, B, C, D)의 자원을 포함하고 있다. 각 유형에는 여러 자원이 있다. 표[7-7]과 [표7-8]에 나타낸 이 시스템은 안전 상태인가? 답을 설명하라. 안전 상태면 모든 프로세스가 성공적으로 실행을 마칠 수 있는 방법을 보여라. 불안전 상태면 교착 상태가 어떻게 발생할 수 있는지 보여라.

위와 같이 모든 프로세스의 실행을 성공적으로 마칠 수 있으므로 해당 알고리즘은 안전 상태이다.

교수님 답

각 자원의 유형에 대한 현 요구가 유용한 유형의 자원의 수보다 적거나 같으면 프로세스의 수행은 마치고 모든 자원을 반납한다. 프로세스 2 혹은 프로세스 5는 현 상태에서 마칠 수 있다. 다음의 이벤트 순서를 생각하자: 프로세스 2가 마치면 유용한 자원의 상태는 (3,7,1,3)이 된다. 프로세스 5가 마치게 되면 유용한 자원의 상태는 (7,9,2,6)이 된다. 이 시점에서 남아 있는 각 프로세스들은 마칠 수 있고 자원들을 반납한다. 결국 모든 프로세스들의 수행은 끝나게 된다. 따라서 상태는 안전 상태이다.

28 교착 상태가 발생할 가능성이 있는 시스템에서 어떤 경우에 교착 상태 탐지 알고리즘을 사용하겠는가?

교착 상태 탐지 : 교착 상태가 발생할 수 있는 시스템에서 사용한다. 교착 상태 탐지의 목적은 교착 상태 발생 여부와 관련 프로세스 및 자원을 밝히는 것이다. 교착 상태 발생을 허용하면서 교착 상태의 위치를 추적하고 제거한다.

교착 상태 탐지 알고리즘은 대체로 교착 상태 성립을 위한 다른 조건들을 충족함을 전제로 할 때 ‘순환 대기 존재 여부’에 초점을 맞춘다. 즉 ‘순환 대기’의 경우에 해당 알고리즘을 사용한다.

교수님 답

교착상태가 의심될 때 사용된다. 즉 어떤 프로세스들이 잠시 동안 동작하는 상태로 들어가지 못하거나 혹은 초기 감지 후 주기적으로 동작하고자 할 때 사용된다.

34 자원이 고장나서 사용이 어려워지면, 일반적으로 교착 상태와 무기한 연기의 위험이 증가하는가, 감소하는가? 답을 설명하라.

교착 상태의 위험성은 증가한다. 자원이 고장나지 않았으면 제대로 수행될 수 있었을 프로세스의 자원요청이 좌절될 수 있기 때문이다. 하지만 무기한 연기의 위험과는 관계가 없다. 자원이 줄어듦으로 인하여 프로세스가 대기하는 시간만 늘어날 뿐, 그 위험성이 증가하지는 않는다.

교수님 답

그러한 상태는 교착상태와 무기한 연기의 가능성을 증가시킬 수 있다. 은행원 알고리즘 의 교착회피 구조에서 이전의 안전 상태를 불안전하게 만드는 효과를 가져올 수 있다. 즉, 프로세스가 수행할 수 있는 유용한 자원이 없어지기 때문에 프로세스의 수행을 끝낼 수 없는 상태가 될 수 있다.

[OS]운영체제론 연습문제 6장 - 문제 및 해설

01 모니터와 세마포어 연산을 비교, 대조하라.

세마포어는 이미 정해져 있는 P, V 함수를 이용하지만, 모니터는 조건 변수를 이용하여 직접 스레드와 자원을 관리한다.

교수님 답

모니터 : 모니터의 클라이언트가 그 변수들을 직접적으로 접근할 수 없고 클라이언트가 내부 모니터 프로시져(함수)를 접근할 수 없는 정보 은닉(information hiding)의 주요 기술이다. 세마포어와 비교하면 상위 수준의 수단이다. 동기화와 상호배제를 위하여 직접 모니터 내부의 변수와 함수들을 호출할 수 없다.

세마포어 : 스레드 동기화와 상호배제를 수행하는 매우 낮은 수준의 수단이다. 사실 모니터는 세마포어를 활용하여 만들어져 모니터는 세마포어만큼 강한 도구이다. 즉, P,V 연 산을 통하여 직접 세마포어 관련 변수들과 함수들을 호출한다.

03 조건 변수는 전통적인 변수들과 어떻게 다른가? 조건 변수를 초기화하는 것이 의미가 있는가?

모니터 내부에 있는 스레드는 모니터 밖에서 조건을 대기할 때 조건 변수를 사용한다. 모니터는 구별된 조건 변수를, 스레드를 대기하게 할 수 있는 구별된 상황들과 연관 짓는다. 조건 변수는 전통적인 변수와 다르다. 모든 조건 변수에는 관련된 큐가 있다. 특정 조건 변수에 wait를 호출하는 스레드는 해당 조건 변수와 연관된 큐에 놓인다. 조건 변수를 초기화하는 것은 모니터에 있는 스레드에 신호를 보내는 것이다.

교수님 답

전통적인 변수들은 단순히 값들을 포함하는 저장장소들이다. 이러한 변수들은 변수들을 읽고 쓸 수 있는 프로그램 코드에 의해 접근가능하다.

반면에 조건 변수는 신호를 받기 위하여 조건변수를 기다리는 스레드 큐와 연관되어 있다. 모니터의 클라이언트가 직접적으로 그것의 조건변수를 참조할 수 없고, 조건 변수에 대한 모든 연산은 모니터 함수들(클라이언트가 직접 접근할 수 없음)을 통하여 클라이언트에서 수행되어진다. 따라서 초기화는 의미가 없음

주) 초기화와 변수 정의는 구분하길 바람. 변수 정의는 변수(클라스인 경우 함수)들에 대 한 저장 장소를 마련하는 것이고 초기화는 필요시 그 저장장소에 알맞은 값을 넣는 것임.

06 순차적 프로그램에 비해 병행 프로그램의 작성이나 수정, 테스트, 정확성 검증이 훨씬 어려운 이유는 무엇인가?

컴퓨터는 유한 상태 머신으로 간주할 수 있다. 컴퓨터는 많은 상태 수를 가질 수 있다. 모든 시스템에 대한 전수 검사는 불가능하다. 이는 시스템에 철저하게 테스트한 후에도 여전히 ‘잠복된 버그’들이 있을 수 있다는 의미다. 병행 프로그램을 코딩, 디버깅, 수정하고 정확성을 증명하는 일은 어려운 작업이다. 왜냐하면 병행 프로그램은 순차적 프로그램과 달리 공유 자원이 존재하기 때문이다.

교수님 답

병행 동작들은 다중프로세스와 같은 병렬 컴퓨팅 구조상에서 동시에 수행되는 형태를 포함 한 절차들에서 수행된다. 다른 문제는 미묘한 타이밍 문제들 때문에 병행 프로그램은 오 동작을 할 수 있다는 것이다. 일어나는 이벤트의 정확한 순서를 모사하는 것이 불가능하며 디버깅 시스템은 어렵다. 수천대의 비행기의 움직임을 모니터링하여 비행 관제 제어시 스템을 예로 보자: 관제 제어시스템에서 버그가 감지되었을 때 비행기가 있었던 위치를 정확하게 비행기가 재위치한다는 것은 불가능하다.

또한 하나의 프로세스 A가 다른 프로세스들과 (통신 혹은 신호등을 통하여) 연동하여 동 작할 때 프로세스 A를 테스트할 시 다른 프로세스들의 동작들의 수행을 제어할 수 없기 때문에(이는 병행 수행이고 디버깅시 제어는 프로세스 A만 가능하기 때문) 항상 프로세스 A의 테스트시 다른 결과가 나올 수 있기 때문에 디버깅이 쉽지 않다.