일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- BFS
- java #자바
- 백준 #알고리즘 #파이썬 #코딩테스트
- 파이썬 #백준 #알고리즘 #코딩테스트
- 투포인터
- java #자바 #생활코딩
- react #리액트 #동빈나
- css #웹 #생활코딩
- 프로그래머스
- 다익스트라
- java #자바 #동빈나
- PYTHON
- 파이썬
- DFS
- Dijkstra
- 프로그래머스 #파이썬 #알고리즘 #코딩테스트
- 코딩테스트
- 자바 #java
- css #생활코딩 #웹
- 파이썬 #알고리즘 #코딩테스트 #프로그래머스
- java #자바 #나동빈
- 프로그래머스 #파이썬 #코딩테스트 #알고리즘
- 백트랙킹
- 백준
- 알고리즘
- 다이나믹프로그래밍
- 재귀
- dp
- 백준 #파이썬 #알고리즘 #코딩테스트
- react #리액트 #동빈나 #나동빈 #유튜브강의
Archives
- Today
- Total
커리까지
[운영체제] 11. CPU Scheduling 2 / Process Synchronization 1 본문
728x90
SMALL
- round robin이 좋은 점은 전에 작업하고 있던 부분을 세이브해줌
Multilevel Queue
- Ready queue를 여러 개로 분할
- foregorund(interactive)
- background(batch - no human interaction)
- 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground - RR
- 사람과 응답하는 것이니
- background - FCFS
- batch잡이니 fcfs가 더 효울적임
- foreground - RR
- 큐에 대한 스케줄링이 필요
- Fixed priority scheduling
- serve all from foreground then from background
- Possibility of starvation
- Time slice
- 각 큐에 CPU time을 적절한 비율로 할당
- Eg., 80% ro foreground in RR, 20% to background in FCFS
- Fixed priority scheduling
Multilevel Queue
- 줄마다 우선순위 존재
- 밑으로 갈수록 우선순위가 낮음
- 태어난 프로세스가 어떤 형식인지에 따라 우선순위가 정해짐
- 변하지 않음
- 프로세스를 어느줄에 넣을 것이냐
Multilevel Feedback Queue
약간 우선 순위가 낮은 프로세스라도 올라갈 수 있음
여러 줄로 줄서기해서 때에 따라 계급 이동 가능
프로세스가 다른 큐로 이동 가능
에이징(aging)을 이와 같은 방식으로 구현할 수 있음
Multilevel-feedback-queue-scheduler를 정의하는 파라미터들
- Queue의 수
- 각 큐의 scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫒는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
cpu 버스트가 짧으면 바로 빠져나갈 수 있지만 길면 아래 큐로 이동해서 할당시간을 더 받을 수 있음
cpu 버스트 시간이 짧은 프로세스에게 우선 순위를 더 많이 주고 긴 프로세스는 밑으로 내려가게 함
짧은 시간에 먼저 배정하기 때문에 예측 할 필요 없음
Example of Multilevel Feedback Queue
- Three queues:
- Q0 - time quantum 8 milliseconds
- Q1 - time quantum 16 milliseconds
- Q2 - FCFS
- Scheduling
- new job이 queue Q0로 들어감
- CPU를 잡아서 할당 시간 8 milliseconds 동안 수행됨
- 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려감
- Q1에 줄서서 기다렸다가 CPU를 잡아서 16ms 동안 수행됨
- 16ms에 끝내지 못한 경우 queue Q2로 쫓겨남
Multiple-Processor Scheduling
- CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
- 골고루 일해야 성능이 좋아짐
- Homogeneous processor인 경우
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
- ex) 이발하러 갔는데 전담 선생이 있는 경우
- Load sharing
- 일부 프로세서에 job에 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
- Symmetric Multiprocessing (SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
- 모든 cpu들이 대등한 것
- Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
- 여러개의 cpu중 하나가 전체적인 컨트롤 타워 역할
Real-Time scheduling
주기적으로 실행되도록 하거나 데드라인이 정해져있음
Hard real-time systems
- 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
Soft real-time computing
- 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
- 데드라인을 보장하지는 않음
Thread scheduling
- Local Scheduling
- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
- 운영체제가 thread의 존재를 모름
- 사용자 프로세스가 직접
- Global scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
- 운영체제가 알기에
Algorithm Evaluation
- Queueing models
- 굉장히 이론적임
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
- 예전에는 많이 썼지만 요즘에는 덜 씀
- Implementation(구현) & Measurement (성능 측정)
- 실제 시스템에 알고리즘을 주현하여 실제 작업(workload)에 대해서 성능을 측정 비교
- Simulation(모의 실험)
- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
- 구현과 성능측정이 어려우면 이 방법을 사용
- trace
- 측정에 사용되는 input 값
Process Synchronization
데이터의 접근
- 데이터를 읽어와서 수정하고 저장하는 경우 문제가 발생할 수 있음
Race Condition
- 서로 초록 박스를 가져가서 더하거나 빼고 싶어함
- 여러 주체가 하나의 데이터에 접근하는게 경쟁상태가 됨
- 이러한 것을 조율해주는게 필요함
- 멀티 프로세서에서는 문제가 생길 수 있음
- 더 중요한 문제는 커널과 관련된 문제들
- 커널의 코드가 실행되면서 커널에 접근하면 문제 발생 할 수 있음
- 연산을 수행하는 cpu가 메모리에 저장
OS에서 race condition은 언제 발생하는가?
- kernel 수행 중 인터럽트 발생 시
- Process가 system call을 하여 kernal mode로 수행 중인데 context switch가 일어나는 경우
- Multiprocessor에서 shared memory내의 kernal data
OS에서의 race condition(1/3) interrupt handler v.s kernel
- 커널이 cpu에서 실행하고 있음
- count를 증가시키고 있었음
- 인터럽트가 들어오면 인터럽트 루틴으로 넘어감
- 인터럽트 핸들러가 처리되는 도중에 count-- 가능
- 커널 데이터를 양쪽에서 건드리면 하나만 저장됨
- 중요 변수를 인터럽트가 들어오면 작업이 끝날 때 까지 인터럽트를 처리하지 않고 먼저 작업이 끝나야 인터럽트를 수행함
- 즉, 순서를 정해주면 됨
- 이걸 어떤 식으로 처리하는게 효율적인지 판단해서
OS에서의 race condition(1/3) Preempt a process running in kernal?
If you preempt CPU while in kernel mode...
- A라는 프로그램이 cpu를 잡고 있다가 끝나고 b가 끝나면 a로 넘어옴
- a가 시스템 콜을 해서 커널을 실행중이고 1을 증가시키고 있는 도중이었는데 할당 시간이 끝나서 b로 넘어감
- b도 하다가 할당 시간이 끝나서 a로 넘어감
- 아까 하던거 이어서 함
- 밑에서 증가한거는 반영안 됨
- 증가시키기 전의 값이 b가 끝난 후 a로 실행할 때 불러와지기 때문에
- 커널 모드가 끝나고 user모드를 빠져나갈 때 b로 넘어감
OS에서의 race condition(3/3) multiprocessor
- 앞에서 설명한 것들로는 해결이 안됨
- 인터럽트로 막아서 해결이 안 됨
- 작업주체가 여럿이기 때문에 문제가 생김
- 데이터에 접근할 때 lock를 걸어야 함
- 다른 누구도 접근 못하게
- 작업이 끝나고 락을 품
- 커널 접근 하는 cpu를 하나로 접근하도록
- 비효율적
- 각각 데이터 락을 걸로 풀고 하는게 더 효율적
Process Synchronization 문제
- 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있음
- 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘 필요
- Race condition
- 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
- race condition을 막기 위해서는 concurrent process는 동기화되어야 함
Example of a Race Condition
- 단순히 p1에서 p2로 넘어갈때는 큰 문제가 발생하지 않음
- 서로 같은 공유데이터에 접근하는게 문제임
The Critical-Section Problem
- n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
- 각 프로세스의 code segment에는 공유 데이터르 접근하는 코드린 critical section이 존재
- Problem
- 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 함
- 공유데이터 접근에서 자유로울 때 공유데이터에 접근할 수 있어야 함
- 기다려야 함
728x90
LIST
'KOCW' 카테고리의 다른 글
[kocw] 01. 자료구조소개1 (0) | 2021.09.23 |
---|---|
[운영체제] 12. Process Synchronization 1 (0) | 2021.07.23 |
[운영체제] 10. CPU Scheduling 1 (0) | 2021.06.23 |
[운영체제] 9. Process Management 2 (0) | 2021.06.18 |
[운영체제] 8. Process Management 1 (0) | 2021.06.16 |
Comments