[운영체제] 병행제어

멀티 프로세서 스케줄링

(제약 조건이 있는 환경: CPU가 여러 개 있는 환경)

• 병렬적으로 돌아간다
• 스케줄링이 조금 더 복잡해진다
• 어떤 작업은 반드시 특정 프로세스에서 수행되어야 한다
  (화장실 한 칸 있다가 여러 칸으로 늘어난 경우, 은행창구에 직원이 여러명인데 번호표를 뽑는 것)

여러 CPU들이 있는 상황에서 여러 CPU가 균형있게 골고루 일을 하게 하는것과
잡들이 몰리지 않도록 로드 쉐어링을 해주는 것이 중요
각 CPU마다 줄을 별도로 세우는 방법
한 줄로 세워놓고 맨 앞단 비면 꺼내가는 방법

멀티프로세싱 기법 두 가지

Symmetric Multiprocessing(대칭)
CPU 들이 다 대등하게 일을 한다
각 CPU들이 알아서 일을 한다 균일한 일들을 한다
비효율적 측면 존재

Asymmetric Multiprocessing(비대칭)
한 개의 CPU가 대장 CPU(브레인)가 되어서 나머지는 그 결정에 따라서 일을 한다

리얼 타임 스케줄링

주어진 시간 안에 꼭 끝내야 하는 것

우리가 일반적으로 쓰는 컴퓨터와 운영체제는 리얼타임이 아니다

하드 리얼타임 시스템

데드라인 어기면 큰일 => 반드시 시간을 어기지 않게 미리 설계해야 한다

• 비싸고 빠른 CPU를 쓰면 CPU가 너무 놀게된다
• 싸고 느린 CPU를 사용하면 시간 어기게 된다
• 그때 그때 수행하기 전에 오프라인(도착 시간을 미리 아는 것)으로 스케줄링을 미리 해놓고 실행한다
  (워낙 데드라인 중요하기 때문에 오프라인 스케줄링)
• Ex) 자율주행, 무기체계

소프트 리얼타임 시스템

데드라인은 있지만 어겼을 때 약간의 불편만 발생
무조건 데드라인 지켜야 하는 것은 아닌 시스템

• 할 일 끝났으면 다음 초가 되기 전까지 쉼 > 그 다음 또 일 (주기적으로 일)
  Ex) 동영상 재생 (동영상 안끊기게 우선순위 높여서 CPU를 더 얻을 수 있게 한다)

SJF(짧은 프로세스가 우선순위 높은 것)는 데드라인 없었다

만약 리얼타임 스케줄링 이라면 도착시간 뒤에 데드라인이라는 조건을 포함
7초 쓰고 싶은데 데드라인이 20초 그 안에 CPU 를 6초밖에 못줬으면 데드라인 어기는 것
제대로 된게 아니다
빨리 처리하는 것보다 데드라인을 만족시키는게 중요!

스레드 스케줄링

스레드 하나의 프로세스 안에 CPU 수행 단위가 여러 개 있는 것

로컬 스케줄링 (유저 레벨 스레드)

• 스레드 존재를 모르고 사용자 프로세스 본인이 내부에 스레드 여러 개 두는 것
• CPU 스케줄러가 스레드 존재를 몰라서 지목할 수 없다
• 프로세스가 내부 스레드 중 어떤 스레드에게 CPU를 줄지 결정 해야한다

글로벌 스케줄링 (커널 레벨 스레드)

• 운영체제가 스레드의 존재를 알고 있다
• 스케줄링 할 때 스레드를 스케줄할지 직접 결정

즉, 운영체제가 스레드의 존재를 안다면 직접 스레드를 결정하고
모른다면 프로세스 내부에서 스레드를 지목한다

알고리즘을 평가할 수 있는 방법 3가지

큐잉 모델 (이론적 계산)

수식을 계산해서 성능 척도 값을 알아내는 방법

• 서버(CPU라고 생각)가 요청을 처리함에 있어 요청이 도착하면 큐에 쌓였다가 끝나면 빠져나가는 형식
• 도착하면 얼마나 빠른 빈도로 도착하느냐와 도착률이 있다
  • 확률 분포로 주어진다
  • 어떤 알고리즘이 얼마나 좋은지 계산
• 1990년대에 많이 사용했지만 최근에는 이론적인 것보다 다른 것을 더 많이 사용

구현 & 성능 측정 방법

실제로 측정해서 알아내는 측정 방법
내가 만든 알고리즘 증명한다면 >
리눅스의 공개 소스코드의 CPU 스케줄링 코드 활용하여내 알고리즘으로 바꾸고 컴파일 >
오리지널 리눅스 설치한 컴퓨터와 내 알고리즘을 심은 컴퓨터에서 프로그램을 돌려서 성능척도의 결과를 확인

시뮬레이션

어려운 구현의 대안이 되는 방법
시스템 구현하는게 아니라 가상으로 돌려보는 것

• 시뮬레이터를 만들어서 작업을 돌려서 성능 척도를 확인
• 시뮬레이션의 인풋 데이터(트레이스)는 신빙성 있어야 하기 때문에 실제 프로그램의 CPU 사용하는 시간을 뽑아서 시뮬레이션 인풋으로 사용
  • 실제 돌아가는 프로그램 패턴을 대변
  • 실제 시스템에서의 트레이스와 유사한 모델을 합쳐서 확인

프로세스 싱크로나이제이션 (프로세스 동기화)

데이터 접근

컴퓨터 안에서 연산이 이루어질 때
1. 데이터 읽어와서 연산
2. 결과를 어딘가에 저장
3. 메모리에 있는 데이터 읽어와서 CPU(왼쪽)에서 연산
4. 다시 데이터를 메모리(오른쪽)로 가져다가 사용
위와 같은 방식으로 I/O를 하는 하드디스크의 파일 읽어와서 내부 작업하고 내보낸다

데이터를 읽어들어와서 일을 하고 결과를 내보내는 형식

Race Condition

데이터를 여러 곳에서 읽어가서 연산하게되면 레이스 컨디션 문제가 발생 !

가운데 저장되어있는 count라는 변수 값
먼저 왼쪽에서 1 증가시키는 연산을 하고 다시 저장
오른쪽에서 1 감소시키는 연산을 하고 다시 저장
count 값은 1 증가 1 감소로 인해 원래 값이 저장되어 있어야 한다

연산할 주체 둘이 있는 경우,
1 증가시키는 도중 카운트 값을 읽어감 > 연산이 끝나서 저장하면 1 증가
다른 곳에서 1 증가 시키기 이전의 값을 읽어감 > 1을 뺀 다음에 최종적으로 저장
모든 연산이 반영되지 않고 도중에 읽어가서 연산하고 저장한 감소만 반영된다

• 문제가 생기지 않는다는 관점

  • CPU 개수 상관없이 레이스 컨디션이 생기지 않는다
    읽어가려는 데이터는 프로세스 내부에 있는 변수
    프로세스는 자기 자신의 주소 공간의 데이터만 접근 가능
    CPU가 2개 중 왼쪽 CPU가 프로세스 A 실행하며 A 주소공간 데이터 접근중
    오른쪽 CPU가 프로세스 B 실행중이면 B 주소공간 데이터 접근
    따라서 레이서 컨디션 문제가 생기지 않는다

• 문제가 생기는 관점 (운영체제가 끼어드는 경우)

  • CPU 개수 상관없이 레이스 컨디션이 발생한다 (CPU가 한 개인 경우라도)
    A 실행중 >
    A 프로세스가 본인이 할 수 없는 일을 운영체제한테 시스템 콜을 해서 요청 >
    운영체제 안의 데이터 값을 바꾸고 있는 상황 >
    CPU 할당 시간 끝나면 A에서 B로 넘어감 >
    B가 실행도중 B도 본인이 할 수 없는 일을 하게 되어서 운영체제한테 시스템 콜 >
    B의 요청에 의해서 또다시 운영체제 코드 실행해서 변수 변경 (똑같은 데이터 건드려야 하는 상황) >
    CPU가 A한테 다시 간다면 운영체제 작업하다 만 일을 계속 진행 (그 다음 CPU 기계어부터 시작)

  • 즉, 시스템 콜 해서 운영체제가 커널 데이터 건드리는 도중에 CPU가 다른 프로세스한테 넘어가면 문제가 생길 수 있다

레이스 컨디션 발생하는 경우

1. 인터럽트 발생시

• 운영체제 코드가 수행 도중, 카운트 변수 1 증가시키려고 한다
  • 해당 변수를 레지스터로 읽어들이고, CPU 안에서 레지스터 값을 1 증가
• 변수를 레지스터로 읽어들인 다음에 1 증가시키려고 하는데 인터럽트 발생
• 무조건 하던일을 멈추고 CPU가 운영체제한테 넘어간다 (하던 일보다 더 긴급한 일이 필요한 상태)
  • 현재 문맥을 저장하고 인터럽트 처리 루틴으로 넘어가서 작업이 끝나고 원래 위치로 돌아온다 (저장했던 문맥을 다시 복원)
  • 여기서 카운트 값은 이미 인터럽트 당하기 전에 레지스터로 읽어왔기 때문에 인터럽트 작업 전의 값을 1을 증가시켜서 저장 => 인터럽트 값 반영이 안된다, 원하지 않는 값이 저장

문제 해결하기 위해 변수를 변경하기 전에 인터럽트 disable 시키고 하던 작업이 끝나면 인터럽트를 받는다
커널의 공유 변수 건드리기 전에 disable 시키고 끝나면 인터럽트를 수용

2. 커널 데이터 변경시

• 프로그램 A가 유저모드에서 본인의 코드 실행할 때 문제 X
  • 주소 공간 공유하지 않아서 문제가 안됨
• 시스템 콜을 통해 커널 데이터(프로세스 입장에서 공유 데이터)를 변경하는 상황에서 문제
  • 도중에 CPU 빼앗기게 되면 레이스 컨디션이 생길 수 있다

3.

커널 모드에서 수행중일 때는 CPU를 빼앗지 않는다
CPU 시간이 끝나도 커널모드의 작업 모두 끝내고 유저 모드로 돌아갈 때 CPU를 넘겨주도록 한다
운영체제는 타임 쉐어링 시스템에서 모두가 행복하자고 만든 것
CPU를 빼앗는 것은 커널 모드에서 일하고 있으면 그 작업 끝난 다음에 CPU를 빼앗자

정리
프로세스 간에는 주소공간 공유하지 않는다고 했는데 레이스 컨디션 문제가 왜 발생?
시스템 콜을 통해 운영체제 들어가서 작업 처리할 때 문제 발생할 수 있다
공유 메모리를 쓰면 메모리 주소공간 일정부분 공유하기 때문에 프로세스가 공유 메모리 안의 변수를 건드리는 도중에 CPU를 빼앗겨서 넘기면 원하지 않는 결과가 나올 수 있다
공유 메모리 쓰는 개별 프로세스가 실행 도중에 CPU 뺏기더라도 문제가 생기지 않도록 코딩해야 한다 => 이후 나오는 프로세스 싱크로나이제이션과 관련된 테크닉

프로세스 싱크로나이제이션

공유데이터의 동시접근으로 생기는 문제

멀티 프로세서(CPU가 여러 개 있는 상황)에서 운영체제가 실행될 때 프로세스 싱크로나이제이션이 발생할 수 있다
프로세스가 각자의 주소공간을 가지고 일하면 문제없지만 운영체제 코드를 양쪽에서 건드려서 문제가 생길 수 있다 => 데이터 불일치 문제

CPU 자체가 여러 개 있다면 한 쪽의 인터럽트를 막아도 다른 쪽에서 읽어갈 수 있다

해결 방법

운영체제 코드가 수행중이면 다른 어떤 CPU도 운영체제를 못들어가게 하는것

문제 원인은 운영체제 동시 접근해서 생기는 것

• 매 순간 CPU 하나만 운영체제를 실행할 수 있게 한다
• 하지만 굉장한 오버헤드도 발생
  • CPU가 여러 개 있고 각 CPU에서 유저/커널 모드를 반복할 텐데 커널 모드에 모든 CPU 중 하나만 들어가면 대단히 비효율적인 상황

공유데이터 각각에 lock을 걸어서 접근하지 못하게 한다

• 운영체제를 수행하면서 변수를 변경하려고 할 때 락이 걸려있으면 접근 불가능
• lock이 풀릴 때까지 접근 불가능

1번 방법은 운영체제 전체를 락 걸어서, 카운트 접근 못하게 하면 혼자만 독점해서 쓰고 다른 친구가 못 쓰게 하는 방법
2번 운영체제 안에 여러 개의 데이터가 존재하고 각 데이터별로 사용중일 때 락 걸고 사용이 끝나면 락 풀게 하는 방법
여러 CPU가 운영체제 수행중이더라도 해당 데이터를 건드리고 있지만 않다면 충분히 운영체제 코드를 동시에 사용할 수 있다

협력하는 프로세스 간의 실행 순서를 정해주는 것이 필요하는 것이 중요하다

레이스 컨디션 예시

1번 프로세스와 2번 프로세스 존재
x=2 일 때 하나는 1 증가시키고 싶고, 하나는 1 감소시키고자 한다
(고급 언어에서의 한 문장이 기계어로 바뀌면 여러 개의 기계어로 나누어서 실행이 된다)
메모리 변수 X는 먼저 레지스터에 읽혀져서 레지스터 값을 증가시키고 그 다음에 그 값을 다시 메모리에 저장
값이 원자적으로 실행되면 문제가 없지만 실행하는 도중에 쪼개져서 CPU가 다른 프로세스한테 넘어갈 수 있다는게 문제