Study & Project repository

• Multilevel Queue(다단계 큐)

• 우선순위가 다른 여러 작업들을 여러개의 큐에 저장
• 각 큐들은 자신만의 스케줄링 알고리즘을 가짐
• 프로세스들은 영원히 하나의 큐에만 할당, 다른 곳으로 갈 수 없음
• 예시

• Multilevel Feedback Queue

• 멀티레벨 큐에 피드백을 줘서 전체 큐를 사용

• 첫 번째 단계에서 8이라는 시간을 할당 받은 후 작업이 남았다면 아래 큐로 옮겨짐
• 두 번째 단계는 16이라는 시간을 할당, 그럼에도 불구하고 작업이 남았다면 마지막 단계로 옮겨짐
• 마지막 단계는 선입선출로 끝냄

• Multiple-Processor Scheduling

• CPU가 여러개 있을 경우
• 기능에 있어서 종료가 같은 경우에는 기능이 동일 -> Homogeneous processors
• 큐에 있는 어떤 프로세스라도 실행 가능
• 이기종 시스템의 경우는 한 쪽의 프로세스만 실행 가능
• Load Balance : 동종의 CPU들 중 한 곳에만 작업이 몰려있다면 비어있는 다른 CPU에 할당해주어 부하를 방지 -> 프로세스마다 큐가 별도로 있어야 함
• Processor affinity(친화성) : 프로세스를 바꾸게 되면 데이터들도 모두 바꿔야 하고 캐시도 모두 없애야 하는데 이는 효율이 안좋아지고 처리 비용이 비싸짐
• soft affinity : 지키려고 노력하지만 보장하지 않음 -> 정해진 CPU에서 정해진 프로세스들만 실행되도록 하지만 부하가 많이 발생하면 풀림
• hard affinity : 프로세서를 옮기지 않도록 지정 가능 -> 무조건 정해진 CPU에서만 정해진 프로세스들이 실행됨

• Symmetric multiprocessing(SMP)에서의 성능 향상

• 여러 개의 프로세서(혹은 코어)는 BUS를 통해 하나의 메모리에 액세스
• single processor(혹은 Core)의 경우는 인터럽트 처리를 위해 스위칭
• SMP의 경우 인터럽트를 처리하는 Core를 별도로 지정해서 처리 -> 기존의 프로세스는 중단없이 진행가능

• NUMA(Non-Uniform Memory Access)

• 각 CPU에 고유한 메모리를 할당하고 CPU들을 협력하여 사용
• 각자의 메모리들은 다른 CPU가 접근할 수 있으나 조금 느려짐
• CPU 하나를 뽑더라도 메모리는 그대로 사용 가능 -> 따라서 고장나면 뽑아서 고친 후 다시 끼울 수 있음

• Load Balancing

• 한 쪽에 부하가 왔을 때, 다른 CPU에 할당하여 부하를 줄이는 방식
• 부하가 심한 CPU에서 작업을 가져와 실행
• Processor Affinity와 상충 -> 최선의 방법은 없음, 알고리즘과 사용자들의 몫

• Multicore Processors

• 두 개의 코어를 쓰고 동일 전력을 사용할 경우, 성능을 174% 정도까지 높일 수 있음
• Multithreaded Multicore System

1. 코어가 하나만 있는 경우에는 CPU혹은 Memory작업 하나씩만을 수행할 수 있음
2. 멀티 코어의 경우 CPU작업을 실행할때 Memory작업을 동시에 할 수 있게됨

• Real-Time CPU Scheduling

• 임베디드 시스템은 작은 OS들이 들어가고 이 OS들은 특성상 real time 시스템을 지향하는 편
• 따라서 real time에 맞는 스케줄링이 필요 -> 정해진 시간안에 완료
• 정해진 시간안에 정해진 일을 끝내는 것이 목표
• 우선순위 기반 스케줄링을 사용
• 문맥 교환시 생기는 dispatch latency를 고려
• 인터럽트 지연시간 : 인터럽트가 게시되고 해당 서비스루틴이 실행되기까지의 지연시간

• 디스패치 지연시간 : 프로세스의 교체시 생기는 지연시간

1. conflicts : 커널에서 실행 중인 프로세스를 선점하는데 생기는 시간, 자원 회수(우선 순위 낮은 프로세스는 우선 순위 높은 프로세스가 요구하는 자원을 놓아줌)하는데 걸리는 시간
2. dispatch : context switching시 걸리는 시간

• Priority-based Scheduling for Real-time

• periodic : 하나의 일이 일어나는 텀(P)
• t : 실제로 작업이 일어나야하는 시간 -> P끝까지 실행하는 것이 아닌 d까지의 데드라인을 맞춰야 함
• d : 작업이 끝나야만하는 시간

• Rate Monotonic Scheduling(realtime)

• CPU 사용시간이 끝나거나 period가 도달되면 스케줄링을 함
• 수행주기가 가장 짧은 프로세스에 가장 높은 우선순위를 부여 -> 피리어드가 짧은 것이 높음(주기가 빠르기 때문)
• 단위 시간당 프로세스 실행 비율과 우선순위간의 관계를 높임
• 단조 증가
• P1과 P2가 있는데, 각 피리어드는 (50,100), 각 수행시간은(20,35) -> P1은 50의 시간안에 20이 수행되어야 하고, P2는 100의 시간안에 35가 수행되면 됨 = 각 프로세스의 주기는 피리어드 만큼
• 데드라인이 없으므로 피리어드 안에 수행이 완료되면 됨

1. P1의 피리어드가 짧기 때문에 먼저 실행
2. P1이 20동안 실행되면 P2가 실행됨(35) -> 50경과 후 P1이 한 번 더 실행되므로 5만큼의 작업을 남기고 P1이 20만큼 실행됨(우선순위 - 선점)
3. 200이라는 시간동안 실행된다면 P1은 4블럭, P2는 2블럭으로 각각 4번 2번 실행되어야 함

• CPU 사용률에 의한 실시간 스케줄링 충분조건 : n개의 작업이 있고 아래 식을 만족하면 실시간 스케줄링이 가능

1. T는 주기, C는 수행시간
2. C/T만큼의 모든 작업을 다 더한것이 오른쪽 항보다 작거나 같으면 실시간 스케줄링이 가능
3. 위의 예시로 계산해보면 n = 2(P1, P2)이고 20/50 + 35/100을 계산하면 0.75
4. 오른쪽 항은 0.828...이 나오는데 이 식을 만족하므로 실시간 스케줄링이 가능

• 또 다른 예시

1. P1은 만족했지만 P2는 만족하지 못함
2. 이는 위와같은 차트로 그리지 않더라도 아래의 식을 계산해보면 실시간 스케줄링의 가능 여부를 파악할 수 있음

• Earliest Deadline First Scheduling(EDF)

• 급할 경우(데드라인이 가까워지는 경우)에는 우선순위를 바꿔서 수행

1. 처음에는 P1의 데드라인(피리어드 마감)이 더 가까우므로 P1이 먼저 실행됨, 그 후 P2 실행
2. 50의 시간이 지난 후(50)에 다시 데드라인을 검사해보면 P2는 30이 남았고 P1은 50이 남았으므로 계속 P2를 실행
3. 그 후 P1이 실행
4. 80경과 시 다시 P2가 들어오는데 P1은 20이 남았고 P2는 80이 남았으므로 P1을 계속 실행
5. P2 실행
6. 100경과 시 P1이 들어오는데 여기서 P2는 60이 남았고 P1은 50이 남았으므로 P1먼저 수행
7. 나머지 P2를 수행

• Linux 스케줄링은 꼭 책을 읽어볼 것
• Windows Priority classes

• 숫자가 큰 것이 우선순위가 높은 것

• 알고리즘의 평가

• Deterministic Evaluation Modeling : 실제로 여러가지 자료들을 평가해보고 결정

• Queueing Models : CPU 와 I/O bursts 시간, 평균 처리량, 이용률 대기시간 등을 대입하여 계산하는 것

1. Little's Formula(law) : 경영학에서 나온 것, 어떤 공간에 머무는 개체수(동시에 처리할 수 있는 수) = 유입량(처리율) * 머무는 시간(처리 응답시간)
2. 식당의 회전율, 재고관리 창고의 재고율 등

• Simulations : 다양한 조건을 넣어서 실행시켜봄
• Implementation : 그냥 미리 구현하여 OS에 적용 시켜보고 오류도 찾아보는 방식

• First-Come, First-Served (FCFS) Scheduling

• 간트차트 : 프로젝트 관리에 사용하는 가로축(시간축)에 따른 일의 진행을 표시한 것
  1. ex)프로젝트(캡스턴)의 진행상황 기록 - 몇 개월간의 계획(시간 순)
  2. 한 프로젝트에 대한 전체 일들이 시간순으로 연결될 수도 있음 - 팀장들이 체크할 것들을 확인 할 수 있음
• 선입선출의 방식으로 먼저 들어온 것이 먼저 실행되는 스케줄링 기법
• 대기시간을 구해보자
  1. P1은 오자마자 실행 되었으므로 0초를 기다림
  2. P2는 P1의 실행시간동안 기다림 - 24초
  3. P3는 P1과 P2의 실행시간을 모두 기다림 - 27초
• 만약 순서를 달리한다면?
  1. P2 -> P3 -> P1순으로 처리한다면 평균 대기시간이 줄어듦
  2. 여기서 알 수 있는 사실은 실행시간이 짧은 프로세스를 먼저 처리한다면 더 효율적이라는 것을 알 수 있음
• 비선점 방식의 스케줄링이 발생하는 경우
  1. 한 프로세스가 모두 실행되어 종료 됐을 때(termination)
  2. I/O 입출력을 기다릴 때 -> waiting으로 갈 때

• Shortest-Jop-First(SJF) Scheduling

• CPU가 비어있을 경우 가장 서비스 시간이 짧은 프로세스를 할당
• 비선점형방식과 선점형방식의 차이가 있음
• 비선점형

1. 가장 짧은 수행시간을 가진 P4가 가장먼저 실행
2. P4가 모두 실행되고 termination되고 스케줄링이 발생
3. P1이 수행 -> termination -> P3 -> termination -> P2
4. 총 24초가 걸리고 평균 대기시간은 (0 + 3 + 9 + 16)/4 = 7초

• 선점형

1. 선점형에서 스케줄링이 발생하는 경우 - ready queue에 상태가 변했을 경우
   
   • 프로세스가 running상태에서 ready상태로 전환 - 할당된 시간이 끝났을 경우, 다른 시스템 콜(interrupt)이 발생했을 경우, 더 우선순위의 프로세스가 ready queue에 들어왔을 경우 ready상태로 들어가 스케줄링이 발생
   • 프로세스가 waiting상태에서 ready로 전환 - waiting에서 I/O를 끝내고 ready로 가서 스케줄링이 발생
2. 도착시간이 각기 다른 4개의 프로세스를 보았을 때 P1은 0초에서 먼저 실행되기 시작
3. 2초가 지난 후 P2가 들어오게 되고 P2는 4초의 시간이 걸리므로 우선순위가 더 높음 -> P1이 멈추고 ready queue로 들어오고 다시 스케줄링이 발생(SJF - 짧은 시간의 작업이 먼저 실행)
4. P2가 실행되는 중 2초가 흐른 후 P3가 ready queue에 들어오고 스케줄링이 다시 발생
5. P3가 가장 짧은 작업시간을 가지므로 P3가 실행됨
6. P4가 들어왔을 때, P3가 종료되고 CPU가 비어서 자연스럽게 스케줄링이 발생 - 선점형, 비선점형 둘 다 해당
7. P2 -> P4 -> P1의 순서로 종료됨
8. P1의 waiting time : 9, P2 의 waiting time : 1, P3 waiting time : 0, P4 waiting time : 2

• Determining Length of Next CPU Burst

1. 실제로 진행한, 방금 지나간 실제 길이 tn
2. 예측하는 다음 시간(타우 n+1), 예측된 이전 시간(타우 n)
3. 0에서 1사이의 값 - 보통 0.5
4. 공식

• 그래프

• Shortest-remaining-time-first(SRTF) - 선점형 방식

• 남은시간이 가장 짧은 작업부터 실행 - SJF 방식에서 발전
• P1이 수행중에 1초 후 P2가 들어와서 P1의 남은시간 7초와 P2의 4초를 비교 후 스케줄링
• P2를 실행, 2초째에 P3가 도착하지만 스케줄링 결과 여전히 P2가 1위이기 때문에 P2계속 진행
• P4가 도착해도 마찬가지이고 P2가 모두 실행된 후 스케줄링에 의해 P4 -> P1 -> P3순으로 진행
• 대기시간은 P1 : 9, P2 : 0, P3 : 15, P4 : 2
• 평균 대기시간은 26/4 = 6.5

• Priority Scheduling - 우선순위 스케줄링

• 우선순위가 프로세스들에게 할당됨 -> 우선순위를 비교하여 스케줄링
• ready queue에 도착한 순간 실행중인 프로세스와 우선순위를 비교, 더 높으면 실행중인 프로세스를 빼내는 선점형, 기다려주는 비선점형의 두 가지가 있음
• 문제 : 우선순위가 높은 프로세스가 계속 들어오게 되면 우선순위가 낮은 프로세스는 계속 기다리게 되는 무한정지(Starvation) 발생
• Aging : 스케줄링이 생길때마다 우선순위를 한단계씩 높여줌

1. 우선순위의 숫자가 낮을수록 우선순위가 높다고 생각하자
2. P2 -> P5 -> P1 -> P3 -> P4

• Round Robin(RR)

• 어느정도의 적당한 시간 크기를 가지는 할당량을 줌
• 이 시간동안 프로세스를 실행한 후 끝나지 않으면 ready queue의 가장 뒤로 보냄
• 원형 큐의 형태로 구현
• CPU 스케줄러는 돌아가면서 시간을 할당
• (n-1)*q이상은 기다리지 않는다.

1. 20초가 Time Quantum이라고 했을 때의 간트 차트이다.
2. P1이 20실행 후 P2가 17초, P3 20초, P4 20초.... 이렇게 순서대로 수행한다.
3. 평균적으로 SJF방식보다 평균 소요시간은 높지만 응답은 높다.
4. Quantum을 너무 길게하면 FCFS와 같아지고 너무 짧게하면 지연시간이 많이 발생한다.

• Priority Scheduling w/ Round-Robin

• RR과 우선순위 스케줄링을 묶은 방식
• 우선순위가 같은 경우 RR형식으로 수행, 그 외에는 그냥 우선순위가 높은 것을 먼저 처리

• Basic Concepts

• CPU burst : CPU중심, I/O가 별로 없고 대부분 CPU의 명령어로 처리
• I/O burst : CPU가 하는 일이 상대적으로 별로 없고 대부분 I/O로 처리
• 다중 프로그램으로 항상 프로세스를 실행상태로 유지함으로써 CPU의 이용률을 최대화 -> 가장 효율적으로 처리
• 프로세스는 위 그림과 같은 형태로 동작하게 됨 - CPU에서 프로세스를 실행하다가 I/O가 발생하여 멈춘 후 I/O를 처리 -> 다시 돌아옴(반복)
• CPU-burst를 가지는 프로세스들의 점유율

1. CPU 쪽의 일(명령만 처리) 연속적으로 나오는 경우가 그렇게 많지 않음
2. 대부분 CPU쪽의 연속적으로 일어나는 일은 짧음 - 길게는 일어나지 않음(별로 없음)
3. 입출력(I/O) 중심의 프로그램은 짧은 CPU burst를 가지고 있고 중앙처리장치(CPU) 중심의 프로그램은 상대적으로 긴 CPU burst를 가지고 있지만 대부분 길지 않고 짧음

• CPU Scheduler

• ready queue에 등록되어있는 여러 프로세스들 중에 정책에 의해 하나를 선택하여 CPU를 할당
• CPU Scheduling의 4가지 조건
  1. 프로세스가 실행상태에서 대기상태로 전환될 때 - CPU를 사용하는 중에 waiting상태(I/O를 기다릴 때)로 전환되면 CPU를 사용하지 않게 되는데 이때 CPU를 사용하기 위해 ready queue의 다른 프로세스들 중에 하나를 선택하는 스케줄링 발생
  2. 프로세스가 running상태에서 ready상태로 전환 - 할당된 시간이 끝났을 경우, 다른 시스템 콜(interrupt)가 발생했을 경우, 더 우선순위의 프로세스가 ready queue에 들어왔을 경우 ready상태로 들어가 스케줄링이 발생
  3. 프로세스가 waiting상태에서 ready로 전환 - waiting에서 I/O를 끝내고 ready로 가서 스케줄링이 발생
  4. terminates - running상태의 프로세스가 모두 끝나서 ready상태의 프로세스들 중 하나가 CPU를 차지
  5. 1번과 4번 상태 - CPU를 차지하던 프로세스가 자발적으로 없어짐 -> nonpreemptive(비선점형)
  6. 2번과 3번 상태 - 실행중이던 프로세스가 다 끝나지 않고 ready로 가거나 waiting에 있다가 ready로 가서 스케줄링이 발생할 수 있음 -> 동작하고 있던 프로세스를 강제로 멈추고 스케줄링 -> preemprive(선점형)
• Dispatcher
  • context switching중에 대기하는 중인 한 프로세스가 CPU를 할당할 수 있도록 해줌
  • 문맥의 교환
  • 사용자 모드로 변환
  • 프로그램을 다시 시작하기위해서 적절한 위치로 이동

1. P0가 실행중에 멈춘 후 P1이 실행되는 동안의 과정
2. P0에서 P1으로 바뀌는 동안의 시간(CPU를 사용하지 않는 지연 시간)을 dispatch latency라고 함 -> 길수록 좋지 않음

• Scheduling Criteria(기준)

• CPU의 이용률(CPU utilization) -> Max
• 단위 시간당 실행 완료된 프로세스의 개수 - 처리율(Throughput) -> Max
• 프로세스를 실행하는데 소요된 시간, 진입시간과 완료된 시간의 차이 - 반환시간, 소요시간(Turnaround time) - Min
• 대기시간(Waiting time) - ready Queue에서 대기하면서 보낸 시간 -> CPU를 사용하고 싶은데 여전히 ready queue에 있는 시간 - Min
• 하나의 작업을 요청한 후, 첫 번째 응답이 나올 때까지의 시간. 출력이 아님 - 응답 시간(Response time) - Min

• First-Come, First-Served(FCFS) Scheduling

• 들어온 순서대로 처리
• 위 스케줄링 기준 5가지 중에 보통 waiting time으로 좋은 방식인지 나쁜 방식인지를 판단

• User threads - 라이브러리에 의해 스레드 형태로 만들어지는 모든 모양
  • 실행되기 위해 라이브러리가 있어야 됨
  • 유저 모드의 스레드들은 커널 스레드와 결합하여 최종적으로는 커널 함수로 돌아감
• Kernel threads - 실제로 커널(또는 CPU)에서 처리되는 스레드
• user 모드에서 라이브러리에 의해 스레드처럼 만들고 돌아가는 형태로 코딩 -> 관리할 여러 모델이 생김 -> 함수 하나에서 스레드들이 떨어짐 + 커널 스레드와 만나서 처리됨
• 동시에 여러 스레드를 동작시킴

• Many-to-One : 유저 모드의 많은 스레드들이 하나의 커널 스레드와 결합  

• One-to-One : 하나의 유저 스레드와 하나의 커널 스레드가 결합

• Many-to-Many : 하나 이상의 유저 스레드가 역시 하나 이상의 커널 스레드와 결합

• Two-level : Many-to-Many와 One-to-One이 함께 있음

• 스레드 라이브러리

• 스레드를 만드는 방법
  1. pthread(POSIX) : 운영체제의 표준안을 만들어 놓고 이 표준안에 따라 각 회사들이 운영체제를 만듦
  2. windows에서 사용하는 windows set
• 스레드를 사용하는 방법 - 예제

1. pthread 방식

1. 전역 변수 선언
2. void * 는 어떤 타입인지 모른다는 뜻 -> 함수에서 void * 를 사용하면 return 값을 사용하지 않는다는 의미(주소를 가짐)
3. arg를 입력 변수로 받음
4. printf 5번 반복한 후 pthread_exit(0)로 스레드를 끝냄
5. pthread_t라는 구조체를 3개 선언
6. pthread_create로 pthread를 만듦 -> pthread.h의 라이브러리 함수
7. 첫 번째 인자는 리턴되는 스레드 번호, 세 번째는 Thread라는 함수를 스레드로 만들겠다는 의미, 마지막 값은 이 함수에 넣을 인자를 의미
8. Thread라는 함수를 독립적으로 떼어내어 이 프로세스 내에서 메인 함수와 독립적으로 실행시킴 -> for문으로 같은 스레드를 3개 만들어냄
9. printf를 하면 입출력이 생기므로 스케줄링이 발생하고 스레드 사이에 순서가 바뀔 수는 있음
10. 결과는 printf가 main문에서 3개, Thread에서 15개, 총 18개가 출력

2. windows 방식

1. windows.h에서 윈도우의 함수들을 사용
2. ThreadFunc를 선언
3. 구조체 선언
4. 주소를 넘겨주므로 내가 원하는 값으로 바꿔서 사용이 가능
5. Sleep은 스케줄링을 요청한다는 의미 -> 잠깐 쉬는 동안 다른 순서의 일을 처리하라는 의미
6. 10번 반복 -> 반복할 때마다 다른 스레드에 기회를 줌
7. CreateThread로 스레드를 만듦

• Multithreaded Server Architecture

• 사용자의 요청에 대한 응답을 만들고 그 응답을 다시 보내주는 것
• 주소를 입력하여 서버에 접속 -> 불특정 다수
• 주소를 입력하면 그 주소에서 생성된 페이지가 가지고 있는 정보를 전달
• 결과를 만들어내고 요청한 결과를 요청한 곳으로 보내줌
• 하는 일이 같기 때문에 프로세스가 하나뿐일 수도 있음
• 프로세스를 만드는 것보다 스레드를 만드는 것이 더 효율적

• 멀티 타스킹

• 위의 경우 점원이 한 사람씩 일괄적으로 처리함 - 1번 손님은 10만큼의 시간이 2번 손님은 5의 시간이 들고 마지막 손님은 1의 시간밖에 들지 않지만 앞의 손님들의 긴 시간들을 모두 기다려야 함
  1. 1번 손님은 대기 없이 바로 10만큼의 처리시간이 걸림 : 10
  2. 2번 손님은 10만큼 대기한 후 5만큼의 처리시간이 걸림 : 15
  3. 3번 손님은 15만큼 대기한 후 2만큼의 처리시간이 걸림 : 17
  4. 4번 손님은 17만큼 대기한 후 8만큼의 처리시간이 걸림 : 25
  5. 5번 손님은 25만큼 대기한 후 1만큼의 처리시간이 걸림 : 26
  6. 모두 더하면 총 93
• 아래의 경우 점원과 손님의 수가 같으나 계산대가 5개 -> 한 번에 한 개씩만 계산 가능 점원이 돌아다니면서 계산 -> 한 사람당 처리할 시간을 1로 정한다면 1번 ~ 5번 손님을 각각 1씩 처리해주면 5번 손님은 위의 경우보다 조금 대기할 수 있음
  1. 5번 손님 : 4명의 손님이 각각 1씩 처리되는 것을 기다린 후 자신은 작업이 끝나므로 5
  2. 3번 손님 : 8
  3. 2번 손님 : 17
  4. 4번 손님 : 24
  5. 1번 손님 : 26 -> 위의 경우에 비해서 1번 손님은 손해를 보게 됨
  6. 그렇지만 총합은 80  
  7. 이 계산은 종업원이 움직이고 일을 처리하는 시간은 제외함

• 손님의 줄이 thread, 각각의 손님이 task, 점원이 CPU
• 정렬되어 있으면 1열로 처리해도 빠르게 처리할 수 있음
• 아래처럼 나눠서 하는 것이 일반적으로 좋음(time sharing)

• Threads

• CPU를 차지하는 실행 단위
• 스레드를 만들지 않으면 프로세스 하나가 스레드가 됨 - 중량 프로세스(heavyweight process) -> 프로세스 스위칭이 일어남
• 프로세스를 스레드로 나누어서 처리하는 것이 경량 프로세스(LWP; lightweight process) -> 스레드의 콘텍스트 스위칭이 일어남
• single and multithreaded processes

1. 함수는 부르는 대로 하나씩 실행되는데 스레드는 알아서 돌아감 -> 무조건 함수가 스레드가 되는 것은 아님
2. 전역 변수나 파일, 코드 등은 공유하고 레지스터 값과 스택은 스레드마다 하나씩 가지고 있음
3. 스레드끼리 교환하는 경우 훨씬 가벼워져서 효율이 좋아짐

• 스레드를 사용하면 좋은 점
  1. 응답성
  2. 자원 공유
  3. 경제성
  4. 확장성

• Multicore Programming

• 각 코어에 프로세스나 스레드를 어떻게 할당할 것인지, 너무 한쪽에 치우치진 않을지, 데이터의 독립성 등등을 생각해야 함
• Parallelism : 하나 이상의 task를 동시에 수행할 수 있다. - 병렬 처리

• Concurrency : 여러 개의 task가 한 번에 하나씩 번갈아가며 수행된다.

• Amdahl's Law

• 전체 작업 중 S%의 부분이 Serial 한 부분, 나머지 부분은 parallel 한 부분
• N배의 성능이 1-S의 부분에 적용됨
• 따라서 그 성능을 나타낸 공식이 위와 같음
• 스피드가 몇 배 빨라졌는지 나타냄
• 그래프

1. 100% 병렬로 한 것이 이론적으로 가장 좋음 -> 불가능
2. 최대는 없으니 그래프와 같이 나누어서 생각해보면
3. 50% 병렬화를 하면 2배를 넘지 못하고 90%는 5배, 95%는 8배를 넘지 못함 -> Core를 늘린 것

• 좀 더 확장해보면

1. core 수를 무한대로 보내보면 어느 한 값에 수렴하는 것을 볼 수 있음
2. 따라서 병렬화를 하여 코어수를 아무리 늘려봐야 95% 병렬화를 한다고 하더라도 20배를 넘지 못함

• Process Creation

• 생성중인 프로세스를 부모 프로세스, 생성된 프로세스를 자식 프로세스라 한다.
• 이런 새로운 프로세스 각각은 다른 프로세스들을 생성할 수 있다.
• 프로세스는 실행 도중에 프로세스 생성 호출을 통하여 여러 개의 새로운 프로세스들을 생성할 수 있다.
• 자원의 공유(Resource sharing) 방법
  1. 모든 자원을 공유하는 경우
  2. 자식 프로세스가 부모의 자원을 일부 공유하는 경우
  3. 공유하지 않는 경우
• 프로세스가 새로운 프로세스를 생성할 때
  1. 부모와 자식은 동시에 실행
  2. 부모가 자식이 끝날 때까지 기다림

• A Tree of Processes in Linux

• 부모 -> 자식(부모) -> 자식... 이렇게 트리 형태로 연결되어 있음
• ex) 로그인을 하는 경우 자식 프로세스를 만들어서 실행

• C Program Forking Separate Process

1. fork를 만나면 하나를 복사
2. 둘 중 하나를 부모, 자식으로 만듦
3. 둘 중 하나에는 pid에 0을, 다른 하나에는 0과 다른 어떤 값을 주는데 이 값이 0보다 작으면 error
4. pid가 0인 것은 자식, 0이 아닌 것은 부모
5. 따라서 서로 조건문에 걸려서 다른 기능을 수행

• 부모가 자식을 만들어서 자식이 exec()로 작업을 수행할 때, 부모 프로세스는 보통 자식 프로세스가 끝날 때까지 대기함
• 부모 프로세스는 wait() 하지 않고도 끝낼 수 있는데 이러한 경우 자식 프로세스가 끝나지 않았다면 exit()를 받기 전까지 유령 프로세스로 남아있음
• windows의 경우는 LINUX와 다름 -> 좀 더 복잡하고 함수 이름이 길다

• Process Termination
  • 마지막 문장을 끝내고 나면 exit()를 실행 -> 부모 프로세스는 이를 기다림 - wait()
  • 부모 프로세스가 종료되면 자식 프로세스가 계속 실행하지 못하도록(허용 x) 하는 것이 원칙
  • 모든 프로세스는 밑에서 같이 끝나게 됨 - cascading termination
• 프로세스들의 커뮤니케이션

• 협업하지 않는 프로세스들은 독립 프로세스(Independent process), 협업을 하도록 만든 프로세스들을 협력 프로세스(Cooperating process)라고 함 -> 만들기 나름
• 협업을 하게 된다면?
  1. 정보를 공유
  2. 프로세스의 연산속도가 상대적으로 증가
  3. 모듈성이 높아짐 -> 가격이 저렴해짐
  4. 편리함, 안정성 up
• 커뮤니케이션 모델

1. 신호(메시지)를 주고 받는 방식
   • 약속된 큐(queue)에 데이터를 집어넣고 가져가는 방식
2. 메모리를 공유하는 방식
   • 두 프로세스 사이에 두 프로세스만 접근할 수 있는 공유 메모리를 가짐

• Shared memory : Producer-Consumer model

• 왼쪽은 생산자, 오른쪽은 소비자 -> 생산자는 데이터를 버퍼에 넣고 소비자는 뽑아내어 쓴다
• 원형 큐를 사용
• 예시

1. in과 out이 0이라는 것은 비어있다는 뜻
2. 이 말은 in과 out이 같아지면 비어있다는 의미가 되며 따라서 버퍼는 항상 1칸을 비워놔야 함

• 생산자의 알고리즘 - 데이터를 만들어서 버퍼에 저장

1. in + 1 이 out과 같아지면 리셋
2. out은 생산자와 소비자가 함께 사용하기 때문에 늘었다 줄었다 할 수 있음

• 소비자의 알고리즘 - 데이터를 뽑아감

• 서로 다른 프로세스가 같은 값을 사용하므로 협조적으로 수행할 수 있음

• Message Passing

• send로 메시지를 보내고 receive로 받음
• 교려 할 점
  1. 연결을 어떻게 해야 하는가
  2. 프로세스 두 개만 하는가 그 이상 해야 하는가
  3. 한 쌍의 프로세스 사이에는 큐가 하나만 있는가 여러 개 있는가
  4. 용량의 크기
  5. 방향은 단방향인가 양방향인가
  6. 길이는 고정인가 가변인가
• Direct 방식
  1. send(P, message) : P에게 보내겠다.
  2. receive(Q, message) : Q에게 받겠다. 받기 전까지 다른 곳에서 받지 않음
• Indirect 방식
  1. 받는 것은 메일박스(우편함)로부터 받음
  2. 접근할 수 있는 누구든지 가져갈 수 있음 - 동시에
  3. 누구에게 보낼지, 받을지가 아니라 사서함 번호를 사용한다. -> send(A-사서함 번호, message)

• 동기화

• 메시지를 주고받을 때의 동기화는 기다린다는 것
• Blocking : send후 상대가 받을 때까지 기다림 - ex) 전화를 상대가 받으면 그때부터 말을 함
• non-Blocking : 보내 놓고 다른 작업을 수행할 수 있음 - ex) 카카오톡 메시지
• 랑데부 프로토콜(rendezvous) : 보내는 쪽, 받는 쪽 모두 Blocking을 사용 -> 1:1로 연결하여 명확해짐 -> 중간에 버퍼가 필요 없음(zero capacity)
• 일반적인 것은 사서함이 필요함 - Bounded capacity -> 정해진 크기의 용량의 버퍼가 필요
• 무한대의 크기도 있을 수 있으나 이론적으로 불가능

• 프로세스 간의 통신(Communications in Client-Server Systems)

• 컴퓨터 내에서만 일어나는 것이 아니라 여러 컴퓨터끼리도 통신을 함
• 소켓(socket) 통신 : (IP주소 + 포트 번호)를 가지고 연결 -> IP주소가 일치하는 컴퓨터는 같은 포트번호를 열어놓고 있어야 주고받을 수 있음

• Process Concept

• 운영체제는 다양한 프로그램들을 실행
• 일괄처리 시스템(Batch system)은 작업(job)을 실행
• 시분할 시스템(Time-shared systems)은 사용자 프로그램이나 태스크(tasks)를 수행
• 우리가 배우는 운영체제 과목에서는 작업, 프로세스, 태스크 모두 같은 것으로 봄
• 프로세스란? - 간단하게 수행, 실행 중인 프로그램
• 실행 중이지 않은 프로그램은 저장되어 있는 프로그램 -> 보조기억장치에 저장(디스크)
• 운영체제 입장에서 프로세스는 로딩(적제)되어 메인 메모리를 차지하고 동작하고 있거나 바로 직전인 상태(수행)
• 순차적인 방식(sequential fashion) : 하나씩 정해진 순서대로 실행되어야 함
• 수행 중인 프로그램은 우리 눈에 보이는 소스 프로그램이나 소스 프로그램이 바뀐 코드 형태 자체만은 아님(부분)
• 프로세스란 단순히 프로그램 그 자체를 의미하는 것이 아니라 다음을 포함한 능동적인 실체이다.(환경까지 모두)
  1. Program counter
  2. stack
  3. data section
  4. 레지스터
  5. 프로그램 코드
  6. ex) 프로그램 코드 실행 -> 실행되는 동안 생성된 데이터들이 저장됨(스택이나 데이터 섹션) -> CPU가 가지고 있는 변화되는 값들이 레지스터에 저장 -> 많은 코드 중 어느 위치에서 실행하는지에 대한 프로그램 카운터
  7. 위의 항목에 다른 것들을 추가한 것을 프로세스 컨트롤 블록이라 한다.

• Process in Memory

• text : 코드와 상수 값들이 들어감, 프로그램이 실행되면 정해진 만큼만 가질 수 있음
• stack, heap : 변화되는 공간
• stack은 높은 번지에서 낮은 번지로 내려오고 heap은 낮은 번지에서 높은 번지로 올라감
• 그렇게 되면 파란색 공간이 버퍼링 공간이 되어 stack과 heap 둘 다 될 수 있음
• overflow도 될 수 있음

• Memory Layout of a C Program(C프로그램에서는 메모리에 어떻게 배치되고 설정이 되고 동작이 되는지)

• x값과 y값이 data에 저장됨
• 메인 함수 안에 변수 2개는 지역변수, stack에 저장
• value에 int형태로 메모리를 할당
• 처음 실행파일을 실행할 때, 메인에 값을 줌(커멘드 창에서)
• 비주얼 스튜디오에서 환경변수를 주는 설정을 사용하여 줄 수도 있음
• argc는 입력하는 값들의 수, argv는 입력한 값들을 순차적으로 저장
• 전역 변수는 data영역으로 - 시스템마다 다를 수 있지만 여기서는 분리되어 저장됨, 0으로 초기화되어 저장될 수도 있음 -> 어떤 환경인지 체크하여 방식을 달리 함
• main함수의 argment들은 가장 위에 저장
• 로컬 변수(지역 변수)는 stack영역으로 - 어떤 시스템도 초기화하지 않는 변수
• value는 포인터이기 때문에 가리키는 주소는 stack에, 할당한 20바이트는 heap영역에 저장된다.
• 예제

1. rose라는 텍스트 자체는 텍스트에 저장되고 읽기만 할 수 있음
2. a안에 r, o, s, e값이 각각 하나씩 배열로 저장되고 마지막에 NULL값이 저장 총 5개(가변 x)
3. p는 지역 변수에 포인터 stack에 저장-> grace라는 값을 가리킴(text에 저장되어 있음)
4. b []도 지역 변수이지만 포인터가 아닌 배열. 역시 stack에 저장(stack에 text값 복사)
5. 따라서 b의 값은 stack에서 얼마든지 바꿀 수 있지만, p의 값은 바꿀 수 없다.

• Process state

• 프로세스는 실행되면서 자신의 상태가 계속 변하게 됨
• new : 모든 프로세스는 만들어지는 과정이 필요. 만들어진 후의 상태
• running : CPU를 차지하고 있는 상태. 동작중인 상태
• waiting : 기다리는 상태. CPU를 차지하기 위한 것이 아니라 외부 입출력(I/O)을 기다리는 상태. 따라서 CPU를 사용하지 않음
• ready : 동작하려 하고 있으나 아직 CPU를 차지하지 않은 상태. 기다림
• terminated : 프로세스가 모드 끝난 상태
• 프로세스가 생성된 후 실행되기 전까지 ready -> CPU를 차지하고 running -> 실행이 끝났으면 terminated -> I/O를 기다려야 한다면 waiting -> 적당한 시간을 두어 끝나지 않는다면 다시 ready로 돌아가 다른 프로세스와 CPU를 차지하기 위해 경쟁하며 끝날 때까지 반복됨

• Process Control Block(PCB)

• 각 프로세스는 운영체제에서 프로세스 제어 블록(PCB)에 의해 표현된다.
• 프로세스의 컨텍스트가 만들어지고 그것들 끼리의 교환이 이루어짐
  1. 프로세스 상태(Process state) : 생성, 준비, 수행, 대기, 정지 상태
  2. 프로그램 카운터(Program counter) : 다음에 실행될 명령어의 주소
  3. CPU 레지스터(CPU registers) : CPU 레지스터는 컴퓨터 구조에 따라 다양한 수와 형태를 갖는다.(다른 작업으로 넘어가기 전에 모든 상태를 저장)
  4. CPU 스케줄링 정보(CPU scheduling information) : 프로세스 운선 순위, 스케줄 큐의 포인터와 다른 스케줄 매게 변수들을 포함
  5. 메모리 관리 정보(Memory-management information) : 기준과 한계 레지스터의 값, 운영체제가 사용하는 기억장치 시스템의 페이지 테이블 또는 세그먼트 테이블의 정보를 포함
  6. 계정 정보(Accounting information) : CPU가 사용된 실시간의 양, 시간 범위, 계정 번호, 작업 또는 프로세스 번호를 포함
  7. 입출력 상태 정보(I/O status information) : 입출력 요구들, 입출력 장치들과 open된 파일의 목록 등을 포함
• 이 PCB는 프로세스와 프로세스간의 스위칭에 이용된다.
• CPU Switch From Process to Process

1. 2개의 프로세스(P0, P1)이 있는데, P0가 실행되는 중에 P1으로 바뀌는 경우의 그림
2. P1이 실행된 후 다시 P0로 돌아가서 실행
3. 화살표는 실행된다는 의미, 나머지 검은 선은 쉬고있다는 의미
4. 상태를 저장하지 않는다면 다시 돌아왔을때, 중간부터 실행하지 못함 -> PCB에 상태 저장
5. P1의 상태를 불러와서 program counter의 위치부터 실행
6. P1에게 주어진 시간이 다 되었거나 모든 실행이 끝났다면 다시 현재 상태를 PCB에 저장한 후 P0의 상태를 불러옴
7. 저장하는 시간과 불러오는 시간이 있으므로 딜레이가 생길 수 있음 -> 이 때는 어느 프로세스도 실행하지 못함
8. 번갈아서 실행이 되지만 동시에 실행되는 것처럼 보임 -> iIde시간과 스위칭하는 시간을 줄이는 것이 좋음
9. 이를 context switching이라고 부른다.

• Threads

• 프로세스를 이루고 있는 실행단위
• 하나의 프로세스안에 여러 쓰레드를 둘 수 있음

• Process Representation in Linux

• Process Scheduling

• 프로세스들의 우선순위를 정해서 CPU를 차지 할 수 있도록 하는 것
• 가장 기본적인 방법인 queue를 사용
  1. ready queue : CPU를 차지하기 위해 대기하고 있는 프로세스들
  2. wait queues : I/O장치를 쓰기위해 대기하고 있는 프로세스들
  3. Device queues : 디바이스들을 기다리고 있는 각각의 프로세스들
• Ready and wait Queues

1. 처음에는 head만 있음
2. queue라고 해서 순서가 있는 것이 아님
3. 모여있는 것들 중 하나를 스케줄링해서 필요한 것을 CPU에 할당

• Representation of Process Scheduling한 프로세스가 CPU를 차지하고 돌아가는 과정

1. ready queue에서 CPU를 할당받아 실행됨
2. 실행이 끝났다면 그냥 종료하면 되지만 끝나지 않고 시간이 만료됐다면 다시 ready상태로 돌아가 우선순위를 스케줄링 -> I/O 요청, 시간 만료, 자식프로세스 fork, 인터럽트를 받아 대기 등

• Schedulers

• 단기 스케줄러 : 실행 준비가 되어 있는 프로세스들 중에 하나를 선택하여 CPU에 할당(ready queue)
• 장기 스케줄러 : 프로세스를 선택하여 실행하기 위해 기억장치로 적재
  1. new로 만들어지면 ready queue로 가서 단기 스케줄러에 의해 CPU를 할당받음
  2. 이 범위를 넘어가는 시스템이 존재 -> 서버 : 사용자 요청이 오면 프로세스를 각자 생성하기 때문에 사용자의 수가 많을 수록 엄청난 양의 프로세스가 생성됨
  3. 단기 스케줄러로 많은 양을 처리하기에 부담
  4. ready queue로 갈지 말지 판단해주는 역할 -> ready queue에 부담이 가지 않도록 관리
• 장기 스케줄러는 단기 스케줄러가 효율적으로 작동할 수 있도록 도와줌
• Addition of Medium Term Scheduling(장기와 단기의 중간)

1. time sharing 시스템을 가지는 일부 운영체제들은 medium term scheduler를 가짐
2. 장기 스케줄러는 가지지 않고 단기 스케줄러만 가짐
3. 프로세스가 많아지는 경우 임시로 우선순위가 떨어지거나 자주 사용하지 않거나 접근한 시간이 없는 프로세스들을 외부로 보냄(swap out)
4. 밖에서 실행되도록 함
5. swap in : 밖에서 실행되는 프로세스를 다시 불러오는 것

• Context Switch(문맥 - 프로세스가 진행되는 흐름)

• 프로세스의 흐름을 멈춘 후 다른 프로세스를 실행 했다면 다시 원래 상태로 돌아왔을 때, 실행됐던 흐름부터 시작할 수 있도록 해줌

• Multitasking in Mobile Systems

• 대부분의 스마트폰은 한번에 한 화면만 나옴 -> 나머지는 뒤에
• 저장장치도 작기때문에 한 순간에 최상위 하나만 실행