In running a C program, there are two types of memory that are allocated.
Stack memory: The allocations of deallocations of it are mangaged implicitly by compiler for a programmer(so called as automatic memory).
A stack frame stores return address, function parameters, and tempral variables etc.
Heap memory: The allocations and deallocations are explicitly handled by the programmer.
void func() {
int *x = (int *)malloc(sizeof(int));
...
}
malloc() 함수
malloc() 호출은 매우 간단하다. Heap에 요철할 공간의 크기를 넘겨 주면, 성공했을 경우 새로 할당된 공간에 대한 포인터를 사용자에게 반환하고 실패할 경우 NULL을 반환한다.
#include <stdlib.h>
...
void *malloc(size_t size);
double *d = (double *) malloc(sizeof(double));
int *x = malloc(10 * sizeof(int));
주의-- 필요로 하는 저장공간을 정확하게 입력 해줘야함. 특히 string
-> 시스템에서 각각의 연산자와 몇 byte를 사용하는지 어떻게 알까? -> 그래서 sizeof()를 사용.
free() call
To free heap memory that is no longer in use, programmers simply call free().
int *x = malloc(10* siezof(int));
...
free(x);
Automatic memory management
With such a facility, a programmer calls something akin to malloc() to allocate memory (usually new) but never have to call something to free space. ← 다른 언어들.
A garbage collector runs after and figures out what memory you no longer have references to and frees it.
JAVA로 구현한 것이 별도의 부하가 발생. Memroy translation, java virtual machine에서 동작하기 때문. 즉 JAVA는 java virtual machine이라는 별도의 부하가 존재하고 이 내에서는 또 Garbage Collector가 돌아다니면서 resource들을 먹고 있기 때문에 C로 구현했을때보다 느리다.
Common Errors
JAVA, C etc .. → stack overflow C, C++ → segmentation fault 발생.
Forgetting to allocate memory
char *src = "hello";
char *dst; // oops! unallocated
strcpy(dst, src); // segfaut and die
Not allocating enough memory
char *src = "hello";
char *dst = (char *)malloc(strlen(src)); // too small
strcpy(dst, src); // work properly
Forgetting to initialize allocated memory
Forgetting to free memory → Memory leak
Freeing memory befroe you are done with it.
Freeing memory repeatedly
Calling free() incorrectly in(부) correct
Two levels of memory management
The first level of memory management is performed by the OS, which hands out memory to processes when they run, and takes it back when process exit (or otherwise die).
The second level of management is within each process, for example within the heap when you call malloc() and free().
Even if a programmer fails to call free(), the OS will reclaim all the memory of the processes when the program is finished running.
sometimes referred to as a fair-share scheduler. Proportional-share is based around a simple concept: Instead of optimizing for turn-around or response time, a scheduler might instead try to guarantee that each job obtain a certain percentage of CPU time.
lottery scheduling: ← Proportional Share의 좋은 예 The basic idea is quite simple: 다음 실행될 프로세스를 추첨을 통해 결정한다. 더 자주 수행되어야하는 프로세스는 당첨 기회를 더 많이 준다.
lottery scheduling
Underlying lottery scheduling is one very basic concept: tickets, which are used to represent the share of a resource that a process (or user or whatever) should receive. The per-cent of tickets that a process has represents its share of the system resource in question.
Ex) Imagine two processes, A and B, and further that A has 75 tickets while B has only 25.
Lottery scheduling achieves this probabilistically (but not deterministically) by holding a lottery every so often (say, every time slice). Holding a lottery is straightforward: the scheduler must know how many total tickets there are (in our example, there are 100)
The scheduler then picks a winning ticket, which is a number from 0 to 99. Assuming A holds tickets 0 through 74 and B 75 through 99, the winning ticket simply determines whether A or B runs.
Basic Concepts
Random approaches have at least three advantages over more traditional decisions. First, random often avoids strange corner-case behaviours that a more traditional algorithm may have trouble handling. Second, random also is lightweight, requiring the little state to track alternatives. Finally, random can be quite fast. As long as generating a random number is quick, making the decision is also, and thus random can be used in a number of places where speed is required. - Random number generator를 만드는 것은 굉장히 어렵다. -
Ticket Mechanisms
One way is with the concept of ticket currency. Currency allows a user with a set of tickets to allocate tickets among their own jobs in whatever currency they would like. the system then automatically converts said currency into the correct global value.
For example, assume users A and B have each been given 100 tickets. User A is running two jobs, A1 and A2, and gives them each 500 tickets (out of 1000 total) in User A’s own currency. User B is running only 1 job and gives it 10 tickets (out of 10 total).
Another useful mechanism is ticket transfer. With transfers, a process can temporarily hand off its tickets to another process. This ability is especially useful in a client/server setting, where a client process sends a message to a server asking it to do some work on the client’s behalf. To speed up the work, the client can pass the tickets to the server and thus try to maximize the performance of the server while the server is handling the client’s request.
Finally, ticket inflation can sometimes be a useful technique.
With inflation, a process can temporarily raise or lower the number of tickets it owns. Rather, inflation can be applied in an environment where a group of processes trust one another in such a case, if any one process knows it needs more CPU time, it can boost its ticket value as a way to reflect that need to the system, all without communicating with any other processes
구현(Implementation)
//counter: used to track if we've found the winner yet
int counter = 0;
//winner: use some call to a random number generator to get a value,
// between 0 and the total # of tickets
int winner = getrandom(0, totaltickets);
//current: use this to walk through the list of jobs
node_t *current = head;
//loop until the sum of ticket values is > the winner
while(current) {
counter = counter + current->tickets;
if (counter > winner)
break; // found the winner
current = current->next;
}
노드를 이어준 링크드 리스트 형태로 구현되어있으며 winner에는 랜덤 넘버수가 있고 A는 0-99, B는 100-149,C는 150-399까지 자신의 수를 가지고 있고 링크드형태로 앞에서부터 순차적으로 훑어간다. counter란 숫자를 A 더하고 B더하고 이런식으로 진행된다. 그리고 counter값이 winner(A,B,C 중 하나)보다 값이 초과된다면 티켓의 당첨자가 된다.
How To Assign Tickets?
One problem we have not addressed with lottery scheduling is: how to assign tickets to jobs?
Why Not Deterministic? → Stride scheduling
random is simple but it occasionally will not deliver the exact right proportions. Waldspurger invented stride scheduling, a deterministic fair-share scheduler
current = remove_min(queue); //pick client with minimum pass
schedule(current);
current->pass += current->stride;
insert(queue, current);
Example: Tree processes A, B, and C with stride values of 100, 200, and 40 and all with pass value initially at 0.
To achieve its efficiency goals, CFS aims to spend very little time making scheduling decisions.
Basic operation
Goal: To fairly divide a CPU evenly among all competing process. vruntime(virtual runtime): A simple counting-based technique. vruntime은 위에 pass와 비슷하다. As each process runs, it accumulates vruntime. Int the most basic case, each process's vruntime increases at the same time, in proportion with physical (real) time. When a scheduling decision occurs, CFS will pick the process with the lowest vruntime to run next.
Q: How does the scheduler know when to stop the currently running process, and run the next one? A: If CFS switches too often, fairness is increased. If CFS switches less often, performance is increased.
Control parameters
sched_latency: CFS uses this value to determine how long one process should run before considering a switch. Example: For n processes, CFS divides the value of sched_latency by n to get a per-process time slice. CFS then schedules the first job and runs it until it has used the per-process time slice, then checks to see if there is a job with lower vruntime to run instead.
만약 sched_latency가 48초라고 했을 때 이를 프로세스 수로 나눈다. 즉 sched_latency/process number 이렇게 하면 현재 프로세스 수는 4임으로 각 프로세스가 실행 시간은 12초가 된다. 만약 프로세스사 실행 도중 끝나거나 새로운 프로세스가 실행된다면 어떻게 될까? 도중에 끝난다면 각 프로세스당 동작 시간이 늘어날 것이다. 왜냐면 sched_latency는 고정 되어있고 process number가 줄어 각 할당 된 동작시간이 늘어난다. 반대로 새로운 프로세스가 들어왔다면 각 할당된 동작 시간이 너무 작아질 수가 있게 된다. 그렇게 된다면 어떻게 해야할까?
이를 막기 위해서 다른 parameter가 있다. 바로 min_granularity CFS will never set the time slice of a process to less than this value, ensuring that not too much time is spent in scheduling overhead.
CFS utilizes a periodic timer interrupt, which means it can only make decisions at fixed time intervals.
This interrupt goes off frequently (e.g., every 1 ms), giving CFS a chance to wake up and determine if the current job has reached the end of its run.
CFS also enables controls over process priority, enabling users or administrators to give some processes a higher share of the CPU.
Nice level of a process: The nice parameter can be set anywhere from 20 to +19 for a process, with a default of 0.
CFS maps the nice value of each process to a weight:
Using Red-Black trees When the scheduler has to find the next job to run, it should to so as quickly as possible. Searching through a long list is wasteful. CFS keeps processes in a red-black tree. CFS keeps only running (or runnable) processes in the RB tree. Example: Ten jobs with vruntime 1, 5, 9, 10, 14, 18, 17, 21, 22, 24.
핵심: CPU를 어떻게 Virtualization을 하느냐? 방법: Time-Sharing을 한다. 조그만한 Time slot을 나눈다 → 각각의 프로세스에 Time slot을 하나씩 배정한다 Process가 Time Slot을 다 쓰고 안 내놓는 가능성이 있었다. ⇒ 초창기 Cooperative Approach 방식 이 방식은 Prcocess가 자신의 load를 다 끝날 때까지 CPU를 손에 잡고 있거나 처리 시간이 너무 오래 걸린다면 알아서 CPU를 내놓을 것이라고 기대했었다.
Non-Cooperative Approach: 하드웨어 타이머를 사용하기로함 하드웨어 타이머가 완료되었을 때 찾아가야하는 트랩핸들러를 부팅 과정에서 기록을 해놓는다. 그리고 타이머가 완료되면은 운영체제한테 제어권을 넘겨준다. 그러면 운영체제는 새로운 프로세스를 선정해서 CPU를 넘겨준다. 이 과정은 Context-Switching을 하는 기본 machism이 된다.
이 장에서는 Process를 어떻게 선정할지에 대해 배우게 된다.
Workload Assumption
Workload ← 일련의 프로세스들이 실행하는 상황
이 Assumption은 우리의 이해를 돕기 위해 설정 된 것이다.
Each job runs for the same amount of time.
All jobs arrive at the same time.
Once started, each job runs to completion.
All jobs only use the CPU(i.e., they perform no I/O
The run-time of each job is Known.
→ 앞으로 하나씩 가정을 완화하면서 실제 Scheduling에 다가간다.
Scheduling metrics
Turnaround time → 반환 시간 → 성능 측면의 평가 기준
Policies
First In, Firsst Out(FIFO)
FIFO scheduling or FCFS(First Come, First Served) scheduling. It is simple and easy to implement.?
Example: Imagine three jobs(A,B,C) arrives in the system at roughly the same time. but A arrived faster than B, and B arrived faster than C. Assume each job runs for 10 seconds. What will the average turn-around time be for these jobs?
Example: Let's again assume three jobs but this time A runs for 100 seconds while B and C run for 10 seconds. ← workload의 1번 Assumption을 완화시켰다. FIFO에서 성능이 구리다...!!!! workload assumption 1 → Each job runs for the same amount of time.
A = 100, B = 110, C = 120, (A+B+C)/3 = 110 << - 😫 Convy effect 현상이 발생!! 어떻게 해결할까?
GeeksforGeeks Convey
Convoy effect: a number of relatively-short potential consumers of a resource get queued behind a heavyweight resource consumer.
Shortest job first(SJT)
FIFO의 문제(Convoy effect)를 해결해보자. It runs the shortest job first, then the next shortest, and so on.
Q: What is the average turn-arround time for the above case?
B = 10, C = 20, A = 120 , 150/3 =50이다.
Example: Assume Arrives at t = 0 and needs to run for 100 seconds, whereas B and C arrive at t =10 and each needs to run for 10seconds. What is the average turn-around time?
↑ 이제 workload의 Assumption 2번을 완화한다. A가 B와 C보다 먼저 도착하면 성능이? 구리다. workload assumption 2 → All jobs arrive at the same time.
A = 100, B= 110-10 = 100, C = 120-10 = 110, Avearge Turn-Arround time = 103.33; ← 😫
Shortest-Time-to-Completion First(STCF)
이제는 실행 시간이 긴 A가 먼저 도착했을 때 어떻게 해결할까? SJF의 문제를 해결해보자.
Workload Assumption 3번을 완하해보자.
workload assumption 3 → Once started, each job runs to completion.
Additional machinery: when another job arrives, the scheduler can preempt the currently running job and decide to run another job. STCF or Preemptive Shortest Job Frist(PSJF): SJT + preemption.
막간 지식
Non-Preemptive Scheduling 한 프로세스가 CPU를 할당받아 실행 중이면 다른 프로세스들이 강제적으로 뺏을 수 없는 스케줄링 방식 예시: FIFO(FCFS), SJF, HRN 등
Preemptive Scheduling 한 프로세스가 CPU를 할당받아 실행중이라도 다른 프로세스가 현재 프로세스를 중지시키고 CPU를 강제적으로 뺏을 수 있는 스케줄링 방식 예시: RR, SRT, Multi Level Queue, Multi Level Feedback Queue 등
Any time a new job enters the system, the STCF scheduler determines which of the remaining jobs (including the new job) has the least time left, and schedules that one.
A = 120-0 B = 20-10 C = 30-10 150→ 50 평균 값
A new metric: response time
Response time 정의: the time form when a job arrives in a system to the first time it is scheduled.
작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며 평가 기준이 Turnaround Time하나라면 STCF는 매우 훌륭한 정책이다. Time-sharing computer의 등장하고 사용자는 terminal에서 작업하여 상호작용이 원활하기 위한 성능이 요구된다. 그래서 Respon Time이 등장한다.
기본 발상: Instead of running jobs to completion, RR runs a job for a time slice(or scheduling quantum) and then switches to the next job in the run queue. RR is sometimes called Time-Slicing.
위의 예의 RR의 A,B,C가 시스템에 동시에 도착하고 각각 5초간 실행된다고 가정하자. RR의 average response time은 (0+1+2)/3 = 1이고, SJF average respone time은 (0+5+10)/3 = 5이다.
Time Slice는 짧아질 수록 Response time 기준으로 RR이 성능은 더 좋아진다. time slice가 짧아질 수록 The cost of switching이 전체 성능에 큰 영향을 미치게된다.
The cost of switching: OS actions of saving and restoring a few registers, state information in CPU caches, TLBs (translation lookaside buffer), branch predictors, and other on-chip hardware. Switching to another job causes the current state to be flushed and new state relevant to the currently-running job to be brought in. What is the turn-around time of RR?
앞의 예를 다시 보자. A, B, C 각 작업은 5초간 실행되고 동시에 도착하며, RR은 1초의 time slice를 가진다. A는 13, B는 14, C는 15에 종료하고 평균 14의 turn-around time을 가진다. 매우 안좋다. RR은 각 작업을 잠깐 실행하고 다음 작업으로 넘어가고 하면서 가능한 한 각 작업을 늘리는 것이 목표다. turn-around time은 완료 시간만 고려하기 때문에 RR은 거의 최악이다. 단순한 FIFO보다 성능이 좋지 않게 된다. Turnaround time vs response time. RR은 공정하다. SJF, STCF은 Turn-around time에 최적화하지만 respone time은 나쁘다. RR은 respone time을 최적화하지만 turn-around time은 나쁘다. 아직 workload assumption 4와 5가 남았다.
4 . All jobs only use the CPU(i.e., they perform no I/O )
5. The run-time of each job is Known.
Incorporatin I/O
workload assumption 4 → All jobs only use the CPU를 완화해보자.
A scheduler clearly has a decision to make when a job initiates an I/O request because the currently-running job won't be using the CPU during the I/O; it is waiting for I/O completion. The scheduler also has to make a decision when the I/O completes. when that occurs, an interrupt is raised, and the OS runs and moves the process that issued the I/O from blocked back to the ready state. It could decide to run the job at that point.
Example: A와 B가 있다고 하자. 각 작업은 50msec의 CPU 시간을 필요로 한다. A는 10mesc동안 실행한 후 I/O 요청을 한다.(I/O 시간은 10msec라고 가정한다.) B는 I/O 작업이 없다. Scheduler는 A를 먼저 실행시키고, B를 다음에 실행시킨다.
STCF Scheduler를 구축하려고 가정해보고 A가 5개의 10msec 작업으로 분할. B는 하나의 50msec의 CPU를 요청한다는 사실을 어떻게 활용할까?
일반적인 접근 방식은 A는 각 10msec 하위 작업을 독립적인 작업으로 다루는 것이다. 시스템이 시작할 때 10msec 작업들과 50msec를 스케줄하는 것이다. STCF의 경우 가장 짧은 작업을 선택한다. A다. A를 실행하고 B를 선점하여 10msec동안 실행한다. 입출력이 끝나기를 기다리는 동안 CPU는 다른 프로세스에 의해 사용되어 연산의 중첩이 가능해진다.
Overlap(중첩)은 높은 이용률을 가능하게 한다. 가능하면 시스템을 활용도를 극대화하기 위해 연산을 Overlap되게 시랭한다.
The fundamental problem
First, it would like to optimize turn-around time, which is done by running shorter jobs first(SJF); but, the OS doesn't generally know how long a job will run for, exactly the knowledge that algorithms like SJT(or STCF) require. Second, MLFQ would like to make a system feel responsive to interactive users(i.e., users sitting and staring at the screen, waiting for a process to finish), and thus minimize response time; unfortunately, algorithms like Round Robin reduce response time but are terrible for turn-around time.
Question: How TO SCHEDULE WITHOUT RERFECT KNOWLEDGE?
How can we design a scheduler that both minimizes response time for interactive jobs while also minimizing turn-around time without a priority knowledge of job length?
MLFQ: Basic Rules
Assumption: The MLFQ has a number of distinct queues, each assigned a different priority level. At any given time, a job that is ready to run is on a single queue. MLFQ uses priorities to decide which job should run at a given time.
Basic rules for MLFQ: Rule 1: if Priority(A) > Priority(B), A runs (B donsen't). Rule 2: if Priority(A) = Priority(B), A&B run in RR. The key to MLFQ scheduling: How the scheduler sets priorities? MLFQ varies the priority of a job based on its observed behaviour.
Example
If a job repeatedly relinquishes the CPU while waiting for input from the keyboard, MLFQ its priority high. if a job uses the CPU intensively for long periods of time, MLFQ will reduce its priority. MLFQ will try to learn about processes as they run, and thus use the history of the job to predict its future behaviour.
Attempt #1: How to Change Priority
First attempt
Rule 3: When a job enters the system, it is placed at the highest priority(the topmost queue). Rule 4a: If a job uses up an entire time slice while running, its priority is reduced(i.e., moves down one queue). Rule 4b: If a job gives up the CPU before the time slice is up, it stays at the same priority level.
Ex 1) Long-running Job Over time
작업은 최고 우선 순위로 진입한다.→ Q2, 10msec timeslice가 하나 지나면 Schduler는 작업의 우선 순위를 한 단계 낮추어 해당 작업을 Q1으로 이동시킨다. 다시 하나의 Time Slice 동안 Q1에서 실행한 후 작업은 마침내 가장 낮은 우선순위를 가지게 되고 Q0으로 이동된다. 이후엔 Q0에 계속 머무른다.
Ex 2) Along Came A Short Job
좀 더 복잡한 예를 살펴보낟. MLFQ가 어떻게 SJF에 근접할 수 있는지 이해해보자. 이 예에서는 2개의 작업이 존재한다. A는 오래 실행되는 CPU 위주 작업, B는 짧은 대화형 작업. A는 얼마동안 이미 실행온 상태이고, B는 이제막 도착했다고 가정한다. → CPU 위주 작업들처럼 A(검은색)는 가장 낮은 우선순위 큐에서 실행되고 있다. B(회색)는 T=100에 시스템에 도착하고 가장 높은 우선순위 큐에 놓여진다. 실행 시간이 짧기 때문에 (단지 2ms), 두 번의 time slice를 소모하면 B는 바닥의 큐에 도착하기 전에 종료한다. A는 낮은 우선 순위에서 실행을 재개한다.
이 예에서 이 알고리즘의 주 목표를 알 수 있다. Scheduler는 작업이 짧은지 긴지 모른다. 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여한다. 진짜 짧으면 빨리 실행하고 바로 종료된다. 길다면 천천히 아래 큐로 이동하게 되고 스스로 긴 배치형 작업이라는 것을 증명한다. 이러한 방식을 MLFQ는 SJF를 근사할 수 있다.
Ex 3) What About I/O?
다음으로 I/O 작업을 수행하는 예를 살펴보자. Rule 4b가 말하는 것처럼, Process가 Time Slice를 소진하기 전에 Processeor를 양도하면 같은 Priority를 유지하게 한다. ← 이 규칙 의도는 간단하다. 대화형 작업이 키보드나 마우스로부터 사용자 입력을 대기하며 자주 입출력을 수행하면 Time Slice가 종료되기 전에 CPU를 양도하게 될 것이다. 그런 경우 동일한 Priority를 유지하게 되는 것이다.
위 예는 이 규칙이 동작하는 예를 보이고 있다. B(회색)는 대화형 작업으로서 I/O를 수행하기 전에 1msec동안만 실행된다. A(검정색)는 긴 배치형 작업으로 B와 CPU를 사용하기 위하여 경쟁한다. B는 CPU를 계속해서 양도하기 때문(대화형 작업이라 계속 CPU를 양도한다.)에 MLFQ방식은 B를 가장 높은 우선순위로 유지한다.
Problems With Our Current MLFQ
현재의 MLFQ는 단순하다. CPU를 긴 작업들과 짧은 작업들 사이에 공유하고, I/O 중심 대화형 작업을 빨리 실행시키기 때문에 잘 동작하는 것처럼 보이지만 심각한 결점을 가진다.
1. Starvation
시스템에 너무 많은 대화형 작업이 존재하면 그들이 모든 CPU 시간을 소모하게 될 것이고 따라서 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 것이다.← Starvation
2. Smart (or wicked) user
Smart user는 Scheduler를 자신에게 유리하게 동작하도록 다시 작성할 수 있다. 일반적으로 Schduler를 속여서 지정된 몫보다 더 많은 시간을 할당하도록 만드는 것을 말한다. 현재까지의 MLFQ는 다음 공격에 취약하다. Time Slice가 끝나기 전에 아무 파일을 대상으로 I/O 요청을 내려 CPU를 양도한다. 제대로 된다면 Time Slice 99%를 실행하고 CPU를 양도하게 되면 CPU를 거의 독점할 수 있다.
3. Transition of behaviors
프로그램은 시간이 지남에 따라 동작이 변할 수 있다. CPU 위주 작업이 대화형 작업으로 바뀔 수 있다. 현재 구현 방식으로는 그런 작업은 다른 대화형 작업들과 같은 대우를 받을 수 없다.
Attempt #2: The Priority Boost
규칙을 보완하여 Starvation 문제를 방지할 수있는지 살펴보자. 간단한 아이디어는 주기적으로 모든 작업의 Priority를 boost(상향 조정)하는 것이다. 일단 간단한 방법: 모두 최상위 큐로 보내는 것이다.
Rule 5: After some time period S, move all the jobs in the system to the topmost queue.
새 규칙은 두가지 문제를 한번에 해결한다.
Processes are guaranteed not to starve: by sitting in the top queue, a job will share the CPU with other high-priority jobs in a RR fashion.
If a CPU-bound job has become interactive, the scheduler treats it properly once it has received the priority boost.
Attempt #3: Better Accounting
해결해야 할 문제가 하나 더 있다. Scheduler를 자신에게 유리하게 동작시키는 것을 어떻게 막을 수 있을까? 이러한 일을 가능하게 만든 주범은 Rule 4a, Rule 4b다.
Rule 4a: If a job uses up an entire time slice while running, its priority is reduced(i.e., moves down one queue). Rule 4b: If a job gives up the CPU before the time slice is up, it stays at the same priority level.
두 규칙은 작업이 Time Slice가 끝나기 전에 CPU를 양보하여 Priority를 유지가 가능하게 한다. 여기서 해결책은 MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하는 것. Scheduler는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장한다. 프로세스가 Time Slice에 해당하는 시간을 모두 소진하면 다음 Priority Queue로 강등된다. Time Slice를 한번에 소진하든 짧게 여러번 소진하든 상관 없다. 규칙 4a와 4b를 합쳐 4로 재정의한다.
Rule 4: One job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced.
EX) Workload가 Scheduler를 자신에게 동작시키려고 할 때 예전 규칙 4a, 4b일 때 행동(왼쪽), 새로운 규칙 4(오른쪽)을 아래 그림을 통해 아 수 있다. 이런 자신에게 유리하도록 조작하는데 대한 방지책이 없다면 프로세스는 time slice가 끝나기 직전에 입출력 명령어를 내릴 수 있어 CPU 시간을 독점할 수 있다. 방지책이 마련되면 프로세스의 입출력 행동과 무관하게 아래 단계 큐로 천천히 이동하게 되어 CPU를 자기 몫 이상으로 사용할 수 없게 된다.
MLFQ Sheduling에는 여러 다른 쟁점이 남아있다.
필요한 변수들을 Scheduler가 어떻게 설정해야 하는가.
몇 개의 Queue가 존재하는가?
Queue당 Time slice의 크기는 얼마로 해야하는가?
Starvation을 피하고 행동을 반영하기 위하여 얼마나 자주 Priority가 Boost해야하는가?
이런 쟁점의 질문은 workload에 대해 충분히 경험하고 계속 조정해나가면서 균형점을 찾아야한다.
MLFQ 요약
이 알고리즘은 Multi level queue를 가지고 있으며, 지정된 작업의 priority를 정하기 위하여 feedback를 사용한다. 과거에 보여준 행동이 priority의 지침이 된다. 작업이 시간이 지남에 따라 어떻게 행동하고 그에 맞게 어떻게 처리하는지에 대해 주의를 기울여야한다.
지금까지 배운 MLFQ의 Rule이다.
Rule 1: if Priority(A) > Priority(B), A runs (B donsen't). Rule 2: if Priority(A) = Priority(B), A&B run in RR. Rule 3: When a job enters the system, it is placed at the highest priority(the topmost queue). Rule 4: One job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced. Rule 5: After some time period S, move all the jobs in the system to the topmost queue.
MLFQ는 작업의 특성에 따라 정보 없이, 작업의 실행을 관찰한 후 그에 따라 Priority를 지정한다. MLFQ는 Turn-around time, respone time을 모두 최적화한다. 짧게 실행되는 대화형 작업에 대해서는 우수한 전반적인 성능을 제공한다.→ SJF, STCF와 유사 오래 실행되는 CPU-집중 workload에 대해서는 공정하게 실행하고 조금이라도 진행되도록 한다.
영문 요약 내용
MLFQ is interesting for the following reason: instead of demandinga prioriknowledge of the nature of a job, it observes the execution of ajob and prioritizes it accordingly. In this way, it manages to achieve thebest of both worlds: it can deliver excellent overall performance(similarto SJF/STCF) for short-running interactive jobs, and is fair and makesprogress for long-running CPU-intensive workloads. For this reason,many systems, including BSD UNIXderivatives [LM+89, B86], Solaris[M06], and Windows NT and subsequent Windows operating systems[CS97] use a form of MLFQ as their base scheduler.
Virtualization of CPU = mechanism + policy란 사실을 우리는 배웠다.🤔 이제 그 중 mechanism에 대해 배운다. 상당히 혼미하다. 😣!
Mechanism: Limited Direct Execution
Introduction
By time sharing the CPU, virtualization is achieved. THEN..
Performance: how can we implement virtualization without adding excessive overhead to the system?
Control: how can we run process efficiently while retaining control over the CPU?
❓ Obtaining high performance while maintaining control is thus one of the central challenges in building an operating system.
❤ Direct execution
Just run the program directly on the CPU.
Thus, when the OS wishes to start a program running, it creates a process entry for it in a process list, allocates some memory for it, loads the program code into memory, locates its entry point (i.e., the main() routine or something similar), jumps to it. and starts running the user's code.
But Direct execution gives rise to a few problems in our quest to virtualize the CPU.
🔆 Questions
Simple thing: if we just run a program, how can the OS make sure the program doesn't do anything that we don't want it to do while running it efficiently?
when we are running a process, how does the operating system stop it from running and switch to another process, thus implementing the time-sharing we require to virtualize the CPU?위에서부터 아래로 실행되니 위에서 아래로 읽어주자
번역
💥Problem #1: restricted Operations
Direct execution has the obvious advantage of being fast; The program runs natively on the hardware CPU and thus executes as quickly as one would expect. But running on the CPU introduces a problem:
what if the process wishes to perform some kind of restricted operation?
User Mode
Code that runs in user mode is restricted in what it can do.
Kernel mode
In which the operating system runs. In this mode, code that runs can do what it likes, including privileged operations such as issuing I/O requests and executing all types of restricted instructions.
💥What should a program to when it wishes to perform some kind of privileged operation?
→ To enable this, virtually all modern hardware provides the ability for user programs to perform a system call. System call: system calls allow the kernel to carefully expose certain key pieces of functionality to user programs. (such as accessing the file system, creating and destroying processes, communicating with other process, and allocating more memory.)
🤩To execute a system call, a program must execute a special trap instruction.
This instruction jumps into the kernel and raises the privilege level to kernel mode; once in the kernel, the system can now perform whatever privileged operation are needed.
✔When finished, the OS calls a special return-from-trap instruction,
which returns into the calling user program while simultaneously reducing the privilege level back to user mode.
The hardware needs to be a bit careful when executing a trap, in that it must make sure to save enough of the caller's registers in order to be able to return correctly when the OS issues the return-from-trap instruction.
커널 스택(kernel stack) : 플래그와 레지스터들을 저장하는 자료구조(각 프로세스마다 있음)
커널 모드와 사용자 모드를 이동할 때 하드웨어에 의해 PC와 레지스터가 저장되고 복원되는 용도
Trap table
Q: How does the trap know which code to run inside the OS?
A: The kernel sets up a trap table at boot time.
OS가 하드웨어에게 예외 사건이 일어났을 때 어떤 코드를 실행해야 하는지 저장하는 자료구조
trap은 trap table을 사용하여 발생시킨다.
The OS informs the hardware of the locations of trap handlers.
Trap handlers = OS는 특정 명령어를 사용하여 하드웨에게 이 위치를 알려주고 하드웨어는 문제를 해결한다. OS는 하드웨어에게 trap handler의 위치를 알려주고 하드웨어는 이 위치를 기억했뒀다가 예외가 발생했을 때 문제를 해결한다.
Once the hardware is informed, it remembers the location of handlers and thus the hardware knows what to do (i.e., what code to jump to) when system calls and other exceptional events take place.
When the machine boots up, it does so in privileged mode, and thus is free to configure machine hardware as need be. One of the first things the OS does is to tell the hardware what code to run when certain exceptional events occur.
System-call number: to specify the exact system call, a system call number is usually assigned to each system call.
The user code is thus responsible for placing the desired system-call number in a register or at a specified location on the stack→ the OS, when handling the system call inside the trap handler, examines this number, ensures it is valid, and, if it is, executes the corresponding code.
This level of indirection serves as a form of protection; user code cannot specify an exact address to jump to, but rather mus request a particular service via number.
번역
LDE 프로토콜 진행 과정
(전반부, 부팅 시)
커널은 트랩 테이블을 초기화하고 CPU는 테이블의 위치를 기억한다.
커널은 커널 모드에서만 사용할 수 있는 명령어를 이용하여 수행한다.
(후반부, return-from-trap을 이용하여 사용자 프로세스를 시작할 때)
새로운 프로세스를 위한 노드를 할당하여 프로세스 리스트에 삽입하고 메모리를 할당한다.
return-from-trap 명령어로 CPU를 사용자 모드로 전환하고 프로세스 실행을 시작한다.
프로세스가 시스템콜을 호출하면 OS로 다시 트랩된다.
OS는 시스템 콜을 처리하고 return-from-trap 명령어를 사용하여 다시 제어를 프로세스에게 넘긴다.
프로세스는 자신의 할 일을 다 하면 main()에서 리턴한다.
종료할 때 exit() 시스템을 호출하고 다시 OS체제로 트랩된다.
Two phases in the limited direct execution protocol.
First phase: the kernel initializes the trap table, and the CPU remembers its location.
Second phase: The kernel sets up a few things(e.g., allocating a node on the process list, allocating memory) before using a return-from-trap instruction to start the execution of the process; this switches the CPU to user mode and begins running the process.
When the process wishes to issue a system call, it traps back into the OS, which handles it and once again returns control via a return-from-trap to the process.
If a process is running on the CPU, this by definition means the OS is not running.
💥Problem #2: Switching Between Process
💥Q: How can the operating system regain control of the CPU so that it can switch between processes?
A: cooperative approach
cooperative approach → system Call 기다리기 In this style, the OS trusts the processes of the system to behave reasonably. Processes that run for too long are assumed to periodically give up the CPU so that the OS can decide to run some other task.
Most processes transfer control of the CPU to the OS by making system calls.
Systems like this often include an explicit yield system call, which des nothing except to transfer control to the OS so it can run other processes.
💥Thus, in cooperative scheduling system, the OS regains control of the CPU by waiting for a system call or an illegal operation of some kind to take place.💥
A Non-Cooperative Approach: The OS Takes Control
Q: How can the OS gain control of the CPU even if processes are not being cooperative? What can the OS do to ensure a rogue process does not take over the machine?
A: A timer interrupt
Interrupt
중단, 새치기. CPU가 프로그램을 실행하고 있을 때, 입출력 하드웨어 등의 장치나 예외상황이 발생하여 처리가 필요한 경우 CPU에게 알려 처리할 수 있도록 하는 것을 말한다.
종류:Hardware Interrupt(I/O), Software Interrupt(예외상황,system call) 자세한 내용은 아래 블로그에 제대로 정리되어 있다.
A timer device can be programmed to raise an interrupt every so many millisecond. when the interrupt is raised, the currently running process is halted, and a pre-configured interrupt handler in the OS runs.
TIP: The addition of a timer interrupt gives the OS the ability to run again on a CPU even if processes act in a non-cooperative fashion. Thus, this hardware feature is essential in helping the OS maintain control of the machine.
Important decision
결정→Whether to continue running the currently-running process or switch to a different one. ↑This decision is made by a part of the operating system known as the scheduler.
Context switch
개념 : All the OS has to do is save a few register values for the currently-executing process (onto its kernel stack, for example) and restore a few for the soon-to-be-executing process(from its kernel stack).
By doing so, the OS thus ensures that when the return-from-trap instruction is finally executed, instead of returning to the process that was running, the system resumes execution of another process.
프로세스 전환을 위해서 운영체제는 저서준 어셈블리 코드를 사용하여 현재 실행 중인 프로세스의 A few registers(General purpose registers, PC, the kernel stack pointer)에 저장한다.
요약
CPU 가상화를 구현하기 위한 핵심적인 저수준 기법에 관해 설명한 챕터. 이 기법을 제한적 직접 실행이라고 한다. 아이어디는 간단: CPU에서 실행하고 싶은 프로그램을 실행시킨다. 그러나 OS는 운영체제가 CPU를 사용하지 못하더라도 프로세스의 작업을 제한할 수 있도록 하드웨어를 셋업해야한다.
일상 생활에서 이러한 방법이 있다. 아이가 있다면 방에 아기 보호 장치를 설치한다. 위험한 물건이 있다면 서랍에 넣어두고 잠그거나 하는 일들이다. 이러면 아이에게 위험한 물건들을 막아 놓아 아이는 자유롭게 방을 안전하게 돌아다니게 할 수 있다. 이렇듯 운영체제는 CPU에게 안전 장치를 준비해 놓는다.
우선 부팅할 때 트랩 핸들러 함수를 셋업하고 인터럽트 타이머를 시작 시키고 그런 후에 제한 모드에서만 프로세스가 실행 하도록 한다. 이러면 OS는 프로세스를 효율적으로 실행할 수 있다.
다음 챕터에서는 특정 시점에 어떤 프로세스를 실행시켜야할까란 질문에 스케쥴러가 답하는 질문에 배운다.
시작하실때 교수님의 말씀: 운영체제는 User,kenel 모드로 나누어져 있으며 kenel 모드엔 user가 접근하지 못한다. 또한 kenel 모드에서 user모드가 시작된다. user는 system의 기능이 사용하고 싶을 때에는 즉, 하드웨어를 사용하고 싶을 때 system call를 사용한다. control은 kenel딴으로 넘어가며 system call이 끝나면 결과 완료를 user에게 넘겨준다.
In this interlude, we discuss process creation in Unix systems.
Unix system
Unix presents one of the most intriguing ways to create a new process with a pair of system calls: fork() and exec(). Wait() → It can be used by a process wishing to wait for a process it has created to complete.
HOW TO CREATE AND CONTROL PROCESS What interfaces should the OS present for process creation and controls? How should these interfaces be designed to enable ease of use as well as utility?
The fork() system call
The fork() system call is used to create a new process. Pid: Process identifier is used to name the process if one wants to do something with the process.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main(int argc, char *argv[]){
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if(rc < 0){ //fork failed; exit
fprintf(stderr, "fork failed\n");
exit(1);
} else if(rc == 0){ //child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
} else { // parent goes down this path (main)
printf("hello, I am parent of %d (pid: %d)\n",
rc, (int) getpid());
}
return 0;
}
실행결과
prompt > ./p1
hello world (pid:29146)
hello, I am parent of 29147 (pid:29146)
hello, I am child (pid: 29147)
prompt >
prompt > ./p1
hello world (pid:29146)
hello, I am child (pid: 29147)
hello, I am parent of 29147 (pid:29146)
prompt >
That means that to the OS, it now looks like there are two copies of the program p1 running, and both are about to return from the fork() system call.
When it first started running The process prints out a hello world message, including PID → The process calls the fork() system call The OS provides as a way to create a new process
else or else if가 실행된다.
The process that is created is an (almost) exact copy of the calling process → the newly-created process (called the child) doesn't start running at main().
child process start fork() system call line next. - ●The newly-created process isn't an exact copy. Specifically, although it now has its own copy of the address space(i.e., its own private memory) its own registers, its own PC, and so forth, the value it returns to the caller of fork() is different.
여러개의 프로그램이 병렬적으로 존재시 어떤 프로그램을 실행시킬지는 Scheduler가 결정한다.
The CPU scheduler, a topic we'll discuss in great detail soon, determines which process runs at a given moment in time. we cannot usually make strong assumptions about what it will choose to do, and hence which process will run first. This nondeterminism, as it turns out, leads to some interestin problems, particularly in muti-threaded programs.
❔🤗 Q. Child process 와 Parent Process는 병렬적으로 실행된다. 하지만 반복문이 아닌데 두번이 실행되는 것이 이해가 되지 않는다. 일단 fork() 함수의 return 값을 알아본다. 그 후 다시 한번 fork()이후 instrution이 실행된다는 것을 알아두자.
fork() system call의 반환 값
fork() 함수가 실행된 후 child process가 생성되면 fork() 다음 instruction부터 시작된다. fork() 실행 후 child, parent 두 개의 프로세스는 Hello 메세지를 출력한다. 이게 바로 반복문이 아니지만 두 개의 프로세스가 존재하여 두번 실행되는 현상이다.
단순히 두번 실행된다. 반복문은 없지만 이 프로세스가 두개라 두번이 실행된다.
Hello가 8번 실행되는데 이는 곧 프로세스 수를 가리킨다. 프로세스 수는 2^n이다. n은 fork() 수 다.
어떤 식으로 fork()가 진행되었는지 보여준다.
fork()가 어떤 방식으로 보여주는 gif이다.
이정도 설명이면 이해가 될 거다.
The wait() system call
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
int main(int argc, char *argv[]){
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if(rc < 0){ //fork failed; exit
fprintf(stderr, "fork failed\n");
exit(1);
} else if(rc == 0){ //child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
} else { // parent goes down this path (main)
int rc_wait = wait(NULL);
printf("hello, I am parent of %d (rc_wait:%d) (pid: %d)\n",
rc, rc_wait, (int) getpid());
}
return 0;
}
실행 결과
prompt> ./p2
hello world (pid:29266)
hello, I am child (pid:29267)
hello, I am parent of 29267 (wc:29267) (pid:29266)
prompt>
It is quite useful for a process to wait for another process to finish. // wait()는 그렇게 어렵지 않는 내용이다. Parent Process는 wait(NULL);로 인해서 child process가 끝날 때까지 기다리게 다음에 실행하게 된다.
The exec() System call
This systems call is useful when you want to run a program that is different from the calling program.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/wait.h>
int main(int argc, char *argv[]){
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if(rc < 0){ // fork failed; exit
fprintf(stderr, "fork failed\n");
exit(1);
} else if(rc == 0){ //child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
char *myargs[3];
myargs[0] = strdup("wc"); // program: "wc" (word count) wc는 명령어
myargs[1] = strdup("p3.c"); // argument: file to count p3.c는 현재 프로그램
myargs[2] = NULL; /* marks end of array execvp는 자신에게 주어지는 string
끝에 NULL로 존재해달라고 요구 */
execvp(myargs[0], myargs); // runs word count // execvp = exec family.
printf("this shouldn't print out");
} else {
int rc_wait = wait(NULL);
printf("hello, I am parent of %d (rc_wait:%d) (pid:%d)\n",
rc, rc_wait, (int) getpid());
}
return 0;
}
실행 결과
prompt> ./p3
hello world (pid:29383)
hello, I am child (pid:29384)
29 107 1030 p3.c
hello, I am parent of 29384 (wc:29384) (pid:29383)
prompt>
Given the name of an executable, and some arguments, exec() loads code ( and static data) from that executable and overwrites its current code segment (and current static data) with it → The heap and stack and other parts of the memory space of the program are re-initialized → Then the OS simply runs that program, passing in any arguments as the argv of that process.
🕳Thus, exec() does not create a new process; rather, it transforms the currently running program into a different running program.
often you want to run a different program; exec() does just that. In this example, the child process calls execvp() in order to run the program wc, which is the word counting program. In fact, it runs wc on the source file p3.c, thus telling us how many lines, words, and bytes are found in the file. ← 소스 코드 안에 다 적혀 있는 내용이다.
a bunch of instructions and maybe some static data
*con-text switch to stop running one program and start running another
*scheduling policy are algorithms for making some kind of decision within the OS.
How To Provide The Illusion Of Many CPUS?
⇒ Virtualizing.
By running one process, then stopping it and running another, and so forth, the OS can promote the illusion that many virtual CPUs exist when in fact there is only one physical CPU (or a few).
Basic technique: time-sharing → Process ↑ Performance ↓ To implement virtualization of CPU = low-level machinery(mechanism) + high-level intelligence(policy)
Process
To understand what constitutes a process → We thus have to understand its machine state: What a Program can read or update when it running. At any given time, what parts of machine state are important to the execution of these programs?
machine state → Memory, Register
Memory(address space)
Instructions lie in Memory. the data that the running program reads and writes sits memory.
Register
many instructions explicitly read or update registers and thus clearly they are important to the execution of the process.
Program Counter : PC = Instruction Pointer : IP
Stack Pointer
frame Pointer
PC or IP tells which instruction of the program is currently being executed.
used to manage the stack for function parameters, local variables, and return address
*Persistent storage ← Program often access
Such I/O information might include a list of the files the process currently has open
Process Control Block → PCB
프로세스에 대한 정보를 저장하는 자료구조 운영체제는 프로세스를 PCB 단위로 관리하며 프로세스 스케줄링을 위한 정보를 PCB를 통해 관리한다. 프로세스가 생성될 때마다 고유의 PCB가 생성되며, 프로세스가 완료되면 PCB는 제거된다. 프로세스 간 Switching이 발생할 때, 운영체제는 PCB를 이용해서 상태를 전이시킨다. (State Transition)
PCB의 데이터 구성
Process Identification Data
Process State Data
Process Control Data
PCB는 다음 정보를 가지고 있다.
Process ID: 프로세스를 구분하는 ID
Process State: 각 State들의 상태를 저장한다.
Program Counter: 다음 Instruction의 주소를 저장하는 카운터, CPU는 이 값을 통해 Process의 Instruction을 수행한다.
Register: Accumulator, CPU Register, General Register등을 포함한다.
CPU Scheduling Information: 우선 순위, 최종 실행시간, CPU 점유시간 등이 포함된다.
Memory Information: 해당 프로세스 주소 공간(lower bound~upper bound)정브를 저장.
Process Information(페이지 테이블, 스케줄링 큐 포인터, 소유자, 부모 등)
Device I/O Status(프로세스에 할당된 입출력 장치 목록, 열린 팔린 목록 등)
Pointer: 부모/자식 프로세스에 대한 포인터, 자원에 대한 포인터 등
Open File List: 프로세스를 위해 열려있는 파일의 리스트
Process Application Programing Interface → Process API
some idea of what must be include in any interface of an OS.
Create
An operating system must include some method to create new process.
▲ type a command into the shell. ▲ double-click on an application icon.
Destroy
many processes will run and just exit by themselves when complete they don't, however, the user may wish to kill them, and thus an interface to halt a runaway process is quite useful.
Wait
Sometimes it is useful to wait for a process to stop running thus some kind of wating interface is often provided.
Miscellaneous Control
Other than killing or waiting for a process, there are sometimes other control that are possible. ex) 1. to suspend a process. 2. stop it from running for a while
Status ← such as how long it has run for, or what state it is in.
There are usually interfaces to get some status information about a process.
메모리 구조 이해하기
Stack에는 함수, 지역변수 Heap은 동적으로 변경되는 Heap같은 것들 BSS 아직 초기화가 이루어지지 않은 변수 Data는 초기화가 된 변수 Code는 Code
Process Creation: A Little More Detail
Q. One mystery that we should unmask a bit is how programs are transformed into processes.
⇒⇒ Specifically, how does the OS get a program up and running?
The OS must do to run a program is to load its code and any static data into Memory.
▪Programs initially reside on disk (modern systems, flash-based SSD) in some kind of executable format. ▪ thus, the process of loading a program and static data into memory requires the OS to read those bytes from disk and place them in memory somewhere By loading places of code or data only as they are needed during program execution.
To truly understand how lazy loading of pieces of code and data works you'll have to understand more about the machinery of Paging and Swapping
For now, just Remember that before running anything, the OS clearly must do some work to get the important program bits from disk into memory
Once the code and static data are loaded into memory → there are a few other the OS needs to do before running the process.
Some memory must be allocated for the program's run-time stack (or just stack).
C programs use the stack for local variables, function parameters, and return address.
The OS allocates this memory and gives it to the process.
The OS will also likely initialize the stack with arguments. specifically, it will fill in the parameters to the main() function, i.e., argc and argv array.
The OS may also allocate some memory for the program's heap.
In C programs, the heap is used for explicitly requested dynamically-allocated data; programs request such space by calling malloc() and free it explicitly by calling free().
The heap is needed for data structures such as linked lists, hash tables, trees, and other interesting data structures. The heap will be small at first; as the program runs, and requests more memory via the malloc() library API, the OS may get involved and allocate more memory to the process to help satisfy such calls.
The OS will also do some other initialization tasks, particularly as related to input/output(I/O).
By loading the code and static data into memory → by creating and initializing a stack → by doing other work as related to I/O setup → the has now (finally) set the stage for program execution. → to start the program running at the entry point( main() ) ⇒ By jumping to the main() routine, the OS transfers control of the CPU to the newly-create process → the program begins its execution.
Process States
Running
In the running state, a process is running on a processor. → it is executing instructions.
Ready
In the ready state, a process is ready to run but for some reason the Os has chosen not to run it at this given moment.
Blocked
In the blocked state, a process has performed some kind of operation that makes it not ready to run until some other event takes place. common ex)When a process initiates an I/O request to a disk, it becomes blocked and thus some other process can use the processor.
Structure
Process List: Process Status를 파악하기 위한 자료구조
Register Context: Process가 중단되었을 때 해당 프로세스의 레지스터 값들을 저장하는 자료구조
