CS/OS

[OS] Scheduling #3

Scheduling [하루OS] Day-6 Scheduling 어제에 이어서 Scheduling을 좀 더 알아보자 지난번 정리 SJF는 turnaround time을 최적화하는데 유용한 방법이다. RR은 빈번한 context switching을 통해서 response time을 줄이는데 최적화된 방법이.. hyeo-noo.tistory.com Starvation 짧은 수행 시간을 가진 interactive job이 너무 많아진다면 우선순위가 낮은 queue에 배치된 작업은 작업(오래 걸리는 작업)은 수행할 수 없게 된다. Game the scheduler 만약 time slice의 99%를 I/O 작업이 가져가 버린다면 오래걸리는 job들은 오히려 CPU를 거의 사용하지 못하게 될 수도 있다. 프로그램의..

[OS] Scheduling #2

Scheduling 이어서 Scheduling을 좀 더 알아보자 지난번 정리 SJF는 turnaround time을 최적화하는데 유용한 방법이다. RR은 빈번한 context switching을 통해서 response time을 줄이는데 최적화된 방법이다. 사용하는 프로그램마다 제각기 다른 특성을 가지고 있다. 한 번에 끝내는게 효율이 좋거나, 여러 번 나눠서 끝내는 게 좋거나 등등 스케줄러가 프로그램의 특성을 파악하고 그에 따라 더 나은 결정을 할 수 있다면 얼마나 좋을까 MLFQ (Multi-Level Feedback Queue) MLFQ는 여러개의 구별된 queue로 구성되고 각각 다른 우선순위를 가진다. 규칙 1 : A의 우선순위 > B의 우선순위 , A를 실행한다. 규칙 2 : A의 우선순위 =..

[OS] Scheduling #1

Scheduling 지금까지 프로세스와 스레드에 대해 알아보았다. 오늘 내일은 프로세스의 CPU Scheduling에 대해서 알아보자 CPU Scheduling은 크게 2가지로 나뉜다 비선점형 스케줄링(Non-preemptive scheduling)과 선점형 스케줄링(Preemptive scheduling) 비선점형 스케줄링 - CPU가 프로세스를 실행하고 있다면 실행중인 프로세스가 종료되거나 스스로 CPU를 양보하기 전까지 다른 프로세스는 CPU는 사용할 수 없다. - 프로세스들 간의 협력이 중요하다. 선점형 스케줄링 - 사실상 모든 현대 스케줄러가 선점형이다 - 다른 프로세스가 CPU를 사용하고 있어도 강제로 프로세스를 쫓아내고 자신이 CPU를 사용할 수 있다. 스케줄링 알고리즘의 성능을 판단하는 척..

[OS] Thread #1

Thread 스레드가 뭘까? 왜 있는걸까? 싱글 프로세스는 멀티코어 CPU의 장점을 활용할 수가 없다. 새로운 프로세스를 만드는데는 많은 자원이 필요하다. (시간, 메모리 공간) 프로세스간의 통신 오버헤드가 크게 발생한다. 프로세스간에 context swiching 비용이 크다. 위와 같은 프로세스의 단점을 보완하기 위해서 스레드가 탄생했다. 하나의 프로세스는 여러개의 스레드를 가질 수 있다. 프로세스는 각자의 고유 메모리를 가지고 있기 때문에 프로세스 내부의 스레드들은 하나의 메모리 공간을 공유한다. 그리고 스레드는 각자의 program counter와 stack pointer를 가진다. 위 사진처럼 스레드가 많아질 수록 프로세스의 메모리 공간이 각각의 stack공간으로 채워짐을 알 수 있다. 그리고 ..

[OS] Process #3 (Context Switching)

Process의 context switching 우리는 컴퓨터가 다양한 프로그램을 동시에 실행시켜주는 것처럼 느낀다. 엄밀히 따지면 동시 실행이 아니다. CPU가 매우 빠른 속도로 프로세스들을 context switching을 시켜주는데 우리는 이 switching 순간을 절대로 느낄 수 없다. Context란? 프로세스가 수행되기 위해서 필요한 정보들이라고 이해하면 된다. Context는 주로 커널 내부에 존재하는 PCB(Process Control Block)에 저장되어 있다. (PCB는 linked list로 구성됨) 우리가 프로그램을 구동시키기 위해서는 프로세스를 생성해야 한다. 프로세스가 생성되면서 해당 프로세스만의 메모리 공간을 할당 받고 code, stack, heap, BSS 공간에 적절한..

[OS] Process #2

Process 프로세스의 상태 전이 표 프로세스는 Ready 상태일때 CPU를 할당받고 Running 상태로 상태전이가 일어난다. 이제 해당 프로세스는 CPU를 이용해 작업을 수행한다. 작업을 마치면 CPU를 반납하고 종료합니다. 만약 작업이 끝나지 않는경우 프로세스는 CPU를 반납하고 ready 상태로 다시 돌아간다. 만약 I/O 작업이 발생한다면 현재 CPU를 사용중인 프로세스는 Block 상태로 전이가 일어난다. I/O작업이 완료되면 해당 프로세스를 ready상태로 전이 시킨다. 작업이 종료되지 않았는데 CPU를 어떻게 반납을 할까? OS는 프로세스의 CPU독점을 방지하기 위해서 하드웨어로 구현된 timer interrupt를 발생시켜 프로세스가 특정 시간 간격동안만 실행할 수 있도록 한다. tim..

[OS] Process #1

Process 프로세스? 실행중인 프로그램을 프로세스 라고 한다. 프로그램은 생명이 없다. 하지만 프로그램이 실행이 되면 프로세스가 되고 프로세스는 프로그램이 종료될 때까지 생명활동을 이어간다. 프로그램이 실행이 되면 아래 그림과 같이 disk의 프로그램 정보가 memory로 load 된다. 프로그램에 속한 모든 정보가 memory로 load되는것은 아니다. OS는 프로그램 실행 도중 필요한 코드를 그때그때 load해서 사용한다. memory 공간은 Code, Data, BSS, Heap, void, Stack 공간으로 구성된다. Code : 프로그램 코드가 올라오는 부분 Data : 초기화된 전역 변수, static 변수 BSS : 초기화되지 않은 전역 변수, static 변수 Heap : malloc..

[운영체제] Semaphore

운영체제의 병행성 기법 중 하나인 Semaphore에 대해서 알아보자 Semaphore는 정수 값을 가지는 객체라고 생각하면 된다. Sem_wait(), Sem_post()같이 Semaphore의 값을 조절하는 함수를 가지고 있다. 첫 번째 인자는 Semaphore객체, 두 번째 인자는 여러 개의 쓰레드에 의해서 공유되고 있다는 것을 의미, 세 번째 인자는 Semaphore값을 1로 초기화 하겠다는 뜻이다. Semaphore의 2가지 동작에 대해서 알아보자 sem_wait() Semaphore값을 1 감소시킨다. 값이 0 이상이라면 즉시 return 한다. 값이 음수가 된다면 wait상태에 들어가고, sem_post()가 호출될 때까지 wait 한다. 여러 개의 쓰레드가 sem_wait()을 호출한다면 ..

[운영체제] Locks #3

[운영체제] Locks #2 [운영체제] Locks #1 Lock에 대해서 알아보자 Lock이 필요한 이유 2개 이상의 tread가 동시에 공유 자원에 접근할 경우 race condition(병행성 문제)이 발생해서 결과를 예측할 수 없다. 따라서 공유 자원에 hyeo-noo.tistory.com 지금까지의 방법들은 매우 비효율적이다. 왜냐하면 lock을 얻기위해서 spin-wait를 하게되는데, 이러한 방식은 CPU를 불필요하게 계속 소모해서 다른 활동을 하지 못하기 때문이다. 따라서 위 문제를 해결할 수 있는 방법들을 알아보자 Just Yield 가장 간단한 구현 방법이다. 만약 lock이 사용중이라면 깔끔하게 CPU를 반납하고 다음 time-slice에 자신의 차례가 올 때까지 기다리는 방법이다. ..

[운영체제] Locks #2

[운영체제] Locks #1 Lock에 대해서 알아보자 Lock이 필요한 이유 2개 이상의 tread가 동시에 공유 자원에 접근할 경우 race condition(병행성 문제)이 발생해서 결과를 예측할 수 없다. 따라서 공유 자원에 대한 동기화 메커 hyeo-noo.tistory.com 하드웨어적으로 lock 변수를 관리하는 instruction에 대해서 알아보자 CPU에서 제공하는 Atomic Instruction을 알아보자 Test and Set test-and-set을 사용한 Spin lock 사용 예 기존의 TestAndSet을 알기 전에는 flag 값이 0인지 확인하기 + flag 값을 1로 바꾸기와 같은 총 2가지 동작으로 나뉘어서 수행을 했다. 그래서 2가지 동작 사이에 context swi..