process scheduling는 실행 가능한 여러 process 중에서 하나의 process를 선택하는 역할을 한다. 여기서 CPU core 하나는 하나의 process를 실행할 수 있다.
process가 시스템에 들어가면 ready queue에 들어가서 준비 상태가 되어 CPU 코어에서 실행되기를 기다린다. 이 queue는 연결 리스트로 저장된다. ready queue 헤더에는 리스트의 첫 번째 PCB에 대한 포인터가 저장되고 각 PCB에는 ready queue 의 다음 PCB를 가리키는 포인터 필드가 포함된다.
또 만약에 process가 disk와 같은 장치에 I/O 요청을 한다고 가정하면. 장치는 processer보다 상당히 느리게 실행되므로 process는 I/O가 사용 가능할 때까지 기다려야한다. I/O 완료와 같은 특정 이벤트가 발생하기를 기다리는 process는 wait queue에 삽입된다.
Linux에서 ready, wait queue에 대한 표현
새 process는 ready queue에 놓인다. process는 실행을 위해 선택되거나 또는 dispatch될 때 까지 기다린다. process에 CPU core가 할당되고 running 상태가 되면, 아래와 같이 이벤트가 발생할 수 있다. 이때 해당 과정들은 CPU scheduler에 의해 진행되는데, CPU scheduler는 적어도 100밀리초마다 한 번씩 실행된다. (CPU core가 할당되는 프로세스가 바뀐다)
process scheduling에 대한 일반적인 표현
Linux에서는 프로세스에 대한 표현을 아래 그림과 같이 task_struct로 표현되는데, 이 구조체는 process의 상태, scheduling과 메모리 관리 정보, 열린 파일 및 부모 프로세스와 자식 프로세스의 리스트를 가리키는 포인터 등의 프로세스를 나타내기 위해 필요한 모든 정보를 가지고 있다.
Linux 커널 안에서 모든 활성 process들은 아래 그림과 같이 현재 실행중인 process를 가리키는 포인터(current)를 유지한 채로 task_struct의 이중 연결 리스트로 표현된다.
이렇게 인터럽트가 발생하면 시스템은 인터럽트 처리가 끝난 후에 context를 복구 할 수 있도록 현재 실행 중인 프로세스의 현재 context를 저장할 필요가 있다. 이러한 방법을 통해 프로세스를 중단했다 재개한다.
요약하면 저장된 context를 통해 state save와 state restore를 반복하면서 CPU core를 돌아가면서 점유하고, 이 작업을 context switch라고 한다. context switch가 진행될 동안 시스템이 아무런 일을 못 하기 때문에 이 시간은 순수한 overhead가 된다.