Link
Tags
more
«   2024/05   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
Archives
Today
Total
관리 메뉴

글

혼공컴구운체 - 운영체제 본문

CS/운영체제

혼공컴구운체 - 운영체제

miensoap 2024. 1. 25. 15:31

운영체제는 프로그램들에게 자원 할당 (CPU , 입출력장치 등)
커널(kernel) 영역

응용 프로그램이 자원에 직접 접근하면 위험
-> 오직 운영체제를 통해서만 접근

이중 모드 : CPU가 명령어를 실행하는 모드를 구분

  • 사용자 모드 : 운영체제의 서비스 X 커널 영역 코드 실행 불가
  • 커널 모드 : 운영체제의 서비스 O , 자원 접근 등 모든 명령어 실행 가능
    플래그 레지스터의 '슈퍼바이저 플래그' 로 구분

시스템 호출 : 커널 모드로 전환 위한 소프트웨어 인터럽트

운영체제의 핵심 서비스

  • 프로세스 관리 : 실행 중인 프로그램
    • 프로세스 / 스레드 , 프로세스 동기화, 교착상태 해결
  • 자원 접근 및 할당
    1. CPU 스케줄링
    2. 메모리 (페이징 , 스와핑 ... )
    3. 입출력장치 (인터럽트 서비스 루틴)
  • 파일 시스템 관리 : 파일 - 폴더(디렉터리 ) 단위로 저장 장치에 보관

프로세스

foreground / background process
데몬(daemon) , 서비스(service) : 사용자와 상호작용 X 프로세스

프로세스 제어 블록 (PCB)
프로세스들은 돌아가며 한정된 시간 만큼 CPU 이용

    • 타이머 인터럽트
    •  

프로세스 관리 위해 사용하는 자료구조 = PCB
프로세스 생성 시 커널 영역에 생성, 종료시 폐기


    • PID : 특정 프로세스 식별 위해 부여하는 고유한 번호
    • 레지스터 값 : 실행 차례가 돌아오면 이전까지 사용한 레지스터 중간 값들 복원해 재개 
        - 프로세스 카운터, 스택 포인터 ...
    • 프로세스 상태
    • CPU 스케줄링 정보
    • 메모리 정보 : 프로세스가 저장된 주소. 페이지 테이블 정보
    • 사용한 파일과 입출력장치 정보

문맥 교환 (context switch)

  • 문맥(context) : 지금까지의 중간 정보. 실행 재개 위해 백업
    기존에 실행되던 프로세스의 중간 정보(문맥)을 백업하고 실행할 프로세스의 문맥 복구

메모리 영역

  • 코드 영역(= 텍스트 영역)
    • 실행할 수 있는 코드, 기계어로 이루어진 명령어 저장
    • read-only
  • 데이터 영역
    • 프로그램이 실행되는 동안 유지할 데이터 (전역변수)
  • 힙 영역
    • 프로그래머가 할당할 수 있는 저장공간
  • 스택 영역
    • 데이터가 일시적 저장 (매개변수, 지역변수)
    • 힙, 스택 영역의 크기는 가변적 (힙은 낮은주소부터, 스택은 높은주소부터)

프로세스 상태

  • 생성 상태 : 막 메모리에 적재되어 PCB 할당
  • 준비 상태 : 차례를 기다리는 상태 (디스패치 -> 실행)
  • 실행 상태 : CPU 할당받아 실행중 (타이머 인터럽트 ->준비 / 입출력 요청-> 대기)
  • 대기 상태 : 실행중 입출력장치 사용 (입출력 완료 -> 준비)
  • 종료 상태 : PCB , 메모리 영역 정리

프로세스 계층 구조

  • 부모 프로세스 - 자식 프로세스 : (시스템 호출을 통해) 생성
  • 부모- 자식은 별개의 프로세스, 서로 다른 PID
  • pstree 명령어

복제와 옷 갈아입기 : Fork - exec 프로세스 생성 기법

  • 부모 프로세스는 fork 시스템 호출을 통해 자신의 복사본을 생성 (자원 상속)
  • 자식 프로세스는 exec 시스템 호출을 통해 자신의 메모리 공간을 교체 (덮어쓰기)

스레드 (thread) : 프로세스를 구성하는 실행 흐름의 단위

  • 스레드 ID, 레지스터 값(프로그램 카운터 등) , 스택
  • 프로세스 내 자원 공유 -> 실행 위한 최소한의 정보

멀티 프로세스 vs 멀티 스레드

  • 자원 공유 여부
  • IPS (프로세스 간 통신)

CPU 스케줄링

프로세스 우선순위(priority)

  • 입출력 집중 프로세스 > CPU 집중 프로세스

스케줄링 큐

  • 준비 큐
  • 대기 큐 : 요구한 장치별로 같은 큐에서 대기

선점형 (preemptive) 스케줄링 : CPU의 자원을 빼앗아 쓸 수 있음
-> 문맥교환시 오버헤드 , 골고루 이용
비선점형 스케줄링

스케줄링 알고리즘

  1. 선입 선처리 = FCFS(First Come First Served) : 비선점, 호위 효과
  2. 최단 작업 우선 = SJF(Shortest Job First) : 비선점
  3. 라운드 로빈 = RR(Round Robin) : 선입선처리 + 타임 슬라이스 , 돌아가며 선점형
  4. 최소 잔여 시간 우선 = SRT(Shortest Remaining Time) : 최단작업우선+라운드로빈
  5. 우선순위 : 우선순위가 같다면 선입선처리, 기아현상(starvation) 문제 -> 에이징(aging)
  6. 다단계 큐 = Multilevel queue , 우선순위별로 준비 큐를 여러개 사용
  7. 다단계 피드백 큐 : 다단계 큐 + 큐 간의 이동 가능 -> 기아현상 해결
동기화

실행 순서 제어
- reader writer problem

상호 배제 : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근
- Bank account problem : '현재 잔액' 공유
- Producer & Consumer problem : '총합' 변수 =공유 자원
- 임계 구역 : 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
- 레이스 컨디션(Race Condition) : 하나의 자원을 놓고 경쟁하는 상황

1. 상호 배제 (mutual exclusion) 
    한 프로세스가 임계 구역에 진입하면 다른 프로세스는 들어올 수 없다.
2. 진행 (progress)
    임계 구역에 어떤 프로세스도 진입하지 않닸다면 진입할 수 있다.
3. 유한 대기 (bounded waiting)
    임계 구역에 들어오기 위해 무한정 대기해서는 안된다.

뮤텍스 락 (Mutex lock) : 상호 배제를 위한 동기화 도구, 자물쇠 역할
전역 변수 lock + 임계 구역을 잠그는 acquire 함수+ 해제하는 release 함수

  • busy waiting : 반복적으로 lock 확인하며 대기

세마포 (Semaphore) : 공유 자원이 여러 개인 경우도 적용 가능
사용 가능한 개수 S +wait함수 + signal 함수 (P/V , down/up)

wait (){
    while(S<=0){}
    S--; /* 가능한 자원이 하나 이상이면 하나 줄이고 진입*/
}

Busy waiting 해결
-> 사용가능한 자원이 없는 경우 대기 상태 (PCB를 대기 큐에 삽입), 생기면 준비 상태

wait(){
    S--;
    if(S<0){
    add this process to Queue;
    sleep();
    }
}

signal(){
    S++
    if(S<=0){
    remove a process p from Queue;
    wakeup(p);
    }
}

모니터 : 개발자가 다루기 편리한 동기화 도구

상호 배제를 위한 동기화
    - 인터페이스를 위한 큐
    - 공유 자원에 접근하고자 하는 프로세스를 큐에 삽입
    - 큐이 삽입된 순서대로 공유 자원 이용

실행 순서 제어를 위한 동기화
    - 조건 변수 이용 
    - 조건 충족 x -> wait 조건 충족 -> signal

모니터 안에는 하나의 프로세스만이 있을 수 있다

교착 상태(deadlock)

  • 자원 할당 그래프 : 교착 상태 발생 조건 파악
    1. 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용 불가
    2. 점유와 대기 : 자원을 할당 받은 상태에서 다른 자원을 대기
    3. 비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못함
    4. 원형 대기 : 원의 형태로 자원 대기
  • 교착 상태 예방 -> 발생 조건 중 하나를 없앤다
    -> 원형 대기 조건 : 자원에 번호를 붙이고 오름차순으로 할당 (일렬 식탁)
    -> 부작용
  • 교착 상태 회피 : 무분별한 자원 할당 X , 자원의 양을 고려해 배분
    • 안전 순서열 : 교착 상태 없이 안전하게 할당할 수 있는 순서
    • 안전 상태 : 교착 상태 없이 모든 프로세스가 자원 할당/종료 가능
    • 불안전 상태 : 교착 상태 발생 가능
    • 은행원 알고리즘
  • 교착 상태 검출 후 회복
    • 선점을 통한 회복 : 해결될 때까지 한 프로세스씩 자원을 몰아줌
    • 프로세스 강제 종료를 통한 회복
      • 해결까지 한 프로세스씩 강제 종료(->오버헤드) , 모두종료(->작업내역위험)
  • 교착 상태 무시 : 타조 알고리즘

가상 메모리

연속 메모리 할당

  • 프로세스에 연속적인 메모리 공간 할당

스와핑 : 스왑 인/아웃

  • 현재 사용되지 않는 프로세스들을 보조기억장치의 스왑 영역으로 보내고 새 프로세스 적재
  • free , top 명령어

최조 적합 (first-fit) : 검색 최소화, 빠른 할당
최적 적합 (best-fit) : 모두 검색한 후, 적재 가능한 가장 작은 공간에 할당
최악 적합 (worst-fit) : 가장 큰 공간에 할당

문제점 1. 외부 단편화 : 실행/종료 반복하며 메모리 사이 빈 공간 낭비

  • 해결
  1. 메모리 압축(compaction) : 프로세스를 재배치시켜 빈 공간을 합침 (->오버헤드)
  2. 가상 메모리 기법, 페이징

문제점 2. 물리 메모리보다 큰 프로세스 실행 불가

페이징 (paging)

  • 프로세스의 논리 주소 공간을 페이지(page)라는 일정 단위로 자르고
  • 메모리의 물리 주소 공간을 프레임(frame)이라는 페이지와 같은 단위로 자른 뒤
  • 페이지를 프레임에 할당하는 가상 메모리 관리 기법
    • 페이지 인 / 페이지 아웃 = 스와핑

문제 1. CPU가 페이지의 위치를 알기 어렵다. 불연속적 -> 순차적 실행 불가
-> 페이지 테이블 : 페이지 번호와 프레임 번호를 매칭 -> 논리 주소에는 연속적으로 배치

문제 2. 내부 단편화 : 프로세스 크기를 페이지로 나눈 나머지만큼 낭비

PTBR (프로세스 테이블 베이스 레지스터) : 각 프로세스의 페이지 테이블을 가리킨다
TLB : 페이지 테이블의 일부를 가져와 저장하는 캐시 메모리

주소 변환

  • 어떤 페이지/프레임 , 접근하려는 주소가 그 페이지로부터 얼마나 떨어져 있는지
  • 논리 주소 = 페이지 번호 + 변위(offset) -> 프레임 번호 + 변위 (페이지 테이블로 변환)
    페이지(논리) , 프레임(물리) 변위는 같다.

페이지 테이블 엔트리(PTE)

  • 유효 비트 : 현재 접근 가능 여부 (메모리 적재 여부)
    • 유효비트가 0인 페이지에 접근 -> page fault '인터럽트' : 백업 - 루틴 - 재개
  • 보호 비트 : 페이지 보호 기능 (읽기 쓰기 실행 가능 여부)
  • 참조 비트 : CPU가 접근한 적이 잇는지 여부
  • 수정 비트 (dirty bit) : CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부
    • 스왑 아웃 시 보조기억장치에 쓰기 작업 여부 판단

쓰기 시 복사

  • fork() 호출 시 부모 프로세스와 동일한 프레임 가리킴 (쓰기 작업 없다면 유지)
  • 둘 중 하나가 쓰기 작업 수행 시 별도의 공간으로 복제
  • 프로세스 생성 시간 , 메모리 절약

계층적 페이징 : 페이지 테이블을 페이징 , Outer 페이지 테이블(최상단)
-> 모든 페이지 테이블을 항상 메모리에 적재할 필요 X

  • 논리 주소 = 바깥 페이지 번호 + 안쪽 페이지번호 + 변위

요구 페이징 : 요구되는 페이지만을 메모리에 적재

  • 언젠가는 메모리가 가득 참 -> 페이지 교체
  • 페이지 교체 알고리즘
  • 페이지 폴트가 적은 알고리즘이 좋다!
  • 페이지 참조열(page reference string)
    CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
  1. FIFO
  2. 2차 기회 페이지 교체 : FIFO + 참조한 적이 있다면 적재 시간 갱신
  3. 최적 페이지 교체 : 앞으로의 사용 빈도가 가장 낮은 페이지 교체
    • 가장 낮은 페이지 폴트율 but 실제구현 어려움 -> 다른 알고리즘 평가 하한선
  4. LRU(Least-Recently-Used) : 가장 오래 사용되지 않은 페이지 교체

페이지 폴트가 자주 발생하는 이유

  • 나쁜 페이지 교체 알고리즘
  • 사용 가능한 프레임 자체가 적음

스래싱(Thrashing) : 프로세스 실행보다 페이징에 더 많은 시간을 소요하여 성능 저해

  • 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악해 적절히 할당해야 한다

프레임 할당 방식

  1. 균등 할당 (equal allocation)
  2. 비례 할당 (proportional) : 프로세스의 크기에 비례해 할당 (실행 고려 X)
  3. 작업 집합 모델 : CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임 할당
    • 작업 집합 : 실행중인 프로세스가 일정 기간 동안 참조한 페이지의 집합
  4. 페이지 폴트 빈도 : 실행하는 과정에서 배분할 프레임 결정
    • 페이지 폴트율이 너무 낮으면 -> 너무 많은 프레임, 높으면 -> 너무 적음
    • 페이지 폴트율의 상/하한선을 정하고 그 범위안에서 프레임 할당

작업 집합 , 페이지 폴트 빈도 = 동적 할당

파일 시스템

파일 시스템 : 파일과 디렉터리로 관리하는 운영체제 내의 프로그램

파일 : 의미 있고 관련 있는 정보를 모은 논리적 단위

  • 실행 정보 + 부가 정보(=속성, 메타 데이터)
  • 파일 연산 - 시스템 호출

디렉터리

  • 트리 구조 디렉터리 (루트( / )+서브 디렉터리)
  • 경로 : 디렉터리를 이용해 파일/디렉터리 위치, 이름을 특정 지을 수 있는 정보
    • 절대 경로(루트부터) / 상대 경로(현재 디렉터리부터)
  • 운영체제는 디렉터리를 '특별한 형태의 파일'로 간주
  • 디렉터리 엔트리 : 파일 이름 , 보조기억장치 내 저장된 위치(를 유추할 수 있는 정보) ..

파티셔닝 : 저장 장치의 논리적 영역을 구획
포매팅 : 파일 시스템을 설정, 파티션마다 다르게 설정 가능

운영체제는 파일/디렉터리를 블록 단위로 읽고 쓴다

  • 하나의 파일은 보조기억장치에 여러 블록에 걸쳐 저장

파일 할당

  • 연속 할당 : 연속된 블록에 할당
    • 첫 블록 주소와 길이만 알면 됨
    • 외부 단편화
  • 불연속 - 연결 할당 : 파일을 이루는 데이터 블록을 연결 리스트로 관리
    • 디렉터리 엔트리 : 파일 이름 & 첫 블록 주소 & 블록 단위 길이
    • 단점 : 반드시 첫 번째 블록부터 읽어야 함, 오류 발생시 이후 블록 접근 어려움
  • 불연속 - 색인 할당 : 파일의 모든 블록 주소를 색인 블록 하나에 모아 관리
    • 디렉터리 엔트리 : 파일 이름 & 색인 블록 주소

FAT (File Allocation Table) 파일 시스템

  • 연결 할당 기반, 단점 보완
  • 각 블록에 포함된 다음 블록 주소를 모아 FAT로 관리
  • -> 메모리에 캐시될 경우 느린 임의 접근 속도 개선 가능

유닉스 파일 시스템

  • 색인 할당 기반
  • 색인 블록 == i-node : 파일의 속성 정보와 15개의 블록 주소 저장 가능
  1. 블록 주소 중 12개에는 직접 블록 주소 저장
    *직접 블록 주소 : 파일 데이터가 저장된 블록
  2. 1번으로 충분하지 않다면 13번째 주소에 단일 간접 블록 주소 저장
    *단일 간접 블록 : 파일 데이터를 저장한 블록 주소가 저장된 블록
  3. 2번으로 충분하지 않다면 14번째 주소에 이중 간접 블록 주소 저장
    *이중 간접 블록 : 단일 간접 블록 주소가 저장된 블록
  4. 3번으로 충분하지 않다면 15번째 주소에 삼중 간접 블록 주소 저장

*NTFS , EXT *