CS 1주차 발자국
운영 체제운영체제 개요컴퓨터는 운영체제가 없어도 동작이 가능예전 전화기는 통화만 되지만 최신 휴대전화는 어플등 다양한 기능이 가능운영체제의 일프로세스 관리메모리 관리하드웨어 관리파일 시스템 관리운영체제의 역사1943 애니악1950초반 직접회로 개발후반 싱글 스트림 배치시스템1960시분할 시스템싱글 스트림 배치 시스템 한계 극복프로그램을 순서대로 실행하는 것이 아닌 메모리에 여러 프로그램을 올려 놓고 시간을 나누어서 빠르게 돌아가며 실행UNIX멀티 프로그래밍다중 사용자파일 시스템1970개인용 컴퓨터의 시대매킨토시, ms-dos 운영체제의 구조커널프로세스와 메모리, 저장 장치를 관리하는 기능사용자는 인터페이스를 통해 접속사용자는 GUI, CLI로 커널 제어어플리케이션과 커널의 인터페이스는 시스템 콜을 사용하드웨어와 커널의 인터페이스는 드라이버를 사용컴퓨터 하드웨어와 구조폰 노이만 구조CPU와 메모리 사이에 버스로 연결.메인보드다른 하드웨어를 연결하는 장치cpu와 메모리가 필수CPU(중앙처리 장치)산술 논리 연산장치, 제어장치, 레지스터의 구조메모리 종류ram전원을 끄면 메모리가 휘발ROM(Read Only Memory)전월을 꺼도 메모리가 보존.바이오스 등 수정되지 않는 데이터를 저장부팅 과정ROM에 저장된 바이오스 실행부트 오더인터럽트cpu는 입출력 작업이 들어오면 입출력 관리자에게 입출력 명령주기적으로 장치들에게 확인→ polling 방식. 효율이 좋지 않음polling방식의 단점을 보완한게 인터럽트입출력 명령을 내리고 입출력 관리자는 입출력이 발생하면 cpu에게 전달cpu는 isr실행시켜 작업 완료.하드웨어 인터럽트소프트웨어 인터럽트 프로그램하드디스크 등과 저장장치에 저장된 명령문의 집합체저장 장치만 사용하는 수동적인 존재프로세스실행중인 프로그램하드디스크에 저장되어 있는 프로그램이 메모리에 올라가있는 상태메모리도 사용하고 운영체제의 cpu 스케줄링 알고르즘도 사용, 출력와 입력도 하는 능동적인 존재프로세스 구조code, data, heap, stack 영역으로 구조code실행하는 코드가 저장data전역 변수와 static(정적) 변수가 저장heap동적으로 메모리를 할당하는데 사용.stack지역 변수와 함수를 호출했을때 필요한 정보들이 저장프로세스가 되는 과정컴파일 과정전처리기 → 컴파일러 → 어셈블러 → 링커(링킹)유니프로그래밍메모리에 오직 하나의 프로세스가 올라와 처리하는 것cpu는 프로세스를 실행하다가 i/o 작업을 만나면 기다렸다가 완료되면 작업을 처리하나의 프로세스를 다 끝내야 다른 프로세스를 실행하는 단점이 존재.멀티 프로그래밍메모리에 여러개의 프로세스를 올려서 실행cpu가 프로세스를 실행하다가 I/O 작업을 만나면 기다리면서 다른 프로세스를 실행cpu 쉬는시간이 줄어들어 효율적여러개의 프로세스를 돌아가면서 짧은시간동안 작업을 진행하여 모든 프로세스를 동시에 실행시키는 것처럼 느끼게 하는 기술→ 멀티태스킹cpu를 한개가 아니라 여러개를 이용→ 멀티 프로세서멀티 프로세서로 작업을 처리하는 방식을 멀티 프로세싱이라 칭함.PCB(Process Control Block)프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 갖고 있는 PCB를 만들고 저장.PCB들은 연결리스트라는 자료 구조로 저장.프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거.연결 리스트의 구조는 유지PCB 구조포인터부모와 자식 프로세스에 대한 포인터와 할당된 자원에 대한 포인터를 저장프로세스 상태현재 프로세스의 5가지 상태를 나타냄생성, 준비, 실행, 대기, 완료프로세스 ID프로세스를 식별하기 위한 숫자프로그램 카운터다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터를 저장레지스터 정보프로세스가 실행될때 사용했던 레지스터 값들을 저장메모리 관련 정보메모리에 있는 위치정보, 경계레지스터 값 등이 저장CPU 스케쥴링 정보스케쥴링에 필요한 우선순위, 최종 실행시간, CPU 점유 시간등이 저장프로세스 상태시분할 시스템을 사용하는 운영체제는 여러개의 프로세스를 돌아가면서 실행cpu가 여러개의 프로세스를 동시에 실행하는 것이 아니라 한 순간에는 하나의 프로세스밖에 처리하지 못함속도가 빨라 사람이 보기엔 동시에 처리로 보임.생성 상태PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태준비 상태CPU를 사용하기 위해 준비하고 있는 상태CPU 스케쥴러에 의해 CPU가 할당됨.대부분의 프로세스 상태실행 상태준비상태에 있는 프로세스가 CPU 스케쥴러에 의해 CPU를 할당받아 실행되는 상태실행상태에 있는 프로세스의 수는 CPU의 갯수만큼부여된 시간만큼만 사용이 가능시간이 완료되면 다시 준비 상태로 변경대기 상태프로세스가 입출력을 요청하면 입출력이 완료될 때까지 기다리는 상태완료 상태프로세스가 종료된 상태데이터를 메모리에서 제거하고 생성된 PCB제거 컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업실행중인 프로세스의 작업 내용을 PCB에 저장하고 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅됨. PCB에 변경되는 값들은 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등컨텍스트 스위칭이 발생하는 이유CPU 점유 시간이 다 된 경우I/O 요청이 있는 경우다른 종류의 인터럽트가 있는 경우프로세스 생성과 종료.exe 파일 실행시 운영체제는 포로그램의 코드영역과 데이터 영역을 메모리에 로드하고 빈스택과 빈 힙을 만들어 공간을 확보프로세스를 관리하기 위한 pcb를 만들어 값을 초기화프로세스 생성과 정은 운영체제가 부팅되고 0번 프로세스가 생성될때 딱 1번만 실행.나머지 모든 프로세스는 새로 생성하지 않고 0번 프로세스를 복사해서 사용복사는 fork()함수를 사용새로 생성하는 것보다 복사하는게 빠르기 때문복사한 프로세스는 자식 프로세스0번 프로세스는 부모 프로세스자식 프로세스는 부모 프로세스의 코드영역, 데이터 영역, 스텍 영역가 pcb 내용을 전부 복사그럼 복사하면 0번 프로세스가 똑같이 실행되는거 아닌가?맞음. 그대로 복사하니 당연한 결과자기가 원하는 코드는 exec() 함수를 이용하여 실행.부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 겂으로 덮어쓰게됨.자식프로세스는 부모 프로세스와 다르게 동작 부모 프로세스와 자식 프로세스는 cpu 스케줄링에 따라 실행되는데 순서는 운영체제 따라 결정.부모 프로세스가 먼저 실행되는 경우pid 값을1 받으면 17번째 줄 함수 실행자식 프로세스의 exit 실행될때까지 대기.자식 프로세스 실행12번 함수 실행 후 13번 함수를 통해 프로세스 종료를 부모 프로세스에게 전달대기하고 있던 부모 프로세서는 자식 프로세스의 종료 신호를 받고 18번 함수 19번 함수를 실행하고 종료만약 부모 프로세스가 자식 프로세스보다 먼저 종료되거나 자식 프로세스가 비정상적인 종료가 되어서 exit신호를 주지 못해 ExitStatus를 읽어오지 못하여 메모리에 계속 살아 있는 상태를 좀비 프로세스라고 함쓰레드운영체제가 작업을 처리하는 단위는 프로세스프로세스를 생성하면 pcb가 생성되고 프로세스 수만큼 pcb, 코드, 데이터, 스택, 힙 영역도 만들어줘야 하기 때문에 너무 무거워짐.그래서 프로세스가 많아질수록 메모리를 많이 차지 하게 됨.⇒ 쓰레드 고안쓰레드는 프로세스 안에 있고 한개 또는 여러개가 존재하게 됨.쓰레드들은 프로세스의 pcb, code, data, heap영역을 공유. 단 stack은 쓰레드마다 하나씩 갖고 있음. 쓰레드들에게 id를 부여하고, 쓰레드를 관리하기 위한 TCB(Thread Control Blcok)이 생성.운영체제 관점에서 쓰레드들도 구분이 가능해짐.브라우저에서 탭을 하나 추가로 생성하면, 프로세스가 생성되는 것이 아니라 쓰레드가 하나 더 생성됨.프로세스와 쓰레드의 장단점안정성프로세스는 서로 독립적이기 때문에 하나의 프로세스가 문제 있어도 다른 프로세스는 영향을 받지 않는다.쓰레드는 하나의 프로세스 안에 존재하기 때문에 프로세스에 문제가 생기면 쓰레드에게도 문제가 생긴다.프로세스 방식이 쓰레드 보다 우수속도와 자원각각의 프로세스는 서로 고유한 자원을 갖고 있음. code, data, heap, stack영역을 전부 따로 두고 있고, 프로세스간 통신을 하려면 IPC를 이용해야 해서 오버헤드가 크고 속도가 느림.쓰레드는 한 프로세스 내에서 stack 영역을 제외한 영역을 공유하므로 오버헤드가 작음. 쓰레드 간의 통신은 데이터를 공유할 수 있으니 쉽지만, 공유되는 공간에서 문제가 생길 수 있음. CPU 스케쥴링 개요운영체제는 모든 프로세스에게 cpu를 할당/해제 하는데 이를 cpu 스케쥴링이라 함.스케줄러(운영체제)의 고려사항어떤 프로세스에게 cpu리소스를 주어야 하는가.cpu를 할당 받은 프로세스가 얼마나 cpu를 사용해야 하는가.시분할 처리 방식으로 여러 프로세스에 짧은 시간동안 돌아가면서 Cpu를 할당.→ 컴퓨터의 성능에 영향을 많이 미침.cpu를 할당받아 처리하는 작업을 CPU Burst. 입출력 작업을 I/O Burst.다중 큐큐먼저 들어온걸 먼저 처리하고, 나중에 들어온걸 나중에 처리하는 구조.프로세스가 실행상태에서 준비 상태로 돌아갈때운영체제는 해당 프로세스의 우선순위를 보고 그에 맞는 준비 큐에 넣음.cpu스케줄러는 준비 상태의 다중큐에 들어있는 프로세스들 중에 적당한 프로세스를 선택해서 실행 상태로 전환.프로세스가 실행상태에서 i/o 요청을 받아 대기상태로 오면i/o 작업 종류에 따라서 분류된 큐에 들어가게 됨.hdd, lan, 키보드 큐큐에 들어가는건 프로세스의 정보를 갖고 있는 PCB가 들어감.프로세스 정보를 담고 있는 PCB는 준비상태의 다중큐에 들어가서 준비되길 기다리며, CPU스케쥴러에 의해 실행 상태로 전환.CPU스케쥴러는 준비상태의 다중큐를 참조하여 어떤 프로세스를 실행시킬지 결정I/O 작업도 종류별로 나누어진 큐에 들어가고 CPU스케쥴러는 이를 참조해 스케쥴링을 진행.스케쥴링 목표리소스 사용률CPU사용률을 높이는것을 또는 I/O 사용률을 높이는것을 목표로 할 수 있음.오버헤드 최소화스케줄링을 하기 위한 계산이 복잡하거나 컨텍스트 스위칭을 자주하면 배보다 배꼽이 커지는 상황이 발생.스케줄러는 이런 오버헤드를 최소화 하는것을 목표공평성모든 프로세스에게 공평하게 CPU가 할당되어야 함.공평의 의미는 시스템에 따라 달라질 수 있음.처리량같은 시간내에 더 많은 처리를 할 수 있는 방법을 목표로 함.대기시간작업을 요청하고 실제 작업이 이뤄지기 전까지 대기하는 시간이 짧은 것을 목표로 함.응답시간대화형 시스템에서 사용자의 요청이 얼마나 빨리 반응하는지가 중요하므로 응답시간이 짧은것을 목표로 함.모든 목표를 최고 수준으로 유지하기는 힘듬.서로 상반된 목표가 있기 때문.처리량을 높이기 위해서는 하나의 프로세스에 cpu를 오래 할당해야함.응답시간을 줄이기 위해서는 여러 프로세스에 cpu를 골고루 할당해야함.→ 처리량과 응답시간의 목표를 같이 달성할 수 없음.→ 사용자가 사용하는 시스템에 따라서 목표를 다르게 설정.스케쥴링 알고리즘FIFO(First In First Out)먼저 들어온 작업이 먼저 나감.스케쥴링 큐에 들어온 순서대로 cpu를 할당하는 방식.먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행 됨.장점단순하고 직관적단점한 프로세스가 완전히 끝나야 다음 프로세스가 실행되기 때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함.또한 I/O작업이 있다면 cpu가 i/o작업이 끝날때까지 기다리기때문에 cpu 사용률이 떨어짐.스케줄링의 성능은 평균 대기 시간으로 평가평균 대기 시간은 프로세스가 여러개 실행될때 이 프로세스가 모두 실행될때까지 대기 시간의 평균.프로세스 1의 burst는 25초, 프로세스2는 5초 프로세스3은 4초.프로세스1이 먼저 도착했으므로 대기시은 0초.프로세스2는 프로세스1이 실행되고 실행 하므로 대기시간은 25초.프로세스 3은 프로세스1과 프로세스2가 실행되고 실행 하므로 대기시간은 30초.평균 대기시간은 18.3초.순서가 바뀌면프로세스3은 바로 시작 되었으므로 대기시간은 0초.프로세스2이 실행되고 프로세스2가 실행. 대기시간은 4초.프로세스1은 프로세스 3,2 실행 시간만큼 기다려서 대기시간은 9초.평균 대기시간은 4.3초.⇒ FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나서 현대 운영체제에서는 잘 쓰이지 않고 일괄 처리 시스템에 사용됨.SJF(Shortest Job First)FIFO의 단점을 보완.이론적으로 FIFO보다 성능이 좋음.하지만 문제점 발생어떤 프로세스가 얼마나 실행될 지 예측이 힘듦.BurstTime이 긴 프로세스는 아주 오래동안 실행되지 않을 수 있음.→ 이러한 문제때문에 SJF알고리즘은 사용되지 않음.RR(Round Robin)FIFO알고리즘은 일괄처리 시스템엔 적절하지만 시분할 처리 시스템엔 부적절SJF알고리즘의 단점은 프로세스의 종료 시간을 예측하기 힘듦.FIFO 알고리즘의 단점을 해결한 프로세스에게 일정 시간만큼 cpu를 할당하고, 할당시간이 지나면 강제로 다른 프로세스에게 일정 시간만큼 cpu를 할당.강제로 cpu를 빼앗긴 프로세스는 큐의 마지막으로 이당.프로세스에게 할당하는 일정 시간은 타임 슬라이스 또는 타임 퀀텀이라고 부름.평균 대기시간 측정타임슬라이스: 10sP1의 BursTime은 25초 / P2는 4초 / P3는 10초P1은 큐에 들어오자마 실행. 대기시간은 0초25초중 타임 슬라이스 값인 10초만 실행되고 나머지 시간은 큐의 제일 뒤로 이동.P2(4s) / P3(10s) / P1(15s)p2는 10초동안 기다림. 대기시간은 10초BurstTime인 4초만 실행하고 종료.P3(10s) / P1(15s)p3은 14초동안 기다림. 대기시간은 14초BurstTime인 10초만 실행하고 종료P1(15s)p1은 p2, p3의 실행 시가만큼 기다림. 대기시간은 14초.BurstTime이 타임 슬라이스 값보다 크므로 10초만 실행.남은 작업시간은 큐의 맨 뒤로 생성P1(5s)다시 P1의 남은 작업을 실행. 큐에 생성되자마자 실행 되므로 대기시간은 0초.→ 평균 대기시간은 12.67sRR방식과 FIFO방식의 평균 대기시간이 비슷할 수 있음.평균 대기시간이 비슷하면 RR방식이 비효율적→ 컨텍스트 스위칭이 있기 때문에 컨텍스트 스위칭 시간이 더 추가되기 때문.→ RR 알고리즘의 성능은 타임슬라이스 값에 따라 크게 달라짐.타임 슬라이스가 무제한인 경우 FIFO와 같음.타임 슬라이스가 작은경우에는 컨텍스트 스위칭이 너무 자주 발생함.타임 슬라이스에서 실행되는 프로세스의 처리 양보다 컨텍스트 스위칭을 처리하는 양이커져서 오버헤드가 너무 커지는 상황 발생.최적의 타임슬라이스를 설정하는 방법은 사용자가 느끼기에 여러 프로세스가 버벅 거리지 않고 동시에 실행된다고 느끼면서 오버헤드가 너무 크지 않는 값을 찾아야 함.윈도우는 20ms, Unix는 100msMLFQ(Multi Level Feedback Queue)가장 일반적으로 쓰이는 cpu 스케쥴링 기법탄생 배경RR의 업그레이드 된 알고리즘P1은 I/O 작업 없이 CPU연사만 하는 프로세스, P2는 1초 CPU 연산을 하고 10초 동안 I/O 작업.P1 → Cpu Bound Process // P2 → I/O Bound ProcessCpu Bound Process는 Cpu 사용률과 처리량을 중요하게 여김.I/O Bound Process는 응답 속도를 중요하게 여김타임 슬라이스 값에 따른 효율 분석. (P2가 먼저 시작된다고 가정)타임 슬라이스가 100초인 경우I/O 요청이 발생하고 P1이 100초동안 실행됨. 타임 슬라이스가 1초인 경우I/O요청이 발생하고 P1이 10번 실행되면 P2의 작업이 끝나 인터럽트가 발생되고, P2는 큐에 들어감.P2는 다시 1초 실행 되고 다시 I/O 작업을 기다림.이후 계속 반속 상황 비교CPU는 쉬지 않고 일해서 CPU사용률은 100%I/O 사용률을 보면 P1이 실행되는 동안 P2의 I/O 작업이 완료된 시점부터 기다리는 시간이 발생하기 때문에 10%밖에 되지 않음.타임 슬라이스가 작기 때문에 P2가 첫번째 상황처럼 기다리며 낭비되는 시간이 거의 없음. 90%정도 나오게 됨. CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임슬라이스를 선택그리고 CPU Boud Process 타임 슬라이스를 크게 설정.운영체제 입장에서 CPU Boud Process와 I/O Bound Process 구분하는 기준CPU를 실행하는 프로세스가 스스로 CPU를 반납하면 CPU사용량이 적은거니 I/O Bound Process일 가능성이 큼.반대로 CPU를 사용하는 프로세스가 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏기는 상황이면 CPU Boud Process일 확률이 높음.우선 순위를 가진 큐를 여러가지 준비.우선순위가 높으면 타임 슬라이스가 낮고 우선순위가 낮을 수록 타임 슬라이스 크기가 커짐.타임 슬라이스 크기를 오버해서 강제로 Cpu를 뺏기면 원래있던 순위보다 우선순위가 낮은 큐로 이동.자료구조 자료구조데이터가 어떻게 저장되고 어떻게 사용되는지 나타냄.가장 간단한 자료구조는 변수, 배열알고리즘어떤 문제를 해결하기 위한 확실한 방법자료구조가 바뀌면 알고리즘도 바뀐다시간복잡도특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간시간을 측정하는 시간이 아닌 실행시간을 예측반복문이 많아지면 시간이 늘어난다.최선의 경우 - $\varOmega$최악의 경우 배열의 길이만큼 - Big-O평균의 경우 - $\Theta$ 배열기본적으로 제공하는 자료구조일반적인 프로그래밍 언어는 배열을 선언할때 배열의 크기를 선언.운영체제는 메모리에서 해당 크기만큼 연속된 빈공간을 찾아서 값을 할당.할당하지 않은 부분은 의미없는 쓰레기 값을 전달하고, 운영체제는 배열의 시작 주소만 기억.배열의 인덱스 참조는 크기에 상관없이 한번에 찾아와서 O(1)의 성능을 갖는다.하지만, 데이터 삽입, 삭제의 성능은 좋지 않음.배열의 데이터는 메모리에 연속된 공간에 할당하고 있음.배열 크기를 넘어서 할당하게 되면 문제가 발생.배열의 끝에는 다른 데이터가 있을경우 운영체제는 다시 연속적인 크기의 메모리를 찾아서 다시 할당하고. 기존의 데이터를 복사까지 해주어야함.그렇다고 배열의 크기를 처음부터 크게 할당하면 일시적으로 해결된것 처럼 보이지만, 처음부터 공간을 크게 할당하면 배열하나의 메모리양이 커지고, 다 사용하지 않으면 공간의 낭비이다.JS의 배열은 상황에 따라서 연속적, 불연속적으로 메모리를 할당하지만 대부분 불연속적으로 할당.메모리는 내부적으로 연결하여 사용자에게는 연속적처럼 느껴지게함.장점읽기, 쓰기와 같은 참조에는 O(1)의 성능을 가진다단점크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있다.데이터 삽입, 삭제가 비효율적이다.연결리스트(Linked List)배열의 단점을 보완.저장하는 데이터들을 메모리에 분산해서 할당하고 데이터들을 서로 연결.Node라는 것을 만들어서 수행Node의 구조데이터를 담는 변수다음 노드를 가리키는 변수연결 리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 할 수 있음.연결이라는 특성 때문에 배열과 다른 장단점을 갖고 있음.장점중간에 데이터를 삽입(삭제)하게 되는 경우 다음 노드의 정보만 바꿔주면 되므로 간단.단점특정 인덱스의 데이터에 바로 접근이 힘듦. 첫번째 노드에서 부터 순서대로 원하는 인덱스까지 이동해야 하므로 데이터 참조는 O(n)의 성능을 가짐.배열과의 비교크기배열은 고정연결리스트는 노드를 만들어 연결해주므로 동적주소배열은 연속적으로 할당연결 리스트는 불연속적인 공간에 할당데이터 참조배열은 메모리 접근이 빠름(O(1)연결리스트는 앞에서부터 해당 노드에 접근해야 하므로 느림(O(n))삽입과 삭제배열은 모든 데이터를 옮겨야해서 O(n)의 성능연결리스트는 삽입하려는 노드까지 계속 노드를 타고가야 하므로 O(n)의 성능 스택(Stack)First In Last Out(FIFO)먼저 들어온 데이터가 마지막에, 가장 늦게 나온 데이터가 제일 앞에 있는 데이터 구조.큐(Queue)First In First Out덱(Deque)덱은 데이터를 tail, head에 삽입과 삭제가 자유로운 자료 구조해시 테이블(Hash Table)해시, 맵, 해시맵, 딕셔너리로 언어마다 다른 이름을 갖고 있음.장점빠른 데이터 읽기삽입, 삭제단점메모리를 많이 차지함.좋은 해시 함수의 구현이 필수정Set데이터 중복을 허용하지 않는 자료 구조해시 테이블을 사용. HashSet이라고 불리기도 함.