04-2.Processes and Threads - Process Scheduling

이 글은 서울대학교 평생교육원 열린강좌 중, 홍성수 교수님의 운영체제 강의 및 pt자료를 정리한 내용임을 알려드립니다. 
서울대학교 평생교육원 열린강좌 - 운영체제 (홍성수 교수님)

Process and Threads

Agenda

1. Process Concepts
2. Process Scheduling
3. Context Switching
4. Process Creation and Termination
5. MultiThreading
6. Conclusion 

2. Process Scheduling

Process Scheduling

• Goal

  • For several processes to shrare a CPU,
  • OS must select a process to run next.

• Constraints - 만족해야하는 제약 조건

  • OS must have
    
    • Fair scheduling ( fair는 상대적인 개념 )
      
      • Make sure each process gets a chance to run.
    • Protection
      
      • Making sure processes don’t trash each other.

---

Scheduler Design principle

• Process scheduler design by system design principle
  
  • Separation of policy and mechanism.
    
    • Separation of scheduling policies and dispatching mechanisms.
  • Leads to two-level architecture.
  • Policy and Mechanism ( 2가지로 나뉠 수 있음. )
    
    • Policy : 어떤 process를 다음에 선택하는지에 대한 기준.
    • Mechanism : CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 방법.
      

---

Dispatcher (1)

• Inner-most portion of OS that runs processes.

1.    loop forever {
2.        run the process for a while
3.        stop it and save its state
4.        load state of another process
5.    }

• program : 수동적
• process : 능동적
• OS는 passive함.
• Dispatcher가 user process를 돌리기 위해서는 2가지가 필요한데.
  
  • User process -> OS(dispatcher) kernel
  • OS(dispatcher) kernel -> User Process
  • H/w적인 interrupt가 필요함.

---

Dispatcher (2)

• Chanllenges
  
  1. How does the dispatcher keep control?
     
     • CPU can only be doing one thing at a time.
     • User process running means that dispatcher isn’t.
  2. Which process is executed next?
     
     • Need to locate runnable processes efficiently.

---

1. Entering and Leaving the Kernel (1)

• How does the dispatcher regain control?
  
  • Trust the process to wakeup the disppatcher.
    
    • On a voluntary basis - “non-preemptive” way
    • Problem: Sometimes processes misbehave.
  • Provide the dispatcher with an alarm clock
    
    • On a compulsory basis - “preemptive” way
    • Timer hardware and interrupts.

---

1. Entering and Leaving the Kernel (2)

• Misconceptions about kernel

  • Like a user process, Kernel is an active and independent entity possessing a thread of control.
  • Kernel is continuously monitoring user processes while they are running.

• In reality,

  • Kernel is a passive entity consisting of kernel functions and interrupt service routines.
  • Kernel is like a library.

---

1. Entering and Leaving the Kernel (3)

• Kernel is a collection of functions running in kernel space
  
• System call 함수
• interrupt servie routine도 존재.

---

1. Entering and Leaving the Kernel (4)

• Kernel space(mode)
  
  • Elevated system state compared to normal user applications.
    
    • Protected memory space.
    • Full access to the hardware.
  • System state + memory space
• User space(mode)
  
  • Restricted system state compared to the kernel.
    
    • A subset of the machine’s available resources.
    • Limited privilege
      
      • Unable to perform certaion system functions
  • Restricted system state + restricted memory space.
  • 프로세스가 user mode에서 수행될 때는 user mode stack을 사용
  • kernel mode에서 수행시는 kernel mode stack을 사용함
  • kernel memory에 stack을 둔다는 의미는?
  • 2개의 다른 stack but, PID는 동일함.

---

1. Entering and Leaving the Kernel (5)

• **Execution modes in protected MMU machine
  

---

1. Entering and Leaving the Kernel (6)

• Dispatching is a kernel function after all
• Control returns to OS on
  
  • Traps : Events internal to user processes
    
    • System calls
    • Error (illegal instructions, address error, etc )
    • Page faults
  • Interrupts: Events external to user processes
    
    • Character typed at a terminal.
    • Completion of a disk transfer.
    • Timer to make sure OS eventually gets control.
  • Non-preemptive vs. Preemptive scheduling
    
    • Non-preemptive scheduling : 프로세스가 자발적으로 cpu를 양보하여 다른 프로세스를 수행하는 스케줄링.
      
      • S/W interrupt(trap)을 사용시 호출가능.
    • Preemptive scheduling : 운영체제가 cpu를 빼앗아 다른 프로세스에게 넘김
      
      • H/W interrupt에 의해 작동
      • Timer circuit을 통해 가능.

---

1.Entering and Leaving the Kernel (7)

• Mode change of process

• Q. debugger를 사용할때 가장 먼저하는 일은?
• A. program에 break point를 걸고, 프로세스 stack을 확인.
  stack의 함수 수행이력을 볼 수 있음.
  함수는 instruction of sequence의 추상화된 개체.

*Program의 수행중인 상태를 trace할때, process stack을 trace함.

• process 요소 2가지
  
  • ”state” : Context( memory, h/w, system )
  • “execution stream” (thread of control) : instruction of sequence –> runtime context

• 함수가 수행되려면 stack공간이 필요, return, 지역변수 등이 실행 주체 process stack을 사용.

  • user mode에서의 stack

• Q. linux process는 PID가 있다. kernel func수행 중 process ID는 무엇인가?

• A. kernel mode이더라도 System call을 한 프로세스이다.

---

1. Entering and Leaving the Kernel (8)

• System call vs. function call
  
  • Common properties
    
    • Transfer control to another routine.
    • Maintain the context of the process
  • Differences
    
    • Syscall incurs mode change but function call doesn’t
    • Syscall is more expensive than function call

---

2, scheduling Policy (1)

• Once dispatcher gets control, how to decide who’s next?
  
  • Possiblities
    
    • Scan process table for first runnable process:
      
      • Might spend much time searching
      • Results in weird priorities: Small PIDs better
      • Question : How do you know a process is runnable?
    • Link together the runbable processes into a queue
      
      • Dispatcher takes from the head of the queue.
      • Runnable processes are inserted at back of queue.
      • Called “ready list” or “run queue”
    • Assign priorities to processes
      
      • Keep the queue sorted by priority
      • Separate queue per priority

---

2. Scheduling Policy (2)

• Who decides priorities and how are priorities chosen?
  
  • Who?
    
    • Separate part of OS : the scheduler
  • Question: Why not by the dispatcher?
    
    • Concept: Separation of policy and mechanusm
  • How?
    
    • Subject of the next topic.