운영 체제의 동기화 기본 요소에 대한 포괄적인 분석
- 不言원래의
- 2018-09-17 15:27:271408검색
이 기사는 운영 체제의 동기화 기본 요소에 대한 포괄적인 분석을 제공합니다. 필요한 친구가 참고할 수 있기를 바랍니다.
Race Conditions
일반 운영 체제에서는 서로 다른 프로세스가 하드 디스크의 메모리나 파일과 같은 공통 저장 영역을 공유할 수 있으며 이러한 프로세스는 이러한 영역에서 읽고 쓸 수 있습니다.
운영 체제에는 올바른 방식으로 원하는 작업을 수행하기 위해 공통 영역을 사용하여 프로세스를 조정하는 몇 가지 책임이 있습니다. 이러한 프로세스는 서로 통신하고 토론을 통해 한 프로세스의 작업이 다른 프로세스의 일반적인 작업에 영향을 미치지 않도록 해야 하며, 이로 인해 프로세스가 실행된 후 예상한 결과를 얻지 못하게 됩니다. 운영체제 개념에서 IPC(Inter Process Communication)라는 용어는 일반적으로 여러 프로세스 간의 통신을 나타내는 데 사용됩니다.
경쟁 조건이 무엇인지 설명하기 위해 간단한 예를 소개합니다.
숫자 n이 파일에 저장되어 있습니다. 프로세스 A와 프로세스 B 모두 이 파일의 번호를 읽고 이를 저장하려고 합니다. 1씩 증가하고 파일에 다시 저장됩니다. n의 초기 값을 0이라고 가정하면 이상적인 경우에는 A 프로세스와 B 프로세스가 실행된 후 파일 내 n 값이 2여야 하지만 실제로는 n 값이 1이 되는 경우도 있습니다. 이 작업을 수행할 때 각 프로세스가 거쳐야 하는 단계를 고려할 수 있습니다.
파일에서 n 값을 읽어보세요
Let n = n + 1
새 n 값 반환 파일을 저장합니다.
경합 조건을 더 자세히 설명하기 전에 먼저 운영 체제 개념에 대한 몇 가지 지식 사항을 검토해야 합니다.
프로세스는 CPU가 하나만 있는 경우에도 동시에 실행될 수 있습니다)
운영 체제 시계
클록 인터럽트 외에도 다른 장치의 인터럽트로 인해 프로세스가 다시 예약됩니다.
프로세스 A가 1단계와 2단계 실행을 마쳤다고 가정합니다. 아직 시작되지 않았습니다. 3단계를 실행하면 클럭 인터럽트가 발생합니다. 이때 운영 체제는 프로세스 B가 실행을 시작하도록 예약합니다. 프로세스 B가 1단계를 실행하면 n의 값이 0임을 확인하여 2단계를 실행합니다. 3, 결국 n = 1 파일에 저장합니다. 프로세스 A가 나중에 계속 실행되면 프로세스 B가 3단계를 실행하기 전에 파일의 값을 수정했다는 사실을 모르기 때문에 프로세스 A도 n = 1을 파일에 다시 씁니다. 이것이 문제입니다. 프로세스 A가 실행되는 동안 다른 프로세스가 작동하는 데이터에 대해 작동합니다.
n = 2로 만드는 유일한 방법은 프로세스 A와 프로세스 B가 각각 모든 단계를 순서대로 완료할 것으로 기대하는 것입니다.
경쟁 조건을 정의할 수 있습니다
두 개 이상의 프로세스가 특정 공유 데이터를 읽고 쓰며, 최종 결과는 프로세스 실행의 정확한 타이밍에 따라 달라지는데, 이를 경쟁 조건이라고 합니다.
위 텍스트에서는 경쟁 조건을 논의하기 위해 프로세스를 객체로 사용했습니다. 실제로 스레드에는 커널 스레드와 사용자 스레드가 포함되지만 이에 국한되지는 않습니다. 운영 체제에서 프로세스는 실제로 스레드를 사용하여 프로그램을 실행하기 때문입니다. 게다가 Java 언어의 스레드 안전성에는 경쟁 조건이라는 개념도 적용됩니다. ("Java 동시 프로그래밍 실습" 2장 참고)
Mutual Exclusion and Critical Sections
경쟁 조건을 피하는 방법은 프로세스가 공유 변수나 파일을 사용할 때 다른 프로세스가 사용할 수 없도록 보장하는 몇 가지 수단을 사용해야 합니다. 동일한 작업을 수행하려면 즉, "상호 배제"가 필요합니다.
위의 예를 예로 들면, 1~3단계의 프로그램 조각을 임계 섹션으로 정의할 수 있습니다. 임계 섹션은 프로세스가 이 영역에 실행되면 공개 데이터가 중요하다는 것을 의미하기 때문에 이 영역이 중요하다는 것을 의미합니다. 영역 또는 파일 작업은 다른 프로세스도 중요 섹션에서 실행될 수 있음을 의미합니다. 두 프로세스가 동시에 임계 영역에 있지 않도록 적절한 조치를 취하면 경쟁 조건을 피할 수 있습니다.
즉, '상호 배제'를 어떻게 달성할 수 있을지 고민해야 합니다.
상호 배제 방식
상호 배제의 핵심은 여러 프로세스가 동시에 임계 영역에 진입하는 것을 방지하는 것입니다
마스크 인터럽트
앞서 언급한 예에서 프로세스 B가 크리티컬 섹션에 진입할 수 있었던 이유는 프로세스 A가 크리티컬 섹션에서 인터럽트를 받았기 때문입니다. 프로세스 A에게 임계 구역에 진입한 직후에 모든 인터럽트를 마스크하고 임계 구역을 떠난 후에만 인터럽트에 응답하도록 요청하면, 인터럽트가 발생하더라도 CPU는 다른 프로세스로 전환하지 않으므로 프로세스 A는 안전하게 인터럽트를 수정할 수 있습니다. 다른 프로세스가 작업을 방해할 것이라는 걱정 없이 파일 내용을 편집할 수 있습니다.
그러나 이 아이디어는 아름답지만 실제로는 실현 가능하지 않습니다. 첫째, CPU가 여러 개인 경우 프로세스 A는 자신을 예약하는 CPU만 마스크할 수 있으므로 다른 CPU가 예약한 프로세스는 여전히 임계 섹션에 들어갈 수 있습니다. 차단 인터럽트 권한이 사용자 프로세스에 부여됩니까? 이 프로세스가 인터럽트를 마스크하고 인터럽트에 응답하지 않으면 프로세스가 전체 운영 체제를 중단시킬 수 있습니다.
잠금 변수
잠금 플래그 비트를 설정하여 초기 값을 0으로 설정할 수도 있습니다. 프로세스가 임계 영역에 들어가고 싶을 때 먼저 잠금 값이 0인지 확인하세요. 0이면 설정하세요. 그런 다음 임계 구역에 들어가서 임계 구역을 종료한 후 잠금 값을 0으로 변경합니다. 검사 시 잠금 값이 이미 1이면 다른 프로세스가 이미 임계 구역에 있다는 의미이므로 프로세스는 루프에서 기다리고 잠금 값이 0이 될 때까지 지속적으로 검색합니다.
하지만 이 방법에도 경쟁 조건이 있습니다. 그 이유는 프로세스가 잠금 값을 0으로 읽을 때 값을 1로 설정하기 전에 다른 프로세스가 예약되어 잠금 값도 읽기 때문입니다. 값은 0이므로 두 프로세스가 동시에 임계 섹션에 있습니다.
엄격한 회전 방식
잠금 변수의 문제점은 실제로 잠금 변수를 0에서 1로 변경하는 동작이 잠금을 획득하려는 프로세스에 의해 수행되기 때문입니다. 잠금을 획득한 프로세스가 이 작업을 수행하도록 변경하면 경쟁 조건이 발생하지 않습니다.
먼저 현재 잠금을 획득할 수 있는 사람을 나타내는 변수 차례를 설정합니다. 프로세스 A의 논리는 다음과 같습니다.
while (turn != 0){// 如果还没轮到自己获取锁，则进入循环等待
}
do_critical_region();// 执行临界区的程序
turn = 1;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
do_non_critical_region();// 执行非临界区的程序
프로세스 B의 논리는 다음과 같습니다.
while (turn != 1) {// 如果还没轮到自己获取锁，则进入循环等待
}
do_critical_region();// 执行临界区的程序
turn = 0;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
do_non_critical_region();// 执行非临界区的程序
그러나 여기서 고려해야 할 사항 중 하나는 프로세스 A의 do_non_tical_region()이 실행하는 데 오랜 시간이 걸린다고 가정합니다. 즉, 프로세스 A의 중요하지 않은 영역의 로직을 오랫동안 실행해야 하는 반면 프로세스 B의 비임계 영역 논리는 당연히 프로세스 A가 임계 영역에 진입하는 빈도가 프로세스 B의 빈도보다 작습니다. 이상적으로는 프로세스 B가 임계 영역에 몇 배 더 진입해야 합니다. 그러나 프로세스 B는 Non-Critical 구간의 로직을 실행하기 전에 Turn을 0으로 설정하므로, Non-Critical 구간의 로직을 빠르게 실행한 후 다시 돌아와 Turn 값을 확인하면 차례의 값은 1이 아닙니다. 이 값을 사용하려면 프로세스 A가 1로 설정되어야 하지만 프로세스 A는 현재 긴 중요하지 않은 섹션 논리 코드를 실행하고 있으므로 프로세스 B는 임계 섹션에 들어갈 수 없습니다.
이는 한 프로세스가 다른 프로세스보다 훨씬 느린 경우 엄격한 순환이 좋은 생각이 아님을 보여줍니다.
Peterson 알고리즘
엄격한 회전 방식의 문제점은 엄격한 단어에 있습니다. 즉, 여러 프로세스가 차례로 임계 영역에 진입하는 근본적인 이유는 잠금을 얻으려는 프로세스가 다른 프로세스에 의존해야 한다는 것입니다. 잠금 변수의 경우 수정 및 기타 프로세스는 잠금 변수를 수정하기 전에 먼저 중요하지 않은 섹션 논리의 실행을 거쳐야 합니다.
엄격 회전 방법의 회전 변수는 잠금을 획득할 차례를 나타내는 데 사용될 뿐만 아니라 값이 변경되기 전에도 다른 프로세스가 임계 영역에 진입하는 것을 방지한다는 의미입니다. 프로세스는 항상 거쳐야 합니다. 비임계 구간의 로직 이후에는 차례의 값이 변경됩니다.
따라서 이를 표현하기 위해 두 개의 변수를 사용할 수 있습니다. 하나의 변수는 현재 잠금을 획득할 차례를 나타내고, 다른 변수는 현재 프로세스가 임계 영역을 벗어났음을 나타냅니다. 이 방법을 실제로 Peterson 알고리즘이라고 합니다. 네덜란드 수학자 T가 발명했습니다. .Dekker가 제안했습니다.
static final int N = 2;
int turn = 0;
boolean[] interested = new boolean[N];
void enter_region(int process) {
int other = 1 - process;
interested[process] = true;
turn = process;
while(turn == process && !interested[other]) {
}
}
void exit_region(int process) {
interested[process] = false;
}
프로세스가 임계 영역에 들어가야 할 때 먼저 Enter_region을 호출합니다. 임계 영역을 떠난 후 Exit_region을 호출합니다. Peterson의 알고리즘은 프로세스가 임계 영역을 떠난 후 임계 영역에 대한 "관심"을 즉시 제거하도록 하므로 다른 프로세스는 차례 값을 기반으로 임계 영역에 합법적으로 들어갈 수 있는지 여부를 판단할 수 있습니다.
TSL Instruction
앞에서 언급한 "변수 잠금" 방법을 검토해 보겠습니다. 치명적인 단점 중 하나는 상태 변수를 0에서 1로 변경하는 경우 또는 에서 1로 변경하는 경우입니다. 1 대 0이면 인터럽트로 인해 중단될 수 있으므로 경쟁 조건이 발생합니다.
나중에 잠금 변수를 기반으로 임계 구역에 진입하려는 프로세스가 아니라 임계 구역에 진입한 후 임계 구역을 떠나려는 프로세스에 의해 잠금 변수가 수정되면, 이를 통해 엄격한 회전 방법으로 이어지는 경쟁 조건을 피할 수 있으며 엄격한 회전 방법을 기반으로 개선된 Peterson 알고리즘이 사용됩니다. 이러한 방법은 모두 소프트웨어 관점에서 고려됩니다. 실제로 하드웨어 CPU의 지원을 통해 잠금 변수의 변경이 중단되지 않도록 보장할 수 있으므로 잠금 변수는 프로세스 상호 배제를 해결하는 좋은 방법이 됩니다.
대부분의 현재 컴퓨터 CPU는 테스트 및 설정 잠금이라고 하는 TSL 명령어를 지원합니다. 이는 메모리 변수(워드)를 레지스터 RX로 읽은 다음 메모리 주소에 0이 아닌 값을 저장합니다. , 읽기 작업 및 쓰기 작업은 하드웨어 수준, 즉 원자 수준에서 중단되지 않도록 보장됩니다. 사용되는 방법은 TSL 명령을 실행할 때 메모리 버스를 잠그고 TSL 명령이 끝나기 전에 다른 CPU가 메모리에 액세스하는 것을 금지하는 것입니다. 이것은 우리가 흔히 CAS(Compare And Set)라고 부르는 것이기도 합니다.
잠금 변수를 0에서 1로 변경해야 하는 경우 먼저 메모리 값을 레지스터에 복사하고 메모리 값을 1로 설정한 다음 레지스터 값이 0인지 확인합니다. 0이면 작업이 수행됩니다. 성공하고, 0이 아니면 레지스터 값이 0이 될 때까지 감지를 반복합니다. 레지스터 값이 0이 되면 다른 프로세스가 임계 영역을 떠났다는 의미입니다. 프로세스가 임계 영역을 벗어나면 메모리에 있는 이 변수의 값을 0으로 설정해야 합니다.
Busy Waiting
위에서 언급한 Peterson 알고리즘과 TSL 방법에는 실제로 하나의 기능이 있습니다. 즉, 임계 영역에 들어가기를 기다릴 때 사용하는 바쁜 대기 방법입니다. , 우리는 종종 스핀이라고 부릅니다. 단점은 CPU 시간 조각을 낭비하고 우선순위 반전 문제를 일으킬 수 있다는 것입니다.
두 개의 프로세스가 있는 컴퓨터를 생각해 보세요. H는 우선순위가 더 높고 L은 우선순위가 낮습니다. 스케줄링 규칙에는 H가 준비 상태에 있는 한 실행될 수 있다고 명시되어 있습니다. 특정 순간에 L은 임계 영역에 있고 H는 준비 상태에 있고 실행할 준비가 되어 있습니다. 그러나 H는 바쁜 대기 상태여야 하고 L은 우선순위가 낮기 때문에 스케줄링할 수 없으므로 임계 영역을 떠날 수 없습니다. 따라서 H는 영원히 바쁜 대기 상태가 되며 L은 임계 영역을 절대 떠날 수 없습니다. 이 상황을 우선순위 반전 문제(우선순위 반전 문제)
프로세스 차단 및 깨우기
운영 체제는 일부 기본 요소, 절전 모드를 제공합니다. 그리고 일어나.
코어 외부 호출을 위해 커널에서 제공하는 프로세스나 기능은 프리미티브가 되며, 프리미티브는 실행 중 중단을 허용하지 않습니다.
sleep은 다른 프로세스가 wakeup 메소드를 호출할 때까지 호출 프로세스를 차단하는 시스템 호출로, 차단된 프로세스를 매개변수로 사용하여 깨우게 됩니다. 차단과 바쁜 대기의 가장 큰 차이점은 프로세스가 차단된 후 CPU가 해당 프로세스에 시간 조각을 할당하지 않는 반면 바쁜 대기는 항상 유휴 상태이며 CPU의 시간 조각을 소비한다는 것입니다.
세마포
가장 먼저 이해해야 할 것은 세마포가 어떤 문제를 해결하는 것으로 보이는지입니다. 예를 들어 프로세스 A는 sleep()을 호출하고 차단에 들어갑니다. 프로세스 B가 wakeup(A)를 호출하면 프로세스 A가 깨어납니다. 서로 다른 프로세스로 진행되기 때문에 중단되는 문제도 있습니다. 로직에 따르면 프로세스 A에 합류할 때 차단 상태에 들어가려면 sleep()을 호출해야 하지만, 슬립 메서드를 호출하기 직전에 클럭 중단으로 인해 프로세스 B가 실행되기 시작합니다. wakeup() 메소드를 호출하여 프로세스 A를 깨우지만, 프로세스 A가 아직 차단 상태에 진입하지 않았으므로 깨우기 신호가 손실됩니다. 프로세스 A가 이전에 중단된 위치에서 계속 실행되어 차단에 들어가면 더 이상 프로세스가 중단될 수 있습니다. 일어나세요.
따라서 프로세스의 차단 및 깨우기를 기록하려면 추가 변수를 도입해야 합니다. 이 변수는 깨울 때마다 변수의 값이 1씩 증가합니다. 이 변수를 사용하면 wakeup 작업이 sleep 작업보다 먼저 발생하더라도 해당 프로세스가 sleep 상태인 경우 다른 프로세스가 이미 wakeup되었으므로 해당 프로세스는 차단에 들어갈 필요가 없다고 간주됩니다. 상태.
이 변수는 운영 체제 개념에서 1965년 Dijkstra가 제안한 방법인 세마포어라고 합니다.
세마포에는 아래쪽과 위쪽의 두 가지 작업이 있습니다.
down 작업은 실제로 절전에 해당합니다. 먼저 세마포어 값이 0보다 큰지 감지합니다. 0보다 큰 경우 1씩 감소합니다. 이때 프로세스는 차단할 필요가 없습니다. 깨우기를 소비하는 것과 같습니다. 세마포어가 0이면 프로세스는 차단 상태로 들어갑니다.
up 작업은 wakeup에 해당합니다. 이 세마포어에서 프로세스가 차단된 것으로 확인되면 시스템은 이를 깨울 프로세스 중 하나를 선택합니다. 이때 세마포어의 값은 필요하지 않습니다. 변경하려면 차단된 프로세스가 이미 하나 적습니다. up 작업 중에 세마포어에 차단된 프로세스가 없으면 세마포어의 값이 1 증가합니다.
Dijkstra의 논문에서는 P와 V가 각각 Down과 Up을 나타내는 데 사용되기 때문에 Down 및 Up 작업을 PV 작업이라고 부르는 곳도 있습니다.
세마포어의 아래로 및 위로 작업은 운영 체제에서 지원하는 기본 작업이며 중단되지 않습니다.
Mutex
Mutex는 실제로 세마포어의 특수한 경우입니다. 그 값은 0과 1뿐입니다. 세마포어의 계산 기능이 필요하지 않은 경우 실제로 뮤텍스를 사용할 수도 있습니다. 동시에 하나의 프로세스만 들어갈 수 있는 반면, 세마포어는 여러 프로세스가 동시에 임계 섹션에 들어갈 수 있습니다.
위 내용은 운영 체제의 동기화 기본 요소에 대한 포괄적인 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!