🎈 Operating System Quiz

Introduction

In a multiprogramming 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. 자원의 무단 복제(stealing, copying)와, 수정이 가능하다. 적절한 계정없이 컴퓨터를 사용한다는 문제가 있다.
2. 불가능하다. 1번에서 서술한 두가지의 문제점과, 다수의 인원이 사용하기 때문에 바이러스에도 취약하다. dedicated machine을 사용하자.

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, Main Memory, Storage
b. Workstations connected to servers : Network
c. Handheld computers : 전력 소비량

Under what circumstances would a user be better off using a time-sharing system rather than a PC or a single-user workstation?

작업이 너무 큰 경우 single user workstation 보다 컴퓨팅 파워가 큰 장비로 수행하는 time-sharing system이 적합할 것 같다. 다만 너무 많지 않은 사용자가 time-sharing 해야한다는 제약조건이 따른다.

Identify which of the functionalities listed below need to be supported by the operating system for (a) handheld devices and (b) real-time systems.

a. Batch programming
b. Virtual memory : (a),(b)
c. Time sharing : (b)

Describe the differences between symmetric and asymmetric multiprocessing. What are three advantages and one disadvantage of multiprocessor systems?

• 빠른 속도, 여러개의 싱글 프로세서보다 유지보수가 쉬움, 한 프로세서가 죽어도 동작함. 각각의 코어는 독립적으로 작동이 가능함.(스케쥴러가 여러개 존재할 수 있음)
• NUMA는 로컬 메모리가 아닌 다른 메모리에 접근할때 링크를 사용하기 때문에 메모리에 대한 접근 속도가 UMA에 비해서 느림. 스케쥴링이 복잡함.

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?

동기, 비동기식 클러스터링이 제공된다면 고가용성을 제공할 수 있다. 동기식의 경우 Active-Active 상태를 유지하며 비동기식 클러스터링의 경우 Active-Standby 상태를 유지한다. 둘 다 한쪽이 실패했을 때 해당 장치를 대체하여 동작할 수 있다. clustered system은 여러개의 장치의 군집을 뜻하고, 멀티프로세서 시스템은 한대의 물리 장치로 구성된다.

Distinguish between the client–server and peer-to-peer models of distributed systems.

server는 client의 요청에 응답 및 서비스를 제공하는 구조이다. peer는 그 자체로 서버이자 클라이언트의 역할을 수행한다. 파일을 공유할 때 peer to peer 구조에서는 여러 peer로부터 파일을 다운로드 할 수 있기 때문에 속도가 빠르다.(비트토렌트) 또한 높은 은닉성도 제공한다.(토르 브라우저).

Consider a computing cluster consisting of two nodes running a database. Describe two ways in which the cluster software can manage access to the data on the disk. Discuss the benefits and disadvantages of each.

비동기식/동기식 클러스터링으로 한개의 데이터베이스를 구성하고 해당 내용을 duplicate하는 방식으로 고가용성을 지원하는 방식의 데이터베이스 운용 방식이 있고, 다른 하나는 병렬 클러스터링을 이용하여 공유DB를 구성하는 방식이 있다. 병렬 클러스터링의 경우 두 대의 컴퓨팅 자원을 모두 활용할 수 있다는 게 이점이지만 공유 데이터베이스의 특성상 락킹기법이 필요하며 락킹에는 오버헤드가 발생한다는게 단점이다. 동기/비동기식의 경우 고가용성 자체가 이점이지만 두 대의 컴퓨팅자원을 모두 활용하지는 못한다는 점이 단점이다.

How are network computers different from traditional personal computers? Describe some usage scenarios in which it is advantageous to use network computers.

NC는 경량화된 운영체제와 최소한의 메모리, CPU를 갖추면 되며 굉장히 가격이 싸다. 이는 전통적인 PC가 사용자가 사용하기 편리한 운영체제를 갖추고 높은 메모리와 고성능 CPU를 갖추는 것과는 대조된다. NC는 네트워크만 지원된다면 원격지의 수퍼컴퓨터 자원을 할당받아서 이용하는 방식이고, 가격이 싼 NC의 특성상 어디에서도 손쉽게 하드웨어를 구입할 수 있으며 간단한 로그인으로 접근이 가능하다는 장점을 가진다. 또한 NC는 원격지의 수퍼컴퓨터를 다수의 사용자가 이용하기 때문에 자원이 놀고있는 상태가 줄어든다.

What is the purpose of interrupts? What are the differences between a trap and an interrupt? Can traps be generated intentionally by a user program? If so, for what purpose?

인터럽트는 하드웨어에서 발생하는 신호이다. 인터럽트가 발생하면 문맥교환이 일어나고 인터럽트 서비스 루틴을 실행한다. 트랩은 일반적으로 소프트웨어에서 발생한 인터럽트라고 불리며 유저프로그램에서도 의도적으로 발생 가능하다. 의도적으로 arithmetic error를 일으키는 코드를 작성하는 행위가 의도적 발생의 예이다.

Direct memory access is used for high-speed I/O devices in order to avoid increasing the CPU’s execution load.

a. How does the CPU interface with the device to coordinate the transfer?
CPU에서 DMA Controller에게 신호를 보내면 DMAC는 작업을 시작하고 작업이 끝나면 CPU에게 인터럽트로 통지한다.

b. How does the CPU know when the memory operations are complete?
작업이 종료되었다는 Interrupt를 통해 CPU에게 알리게 된다.

c. The CPU is allowed to execute other programs while the DMA controller is transferring data. Does this process interfere with the excution of the user programs? If so, describe what forms of interference are caused.
DMA가 메모리에 접근할때 메모리 버스에서 싸이클 스틸링이 발생하면 DMA의 우선순위가 높기때문에 CPU에서는 메모리로의 접근이 불가능하다. 따라서 CPU의 정상적인 User program 운용에 문제가 생길 수 있다.

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?

• 캐시는 메모리로의 액세스를 줄여준다. 캐시의 이용은 접근 속도가 빠른 저장장치이기 때문에 전체 컴퓨터 처리속도의 향상이 이루어진다.
• 빠른 장치인 CPU와 느린 장치 사이의 지연문제를 해결한다.
• NUMA 모델에서 P1 프로세서가 5라는 값을 가진 A를 가져와서 P1의 로컬캐시에 저장했고, 그 다음으로 P2 프로세서가 A를 자신의 로컬캐시에 저장했다. 직후 P1은 A를 10으로 변경한다고 해도 P2에 남아있는 A의 값은 그대로라는 문제가 존재한다.
• 만약 캐시가 휘발성이 아니며 가격이 합당하다면 저장소를 대체할 수 있다.

Consider an SMP system similar to what is shown in Figure 1.6. Illustrate with an example how data residing in memory could in fact have two different values in each of the local caches

위 문제의 data update와 동일한 내용이다.

Discuss, with examples, how the problem of maintaining coherence of cached data manifests itself in the following processing environments:

a. Single-processor systems
b. Multiprocessor systems
c. Distributed systems

a. 프로세서가 캐시 값을 변경하면 메모리에 업데이트 한다.
b. 프로세서가 로컬캐시 값을 변경하면 다른 프로세서들의 로컬캐시 값도 변경 또는 사용불가 상태가 되어야 하며 해당 내용이 메모리에 업데이트 되어야한다.
c. 별도의 업데이트는 하지 않는다. 클라이언트의 캐시 파일 데이터에 의해 불일치 현상이 나타날 수도 있다.

Describe a mechanism for enforcing memory protection in order to prevent a program from modifying the memory associated with other programs

base and limit register를 이용하여 메모리 보호를 진행한다.

base register - process의 시작지점
limit register - 시작지점부터 메모리에 접근할 수 있는 지점을 표시한다.
base <= 주소 <= base+limit

Operating system structure

The services and functions provided by an operating system can be divided into two main categories. Briefly describe the two categories and discuss how they differ.

• 프로세스의 보호
• 하드웨어가 제공하지 못하는 다양한 기능의 제공 (파일시스템, 가상메모리 등)

Describe three general methods for passing parameters to the operating system.

1. 파라미터를 레지스터에 전달한다.
2. 파라미터를 메모리내의 불록이나 테이블에 저장하고 블록의 주소값을 레지스터에 전달한다.
3. 매개변수는 프로그램에 의해 스택에 Push되고, OS에 의해 Pop된다.

• OS는 블록이나 스택방식 (2),(3)번을 선호한다. 왜냐하면 전달되는 매개변수의 개수나 길이를 제한하지 않기 때문이다.

What are the five major activities of an operating system in regard to file management?

파일의 생성, 파일의 삭제, 디렉터리 생성, 디렉터리 삭제, The application's symbolic instructions need to be translated into the machine-level instructions either by an interpreter or by compiling the application code, 파일 백업, 영구 저장소로 매핑

Would it be possible for the user to develop a new command interpreter using the system-call interface provided by the operating system?

Processes

Describe the differences among short-term, medium-term, and long-term scheduling.

Short-term(CPU scheduler) : 메모리로부터 ready 상태에 있는 job 들을 선택해서 CPU를 할당하는 스케쥴링
medium-term : 특히 시분할 시스템에서 사용되는 medium-term scheduler는 CPU경쟁완화를 위하여 메모리에서 프로세스들을 제거하며, 다중 프로그래밍의 정도를 완화하는 것이다. 추후 프로세스를 메모리로 불러와서 중단된 지점부터 재개하는 swapping기법을 사용한다.
long-term : 보조기억장치로부터 주기억장치로 job을 load하여 해당 프로세스를 ready 상태로 만든다.
주요한 차이는 실행 빈도수이다. short-term은 새로운 프로세스를 자주 선택해야하고, long-term은 job이 끝나는 시간을 기다려야 하기 때문에 다른 job을 수용하는데에 상대적으로 긴 시간이 걸린다.

Describe the actions taken by a kernel to context-switch between processes.

커널은 현재 실행중인 프로세스의 상태를 저장해야만 한다. 또, 다음으로 실행될 프로세스의 상태를 restore 해야한다.

The OS must save the PC and user stack pointer of the currently executing process, in response to a clock interrupt and transfers control to the kernel clock interrupt handler

Saving the rest of the registers, as well as other machine state, such as the state of the floating point registers, in the process PCB is done by the clock interrupt handler.

The scheduler to determine the next process to execute is invoked the OS.

Then the state of the next process from its PCB is retrieved by OS and restores the registers. The restore operation takes the processor back to the state in which the previous process was previously interrupted, executing in user code with user-mode privileges.

Construct a process tree similar to Figure 3.8. To obtain process information for the UNIX or Linux system, use the command ps -ael. Use the command man ps to get more information about the ps command. On Windows systems, you will have to use the task manager.

Including the initial parent process, how many processes are created by the program shown in Figure 3.32?

네 번의 fork()가 진행된다.

#1 2개의 프로세스로 분기한다.
#2 2개의 프로세스가 각각 2개로 분기하여 총 4개가 된다.
#3 4개의 프로세스가 각각 2개로 분기하여 총 8개가 된다.
#4 8개의 프로세스가 각각 2개로 분기하여 총 16개가 된다.

Explain the circumstances under which which the line of code marked printf("LINE J") in Figure 3.33 will be reached.

해당 코드에 도달할 수 있는 환경은 다음과 같다.
fork() 시스템 콜로 분기된 자식 프로세스는 pid가 0이다. 따라서 자식 프로세스에서는 ls 명령어를 실행시킨 후 “LINE J”를 출력하게 된다. 부모 프로세스는 wait(NULL)로 자식 프로세스가 종료될 때까지 기다렸다가 “Child Complete”를 출력한다.

Using the program in Figure 3.34, identify the values of pid at lines A, B, C, and D. (Assume that the actual pids of the parent and child are 2600 and 2603, respectively.)

A=0, B=2603, C=2603, D=2600

Give an example of a situation in which ordinary pipes are more suitable than named pipes and an example of a situation in which named pipes are more suitable than ordinary pipes.

쉘 만들기 과제를 할 때, pipe를 구현한다고 가정한다면, ordinary pipe가 적당할 것이라고 생각한다. 왜냐하면 실행된 전 명령어를 이용하여 다음 명령어에서 사용하기 때문에 해당 내용이 저장되어 남을 필요가 없기 때문이다. 하지만 만약 보안 관점에서 Accountability를 위해 사용자가 입력한 모든 명령어를 logging 한다고 가정하는 상황이라면 named pipe가 적당할 것으로 보인다.

Consider the RPC mechanism. Describe the undesirable circumstances that could arise from not enforcing either the “at most once” or “exactly once” semantics. Describe possible uses for a mechanism that had neither of these guarantees

두 명령어 모두 한번의 호출 을 의미하지만, 실패시의 동작이 다르다.
at-least-once의 경우 시스템이 해당 함수 호출이 성공했다는 사실을 알 때까지 반복하므로 결제 업무 등에 적용되면 안된다. 데이터 베이스의 업데이트와 같이 최신의 값으로 덮어써도 되는 경우 사용하면 좋다. 반면 at-most-once의 경우 실수로 다른 사람에게 두번 결제 하고싶지 않을때 사용한다. exactly-once의 at-most-once와 비슷하다. 하지만 다른점이 있다면 at-most-once는 ACK를 받았을 때 더 이상 재전송 하지 않는 방식이라면 exactly-once 방식은 cache가 존재한다면 해당 값을 돌려주어 duplicate 현상을 방지한다.

At-least-once

At-most-once

Exactly-once

sing the program shown in Figure 3.35, explain what the output will be at lines X and Y.

What are the benefits and detriments of each of the following? Consider both the systems and the programmers’ levels.

a. Synchronous and asynchronous communication
동기적 송신은 구현이 간단하고 별다른 이벤트에 대한 핸들링이 필요 없다. 하지만 blocking 방식으로 한 메시지를 주고 받을 때 다른 동작을 하지 못한다는 단점이 있다. (rendezvous) 반면 비동기적 통신은 다른 작업도 수행할 수 있지만, 별도의 이벤트 핸들링이 필요하다.

b. Automatic and explicit buffering
자동 버퍼링은 효율적인 자원 활용이 가능하며, 전송자가 block을 할 필요가 없다. 명시적 버퍼링은 큐가 다 차면 block해야한다는 단점이 있으나 잘 조정한다면 자동 버퍼링보다 효율적일 수 있다.

c. Send by copy and send by reference
복사 원본이 남기 때문에 안전성을 확보할 수 있으나 메모리의 낭비가 일어난다.
반대로 참조는 의도치 않은 값 변경이라는 부작용이 있을 수 있다.

d. Fixed-sized and variable-sized messages
고정 크기의 메시지는 구현이 쉽고, 시스템 연산의 최적화가 해당 사이즈에 맞추어 가능해진다.
반대로 가변 크기 메시지는 공간의 효율적 활용과 메모리 범위 내의 모든 크기 메시지를 전송할 수 있다는 장점이 있다. 하지만 시스템 연산의 최적화는 불가능하다.

Thread

Provide two programming examples in which multithreading does not provide better performance than a single-threaded solution

순차적으로 실행되는 프로그램의 경우 멀티쓰레딩은 적합하지 않다.
반면, shell 만들기 과제와 같이 백그라운드 실행을 지원하며 실시간으로 사용자와 커뮤니케이션을 하는 프로그램이라면 멀티 쓰레딩이 필요하다.

Describe the actions taken by a thread library to context switch between user-level threads.

프로세스의 문맥 교환과도 상당히 비슷하지만 더 적은 오버헤드를 가진다. stack 영역을 제외한 모든 메모리를 공유하기 때문에 Context switching 발생시 Stack 영역만 변경하여 진행하면 된다.

Under what circumstances does a multithreaded solution using multiple kernel threads provide better performance than a single-threaded solution on a single-processor system?

단일 스레드 프로그램은 요구가 도착할 때마다 새로운 프로세스를 생성하고
문맥교환에 오버헤드가 발생하지만, 다중 스레드라면 해당 요구에 대해서 스레드로 처리
하므로 문맥교환 비용이 감소한다.

Which of the following components of program state are shared across threads in a multithreaded process?

a. Register values
b. Heap memory
c. Global variables
d. Stack memory

b,c

Can a multithreaded solution using multiple user-level threads achieve better performance on a multiprocessor system than on a single-processor system?

사용자 수준 스레드는 OS에서 단일 프로세스로만 해석되며 별도의 프로세서에서 프로세스의 다른 스레드를 스케쥴링하지 않습니다. 이는이 상황에서 성능상의 이점이 없음을 강력히 시사합니다.

As described in Section 4.5.2, Linux does not distinguish between processes and threads. Instead, Linux treats both in the same way, allowing a task to be more akin to a process or a thread depending on the set of flags passed to the clone() system call. However, many operating systems—such as Windows XP and Solaris—treat processes and threads differently. Typically, such systems use a notation wherein the data structure for a process contains pointers to the separate threads belonging to the process. Contrast these two approaches for modeling processes and threads within the kernel.

어떤 스레드가 어떤 프로세스에 해당하는지 식별하고 Accounting을 할 때 추가적인 복잡성이 요구된다. 하지만 스케쥴링시 구별하지 않기 때문에 더 단순하게 구현 할 수 있다.
fork() 명령어를 수행하면 부모 프로세스의 자료구조를 복사하지만 clone() 명령어를 수행하면 전달된 플래그가 다르며, 부모 프로세스의 자료구조를 포인팅 한다.

In Chapter 3, we discussed Google’s Chrome browser and its practice of opening each new website in a separate process. Would the same benefits have been achieved if instead Chrome had been designed to open each new website in a separate thread? Explain.

한 스레드에서 오류가 발생하면 프로세스 자체의 오류로 번지기 때문에 다른 스레드들도 전부 종료되는 부작용이 생긴다. 따라서 개별 프로세스로 작용하는게 맞다.

Is it possible to have concurrency but not parallelism? Explain. (동시수행성, 병렬성)

사용자의 인지보다 빠르게 문맥교환을 한다면 concurrency하게 느낄 수 있다.

Using Amdahl’s Law, calculate the speedup gain of an application that has a 60 percent parallel component for (a) two processing cores and (b) four processing cores.

암달의 법칙
S는 순차수행 부분이기 때문에 40percent인 0.4이고, N은 a에서 2, b에서 4이다.
각각의 계산 결과값은 (a) <= 1 / 0.4+0.3 = 약 1.42 , (b) <= 1 / 0.4+0.15 = 약 1.81

Determine if the following problems exhibit task or data parallelism

데이터 병렬성
데이터 병렬성은 전체 데이터를 서브 데이터들로 나눈 후
서브 데이터들을 병렬 처리하여 작업을 빠르게 수행하는 것을 말한다.

태스크 병렬성
태스크 병렬성은 서로 다른 작업을 병렬 처리하는 것을 말한다.
ex) 웹 서버는 각각의 클라이언트에서 요청한 내용을 스레드로 병렬로 처리한다.

• The multithreaded statistical program described in Exercise 4.21
세개의 스레드로 각각의 값을 구하는 태스크 병렬설
• The multithreaded Sudoku validator described in Project 1 in this
chapter 2개의 스레드로 행렬을 검사(태스크 병렬성)하고, 9개의 스레드로 3x3 9개의 부분을 각각 검사(데이터 병렬성)한다.
• The multithreaded sorting program described in Project 2 in this

chapter 전체 데이터를 2개로 devide(데이터 병렬성)하여 정렬하고 스레드를 merge한다.

• The multithreaded web server described in Section 4.1
서버는 클라이언트로부터 요청이 들어오면 개별 스레드로 처리한다 (태스크 병렬성)

A system with two dual-core processors has four processors available for scheduling. A CPU-intensive application is running on this system. All input is performed at program start-up, when a single file must be opened. Similarly, all output is performed just before the programExercises 193 terminates, when the program results must be written to a single file. Between startup and termination, the program is entirely CPU-bound. Your task is to improve the performance of this application by multithreading it. The application runs on a system that uses the one-to-one threading model (each user thread maps to a kernel thread).

두 개의 이중 코어 처리기는 스케줄 가능한 4개의 처리기를 가지고 있다. CPU-bound application이 시스템에서 실행중이라고 하자. 모든 입력은 프로그램이 시작할 때 주어지고 반드시 하나의 파일이 열려야 한다. 마찬가지로 모든 출력은 프로그램이 종료되기 전에 수행된다. 프로그램의 결과는 하나의 파일에 모두 기록되어야한다. 프로그램이 시작해서 종료할 때까지 프로그램은 CPU 집중적이다. 여러분은 이 프로그램을 다중 스레드화하여 성능을 향상시켜야한다. application은 일대일 스레드 모델을 사용하며 각 사용자 수준 스레드는 커널스레드에 사상된다.

• How many threads will you create to perform the input and output?
Explain. 인풋 1개 스레드, 아웃풋 1개 스레드
• How many threads will you create for the CPU-intensive portion of
the application? Explain. 4개 스레드 모두 할당.

Consider the following code segment

a. How many unique processes are created?
6개의 프로세스가 생성된다.
b. How many unique threads are created?
8개의 스레드가 생성된다. (4개의 단일 스레드 프로세스 + 2개의 더블 스레드 프로세스)

• The initial call to fork() (labeled “1” above) creates a copy of the original process (2 processes at this point)
• The second call to fork() (labeled “2” above) is executed only by the child process from the first fork() call. (3 processes at this point)
• There are now two processes executing the code inside the if statement, meaning both of those processes call thread_create() (3 processes, 2 threads)
o What should have been made clear in the original assignment is that each newly created thread starts a different function than the one currently executing—one of the arguments to a thread_create() function is a pointer to the function to begin executing. The threads therefore don’t move on to the last fork() call.
• All three processes execute the final call to fork() (labeled “4” above), so each process copies itself at that point (6 processes, 2 threads)
However, Peter brought to my attention the fact that the above solution does not account for the fact that each process starts as a single thread of execution. A better solution would be to say that this code segment creates a total of six processes and eight threads (two threads created by calls
to thread_create() and six threads corresponding to the six single-threaded processes).

The program shown in Figure 4.16 uses the Pthreads API. What would be the output from the program at LINE C and LINE P?

attr : 스레드 특성 지정
pthread_create : 스레드 생성, 특히 세번째 인자는 스레드 시작시 실행할 스레드 함수.
pthread_join : 스레드의 종료를 기다린다.

child : 5, parent : 0

Consider a multicore system and a multithreaded program written using the many-to-many threading model. Let the number of user-level threads in the program be greater than the number of processing cores in the system. Discuss the performance implications of the following scenarios.

a. The number of kernel threads allocated to the program is less than
the number of processing cores.
모든 커널 스레드는 1대1로 대응하여 서비스를 받고, 일부 프로세싱 코어는 idle 시간을 가진다.

b. The number of kernel threads allocated to the program is equal to
the number of processing cores.
모든 커널스레드는 프로세서와 1대1 대응하여 서비스를 받는다. 그렇지만 만약 커널스레드에 봉쇄(block)가 발생한다면 (페이지 부재, 시스템 콜 등의 이유로) 대응하는 프로세서는 idle 시간을 가지게 되겠다.

c. The number of kernel threads allocated to the program is greater
than the number of processing cores but less than the number of
user-level threads.
서비스 받으려고 경쟁이 시작된다. pcs와 scs가 둘 다 발생함.

• PCS(Process contention scope) : 프로세스 경쟁 범위(PSC)이다. (LWP 포함)
• SCS(System contention scope) : 커널 스레드 간의 경쟁 범위

Pthreads provides an API for managing thread cancellation. The pthread setcancelstate() function is used to set the cancellation state. Its prototype appears as follows:The two possible values for the state are PTHREAD CANCEL ENABLE and PTHREAD CANCEL DISABLE. Using the code segment shown in Figure 4.17, provide examples of two operations that would be suitable to perform between the calls to disable and enable thread cancellation.

CPU Scheduling

Why is it important for the scheduler to distinguish I/O-bound programs from CPU-bound programs?

I/O 바운드 프로그램은 CPU의 점유율이 낮고 자주 I/O 처리를 하러 가기 때문에 CPU Burst time이 짧고, CPU 바운드 프로그램은 Burst time이 길다. 따라서 CPU 바운드 프로그램이 CPU를 오랫동안 점유하면 다른 프로세스들이 오랫동안 기다리는 Convoy effect(호위 효과)가 발생한다.

Discuss how the following pairs of scheduling criteria conflict in certain settings.

a. CPU utilization and response time
CPU 사용량을 늘리려면 Context switch를 최소화하면 되지만, 그럴 경우 한 프로세스가 오래 CPU를 점유하는 호위 효과가 발생할 수 있기때문에 response time은 커지게(느려지게) 된다.

b. Average turnaround time and maximum waiting time
짧은 작업부터 스케쥴링 하고 서비스 한다면 평균 turnaround time은 줄어들지만, 무한정 waiting하는 기아상태가 발생할 수 있다.

c. I/O device utilization and CPU utilization
CPU의 사용량을 최대화하려면 CPU 바운드 태스크를 수행하는게 맞고, I/O장치의 경우 I/O 바운드 태스크를 수행할 때 사용량이 최대가 되고 과정에서 문맥교환이 많이 일어나게 된다.

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?

implications

a. alpha가 0 이라는 소리는 현재의 값에 대해서 반영을 하지 않겠다는 뜻이기 때문에 burst time은 항상 100이 나오게 된다.
b. alpha가 0.99라는 것은 현재의 값에 대한 반영률을 99퍼센트로 하고 과거의 데이터들은 1퍼센트만 반영한다는 이야기이다. 이전의 burst 값을 거의 동일하게 사용한다는 뜻이 된다.

Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

a. Draw four Gantt charts illustrating the execution of these processes
using FCFS, SJF, a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling.
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 the scheduling
algorithms in part a?
d. Which of the schedules in part a results in the minimal average
waiting time (over all processes)?

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,d

Consider a variant of the RR scheduling algorithm where the entries in the ready queue are pointers to the PCBs.

a. What would be the effect of putting two pointers to the same process in the ready queue?
b. What would be the major advantages and disadvantages of this scheme?
c. How would you modify the basic RR algorithm to achieve the same effect without the duplicate pointers?

a. 프로세스는 더 자주 시간을 할당받게 된다. 따라서 우선순위가 높아진다.
b : 중요한 프로세스 우선순위를 높일 수 있다. 덜 중요한 작업은 밀려날 수 있다.
c : 높은 우선순위를 가진 프로세스에 긴 시간을 할당한다. RR 스케줄에서 더 많은 퀀텀을 준다.

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.

What is the CPU utilization for a round-robin scheduler when:
a. The time quantum is 1 millisecond
b. The time quantum is 10 milliseconds

a. time quantum이 1ms 이므로, 1ms + 0.1ms = 1.1ms가 되고, 사용시간은 1ms가 된다. 따라서 CPU 사용률은 1/1.1 100 = 91(%)이다.
b. time quantum이 10ms 이다. 10개의 1.1ms와 1개의 10.1ms의 작업이 총 걸린 시간이고, 실제 사용 시간은 110.1ms을 뺀 20ms이다. 따라서 20/21.1 *100 = 94(%) 이다.

Consider a system implementing multilevel queue scheduling. What strategy can a computer user employ to maximize the amount of CPU time allocated to the user’s process?

답 : OS 관점에서는 User job 큐의 시간 할당을 다른 큐들보다 늘려준다.

더 나아가기 : 스케쥴링 알고리즘이 타임슬라이스를 채우지 않고 끝난 프로세스에 대해서 우선순위를 높여주는 방식으로 설계되었다면, 즉 멀티레벨큐 중 멀티 레벨 피드백 큐로서 설계 되었다면, 프로그램은 시간 퀀텀을 완전히 활용하지 않음으로써 할당되는 CPU 시간을 최대화할 수 있다. 할당된 퀀텀의 많은 부분을 사용할 수 있지만, 퀀텀이 끝나기 전에 CPU를 포기하여 프로세스와 관련된 우선 순위를 증가시킨다.

다중 수준 피드백 대기열은 특별한 CPU 예약을 구현합니다. 프로세스가 할당된 전체 퀀텀을 사용하지 않는 경우 OS는 이 프로세스가 일부 I/O 디바이스를 기다리고 있다고 가정합니다. 따라서 나중에 CPU를 최대한 빨리 가져올 수 있도록 우선 순위가 높은 대기열에 보관해야 합니다. 반면에, 프로세스가 할당된 전체 시간 퀀텀을 사용하는 경우, OS는 이 프로세스가 시간이 많이 걸리는 프로세스라고 생각하여 우선 순위가 낮은 대기열로 이동합니다. 이렇게 하면 시스템은 항상 새로운 프로세스를 선호하고 먼저 실행합니다.
따라서 CPU 시간을 최대화하기 위해 사용자 프로세스는 높은 우선 순위 대기열에 머무르고 1회 양자 내에 완료되지 않을 때 낮은 우선 순위 대기열에 푸시되지 않기를 원합니다. I/O 경계 프로세스로 가장하는 것이 전략입니다. 첫 번째 단락에서 설명한 메커니즘에 따르면, 프로세스가 시간 퀀텀을 사용하지 않고 CPU에 남아 있으면 OS는 I/O 경계 프로세스로 간주하여 높은 우선 순위 대기열에 보관합니다.

Consider a preemptive priority scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate a; when it is running, its priority changes at a rate b. All processes are given a priority of 0 when they enter the ready queue. The parameters a and b can be set to give many different scheduling algorithms.

정리하자면 running 상태에서는 B의 rate로 변하는 우선순위, ready 상태에서는 A의 rate로 변한다.
B>A>0인 경우 : running 상태에 있는 프로세스의 우선순위가 가장 높아진다는 말은 즉 먼저 들어온게 먼저 나간다는 의미이다. FIFO(FCFS)
A<B<0인 경우 : 마지막으로 ready 큐로 진입한 프로세스의 우선순위가 가장 높다. LIFO

Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes:

*discriminate in favor of (~를 우대하다)

a. FCFS
b. RR
c. Multilevel feedback queues

a. ready queue에 들어온 순서대로 서비스를 하는 방식이다. 짧은 작업을 우대하거나 먼저 처리하지 않는다.
b. time slice 단위로 프로세스들에게 공정하게 CPU자원을 할당한다. 짧은 작업을 우대하거나 먼저 처리하지 않지만, 타임 슬라이스 안에서 동등하게 처리되기 때문에 짧은 작업이 FCFS보다 상대적으로 빠르게 끝낸다.
c. 여러 단계의 큐를 두고, 첫번째 큐에서 끝나지 않는 작업은 시간이 오래 걸릴 것이라고 가정하며 다음 큐로 이동시킨다. 짧은 작업은 최초의 큐에서 처리되는 편이기 때문에 짧은 작업을 우대한다.