[CS스터디] 1주차 발자국
강의
자료구조와 알고리즘
배열
스택 (LIFO)
컴퓨터 ctrl+z같이 되돌리기 작업
문법 검사 (같은 괄호 만나면 스택에서 꺼내기)
Push, pop, peek, isEmpty -> 연결리스트로 구현
큐(FIFO)
Head, tail 변수 두개로 양방향 조회 기능
CurrentNode 바꿔줘야 함
Enqueue, dequeue, front, isEmpty -> 이중연결리스트로 구현
운영체제
구조
커널 : 직접 접근 안됨
인터페이스 : 커널에 접근 (gui, cli)
시스템콜: 어플리케이션이 커널을 사용하기 위한 인터페이스
드라이버: 하드웨어가 커널을 사용하기 위한 인터페이스
하드웨어와 구조메인보드: 하드웨어 연결, 버스가 연결해줌
Cpu
제어장치(Control Unit)
산술논리연산장치 (ALU) : 실제로 연산하는 장치
레지스터 : 연산하기 위해 잠시 저장; 변수라고 생각하면 된다
메모리
RAM : 메인 메모리, 임시, 속도 동일하게 데이터 조회
ROM : 영구, 부팅 관련 데이터(바이오스)
연결단자: 스피커, 모니터, 키보드 등
인터럽트
폴링 방식 : 주기적으로 cpu가 확인 -> 성능 안좋음
인터럽트 방식: ISR(인터럽트 서비스 루틴) 실행, 비동기적으로 동작 -> 성능 좋음
하드웨어 방식 : 하드웨어 입출력
소프트웨어 방식 : 유효하지 않은 메모리에 접근, 0으로 나누는 명령어 등
프로그램과 프로세스
프로그램 : 애플리케이션, .exe
프로세스: 실행중인 프로그램
하드웨어에 있는 프로그램이 RAM메모리에 올라갔을 때 실행 중인 프로그램
Code : 실행하는 코드 저장
Data : 전역, static변수
Heap: 지역변수, 함수호출시 필요한 정보
Stack : 사람이 동적으로 할당할 수 있는 공간 (malloc, free등)
멀티프로그래밍과 멀티 프로세싱
멀티프로그래밍: 여러 개의 프로세스에 여러 개의 프로그램이 올라 온 것
멀티프로세싱: CPU가 여러 개의 프로세스를 처리하는 것 (시분할)
PCB (Process Control Block)
: 멀티 프로세싱을 위해서 OS는 해당 프로세스의 정보를 가지고 있는 것
연결리스트로 저장
프로세스 종료시 PCB를 연결리스트에서 제거
포인터, 프로세스 상태, 프로세스ID, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보, CPU스케줄링정보 등…
프로세스 상태
시분할 -> 여러 프로세스를 돌아가며 실행, 속도가 빨라서 동시처럼 보이지만 한번에 한 프로세스밖에 실행할 수 있음
생성 : PCB생성 후 메모리에 프로그램 적재 요청
준비 : CPU 사용을 기다리고 있음, CPU 스케줄러에 의해 할당됨, 대부분의 상태로 존재
실행 : 준비 상태에 있는 프로세스가 CPU를 할당받아 실행되는 상태, CPU개수만큼 실행할 수 있음, 할당받은 시간이 끝나면 준비상태로 돌아감
대기 : 프로세스가 입출력 요청을 하면 입출력이 완료될때까지 기다림, 대기 상태에 두고 다른 프로세스를 실행 상태가 될 수 있음 -> 입출력이 느리기 때문에 효율적
완료 : 프로세스가 종료, PCB제거
컨텍스트 스위칭
A 프로세스를 실행하는 중에 다른 B 프로세스를 실행하기 위해 실행 중이였던 A 프로세스 상태를 저장하고 다른 B 프로세스의 정보를 가져오는 상황
이때 PCB(상태 저장하는 곳) 내용이 변경 됨
프로세스 할당 시간 끝남
운영체제는 인터럽트를 발생시킴
현재 CPU의 레지스터 값을 PCB A에 저장
PCB B에 있는 값으로 CPU 레지스터 세팅
프로그램 카운터(PC) 정보 포함: 다음 실행할 명령어의 주소 -> 바로 B실행 가능
B의 할당 시간 끝남
인터럽트 발생
B의 상태를 PCB B에 저장
PCB A에서 A의 상태를 가져오고 다시 A를 실행
입출력 요청, 점유시간이 끝남, 인터럽트가 있을 때 등..
프로세스 생성과 종료
.exe 실행
프로그램의 code영역과 data영역을 메모리에 로드
빈 스택과 빈 힙을 만듦
PCB 생성 후 값 초기화
일련의 과정은 부팅되고 0번 프로세스(부모) 실행할 때 딱 한번 실행
이후엔 0번 프로세스를 복사(fork)해서 사용 (자식)
복사할 때 모든 프로세스 내용(code, data, heap, stack)과 PCB내용을 전부 복사해 옴
이 후 exec함수를 실행시키면 본인이 원하는 값으로 덮어쓰게 됨
쓰레드
프로세스가 많아질수록 차지하는 메모리가 많이 차지하기 때문에 필요 -> 한개의 프로세스 내에 n개의 쓰레드가 있음
Code, data, heap을 공유하며, stack은 쓰레드마다 하나씩 가지고 있음
쓰레드 id와 Thread Control Block (TCB) 생김
-> 운영체제가 작업을 처리하는 단위는 프로세스가 아닌 쓰레드임
CPU 스케줄링
어떤 프로세스
얼마의 시간동안
CPU Burst: CPU할당받아 실행
I/O Burst: 입출력 작업
다중큐
준비, 대기상태는 큐로 존재
실행->준비: 우선순위를 보고 그에 맞는 준비 큐에 PCB를 넣음
스케줄링 목표
리소스 사용률
오버헤드 최소화
공평성
처리량
대기시간
응답시간
스케줄링 알고리즘
FIFO
스케줄링 큐에 들어온 순서대로 할당
앞선 프로세스가 완전히 끝나야만 다음 프로세스가 실행할 수 있음
평균대기시간이 순서에 따라 차이가 심하게 남 -> 성능 차이 -> 일괄처리시스템에 보통 사용
미션
운영체제
인터럽트 방식으로 해결
2. 프로그램: .exe형식의 애플리케이션
프로세스: 실행 중인 프로그램
3. 멀티프로그래밍: 여러 프로그램을 실행
멀티프로세싱: (CPU관점) cpu가 여러 프로세스를 처리
4. PCB를 사용하여 멀티 프로세싱을 가능하게 관리함
5. 어떤 프로세스 실행 중에 다른 프로세스를 실행하기 위해 원래 프로세스 정보를 저장해두고 다른 프로세스를 처리하는 것
자료구조와 알고리즘
1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.
이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요?
이유를 함께 적어주세요.
프로그램의 목표: 저장 및 열람을 해야 함
교실의 학생 정보: 자주 바뀌지 않음
열람: 조회는 자주 함
삽입 삭제는 자주 일어나지 않지만 조회는 많이 한다면 배열을 선택하는 것이 좋음
2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다.
주문은 들어온 순서대로 처리됩니다.
이 때 여러분이라면 어떤 자료구조를 선택하실 건가요?
이유를 함께 적어주세요.
들어온 순서대로라면 fifo 즉 큐 자료구조가 필요하다
댓글을 작성해보세요.
