운영 체제 도론
4490 단어 소프트웨어 이론
변환 그림:
-> -> ->
|----CPU 3단계 스케줄링: 고급 스케줄링(작업): 외부 메모리->메모리 중급 스케줄링: 대기->준비, 메모리->메모리 저급 스케줄링(프로세스): 메모리->Cpu 계산 공식: 작업 응답 시간 = 이미 대기 시간 + 서비스 시간 요구;R = w+s - 이론적으로 작업 응답 비율 H = 작업 응답 시간/요구 서비스 시간 H = (w+s)/s 작업 회전 시간 Ti = 작업 수행 시간 + 작업 대기 시간(제출에서 완료까지의 시간)--실제 중 평균 회전 시간:sum(Ti)/n은 서로 다른 스케줄링 알고리즘의 성능을 평가한다.Ti/Ts 반응 작업 길이: 짧은 작업이 크고 긴 작업이 작은 평균 회전 시간:sum(Ti/Ts)/n은 같은 스케줄링 알고리즘이 서로 다른 작업 흐름에 대한 성능Ts:작업이 Cpu에서 실행되는 시간 cpu 이용률 = cpu 작업 시간/(cpu 작업 시간+cpu 여가 시간).프로세스 스케줄링 알고리즘: FCFS: 제출 시간에 따라 작업이 막히거나 끝날 때까지 조정됩니다.SJF: 작업 요구에 따라 서비스 시간Ts에 따라 정렬하고 준비 대기열에서 막히기(먼저 들어가서 기다리고 준비) 또는 종료까지 이동합니다.기아 현상이 발생할 수 있다.HRRN: 매번 불러오기 전에 준비된 대기열의 모든 작업의 응답비 H를 계산하고 내림차순 불러오기;RR: 준비 대기열의 모든 작업은 타임 슬라이스를 실행하고 실행이 끝나면 대기열에 들어갑니다.선점식 스케줄링: SJF+HRRN+RR 잠금: 한 프로세스의 모든 프로세스가 다른 프로세스가 자원을 방출하기를 기다리고 있습니다.자원 동기화 상호 배척;2. 프로세스가 자원을 점용하고 새로운 요청을 하는 것을 유지한다.3. 프로세스가 이미 보유한 자원을 선점할 수 없습니다.4. 순환 대기 체인: p0->p1->.....->pn->p0; *은행가 알고리즘: 시스템 잠금 해제(Dijkstra) 방지
{
struct:
avab[m]: m :
maxn[n][m]:n
alloc[n][m]:n
need[n][m] = max[n][m]-alloc[n][m]
i :
work[m]=avab[m]
finish[m]= , false
: i ( n )
if(request[j]<=need[i][j]) ;else exit(-1);
if(request[j]<=avab[j]) ;else i ;
:
{
avab[j] = avab[j]-request[j];
alloc[i][j] = alloc[i][j]+request[j];
need[i][j] = need[i][j] - request[j];
}
if( ok) ;
else ,avab[j],alloc[i][j],need[i][j] i ;
:
{
for(i=0;i메모리의 다중 구조 cpu 레지스터, {고속 캐시, 메인 메모리, 디스크 캐시}(메인 메모리, 메인 메모리 + 레지스터 = 실행 가능한 메모리), {고정 하드디스크, 이동 디스크}(보조 메모리) 1.연속 분배 저장소 고정 분배: 등분 구역 분배, 부등분 구역 분배(매번 메모리를 불러오기 전, 작은 것부터 큰 것까지 스캔할 때 분배되지 않은 메모리 구역: 욕심 알고리즘) 동적 분배: 데이터 구조 + 분배 알고리즘 + 회수 조작은 주소 번호에 따라 한 순서만 배열한다: FF 최초 적응 알고리즘: 구역은 하나의 체인을 형성하고 처음부터 설치할 수 있는 블록을 찾아 두 노드로 분해한다. 하나는 이미 분배되었다.미분배(순서 찾기)NF 순환 초기 적응: FF에 시작 찾기 주소를 추가하여 낮은 주소 공간의 파편이 너무 많은 것을 피한다.매번 일치 전 정렬: BF 최적 적응: 주소 체인을 공간 크기에 따라 정렬(욕심 알고리즘), 미시적 최적, 극소 파편 발생하기 쉬움 WF 최악 적응: 직접 체인 헤더를 찾아 비교하고 거시적으로 파편이 크고 찾기가 빠르다.2. 페이지 저장 관리 페이지: 프로세스의 논리적 주소 공간 블록 주소 구조(이진법): 000000000: 페이지 번호, 위치 이동 - 2^4-1페이지, 2^6-1페이지 내 위치 이동;시트: (key=페이지 번호,val=물리 블록 번호) 계산 방법: (페이지 크기== 물리 블록 크기size) 물리 주소addr-> 논리 주소(p,w): p=floor(addr/size), w=p%size;논리 주소(p,w)->물리 주소addr:addr=p*size+w;3. 페이지 교체 알고리즘(주류 집합: 물리적 블록 수, 명중 부족) 프로세스 떨림: 방금 탈락한 페이지는 방문을 불러옵니다.Belady 현상: 분배된 페이지 수(주류 집합)가 증가하지만 결장률(=결장 횟수/프로세스 페이지 수)은 오히려 FIFO를 높인다. 가장 먼저 들어온 페이지(다시 명중시켜도 갱신하지 않음) 주류 집합의 페이지를 항상 탈락시키면 Belady 현상이 나타난다.LRU: 최근 가장 오랫동안 사용하지 않은 페이지 제거하기;OPT: 앞으로 가장 긴 시간 동안 사용하지 않을 페이지(같은 시간의 페이지 번호 찾기)의 탈락;이론은 다른 알고리즘의 성능을 평가하는 데만 쓸 수 있다.디스크의 조직 형식(가상 형상, 실제는 서로 다른 테이프 부채 수가 같지만 모든 트랙과 같은 부채 수가 아니다): 디스크: 한 디스크에 여러 디스크가 포함됩니다.디스크 서피스: 디스크당 여러 개의 스토리지 면이 있을 수 있습니다.트랙(기둥면)Track: 트랙의 바깥에서 안까지 번호가 0에서 많음;트랙 사이에 갭이 있음;각 트랙은 같은 수량의 이진 비트(내부 밀도가 높음)를 저장할 수 있다.섹터Sectors: 하나의 트랙이 여러 섹터를 구분하고 섹터 사이에 갭이 있습니다.섹터 용량이 같음;고정 헤드 디스크: 트랙마다 읽기 헤드가 있어 병렬 읽기와 쓰기가 가능합니다.헤드 디스크 이동: 한 면에 읽기 전용 헤드만 있고 직렬 읽기 전용 헤드만 있습니다.접근 시간 = 탐색 + 회전 선택 섹터 + 읽기와 쓰기 전송 디스크 스케줄링 알고리즘 (탐색 시간 변경): 헤드 운동 방향이 양방향으로 읽기와 쓰기가 가능한지 주의하십시오.FCFS: 프로세스에 따라 트랙에 액세스한 후 순차적으로 데이터를 읽고 쓰기;SSTF: 읽기와 쓰기가 현재 헤드와 가장 가까운 트랙으로 배고픔 현상이 발생하기 쉽다.SCAN: SSTF를 바탕으로 헤드의 이동 방향을 제한한다(같은 방향의 최단 트랙).
CSCAN:SCAN을 바탕으로 읽기와 쓰기 방향을 정하고 역읽기와 쓰기 방향을 할 때 읽기와 쓰기를 하지 않는다.
다음에 은행가 알고리즘의 C++ 버전을 추가하기;
좋은 웹페이지 즐겨찾기
