Operating System Concepts 9th

1.1 In a multi-programming and time-sharing environment, several users

share the system simultaneously. This situation can result in various

security problems.

a. What are two such problems?

저장장소나 메모리 자원 등의 공유로 인해 데이터의 보안이 약할 수 있다.

다른 유저의 데이터를 훔치거나 복사할 수 있다.

b. Can we ensure the same degree of security in a time-shared

machine as in a dedicated machine? Explain your answer.

특수 목적으로 사용이 허가된 한정된 인원이 사용하는 전용 컴퓨터(군사 목적의 워크스테이션 등)에 비해서 범용 컴퓨터(도서관의 프린터용 컴퓨터 등)의 경우 컴퓨터 기술 외적으로 물리적인 보안에서 차이가 나기 때문에 전용컴퓨터 정도의 보안을 보장할 수는 없을 것 같다.

1.13 The issue of resource utilization shows up in different forms in different

types of operating systems. List what resources must be managed

carefully in the following settings:

a. Mainframe or minicomputer systems

한 대에 여러사람이 접속하기 때문에 cpu time, memory, I/O 가 효율적으로 공평하게 공유될 수 있게 고려해야한다.

b. Workstations connected to servers

c. Mobile computers

1.4 Describe the differences between symmetric and asymmetric multiprocessing.

What are three advantages and one disadvantage of multiprocessor

systems?

대칭적 멀티프로세싱은 CPU 가 서로 정보를 공유하여 동일한 프로세스를 병렬적으로 수행한다. 이는 특정 CPU의 과부하를 막을 수 있고 여러 CPU 중 일부에 문제가 생기더라도 문제가 없는 CPU에 작업을 분배하여 안정성이 높다.

비대칭적 멀티프로세싱의 경우 각 CPU가 프로세스 내에 수행되는 각 역할을 나누어 지정된 해당 역할만 수행하는 형태로 구현이 쉽지만, 일부 CPU에 이상이 생겼을 시 해당 CPU가 맡고 있던 작업이 수행되지 않아 프로세스 전체의 구동이 멈추던가 혹은 모든 CPU에 이상이 없더라도 각 CPU당 작업의 강도가 달라 일부 CPU에 과부하가 걸려 동작효율이 나빠질 수 있다.

1.5 How do clustered systems differ from multiprocessor systems? What is

required for two machines belonging to a cluster to cooperate to provide

a highly available service?

멀티프로세서 시스템은 하나의 컴퓨터 내에 여러개의 CPU가 있는 것, 클러스터 시스템은 독립적인 다수의 컴퓨터가 협업을 통해 동작을 수행하는 것을 말하며 이를 위해서는 컴퓨터간의 데이터 공유를 위한 통신이 필요하다.

1.8 What is the purpose of interrupts? How does an interrupt differ from a

trap? Can traps be generated intentionally by a user program? If so, for

what purpose?

인터럽트란 프로세서가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 또는 예외상황이 발생하여 처리가 필요한 경우 프로세서에 알려 처리할 수 있도록 하는 것.

트랩은 어떤 프로세스가 특정 시스템 기능을 사용하려고 할 때 그 기능을 운영체제에게 요청하는 것.

트랩은 에러를 처리할때나 디버깅을 좀더 편리하게 하기위해 의도적으로 발생시킬 수 있다.

1.13 Discuss, with examples, how the problem of maintaining coherence of

cached data manifests itself in the following processing environments:

a. Single-processor systems

예를 들어 한 변수A가 디스크에 저장되어 있을 때 특정 프로세스에 의해서 이 변수A가 변경되는 동작이 시행된다면 해당 변수A는 메인메모리를 통해 프로세스의 레지스터에 저장되어 있는 상태로 값의 변화가 시행되는데 이 시점에서 변경된 값은 디스크에 업데이트 되지 않은 상태이기 때문에 일관성에 문제가 생긴다.

b. Multiprocessor systems

위와 같은 상황에서 프로세스가 여러개라면, 각각의 프로세스는 스스로의 캐쉬메모리를 가지고 있기 때문에 여러개의 프로세스가 동시에 해당 변수A에 접근하여 병렬적으로 서로 다른 값의 변화를 주는 동작을 수행한다면 각 캐쉬메모리에 저장되어있는 동일한 이름의 변수A는 같은 데이터임에도 불구하고 값이 달라질 수 있다.

c. Distributed systems

분산 환경에서는 한 파일의 여러 복사본이 다른 여러 컴퓨터에 저장되어 있을 수 있는데 이 복사된 파일들이 동시에 접근되거나 변경될 수 있기 때문에 해당파일의 일관성에 문제가 생길 수 있다.

1.14 Describe a mechanism for enforcing memory protection in order to

prevent a program from modifying the memory associated with other

programs.

메모리 주소를 지정하여 프로세스가 자신만의 주소 공간내의 메모리를 사용하도록 실행시킬 수 있다.

타이머를 이용하여 프로세스가 CPU를 관리할 권한을 갖지 못하게 할 수 있다.

장치관리 레지스터는 유저가 접근할 수 없도록 함으로써 주변 장치의 데이터 완전성은 보호될 수 있다.

1.17 What are some advantages of peer-to-peer systems over client-server

systems?

모든 유저의 단말기가 서버역할을 겸비하기 때문에 p2p 네트워크 전체를 shut down 시키는 것은 거의 불가능하고 네트워크가 커짐에 따라 들어가는 비용이 거의 없어 확장성이 높다. 또한 같은 이유로 불균형적인 통신 과부하가 줄어든다.

1.18 Describe some distributed applications that would be appropriate for a

peer-to-peer system.

토렌트와 같은 유저간 파일 공유 프로그램, 비트코인과 같은 가상 화폐에 대한 응용 등이 있다.

Practice Exercises

1.1 What are the three main purposes of an operating system?

사용자가 컴퓨터를 사용하기 쉽게 하기 위한 인터페이스 제공

자원의 효율적인 할당

여러 가지 주변 장치와 사용자 프로그램의 컨트롤 (에러방지와 부적절한 사용 방지)

1.2 We have stressed the need for an operating system to make efficient use

of the computing hardware. When is it appropriate for the operating

system to forsake this principle and to “waste” resources? Why is such

a system not really wasteful?

개인용 시스템은 사용자를 위해 최적화 되어야 한다. GUI는 자원을 낭비하지만 시스템과 유저의 상호작용을 최적화할 수 있기 때문에 사용된다.

1.3 What is the main difficulty that a programmer must overcome in writing

an operating system for a real-time environment?

제한된 시간을 지키는 것. 시스템이 제한된 시간내에 일을 수행하지 못하면 그것은 시스템전체의 고장을 야기시키기 때문에 RTOS 를 짜는 프로그래머는 스케쥴링 계획에서 응답 시간이 제한된 시간을 초과하지 않도록 반드시 보장해야 한다.

1.4 Keeping in mind the various definitions of operating system, consider

whether the operating system should include applications such as web

browsers and mail programs. Argue both that it should and that it should

not, and support your answers.

어플리케이션을 운영체제에 포함시키면 물론 수행 속도는 빨라질 것이다. 그러나 보안에 취약해지고, 운영체제를 부풀리게 되어 비효율적이게 된다.

1.5 How does the distinction between kernel mode and user mode function

as a rudimentary form of protection (security) system?

특정한 인스트럭션들 만이 CPU가 커널모드일때 사용될 수 있다. 하드웨어 장치들은 프로그램이 커널 모드에서 실행되고 있을 때만 접근될 수 있다. 인스트럭션들이 사용될지 혹은 사용되지 않을지에 대한 결정 역시 CPU가 커널모드일때만 가능하다. 그 결과 CPU는 유저모드에서 매우 제한적으로 사용되는데 이는 치명적인 자원에 대한 보호가 된다.

1.6 Which of the following instructions should be privileged?

a. Set value of timer.

b. Read the clock.

c. Clear memory.

d. Issue a trap instruction.

e. Turn off interrupts.

f. Modify entries in device-status table.

g. Switch from user to kernel mode.

h. Access I/O device.

1.7 Some early computers protected the operating system by placing it in

a memory partition that could not be modified by either the user job

or the operating system itself. Describe two difficulties that you think

could arise with such a scheme.

운영체제에 의해 요구되는 데이터들은 보호되지 않는 메모리에 저장되거나 그 부분으로 이동되어야 허가되지 않은 유저가 접근 가능하다..??

1.8 Some CPUs provide for more than two modes of operation. What are

two possible uses of these multiple modes?

유저모드와 커널모드 등과 같이 나눔으로써 좀더 나은 보안 정책을 제공할 수 있다.

1.9 Timers could be used to compute the current time. Provide a short

description of how this could be accomplished.

1.10 Give two reasons why caches are useful. What problems do they solve?

What problems do they cause? If a cache can be made as large as the

device for which it is caching (for instance, a cache as large as a disk),

why not make it that large and eliminate the device?

속도가 다른 장치들 사이에 데이터를 전송할 때 중간에 캐쉬에 미리 저장함으로써 빠른 장치가 느린 장치를 기다릴 필요가 없어진다. 많은 수의 캐쉬는 데이터 일관성부분에서 문제를 일으킬 수 있고, 캐쉬는 비용이 커 디스크만큼 크게 만들 수 없다. 또한 캐시 메모리는 휘발성이기 때문에 대량의 데이터를 저장하기에 부적절하다. 또한 캐시메모리의 용량이 크면 주소를 계산하는데 많은 시간이 걸리기 때문에 용량과 속도가 비례하지 않는다.

1.11 Distinguish between the client–erver and peer-to-peer models of

distributed systems.

클라이언트-서버 시스템의 경우 역할이 정확하게 나뉘어 있어 클라이언트가 서비스를 요청하면 서버가 서비스를 제공하는 방식이지만 peer-to-peer 모델의 경우 역할이 명확하게 나뉘지 않아 노드가 서비스를 요청할수도, 혹은 다른노드에게 서비스를 제공할 수 도 있다.

2.5 시스템 프로그램 (System Programs)

운영체제는 알려진 프로그램의 개발과 실행을 위해 좀 더 편리한 환경을 구축하도록 도움을 주는 시스템 유틸리티(System Utility) 즉, 시스템 프로그램을 제공한다. 다음과 같은 범주로 분류할 수 있다.

파일 관리 : 파일과 디렉터리를 생성(create), 삭제(delete), 복사(copy), 이름변경(rename), 인쇄(print), 덤프(dump), 리스트(list) 등 일반적인 조작

상태 정보 : 시스템의 날짜(date), 사용가능한 메모리(memory)와 디스크의 공간의 양, 사용자 수 와같은 상태 정보를 제공한다.

파일 변경 : 디스크 혹은 다른 저장장치의 파일의 내용을 생성하고 변경하기위해 사용된다. Windows의 메모장(notepad)나 Linux의 vi, emacs 같은 것이 속한다. 통칭 문장 편집기(text editor(라 불린다.

프로그래밍 언어 지원 : 일반적인 프로그래밍 언어들(C, C++, JAVA 등)에 대한 컴파일러(Compilers), 어셈블러(Assemblers), 인터프리터(Interpreters)가 제공된다.

프로그램 적제와 실행 : 프로그램이 실행되기 위해서는 메모리에 적제되어야 한다. 그를 위한 절대 로더(absolute loader), 재배치 가능 로더(relocatable loder), 링키지 에디터(linkage editor)와 중첩 로드(overlay loader) 등을 제공할 수 있다.

통신 : E-mail, remote login, telnet 등을 통해 통신 관련 서비스를 제공한다.

1.1. 마이크로 커널

1970년대에 발명된 마이크로 커널은 운영체제의 서비스를 커널에서 꺼내서 사용자 모드로 옮겨서 사용하는 것을 기본 아이디어로 한다.

초기 운영체제 시스템은 컴퓨터 메모리의 한계 때문에 작게 설계될 수 밖에 없었다. 컴퓨터의 성능이 좋아지면서 운영체제가 다루는 장치의 갯수가 늘어나고 커널역시 이들 장치를 제어하기 위해서 점점 커지게 된다. 초기 유닉스 시스템의 커널은 디바이스 드라이버와 파일 시스템 관리 기능등을 포함해도 매우 작은 크기를 가질 뿐이었다. 주소공간이 16비트에서 32비트로 확장되면서 커널 디자인은 비좁흔 하드웨어의 구조적 제한에서 벗어나서 독립적으로 성장한다.

버클리 UNIX는 커다란 커널을 가진 최초의 유닉스 시스템이라고 할 수 있다. 이 운영체제는 CPU, 디스크, 프린터를 제어하기위한 기능들외에 파일 시스템과 완전한 TCP/IP 네트워킹 시스템을 포함했다. 그리고 수년에 걸쳐서 지속적으로 기능을 추가하면서 그 크기가 수백만 라인에 이르게 되었다. 코드가 방대해진 만큼 커널은 관리하기 힘들어졌고 그만큼 버그를 포함할 가능성이 높아졌다.

마이크로 커널은 핵심 기능만 유지하고 나머지는 유저 스페이스 영역에서 모듈형태로 개발해서 덧붙이는 방식으로 디자인 되었다. 커널은 작은 크기로 유지되므로 그만큼 유지하기가 쉬웠으며, 모놀리틱 커널에 비해서 더 견고하게 개발할 수 있다.

단점은 message passing 문제로 인한 성능 저하다.

2.2 운영체제에게 매개변수를 전달하는 보편적인 방법 3가지를 설명하시오.

가장 간단한 방법은 매개변수를 레지스터로 바로 넘겨주는 것이다. 하지만 이 방법은 레지스터의 개수에 따라 전달할 수 있는 매개변수의 개수가 한정되기 때문에 메모리에 있는 블록 혹은 테이블에 저장하여 해당 블록 및 테이블의 주소를 전송하는 방법을 택한다. 또는 메모리의 스택에 매개변수를 넣거나(push) 빼내어(pop) 전달할 수 있다.

2.9 운영체제의 두 구성요소가 서로에게 종속적인 경우 계층구조로 시스템을 구성하는 것이 어려울 때가 있다. 서로의 기능이 밀접하게 연결되어 있어서 계층구조로 나누는 방법이 불분명한 경우를 제시하시오.

가상메모리에 의해 사용되는 보조 기억장치의 장치 드라이버는 입출력을 기다릴때가 있고 그동안 처리순서가 다시 편성되기 때문에 일반적으로 CPU 스케쥴러 위에 위치하는데, CPU 스케쥴러는 모든 활성화된 프로세스의 정보를 가지고 있다. 그리고 이 정보는 보조기억 장치 관리자의 행동이 CPU 스케쥴러 아래에 있음을 요구하면서 메모리에 들어가거나 혹은 빠져나와야 할 때가 있다. 이는 각 레이어 계층끼리의 상하관계가 복잡하게 얽혀있음을 보여주며 고로 계층구조로 나누는 방법이 불분명한 경우를 보여주는 한 예이다.

2.10 시스템을 설계할 때 마이크로커널 방식을 사용하는 장점은 무엇인가?　마이크로커널 구조에서 사용자 프로그램과 시스템 서비스가 상호작용하는 방식에 대해 설명하시오. 마이크로커널 방식을 사용할 때의 단점은 무엇인가?

마이크로커널 방식을 사용하면 OS의 확장을 쉽게 할 수 있다. 모든 새로운 서비스는 사용자 공간에서 추가되기 때문에 커널의 변경이 요구되지 않기 때문이다. 또한 마이크로커널은 작은 커널이기 때문에 변경된다해도 변경할 부분이 많지 않아 효율적이다. 추가로 대부분의 서비스가 사용자 공간에서 서비스되기 때문에 커널공간에서 실행되는 구조보다 보안성, 신뢰성이 높다.

마이크로커널 구조에서 사용자 프로그램과 시스템 서비스는 직접 상호 작용하지 않고 마이크로커널과 메시지를 교환함으로써 통신 한다.

마이크로커널 구조로 이루어진 OS는 기존의 모놀리딕(Monolithic)구조의 OS보다 가중된 시스템 기능 오버헤드 때문에 성능이 감소 된다.

2.11 적재가능 커널 모듈을 사용하는 장점은 무엇인가?

마이크로커널 방식과 같이 보안성, 신뢰성이 좋고 유연성이 강하지만 마이크로커널과 달리 모듈은 각자가 통신을 위해 메시지를 교환하지 않기 때문에 더 효율적이다.

2.12 iOS와 Android의 유사점을 설명하시오. 둘의 차이점은 무엇인가?

모바일 어플리케이션 개발 및 발전을 위한 풍부한 체계를 지원해주는 소프트웨어가 계층구조를 이루고 있다는 점에서 안드로이드와 iOS는 유사하다.

ios	android
objective-c 기반으로 커널에 직접 명령을 보낸다.	자바 기반이라 명령을 dvm 을 거쳐서 os에 보낸다.
백그라운드에서의 프로세스 실행을 허용하지 않는다. (모두 저장 후 종료)	실행중인 모든 프로세스에 사용빈도에 따라 메모리를 분산 배치

2.1 What is the purpose of system calls?

시스템 콜은 유저레벨의 프로세스가 OS에 서비스를 요청할 수 있게 해준다.

2.2 What are the five major activities of an operating system with regard to

process management?

프로세스의 생성과 삭제

프로세스의 일시적 정지 와 재개

프로세스 동기화를 위한 메카니즘 제공

프로세스간 통신을 위한 메카니즘 제공

데드락을 처리할 수 있는 메카니즘 제공

2.3 What are the three major activities of an operating system with regard

to memory management?

현재 메모리의 어느 부분이 누구에 의해 사용되고 있는지를 계속 추적하는 것

메모리 공간이 사용가능할 때 어떤 프로세스를 로드시켜줄지

필요에 따라 메모리의 할당과 반환

2.4 What are the three major activities of an operating system with regard

to secondary-storage management?

남는 공간 관리

공간 할당

디스크 스케쥴링 (빠른 접근 시간과 높은 전송량을 위함)

2.5 What is the purpose of the command interpreter? Why is it usually

separate from the kernel?

a. 쉘은 이용자와 시스템 간의 '대화'를 가능하게 해주며, 이용자가 입력한 문장을 읽어 그 문장이 요청하는 시스템 기능을 수행하도록 해주는 명령어 해석기

b. 쉘은 커널같이 주기억 장치에 상주하는것이 아닌 보조 기억장치에서 교체 될 수 있다.

3-a 에서와 같이 쉘은 이용자(사람)와 시스템간의 대화를 가능하게 해주는것입니다. 그럼 몇몇 예시 문제를 보시면 커널과 쉘이 구분될것입니다.

ex) 이용자와 커널이 대화하는 인터페이스의 기능을 제공하는 것으로 커널과 직접적으로 연결되어 있으며 명령어를 해석한 결과를 다른 프로그램으로 넘겨주기도 하고 보내기 도 한다. - 쉘(Shell)

ex) 시스템내의 메모리 접근, 프로세스 생성 및 관리 입출력 관리, 파일시스템을 통한 파일 관리 서비스 제공 등의 역할을 수행하는 운영체제 핵심은? - 커널(Kernel)

[출처] [정보보안기사] 커널(Kernel과 쉘(Shell)|작성자 Su

2.6 What system calls have to be executed by a command interpreter or shell

in order to start a new process?

fork, exec

2.7 What is the purpose of system programs?

시스템 콜의 번들이라고 볼 수 있는데 이를 통해 프로그램을 실행시킬때 필요한 기본적인 기능을 제공해준다.

2.8 What is the main advantage of the layered approach to system design?

What are the disadvantages of the layered approach?

시스템의 구성과 디버그를 쉽게 해준다. 시스템을 변경할 때 그 영향과 그에 따른 버그는 제한된 계층에만 영향을 미치기 때문에 디버그를 쉽게 할 수 있다.

2.9 List five services provided by an operating system, and explain how each

creates convenience for users. In which cases would it be impossible for

user-level programs to provide these services? Explain your answer.

프로그램 실행

입출력 작동

파일 시스템 조종

통신

에러 찾기

2.10 Why do some systems store the operating system in firmware, while

others store it on disk?

범용성을 가지는 일반 컴퓨터가 아닌 특정한 일을 수행하거나 portable 해야 하는 기기들의 경우 OS를 디스크에 저장하는 방법은 적절하지 못하다.

2.11 How could a system be designed to allow a choice of operating systems

from which to boot? What would the bootstrap program need to do?

시스템이 시작될 때 부트 메니저가 가장 처음으로 실행되고, 부트 매니저는 어떤 OS를 부팅시킬지 결정하여 부팅시킨다. bootstrap (=시동)

3.1 단기, 중기, 장기 스케줄링의 차이점을 설명하시오.

단기 스케줄링은 주기억장치에 올라와있는 프로세스들 중 CPU를 어떤 프로세스가 사용할 수 있게 할 것인지 time sharing 등을 통해 스케줄링해주는 것.

장기 스케줄링의 경우 디스크에 있는 프로그램중 동시에 처리하고자 하는 프로세스들을 메인 메모리에 올려주는 스케줄링을 하는 것.

중기 스케줄링은 CPU를 사용하고자하는 프로세스들이 너무 많을 때 그중 우선순위가 낮은 일부 프로세스를 디스크에 잠시 저장함으로써 프로세스간의 과도한 경쟁을 피하게 하기 위한 스케줄링이며 우선순위가 높은 프로세스의 작업이 완료되면 다시 메인메모리로 올려준다. 이 세가지 스케줄링의 가장 큰 차이점은 실행빈도라 할수 있는데 위의 역할에 의해 단기 스케줄링이 가장 자주 발생하고, 중기, 장기 스케줄링의 순서로 빈도가 낮아진다.

3.2 프로세스들 사이에 문맥을 교환할 때 커널이 수행하는 작업을 설명하시오.

context switching 이 발생할 때에는 현재 실행하던 프로세스들의 정보를 PCB에 저장하고 불러올 프로세스의 정보가 저장되어있던 PCB에서 정보를 가져와 CPU에 적재하는 일이 필요한데 이 부분을 커널이 수행한다.

3.4 어떤 부모 프로세스가 wait() 을 통해 자식 프로세스가 종료되었을 때 해당 자원을 release 시킨다. 그러나 만약 자식 프로세스가 종료되었을 때 부모 프로세스가 기다리고 있지 않다면 그 프로세스가 사용하던 자원이 올바르게 반환되지 않게 되는데 이를 orphan 혹은 zombie 프로세스라 한다. 이때 계층적 구조로 이루어진 모든 프로세스의 최상위에 있는 init 프로세스가 부모프로세스의 역할을 대신하여 해당 프로세스의 자원 반환을 해주는 역할을 한다.

3.5 fork() 시 존재하던 모든 프로세스에서 같이 fork()를 하기에 24=16개가 된다.

3.6 그림 3.32의 프로그램에서 execlp 함수는 에러 없이 실행되면 프로세스를 종료하기 때문에 LINE J 가 출력되기 위해선 execlp 함수가 접근하는 파일이 실행될 수 없어야한다.

3.7 A=0, B는 자식의 PID : 2603, C는 fork() 수행 후 반환값으로 나온 자식의 PID : 2603, D는 부모 프로세스의 PID : 2600

3.10 fork() 를 한 시점에서부터 nums는 프로세스별로 각자 가지고 있는 배열이기 때문에 X의 경우 자식프로세스에서 0,-1,-4,-9,-16 으로 출력되고 Y의 경우 부모프로세스에서 0,1,2,3,4 로 출력됨

3.1 Using the program shown in Figure 3.30, explain what the output will

be at LINE A. = 5

3.2 Including the initial parent process, how many processes are created by

the program shown in Figure 3.31? = 8

#include <stdio.h>

#include <unistd.h>

int main()

{

/* fork a child process */

fork();

/* fork another child process */

fork();

/* and fork another */

fork();

return 0;

}

Figure 3.31 How many processes are created?

3.3 Original versions of Apple’s mobile iOS operating system provided no

means of concurrent processing. Discuss three major complications that

concurrent processing adds to an operating system.

cpu 자원 할당, 프로세스간 우선순위, 데이터 공유

3.4 The Sun UltraSPARC processor has multiple register sets. Describe what

happens when a context switch occurs if the new context is already

loaded into one of the register sets. What happens if the new context is

in memory rather than in a register set and all the register sets are in

use?

3.5 When a process creates a new process using the fork() operation, which

of the following states is shared between the parent process and the child

process?

a. Stack

b. Heap

c. Shared memory segments

3.6 Consider the “exactly once”semantic with respect to the RPC mechanism.

Does the algorithm for implementing this semantic execute correctly

even if the ACK message sent back to the client is lost due to a network

problem? Describe the sequence of messages, and discuss whether

“exactly once” is still preserved.

3.7 Assume that a distributed system is susceptible to server failure. What

mechanisms would be required to guarantee the “exactly once” semantic

for execution of RPCs?

5.1 Why is it important for the scheduler to distinguish I/O-bound programs

from CPU-bound programs?

입출력 중심 프로그램과 cpu 중심 프로그램의 실행순서를 잘 섞어야 cpu 사용 효율이 좋아지기 때문에 스케줄러는 구분하여 적절히 섞을 수 있어야 한다.

5.2 Discuss how the following pairs of scheduling criteria conflict in certain

settings.

a. CPU utilization and response time

cpu 사용률이 높으려면 컨텍스트 스위치가 일어나지 않고 하나의 프로세스가 계속 cpu를 사용하여야 하지만 컨텍스트 스위치가 자주 일어나지 않으면 반응 시간이 길어진다.

b. Average turnaround time and maximum waiting time

평균 turnaround time 을 줄이기 위해선 짧은 프로세스를 먼저 수행하는 SJF 방법을 이용하여야 하는데 이는 긴 프로세스의 최대 waiting time 이 길어지는 단점을 동반한다.

c. I/O device utilization and CPU utilization

I/O 장치 사용률이 극대화 되려면 io 인터럽트가 발생하거나 io 가 완료되는 시점에서 즉시 컨텍스트 스위치가 되어야 하는데 이는 cpu 사용률의 저하를 동반한다.

5.4 In Chapter 5, we discussed possible race conditions on various kernel

data structures. Most scheduling algorithms maintain a run queue,

which lists processes eligible to run on a processor.On multicore systems,

there are two general options: (1) each processing core has its own run queue, or (2) a single run queue is shared by all processing cores. What are the advantages and disadvantages of each of these approaches?

후자의 경우 마스터 cpu 만이 커널코드를 실행하고(마스터 cpu만이 시스템 데이터 구조와 공유 데이터 접근 가능), 나머지 cpu들은 유저코드만 실행하며 IO작업이나 커널코드의 실행이 필요하면 마스터cpu 에 시스템 콜을 하기 때문에 critical section problem 이 없어 구현하기 쉽다는 장점을 가지고 있지만 프로그램 실행에 있어서 비효율적이다. 전자의 경우 후자에 비해 프로그램 실행에 효율적이지만 race condition에 따라 critical section problem이 발생하기 때문에 구현시 이를 해결하기 위한 해결방법이 필요하다.

5.5 Consider the exponential average formula used to predict the length of

the next CPU burst. What are the implications of assigning the following

values to the parameters used by the algorithm?

a. = 0 and 0 = 100 milliseconds

b. = 0.99 and 0 = 10 milliseconds

a. 가장 최근에 수행되었던 프로세스의 cpu 버스트 시간은 고려하지 않고, 가장 처음에 수행되었던 프로세스의 cpu 버스트 시간은 100 밀리초였다.

b. 가장 최근에 수행되었던 프로세스의 cpu 버스트 시간을 중점적으로 고려하고, 가장 처음에 수행되었던 프로세스의 cpu 버스트 시간은 10 밀리초였다.

5.7 Consider the following set of processes, with the length of the CPU burst

given in milliseconds:

Process Burst Time Priority

P1 2 2

P2 1 1

P3 8 4

P4 4 2

P5 5 3

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5,

all at time 0.

a. Draw four Gantt charts that illustrate the execution of these

processes using the following scheduling algorithms: FCFS, SJF,

nonpreemptive priority (a larger priority number implies a higher

priority), and RR (quantum = 2).

b. What is the turnaround time of each process for each of the

scheduling algorithms in part a?

c. What is the waiting time of each process for each of these scheduling

algorithms?

d. Which of the algorithms results in the minimum average waiting

time (over all processes)?

a.

b.

FCFS p1 : 2 ms, p2 : 3 ms, p3 : 11 ms, p4 : 15 ms, p5 : 20 ms

SJF p1: 3 ms, p2 : 1ms, p3 : 20 ms, p4 : 7 ms, p5 : 12 ms

비선점 우선순위 p1: 15 ms, p2 : 20ms, p3 : 8 ms, p4 : 19 ms, p5 : 13 ms

RR p1: 2 ms, p2: 3 ms, p3 : 20ms, p4 : 13ms p5 : 19 ms

c.

FCFS p1 : 0 ms, p2 : 2ms, p3 : 3ms, p4 : 11ms, p5 : 15ms

SJF p1: 1ms, p2 : 0ms, p3 : 12ms, p4 : 3ms, p5 : 7ms

비선점 우선순위 p1: 13ms, p2 : 19ms p3 : 0ms, p4 : 15ms, p5 : 8ms

RR p1: 0ms, p2: 2ms, p3 : 13ms, p4 : 9ms p5 : 17 ms

d.

FCFS : 6.2

SJF : 4.6

비선점 우선순위 : 11

RR : 8.2 로 SJF 가 최소의 평균 대기시간을 가진다.

5.10 Which of the following scheduling algorithms could result in starvation?

a. First-come, first-served

b. Shortest job first

c. Round robin

d. Priority

b. 최소 작업 우선은 레디큐에 들어있는 긴 작업의 프로세스에 기아 현상을 일으킬 수 있다.

5.12 Consider a system running ten I/O-bound tasks and one CPU-bound

task. Assume that the I/O-bound tasks issue an I/O operation once for

every millisecond of CPU computing and that each I/O operation takes

10 milliseconds to complete. Also assume that the context-switching

overhead is 0.1 millisecond and that all processes are long-running tasks.

Describe the CPU utilization for a round-robin scheduler when:

a. The time quantum is 1 millisecond

b. The time quantum is 10 milliseconds

a. 입출력 중심 태스크가 먼저 10개 실행 된 후 cpu 중심 태스크를 실시한다고 가정하면 12.2초동안 11개의 태스크가 실행되고 이는 계속 반복되기 때문에 11/12.2 = 약 90% 의 cpu 사용률을 보인다

b. 위와 같이 입출력 중심 태스크가 먼저 10개 실행되면 11.1초 중 10초간 cpu를 사용하고 다음 cpu 태스크에서 10.1초 중 10초간 cpu를 사용하기에 20/21.2 = 약94%의 cpu 사용률을 보인다.

5.15 Explain the differences in how much the following scheduling algorithms

discriminate in favor of short processes:

a. FCFS

b. RR

c. Multilevel feedback queues

a. 우대하지 않는다

b. 우대하지 않는다

c. 긴 프로세스를 우선순위가 낮은 큐로 넣기 때문에 상대적으로 짧은 프로세스가 우선순위가 높아진다.

5.16 Using the Windows scheduling algorithm, determine the numeric

priority of each of the following threads.

a. A thread in the REALTIME PRIORITY CLASS with a relative priority

of NORMAL

b. A thread in the ABOVE NORMAL PRIORITY CLASS with a relative

priority of HIGHEST

c. A thread in the BELOW NORMAL PRIORITY CLASS with a relative

priority of ABOVE NORMAL

a. 24

b. 10

c. 7

5.18

a. 160, 40

b. 40

c. 52